페이지 교체 알고리즘

Page Reference String

page size = 100bytes 일때

CPU 주소 = {100, 101, 102, 432, 612, 103, 104, 611, 612}
Page 번호 = {1, 1, 1, 4, 6, 1, 1, 6, 6}
Page reference string = {1, 4, 6, 1, 6}

Page Reference String

• 연속된 페이지는 생략하고 하나의 페이지 번호만 나타낸 것으로 볼 수 있다.
• 연속된 페이지를 참조할 때는 한 번 page fault가 발생하면 같은 페이지를 사용하는 동안에는 절대 page fault가 발생할 수 없다.

페이지 교체 알고리즘

1. First-In First-Out(FIFO)

가장 먼저 page-in 한 페이지를 먼저 page-out한다.

✏️ Belady's Anomaly

프레임 수가 증가하면(= 메모리 용량이 증가하면) page fault 수가 줄어드는 것이 정상적이지만, 특정한 페이지 참조열에 대해서는 프레임 수가 증가해도 page fault 수가 오히려 증가하는 이상 현상이 발생

• 원인 : Locality를 고려하지 않은 FIFO 한계로 부재 증가
• 영향 : 페이지 부재율 증가로 성능 저하 및 스래싱 발생

2. Optimal (OPT)

가장 오랫동안 사용되지 않을 페이지를 희생양 페이지로 선택한다.
현재 시점 에서 그 이후에 최초로 나타나는 시점의 거리를 구해, 값이 가장 큰 페이지를 가장 오랫동안 사용되지 않은 페이지로 정한다.

• 현실적으로 불가능한 방법
• 미래에 어떤 프로세스가 사용되는지 알 수 없다.

3. Least-Recently-Used (LRU)

최근에 사용되지 않으면 나중에도 사용되지 않을 것이라는 개념으로 가장 최근에 이용되지 않은 페이지를 희생양 페이지로 선택한다.

• 현재 대부분의 환경에서 가장 많이 사용