페이징 알고리즘(paging algorithm)

# 페이징 알고리즘(paging algorithm)

페이지 부재(Page Fault)가 발생했을 때, 주기억장치의 모든 페이지 프레임이 사용 중이라면 어떤 페이지 프레임을 선택하여 교체할 것인지를 결정하는 것을 말한다.

(1) OPT(Optimal Replacement, 최적 교체)

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

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

(2) FIFO(First In First Out)

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

- 이해하기 쉽고, 프로그래밍 및 설계가 간단하며, 벨레이디의 모순현상이 발생함

※ Belady's Anomaly : FIFO 알고리즘에서 기존 페이지 프레임의 개수를 늘리면 Page Fault 발생이 감소해야하나, 오히려 늘어나는 현상

(3) LRU(Least Recently Used)

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

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

(4) LFU(Least Frequently Used)

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

- 프로그램 실행 초기에 많이 사용된 페이지가 그 후로 사용되지 않을 경우에도 프레임을 계속 차지하는 단점이 존재

(5) NUR(Not Used Recently)

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

- 사용 여부를 확인하기 위하여 각 페이지마다 참조비트와 변형비트가 사용됨

(6) SCR(Second Chance Replacement)

- 가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 기법

- FIFO 알고리즘 기법의 단점을 보완하는 기법

Ex)

1. FIFO(First In First Out)

2. LFU(Least Frequently Used) - 사용빈도가 가장 적은 페이지를 교체하는 기법

3. LRU (Least Recently Used) - 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법

- 출처 : http://blog.naver.com/madplay/220184723275