[운영체제] 페이지 교체 알고리즘

1. 페이지 교체 알고리즘의 개요

- 페이지 교체 알고리즘은 페이지 부재(Page Fault)가 발생했을 때 가상기억장치의 필요한 페이지를 주기억장치에 적재해야 하는데, 이때 주기억장치의 모든 페이지 프레임이 사용중이면 어떤 페이지 프레임을 선택하여 교체할 것인지를 결정하는 기법이다.

- 페이지 교체 알고리즘에는 OTP, FIFO, LRU, LFU, NUR, SCR 등이 있다.

2. OTP(OPTimal replacement, 최적 교체)

- OTP는 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법이다.

- 벨레이디(Belady)가 제안한 것으로, 페이지 부재 횟수가 가장 적게 발생하는 가장 효율적인 알고리즘이다.

- 각 페이지 호출 순서와 참조 상황을 미리 예측해야 하므로 실현 가능성이 희박하다.

3. FIFO(First In First Out)

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

- 이해하기 쉽고, 프로그래밍 및 설계가 간단하다.

- 벨레이디의 모순(Belady's Anomaly) 현상이 발생한다.

4. LRU(Least Recently Used)

- LRU는 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법이다.

- 각 페이지마다 계수기(Counter)나 스택(Stack)을 두어 현 시점에서 가장 오랫동안 사용하지 않은, 즉 가장 오래 전에 사용된 페이지를 교체한다.

- 계수기나 스택과 같은 별도의 하드웨어가 필요하며, 시간적인 오버헤드가 발생된다.

- 실제로 구현하기가 매우 어렵다.

5. LFU(Least Frequently Used)

- LFU는 사용 빈도가 가장 적은 페이지를 교체하는 기법이다.

- 활발하게 사용되는 페이지는 사용 횟수가 많아 교체되지 않고 사용된다.

- 프로그램 실행 초기에 많이 사용된 페이지가 그 후로 사용되지 않을 경우에도 프레임을 계속 차지할 수 있다.

6. NUR(Not Used Recently)

- NUR은 LRU와 비슷한 알고리즘으로, 최근에 사용하지 않은 페이지를 교체하는 기법이다.

- 최근에 사용되지 않은 페이지는 향후에도 사용되지 않을 가능성이 높다는 것을 전제로, LRU에서 나타나는 시간적인 오버헤드를 줄일 수 있다.

- 최근의 사용 여부를 확인하기 위해서 각 페이지마다 두 개의 비트, 즉 참조 비트(Reference Bit)와 변형 비트(Modified Bit, Dirty Bit)가 사용된다.

- 참조 비트 : 페이지가 호출되지 않았을 때는 0, 호출되었을 때는 1로 지정된다.

- 변형 비트 : 페이지 내용이 변경되지 않았을 때는 0, 변경되었을 때는 1로 지정된다.

- 다음과 같이 참조 비트와 변형 비트의 값에 따라 교체될 페이지의 순서가 결정된다.

참조 비트	변형 비트	교체 순서
0	0	1
0	1	2
1	0	3
1	1	4

7. SCR(2차 기회 교체)

- SCR(Second Chance Replacement)은 가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 것으로, FIFO 기법의 단점을 보완하기 위한 기법이다.

- 각 페이지마다 참조 비트를 두고, FIFO 기법을 이용하여 페이지 교체 수행 중 참조 비트가 0일 경우에는 교체하고, 참조 비트가 1인 경우에는 참조 비트를 0으로 지정한 후 FIFO 리스트의 맨 마지막으로 피드백시켜 다음 순서를 기다리게 한다.

- 교체 대상이 되기 전에 참조 비트를 검사하여 1일 경우 한 번의 기회를 더 부여하기 때문에 'Second Chance'라고도 한다.