페이지 교체 알고리즘

페이지 교체 알고리즘
페이징 기법으로 메모리를 관리하는 운영체제에서, 페이지 부재가 발생하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할 지 결정하는 방법

• page-fault 발생 비율을 줄이는 것이 목표.

성능 평가 기준

• 페이지 부재 횟수, 페이지 성공 횟수 기준
• 유지 비용도 고려. 계산 횟수, 메모리 차지 양 고려

FIFO

• 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보냄
• 구현 간단, 성능 좋지 않음.
• 들어온 시간을 저장하거나, 큐를 이용해서 순서 저장
• Belady's Anomaly 현상 가능 : 프레임 개수가 많아져도 page-fault가 줄지 않고 늘어나는 현상

OPT (Optimal)

• 앞으로 가장 오래 사용하지 않을 페이지를 교체
• page-fault 발생이 가장 적음
• Belady's Anomaly 현상 없음
• 프로세스가 앞으로 사용할 페이지 미리 알아야 함. 거의 불가능
• 연구목적으로 사용

LRU (Least Recently Used)

• 가장 오랫동안 사용되지 않은 페이지 교체
• 최적 알고리즘과 비슷한 효과. 성능 좋음
• 많은 운영체제가 채택

LFU (Least Frequently Used)

• 참조횟수가 가장 적은 페이지 교체
• 교체 대상이 여러 개면 가장 오랫동안 사용하지 않은 페이지 교체

MFU (Most Frequently Used)

• 참조 횟수가 가장 많은 페이지를 교체

https://velog.io/@chappi/OS%EB%8A%94-%ED%95%A0%EA%BB%80%EB%8D%B0-%ED%95%B5%EC%8B%AC%EB%A7%8C-%ED%95%A9%EB%8B%88%EB%8B%A4.-17%ED%8E%B8-%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%98FIFO-LRU-LFU-NUR-2%EC%B0%A8-%EA%B8%B0%ED%9A%8C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%9C%EA%B3%84-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98