페이지 교체 알고리즘

페이지 교체 알고리즘(Page Replacement Algorithm)은 가상 메모리(Virtual Memory) 시스템에서 페이지 부재(Page Fault)가 발생했을 때 어떤 페이지를 메모리에 올릴지 결정하는 알고리즘입니다. 페이지 교체 알고리즘은 제한된 메모리 용량에서 최적의 성능을 내기 위해 페이지 교체를 수행하는 방법을 결정합니다. 아래의 세개 이외에도 여러 페이지 교체 알고리즘이 있습니다.

 

FIFO (First In First Out)

• 첫번째로 넣은 페이지를 처음으로 꺼내는 알고리즘이다.( 가장 오래된 페이지를 교체하는 방식으로 동작합니다)
• 구현은 간단하지만, 페이지의 접근 패턴에 따라 성능이 좋지 않을 수 있습니다.

 

 

LFU (Least Frequently Used)

• LFU 알고리즘은 참조횟수가 가장 적은 페이지를 교체하는 알고리즘이다.
• 교체 대상이 여러 개라면 가장 오랫동안 사용하지 않은 페이지를 교체한다.
• 사용 빈도가 낮은 페이지를 교체하기 때문에 일부 특정 페이지만 반복적으로 사용될 경우 좋은 성능을 보입니다.

 

 

 

LRU (Least Recently Used)

• 가장 오랫동안 사용되지 않은 페이지를 교체합니다. 페이지에 접근할 때마다 타임스탬프를 갱신하고, 가장 오래전에 접근된 페이지를 교체합니다.
• 타임스탬프 갱신에 따른 오버헤드가 발생할 수 있습니다.

프로그래머스에서 푼 관련 문제

GITHUB