가상기억장치(Virtual memory device)의 페이지 교체 알고리즘(Page Replacement Algorithm)

가상 기억장치(Virtual Memory Device)란?

보조 기억장치의 일부를 주기억장치인것처럼 사용하는 방법으로 용량이 작은 주기억장치를 마치 더 큰 용량을 갖은 것처럼하여 주기억장치보다 더 큰 용량의 프로그램을 실행하기 위하여 주로 사용하는 방법이다. 이를 위해서 가상기억장치의 주소를 주기억장치의 주소로 변환하는 주소 사상화(Mapping) 과정이 필요하다.

가상기억장치를 구현하기 위하여 페이징(Paging) 기법과, 세그멘테이션(Segmentation) 기법을 사용하게 된다.

페이지 교체 알고리즘 (Page Replacement Algorithm)

페이지 부재(page fault)가 발생하였을 경우, 가상기억장치의 필요한 페이지를 주기억장치의 어떤 페이지 프레임을 선택, 교체 해야 하는 가를 결정하는 기법

페이지 교체 알고리즘은 페이징 기법으로 메모리를 관리하는 운영체제에서, 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 방법이다. 이 알고리즘이 사용되는 시기는 페이지 부재가 발생했는데, 페이지 부재가 발생하면 새로운 페이지가 주기억장치로 들여와야 한다. 이때 메모리에 공간이 없으면(시스템의 종류에 따라 약간 다를 수 있으나, 대체로는 빈 페이지가 하나도 없거나, 미리 정한 수보다 적을 때 발생한다.) 이미 올라와 있던 페이지중 하나를 희생시키고 그곳으로 새 페이지를 load해야 한다. 페이지 교체 알고리즘은 희생시킬 페이지를 고를 때 사용되는 알고리즘을 말한다.

이러한 알고리즘들의 주요한 평가 기준은 페이지 부재율 이다. 페이지 교체 알고리즘이 운영체제에서 필요한 이유는 제한된 주기억장치 용량이 적었던 때 부족한 메인메모리 사용공간을 확보해서 사용하기 위함이었고 최근에는 64bit 환경에 들어서면서 사용가능한 메모리공간이 무한대로 확장되었지만 그래도 대다수의 환경은 메인메모리 용량이 제한 되어있기 때문에 이러한 기법은 아직까진 필수적이다.

OPT (Optimal)

앞으로 가장 오랫동안 사용하지 않을 페이지를 교체 ; 미리 페이지의 사용 여부를 예측해야하므로 실현 가능성이 희박함

FIFO (First In First Out)

각 페이지가 주기억장치에 적재될 때마다 그때의 시간을 기억시켜 가장 먼저 들어와 가장 오래 있던 페이지를 교체

Belady's Anomaly 현상 발생 ; 페이지 프레임 수가 증가하면 페이지 부재가 더 증가하는 모순 발생

LRU (Least Recently Used)

사용된 시간을 확인하여 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체하는 방법

가장 최근에 사용된 페이지가 교체되지 않는다고 할 수 있음

이 알고리즘은 페이지 참조의 시간적 구역성을 고려하여 FIFO 알고리즘의 모순을 개선하기 위해 고안

즉, 프로그램의 구역성을 고려할 때 최근에 참조된 페이지는 앞으로도 참조될 가능성이 많고 최근에 참조되지 않은 페이지는 앞으로도 참조되지 않을 가능성이 많다는 사실을 알 수 있음

LFU (Least Frequently Used)

사용된 횟수를 확인하여 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체하는 방법

각 페이지별 사용한 횟수를 기억시켜 놓아야 함

기억장치에 저장된 페이지들 중에서 사용한 횟수가 가장 적은 페이지를 교체함

NUR (Not Used Frequently)

최근에 사용하지 않은 페이지를 교체하는 기법

"근래에 쓰이지 않은 페이지들은 가까운 미래에도 쓰이지 않을 가능이 높다." 라는 이론에 근거

각 페이지마다 2개의 하드웨어 비트(호출 비트, 변형 비트)가 사용됨

참고자료

• Wiki Bélády's anomaly
• 가상기억장치