FIFO 알고리즘

선입선출(FIFO: First-In-First-Out) 페이지 교체 알고리즘으로 주기억장치에서 가장 많은 시간을 보낸 페이지부터 교체하는 알고리즘이다. 페이지들의 주기억장치 적재 순서를 기록 -> 선입선출 큐를 유지 관리한다. page의 적재된 시간을 기억시켜 놓고 그 중 가장 먼저 적재된 page를 교체시키는 방법으로 간단하고 이해하기 쉬우나 locality를 전혀 고려 하지 않은 알고리즘이어서 성능은 별로 좋지 않다.

 

그림 1. FIFO Algorithm

 

Belady의 이상현상(Belady's anomaly) - 실패가 자주 발생할 경우 page frame을 증가시키면, 즉 사용 가능한 메모리를 늘리면 직관적으로 생각할 때 실패가 감소될 것으로 보이나 실제로는 그렇지 않게 되는 현상이 발생하는 수도 있음을 Belady가 발견하였다. 즉 page frame의 수를 늘렸는데 오히려 실패가 증가하는 수도 있었다. 이를 Belady's anomaly(변이,이상 현상,모순) 또는 FIFO anomaly라 한다.