페이지 교체 알고리즘

한혜성·2022년 12월 15일
0

OS

목록 보기
2/2

1. 페이지 교체 알고리즘이란

- 페이지 부재가 발생하여 새로운 페이지를 할당하여야하는 상황에서 현재 할당된 페이지 중 어떤 것으로 교체할 지 결정하는 방법

  1. 가상메모리는 요구 페이지 기법을 통해 필요한 페이지만 메모리에 적재함.
  2. 하지만 필요한 페이지만 올려도 메모리는 가득차게 될 수 있음.
  3. 이때 추가로 페이지를 가져오기 위해 안쓰는 페이지는 out, 해당 공간에 현재 필요한 페이지를 in 해야함.
  4. 여기서 어떠한 페이지를 out 해야할 지(victim page) 정하는 방식이 페이지 교체 알고리즘이다.
    • 기왕이면 수정이 되지 않는 페이지를 선택하는 것이 좋음 (만약 수정되면 메인 메모리에서 내보낼 때, 하드디스크에서 또 수정을 해야하므로 시간이 오래 걸리게 되기 때문)

2. Page Reference String(페이지 참조열)

  • 페이지 교체 알고리즘을 계산하기 위해서는 페이지 단위로 계산해야 함.
  • 하지만 CPU가 내는 주소는 이진수 단위이므로 페이지 단위로 변형해야 함.
  • Page Reference String은 연속된 페이지는 생략하고 하나의 페이지 번호로만 나타낸 것
- CPU가 내는 주소 = {100, 101, 102, 402, 692, 103, 104, 611, 612}

if 페이지의 크기 = 100 bytes
- 페이지 주소 = {1, 1, 1, 4, 6, 1, 1, 6, 6}
- Page Reference String = {1, 4, 6, 1, 6}


3. 페이지 교체 알고리즘 종류(FIFO, OPT, LRU)

1) FIFO(First-In First-Out) : 가장 먼저 page-in한 페이지 순으로 out 시킨다.

  • Page Reference String : {7,0,1,2,0,7,0,1,2,3}

  • 프레임 개수 : 3

    번호12345678910
    PRS7012070123
    status77 07 0 12 0 12 0 12 7 12 7 01 7 01 2 01 2 3
    Page Fault1234456789
  • 최종 page fault는 9, 이전에 page-out한 페이지를 그 다음에 바로 page-in 하려한다면 다시 page fault가 발생하기 때문에 비효율적인 모습을 볼 수 있음.

- Belady's Anomaly

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

2) OPT(Optimal) : 가장 오랫동안 사용되지 않을 페이지를 out 시킨다.

  • 가장 오랫동안 사용되지 않을 페이지를 계산하기 위해 현재 시점에서 그 이후에 최초로 나타나는 시점의 거리를 distance로 두어 계산한다. distance가 가장 큰 페이지를 교체하는 규칙. (해당 페이지가 이후에 나오지 않는 경우는 INF로 지정한다.)

    번호12345678910
    PRS7012070123
    status77 07 0 17 0 27 0 27 0 27 0 21 0 21 0 21 3 2
    distance54 33 2 52 1 51 2 4INF 1 3INF INF 2INF INF 1INF INF INFINF INF INF
    Page Fault1234444556
  • 최종 page fault는 6, FIFO와 비교했을 때 많이 줄어든 모습을 볼 수 있으나 현실적으로 OPT의 방법은 불가능하다. 실제 컴퓨터에서는 미래에 어떤 프로세스가 사용될 지 알 수 없으므로 어느 프로세스가 가장 오래 사용되지 않는 지를 계산할 수 없다.


3) LRU(Least-Recently-Used) : 최근에 사용되지 않은 page를 out시킨다.

  • OPT는 최적해를 구할 수 있지만 미래를 알 수 없으므로 현실적으로 불가능한 방법이었는데, 최적의 해는 아니더라도 근사의 해를 구하기 위해서 LRU가 나왔다.
    LRU는 최근에 사용되지 않으면 나중에도 사용되지 않을 것이라는 개념으로 과거의 페이지 기록을 통해 out할 페이지를 선택한다.

    번호12345678910
    PRS7012070123
    status77 07 0 12 0 12 0 12 0 72 0 71 0 71 0 21 3 2
    Page Fault1234455678
  • LRU는 근사 해를 구하므로 OPT보다는 page fault가 많이 발생하지만, FIFO보다는 일반적으로 적게 일어난다. 그러므로 현재 대부분 환경에서는 LRU를 사용하고 있다.

profile
백엔드하고 싶은 사람 소오오온~~

0개의 댓글