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

페이지 교체

페이지 부재(Page Fault)가 발생하면, 요청된 메모리를 디스크에서 메모리로 읽어와야한다.

물리 메모리에 올라와 있는 페이지 중 하나를 선택해서 디스크의 스왑 영역으로 보내는 것

 

페이지 교체 알고리즘

어떠한 프레임에 있는 페이지를 디스크의 스왑 영역으로 보낼 것인지를 결정하는 알고리즘

알고리즘의 목표는 페이지의 부재율를 최소화하기 위함이다.

• 프레임: 물리 메모리를 일정한 크기로 나눈 블록
• 페이지: 가상 메모리를 일정한 크기로 나눈 블록

 

FIFO 알고리즘

메모리에 먼저 올라온 페이지를 먼저 내보내는 알고리즘

out 되는 페이지는 가장 먼저 메모리에 올라온 페이지

 

OPT 알고리즘

Optimal 알고리즘, 앞으로 가장 사용하지 않을 페이지를 가장 우선적으로 내보냄

FIFO에 비해 페이지 결함의 횟수를 많이 감소 시킬 수 있다.

하지만, 실질적으로 페이지가 앞으로 잘 사용되지 않을 것이라는 보장이 없기 때문에 수행하기 어려운 알고리즘이다.

 

LRU 알고리즘

Least-Recently-Used, 최근에 사용하지 않은 페이지를 가장 먼저 내보내는 알고리즘

OPT의 경우 미래 예측이지만, LRU의 경우는 과고를 보고 판단하므로 실질적으로 사용 가능한 알고리즘

OPT 보다는 페이지 결함이 더 일어날 수 있지만, 실제로 사용할 수 있는 페이지 교체 알고리즘에서는 가장 좋은 방법이다.

 

LFU 알고리즘

Least-Frequently-Used, 사용된 빈도가 낮은 페이지를 먼저 내보내는 알고리즘

페이지가 몇 번 사용되었는지를 기준으로 페이지를 선정한다.