29. 페이지 교체 알고리즘

페이지 교체 정책

운영체제가 특정 페이지를 물리 메모리에 올리려 하는데 물리 메모리가 더 이상 공간이 없다면 기존 페이지 중 하나를 물리 메모리에서 저장 매체에 저장하고 새로운 페이지를 해당 물리 공간에 올린다.

이 때 페이지를 결정하는 것이 Page Replacement Algorithm

FIFO

FIFO Page Replacement Algorithm은 이름과 같이 먼저 들어온 페이지를 내리는 기법이다.

OPT

OPTimal Replacement Algorithm은 앞으로 가장 오랫동안 사용하지 않을 페이지를 내리는 기법이고 일반 OS에서는 구현이 불가하다.

LRU

Least Recently Used Page Replacement Algorithm은 가장 오래 전에 사용된 페이지를 교체한다. OPT 교체 알고리즘이 구현 불가하므로 이렇게 과거 기반으로 시도한다. 가장 많이 사용된다.

다음과 같은 예시가 있을 때 색칠 된 시점에서 메모리에 올라가지 않은 4번 페이지가 요청되면 가장 오래전에 사용되었던 3번 페이지를 내리고 4번을 올린다.

LFU

Least Frequently Used Page Replacement Algorithm은 가장 적게 사용된 페이지를 내리는 기법이다.

NUR

Not Used Recently Page Replacement Algorithm은 LRU와 마찬가지로 최근에 사용하지 않은 페이지부터 교체하는 기법이며 각 페이지마다 참조비트(R), 수정비트(M)을 둔다.

따라서 각 페이지마다 (R, M) 쌍의 정보를 가지게 되며 읽기 요청만 있으면 (1, 0), 수정 요청만 있으면 (0, 1)과 같은 식으로 저장된다.

(0, 0), (0, 1), (1, 0), (1, 1) 순으로 페이지 교체

Thrashing

반복적으로 페이지 폴트가 발생하여 과도하게 페이지 교체 작업이 일어나 실제로는 아무일도 하지 못하게 되는 상황을 쓰레싱이라고 한다.