[Operating System] 페이지 교체 알고리즘

메모리가 한정되어 있으므로 스와핑이 많이 일어나며 이러한 스와핑은 많이 일어나지 않도록 설계되어야 한다.

스와핑은 페이지 교체 알고리즘을 기반으로 일어난다.

 

오프라인 알고리즘(offline algorithm)

먼 미래에 참조되는 페이지와 현재 할당하는 페이지를 바꾸는 알고리즘.

가장 좋은 방법이나 미래에 사용되는 프로세스를 우리는 알 수 없기 때문에 사용할 수 없는 알고리즘이다.

다른 알고리즘과의 성능 비교에 대한 기준으로 사용한다.

 

FIFO(First In First Out)

출처 : Jogamohan Medak, Partha Pratim Gogoi, Critical Scrutiny of Page Replacement Algorithms: FIFO, Optimal and LRU(IJITEE)

가장 먼저 온 페이지를 교체 영역에 가장 먼저 놓는 방법

 

LRU(Least Recentle Used)

출처 : Jogamohan Medak, Partha Pratim Gogoi, Critical Scrutiny of Page Replacement Algorithms: FIFO, Optimal and LRU(IJITEE)

참조가 가장 오래된 페이지를 바꾼다.

이 오래된 것을 파악하기 위해 각 페이지마다 계수기(counter), 스택을 두어야 하는 문제점이 있다.

 

해시 테이블과 이중 연결 리스트를 사용해서 구현한다.

해시 테이블은 이중 연결 리스트에서 빠르게 찾을 수 있도록 쓰고,

이중 연결 리스트는 한정된 메모리를 나타낸다.

 

NUR(Not Used Recently)

출처 : 면접을 위한 CS 전공지식 노트(2022)

최근에 사용한 적이 없는 페이지를 스왑 영역으로 보내는 알고리즘.

 

LRU에서 발전한 알고리즘이다. 일명 clock 알고리즘이라고 한다.

0과 1을 가진 비트를 둔다.

0은 참조되지 않은 것이며, 1은 최근에 참조된 것이다.

시계 방향으로 돌면서 0을 찾고 0을 찾은 순간 해당 프로세스를 교체하고,

해당 부분을 1로 바꾸는 알고리즘이다.

 

LFU(Least Frequently Used)

출처 : Page Replacement Algorithms in OS(https://webeduclick.com/page-replacement-algorithms-in-os/)

가장 참조 횟수가 적은 페이지를 교체한다.

많이 사용하지 않은 것을 교체하는 것이다.

 

페이지 교체 알고리즘은 페이지 부재 횟수와 페이지 성공 횟수를 비교하며 성능 평가를 할 수 있다.

물론 이외에도 다른 성능 평가 기준들이 있다.

 

참조

• 주홍철, 면접을 위한 CS 전공지식 노트, 길벗(2022)
• 조성호, 쉽게 배우는 운영체제, 한빛아카데미(2018)