페이징 교체 알고리즘

| 최적 교체(Optimal Replacement)

  - Belady가 제안한 기법으로 Belady의 MIN 페이지 교체 기법이라고도 함

  - 현재 주기억 장치에 적재되어있는 페이지들 중 현재 시점 이후로 가장 오랫동안 참조되지 않을 페이지를 교체함

  - 효율이 가장 좋고 Belady의 모순이 발생하지 않음

  - 단점

    > 구현이 어렵고 복잡

| 선입 선출(FIFO)

  - 각 페이지가 주기억장치로 들어올 때마다 타임스탬프를 찍어 그 시간을 기억하고 있다가 페이지가 교체될 필요가 있을 때, 가장 먼저 주기억 장치에 들어 있는 페이지와 교체시키는 방법

  - 가장 간단한 페이지 교체 알고리즘

  - 단점

    > 중요한 페이지가 오랫동안 있었다는 이유만으로 교체되는 현상이 발생할 수 있음

    > Belady의 모순 발생 가능

        : 프로세스에게 프레임을 더 주었는데 오히려 페이지 부재율이 더 증가하는 현상

| LRU(Least Recently Used)

  - 가장 널리 사용되는 방법

  - 각 페이지마다 카운터를 두어 현시점에서 가장 오랫동안 사용되지 않은 페이지를 제거하는 방법

  - 국부성(지역성)에 의존

  - 단점

    > 시간 오버헤드 발생(불러왔던 시간을 기록해야 함)

    > 구현이 매우 복잡

 | LFU(Least Frequently Used)

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

  - 구역성 문제가 발생

  - 단점

    > 바로 불러온 페이지가 교체될 수 있음

| NUR(Not Used Recently)

  - LRU 교체의 단점인 시간 오버헤드를 적게 하는 방법

  - 최근에 사용되지 않은 페이지를 교체

  - 참조비트와 변형비트를 두어 관리

[참조]

알기쉬운 정보보안기사&산업기사 / 도서출탄 탑스팟 / 조상진 저

http://faithpac27.tistory.com/entry/%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B2%B4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-PageReplacement-Algorithm