[운영체제] 페이징 교체 알고리즘

 

최적(OPT)

가장 오랫동안 참조되지 않을 페이지 교체
가장 낮은 페이지 폴트를 발생시키지만 미래를 예측할 수 없어 구현 불가능
→ 다른 알고리즘을 평가하는 참고용으로만 쓰인다.
 

 

LRU

가장 오랫동안 참조되지 않은 페이지 교체
최적에 근접한 성능이나 구현이 어렵고 오버헤드가 크다.
페이지 참조시간을 기록하는 공간이 사용된다
구현방법

1. 각 페이지의 최종 참고시간을 기록하는 테이블을 생성한다.
2. 이중연결리스트 스택을 이용한다.

 

 

 

FIFO

가장 오래 전에 적재된 페이지 교체한다.

가장 쉽게 구현 가능하지만, 페이지 폴트 가능성이 높다.

교체되는 페이지 메모리 위치에 적재가 된다. FIFO라고 페이지가 큐처럼 움직이는 것이 아니다.

 

LFU

가장 참조횟수가 적은 페이지 교체
교체 대상이 여러 개 이면 가장 오래된 페이지를 교체한다.
카운터를 이용하는 교체정책이다. 각 페이지마다 참조 횟수 카운터가 있다.

카운터를 사용해 페이지 참조횟수를 기록한다. 5초에 페이지1이 두 번 참조 됐고, 페이지2는 한 번 참조 됐으므로 페이지2를 교체한다. 8초에서도 페이지1은 세 번 참조, 페이지6은 한 번 참조됐으므로 페이지6을 교체 대상으로 삼는다.

 

문제점 및 해결점

• 프로세스의 초기 단계에서 한 페이지를 많이 사용한 후 다시는 사용하지 않을 때 곤란
• 카운터를 일정한 시간 간격으로 하나씩 오른쪽으로 이동하여 지수적으로 감소하는 평균 사용수를 형성하는 것

 

 

MFU

LFU와 반대로 가장 많이 사용한 페이지를 교체한다.
카운팅이 적은 페이지는 방금 들어와서 아직 사용하지 않았기 때문이라고 판단.
일반적이지 않은 방법이다. 구현 비용 높음. 성능 낮음.
 

---

 

부록) 클럭 알고리즘

LRU의 오버헤드를 줄이기 위한 방법이다. FINUFO(First In Not Used First Out)이나NUR, NRU(Not Recently Used)라고도 불린다.

1. 페이지를 적재한 프레임들이 환형으로 배치되어 있다고 간주하고, 첫 교체 후보를 가리키는 포인터(시계바늘)을 설정한다.
2. 프레임 별로 ‘사용비트’라는 1비트를 연계시켜, 처음 반입시와 참조시 1로 설정한다.
3. 시계방향으로 포인터를 이동시키면서 포인터가 가리키는 프레임 중
   1. 사용 비트가 0인 첫 프레임 상의 페이지를 교체한다.
   2. 사용 비트가 1인 경우 교체하지 않고 사용비트를 0으로 변경하고 다음 프레임으로 이동한다.

즉, 프레임이 한 바퀴 도는 동안 사용하지 않으면 0이 되고 다시 한 바퀴를 도는 동안 참조되지 않으면 교체 대상으로 선정하는 알고리즘이다. 두 번의 기회를 주기 때문에 2차 기회 알고리즘이라고도 한다.