[알고리즘] 페이지 교체 알고리즘

🔴 페이지 교체 알고리즘

페이지 교체 알고리즘은 메모리 관리 시스템에서 페이지의 부재(page fault)가 있으면 어떤 페이지를 교체할지 결정하는 알고리즘이다. 페이지를 교체하는 작업은 오버헤드를 동반하므로 가능하면 페이지 교체가 적게 일어나도록 하는 것이 효율적이다.

 이러한 페이지 교체를 적게하여 페이지 부재율을 최소화
하는 것이 페이지 교체 알고리즘이다.

✔ 선입선출 알고리즘

-가장 간단하고 직관적인 페이지 교체 알고리즘이다.
-간단하게 가장 먼저 들어온 페이지를 교체한다.

 위의 경우 cache memory가 3이고 아래의 경우는 cache memory가 4이다. 위의 경우 페이지 부개의 경우가 8번이고 페이지 hit가 2번이다.

 그리고 아래 cache memory가 4의 경우는 페이지 부재가 8번이고 페이지 hit가 2번이다. 결론적으로 페이지 프레임이 더 많이 사용한다고 해서 페이지 부재 횟수가 줄어들지 않는다는 것이다. 이를 FIFO 이상현상이라고 한다.

✔ LRU 알고리즘(Least Recently used)

-가장 최근에 사용되지 않은 페이지를 교체한다.
-페이지 교체 시 가장 오래전에 참조가 이루어진 페이지를 내보내는 알고리즘이다.

 페이지 부재가 6번이고 4번의 페이지 히트가 발생하여 FIFO보다 효율적인 것을 확인할 수 있다.

✔ LFU 알고리즘(Least frequency used)

 사용 빈도가 낮은 페이지를 교체한다.

 다음과 같이 5번을 참조 하려고 하면 페이지 부재가 발생한다. 1번 페이지가 오랫동안 쓰이지 않았지만 참조 횟수가 작은 4번 페이지 프레임이 5번으로 교체된다.

👍올바른 피드백은 언제든지 환영입니다~!