[1일1cs] 페이지 교체 알고리즘

먼저 페이지란 일정한 크기로 가상메모리를 분할한것( 가변적 크기는 세그멘테이션) 페이징은 일정한 크기이기에 내부단편화 발생 가능성이 있다.(세그멘테이션은 외부단편화) 페이지 테이블은 램에 두기에 그 속도가 느려질수밖에 없고 이를 위해 tlb를 쓰곤한다.

여기까지 페이지 교체 알고리즘을 위한 개괄적인 페이징 설명이고 자세한건 추후에 있을 페이징 파트에서 다루겠다.

페이지 알고리즘에는
먼저 opt ,optional page translation 즉 가장 나중에 쓰일 페이지 부터 갈아치우는 것이 있다.
허나 이는 미래를 예측해야하만 하므로 현실적으로 불가능하다. 그러므로 가장 최고의 성능으로써 비교하기 위해 쓰인다.

다음으로 언제나 등장하는 fifo,
큐를 이용해 저장한다.

다음으론 least recently used,
최근 가장 적게 쓰인 페이지 부터 갈아치우는 것이다.
즉 가장 오래 사용되지 않은 페이지를 갈아 치유게 되고, 특정 볓몇 케이스가 아니라면 괜찮은 성능을 보인다. 그렇기에 많은 운영체제에서 쓰인다.

마지막으로 least freqently used,
빈도수 기준 가장 작은 빈도수를 보이는 페이지 부터 갈아치운다.

이 알고리즘들은 보통 지역성을 가정한다.