CS - Operating System - 페이지 교체 알고리즘

페이지 교체 알고리즘

 

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

 

스와핑이 적게 일어나는 페이지 교체 알고리즘이 좋은 알고리즘입니다.

 

 

[ 오프라인 알고리즘 ]

 

offline-algorithm

 

먼 미래에 참조되는 페이지와 현재 할당하는 페이지를 바꾸는 알고리즘이며, 가장 좋은 알고리즘입니다.

그러나 미래에 사용되는 프로세스를 알 방법은 없습니다. 즉, 사용할 수 없는 알고리즘이지만 다른 알고리즘과의 성능 비교에 대한 기준을 제공합니다.

 

[ FIFO ]

 

FIFO(First In First Out)는 가장 먼저 온 페이지를 교체 영역에 가장 먼저 놓은 방법을 의미합니다.

 

[ LRU ]

 

LRU(Least Recentle Used)는 참조가 가장 오래된 페이지를 바꿉니다. '오래된' 것을 파악하기 위해 각 페이지마다 계수기, 스택을 두어야 하는 문제점이 있습니다.

 

LRU 구현은 보통 두 개의 자료 구조로 구현합니다. 바로 해시 테이블과 이중 연결 리스트입니다. 해시 테이블은 이중 연결 리스트에서 빠르게 찾을 수 있도록 쓰고, 이중 연결 리스트는 한정된 메모리를 나타냅니다.

 

[ NUR ]

 

LRU에서 발전한 NUR(Not Used Recently) 알고리즘이 있습니다.

일명 clock 알고리즘이라고 하며 먼저 0과 1을 가진 비트를 둡니다. 1은 최근에 참조되었고 0은 그 반대입니다. 시계 방향을 돌면서 0을 찾고 0을 찾은 순간 해당 프로세스를 교체하고, 해당 부분을 1로 바꾸는 알고리즘입니다.