[ 운영체제 ] 14. 페이지 교체 / 프레임 할당

물리 메모리는 크기가 한정되어있다.

따라서 OS가 메모리를 할당하는 것에 대해서 해야할 일이 2가지가 있다.

 

1. 기존 적재된 불필요한 페이지를 선별 → 보조기억장치로 보낸다.

   = 페이지 교체

 

2. 프로세스들에게 적절한 프레임 할당

[ 요구 페이징 ] 이란?

' 요구되는 페이지만 메모리에 적재 '하는 기법

( * 처음부터 모든 페이지를 적재하지 않고, 필요한 페이지만을 적재하는 기법 )

 

요구 페이징 작동 방식 → 유효 비트를 사용하여 적재 유무를 판단한다.

 

 

●  요구 페이징이 안정적으로 작동하기 위해 해결해야 하는 문제

 

1. 페이지 교체

2. 프레임 할당

 

 

---

페이지 교체 (알고리즘)

 

 

페이지를 적재하다보면 언젠가는 메모리가 가득 찬다.

▶ 적재되어 있는 페이지 중에서 일부를 보조기억장치로 보내야 함. ... 어떤 걸 보낼까??

→ 페이지 교체 알고리즘

 

 

가장 좋은 페이지 교체 알고리즘 = 페이지 폴트가 적은 알고리즘!

(폴트가 일어나면 보조기억 장치에서 가져오는 시간이 걸리기 때문 = 성능 저하)

 

● 페이지 참조열

: CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열

  페이지 폴트 횟수를 알 수 있는 방법 중 하나이다.

 

 

---

FIFO 선입선출

● 특징

- 가장 단순한 방식

- 메모리에 가장 먼저 왔던 페이지를 보조기억장치로 보낸다.

   = 가장 오래 있었던 페이지가 나간다. 

- 프로그램 초기 설정에 관련된 페이지들이 주로 나간다. 

● 단점

- 프로그램 실행 내내 사용될 페이지면  오래 되어도 내쫓으면 안 된다.

 

 

 

---

 

2차 기회 페이지 교체 알고리즘

참조 비트가 1일 때는, 0으로 초기화 ▶ 적재 시간을 현재 시간으로 설정한다.

 

컴구에서 배웠던 것 같음.

 

- 가장 옛날에 사용된 페이지를 내쫓는다.

 

- 뒤에서 부터 매들고 오면서 참조 비트가 0인 애를 먼저 때려보냄. 

 

---

 

최적 페이지 교체 알고리즘

- 앞으로의 사용 빈도가 가장 낮은 페이지를 교체

 

 

FIFO에 비해 page fault 가 훨씬 낮다!!

 

● 특징

- 가장 낮은 page fault rate 보장

- 실제 구현이 어렵다 << 앞으로 많이 쓰일지 아닐지 어떻게 알 수 있느냐?

 

---

LRU 알고리즘

 

- 컴구에서 배웠던 거 = 가장 오래 사용되지 않았던 페이지 교체

- 최적 : 미래 예측 / LRU : 과거 분석

 

 

---

프레임 할당 / 스레싱

[ 배경 ]

페이지 폴트가 발생하는 이유

1. 잘 맞지 않는 페이지 교체 알고리즘

2. 프로세스가 사용할 수 있는 프레임 자체가 적어서.

 

 

넉넉하지 않은 프레임을 할당하는 컴퓨터라면

▶ 페이지 폴트가 많이 일어나고

▶ 그로 인해 페이지 교체가 많이 일어나게 되면서

컴퓨터의 성능이 저하된다.

 

 

스레싱 

: 프로세스가 실행되는 시간 < 페이징 시간으로, 성능이 저해되는 문제

 

 

 

 

 

각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문에 발생한다.

 

따라서

각 프로세스가 필요로 하는 최소한의 프레임 수를 파악

▶ 프로세스들에게 적절한 프레임을 할당해주어야 한다.

 

 

---

프레임 할당 방식

 

1. 균등 할당 ( Equal allocation )

- 가장 단순한 할당 방식

- 모든 프로세스들에게 균등하게 프레임을 할당하는 방식

 

단점 : 실행되는 프로세스들마다 크기가 다르다.

          비효율적이다.

 

2. 비례 할당 ( proportional allocation )

- 프로세스의 크기에 비례하여 프레임 할당

 

단점 : 프로세스의 크기가 큰데 , 실행해보니 프레임이 별로 필요 X

           프로세스가 필요한 프레임 수는 실행해봐야 알 수 있다.

 

 

3. 작업 집합 모델

- 프로세스가 실행되는 과정에서 배분할 프레임 결정

 

- 스레싱이 발생하는 이유 = 빈번한 페이지 교체

   ▶ CPU가 특정 시간동안 주로 참조한 페이지 개수만큼만 프레임을 할당 

   ex) 3초에 20페이지를 접근하네? >  그 프로세스를 위해 3초동안은 20페이지를 할당해준다.

 

 

작업 집합 구하기 위해서는

 

1. 프로세스가 참조한 페이지

2. 시간 간격

 

을 알고있어야 한다.

 

 

이런 경우에는 7초동안 5,6,7을 참조했기 때문에

3페이지가 필요하다고 할 수 있다.

 

이런 경우에는 7초동안 1,2,4,7,8 을 참조했기 때문에

5 페이지가 필요하다고 할 수 있다.

 

 

 

 

4. 페이지 폴트 빈도

- 프로세스가 실행되는 과정에서 배분할 프레임 결정

- 아래 두 개의 가정에서 생겨난 아이디어

   1) 페이지 폴트율이 너무 높다 > 그 프로세스는 적은 프레임을 갖고 있다.

   2) 페이지 폴트율이 너무 낮다 > 그 프로세스는 많은 프레임을 갖고 있다.

 

 

페이지 폴트율에 상한선과 하한선을 정하고,

그 내부 범위 안에서만 프레임을 할당한다.

 

(출처)

유튜브 한빛미디어