36_가상 메모리 페이지 교체(Page Replacement) - FIFO, 최적(optimal), LRU(Least Recently Used) 페이지 교체

36_가상 메모리 페이지 교체(Page Replacement)

• FIFO, 최적(optimal), LRU(Least Recently Used) 페이지 교체

 

[FIFO 페이지 교체 (FIFO Page Replacement)]

FIFO 페이지 교체 알고리즘은 어떤 페이지를 교체해야 할 때 메모리에서 가장 오래된 페이지를 내보낸다. FIFO 페이지 교체 알고리즘은 이해하기도 쉽고 프로그램 하기도 쉬우나 항상 성능이 좋은 것은 아니다.

 

예를 들어 교체된 페이지 중 오래 전 사용된 후 더 이상 사용되지 않는 경우도 있으나 교체된 페이지가 초기화 된 후 계속 사용되는 페이지의 경우에는 다시 적재 하는 동안 부재율을 높이고 프로세스의 실행속도를 떨어뜨리기 때문이다.

 

그러나 FIFO 페이지 교체 알고리즘은 잘못된 실행을 발생 시키지는 않는다. 페이지가 교체된 뒤 그 즉시 그 페이지를 다시 적재하기 때문이다.

 

 

 

FIFO 페이지 교체 알고리즘에는 Belady의 모순(Belady's anomaly)이라는 것이 있는데 이것은 프로세스에게 프레임을 더 많이 할당 하였는데 오히려 페이지 부재율이 더 증가하는 현상을 일컫는다.

 

아래 그림을 보면 3프레임보다 4프레임 할당 시 더 많은 페이지 부재율을 나타내고 있다.

 

 

[최적 페이지 교체 (Optimal Page Replacement)]

최적 페이지 교체 알고리즘은 "앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아서 교체해라"라는 의미이다. 이 알고리즘은 낮은 페이지 부재율을 보이며 Belady의 모순이 발생하지 않는다.

 

이 알고리즘은 할당된 프레임의 수가 고정된 경우 낮은 페이지 부재율을 보장한다. 하지만 이 방식의 알고리즘은 실제 구현이 어렵다. 앞으로 어떤 프로세스가 어떻게 참조할 것인지를 미리 알아야 하기 때문이다. 따라서 최적 페이지 알고리즘은 주로 비교 연구 목적을 위해 사용한다.

 

 

프로세스에서는 SJF 스케줄링 경우와 유사하다.

• SJF 스케줄링 : http://sqlmvp.kr/140190172905

 

 

[LRU 페이지 교체 (Least Recently Used Page Replacement)]

FIFO 알고리즘은 메모리로 들어온 시간을, 최적(OPT) 알고리즘은 페이지가 사용될 시간을 이용한다. 최근의 과거 가까운 미래의 근사치로 본다면 가장 오랜 기간 동안 사용되지 않은 페이지를 교체 할 수가 있다. 이 기법이 LRU 기법이다.

 

LRU 알고리즘은 각 페이지마다 마지막 사용 시간을 유지 한다. 페이지 교체 시에 LRU는 가장 오랫동안 사용되지 않은 페이지를 선택 한다. 이 정책은 미래 대신 과거 시간에 대해 적용한 최적 교체 정책으로 생각할 수 있다.

 

 

문제는 어떻게 이 알고리즘을 구현하느냐는 것인데 LRU 페이지 교체 알고리즘은 하드웨어의 지원이 필요하다. 프레임들은 최근 사용된 시간 순서로 파악할 수 있어야 하며 2가지 방식이 사용된다.

 

• 카운터(Counter) : 가장 간단한 방법으로 각 페이지 항목마다 사용시간 필드를 넣고 CPU에 논리적인 시계나 카운터를 추가한다. 페이지 테이블이 변경될 때마다 시간 값을 관리해야 하며 시간 값의 오버플로우도 고려해야 한다.
• 스택(Stack) : LFU 교체 정책의 다른 구현방법은 페이지 번호의 스택을 유지하는 방법이다. 페이지가 참조될 때마다 페이지 번호는 스택 중간에 제거되어 스택 꼭대기(top)에 놓이게 된다. 이런 방식은 스택 꼭대기는 항상 최근에 사용된 페이지가 위치하게 되며 바닥에는 가장 오랫동안 이용하지 않은 페이지가 위치한다. 스택은 중간에서 항목을 제거해야 할 필요가 있으므로 보통 이중연결리스트 구조로 되어 있다. 페이지를 참조할 때마다 스택의 위치 이동이 발생 하기 때문에 오버헤드가 발생한다. 최악의 경우 맨 밑에 있는 스택의 위치가 상단으로 이동 될 경우 많은 주소 변환이 필요하다.

 

[참고자료]

Operating System Concepts / 홍릉과학출판사