페이지 교체 알고리즘 - FIFO, OPT, LRU

1. 페이지 교체

1) 요구 페이징(Demand Paging)

  요구되어지는 페이지만 backing store 에서 메모리로 가져온다.

프로그램이 계속 실행되면서 요구 페이지가 늘어나고, 언젠가는 메모리가 가득 차게 된다.

=> Memory full!

 

메모리가 가득 차면 추가로 페이지를 가져오기 위해

어떤 페이지는 backing store로 몰아내고(page-out)

그 빈 공간으로 페이지를 가져온다.(page-in)

용어 : victim page ; victim이란 말은 희생양 이라는 뜻이다. 즉, 페이지 교체를 위해 backing store로 쫓겨난 페이지를 말한다.

2. Victim Page

  페이지 교체를 위해 어느 페이지를 몰아낼 것인가?

=> i/o 시간 절약을 위해 기왕이면 modify 되지 않은 페이지를 victim page로 선택한다!

페이지가 수정되었다면 backing store로 몰아낼 때 하드디스크에 있는 페이지도 수정해야 하기 때문이다.(write에 부담이 발생)

- 방법: modified bit(= dirty bit) 이용

  　

3. 페이지 교체 알고리즘

여러 페이지 중 어떤 페이지를 victim으로 선택할 것인가를 결정하는 알고리즘을 말한다.

1) Page reference string (페이지 참조열)

  CPU가 내는 주소가 100 101 102 432 612 103 104 611 612 라고 가정해보자.

이때 Page size = 100byte 라면, 페이지 번호는 1 1 1 4 6 1 1 1 6 6 이 된다.

여기서 Page reference string은 1 4 6 1 6 이다.

 

  페이지 참조열이 이렇게 되는 이유는 page 차원에서 연속된 주소는 의미없기 때문이다. 같은 페이지라면 page fault가 일어나지 않기 때문이 100 101 102 모두 1로 본다.

2) First-In First-Out (FIFO)

  페이지 교체 알고리즘 중 가장 간단한 알고리즘이다. 초기화 코드는 더이상 사용되지 않을 것이라는게 FIFO 기반에 깔린 생각이다.

• 예제
• 페이지 참조열 = 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
• # of frames = 3
• page fault가 발생할 때마다 가장 먼저 들어온 페이지를 교체한다면 15 page faults가 발생한다.

Belady's Anomaly

 : 프레임 수(=메모리 용량)가 증가하면서 page fault 회수가 증가하지 않는 구간이 있다.

Belady's Anomaly

 

3) Optimal (OPT)

  앞으로 가장 오랫동안 사용하지 않을 페이지를 victim page로 선택한다.

• 예제
• 페이지 참조열 = 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
• # of frames = 3
• page fault가 발생할 때마다 앞으로 가장 오랫동안 사용되지 않는 페이지를 교체한다면 9 page faults가 발생한다.

실제로 OPT 알고리즘은 비현실적이다! 왜냐하면 미래는 알수 없기 때문이다.

cf. SJF CPU scheduling algorithm : CPU 스케쥴링에서 작업시간이 가장 짧은 것을 선택하는 알고리즘

　

4) Least-Recently-Used (LRU)

  그동안 가장 오랫동안 사용하지 않았던 페이지를 victim page로 선택한다. 최근에 사용되지 않으면 나중에도 사용되지 않을 것이라는 게 LRU 알고리즘의 기저에 깔린 생각이다.

• 예제
• 페이지 참조열 = 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
• # of frames = 3
• page fault가 발생할 때마다 그동안 가장 오랫동안 사용되지 않았던 페이지를 교체한다면 12 page faults가 발생한다.

  　

5) Global vs Local Replacement

  -  Global replacement : 메모리 상의 모든 프로세스 페이지에 대해 교체

  -  Local replacement : 메모리 상의 자기 프로세스 페이지에 대해 교체

성능 비교

  - Global replacement가 더 효율적일 수 있다.