Page Replacement

페이지 교체 알고리즘에 대해 설명해 주세요.

페이지 교체 알고리즘

페이지 교체 알고리즘은 물리적 메모리에서 페이지를 적절하게 교체하는 방법을 정의한 알고리즘이다. 컴퓨터가 가상 메모리를 사용하는 동안, 프로세스는 메모리 상의 가용 페이지 수보다 더 많은 페이지를 요구할 수 있다. 이때 페이지 폴트가 발생하고 운영체제는 물리 메모리에 새 페이지를 로드하기 위해 기존 페이지 중 일부를 교체해야 한다.

페이지 알고리즘의 예시

FIFO(First In First Out)

가장 오래된 페이지를 교체한다. 구현이 간단하지만 벨러먼의 문제가 발생할 수 있다.

일반적으로 프레임 수가 증가하면 페이지 폴트가 줄어들어야 하지만, FIFO는 가장 오래된 페이지를 단순히 제거하기 때문에 프레임 수가 많아지더라도 특정 접근 패턴에서 불필요한 페이지 교체가 더 자주 발생할 수 있다.

LRU(Least Recently Used)

가장 오랫동안 사용되지 않은 페이지를 교체한다. 페이지가 사용될 때마다 해당 페이지를 최신으로 간주하고 가장 오래 사용되지 않은 페이지를 교체 대상자로 지정한다.

Optimal(OPT)

이론적인 최적의 알고리즘으로 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체한다. 실제적으로 구현이 어렵고 미래의 참조를 알 수 없다는 문제점이 있다.

Clock Algorithm

FIFO 알고리즘의 변형으로 원형 큐를 사용하여 페이지의 참조 비트를 통해 오래된 페이지를 선택적으로 교체한다.

Second Chance

FIFO와 비슷하지만 페이지를 교체할 때 페이지의 참조 비트가 1이면 다시 기회를 주고 0이면 교체한다.

LRU 알고리즘은 어떤 특성을 이용한 알고리즘이라고 할 수 있을까요?

LRU 알고리즘은 가장 오래 사용되지 않은 페이지를 교체 대상으로 선택한다. 이 알고리즘은 최슨에 사용한 페이지는 앞으로도 자주 사용될 가능성이 크고, 가장 오래 사용되지 않은 페이지는 앞으로도 사용될 가능성이 낮다는 가설을 기반으로 한다.

시간적 지역성을 활용한 알고리즘이다. 최근에 사용한 데이터나 코드는 다시 사용할 가능성이 높다고 판단하기 때문이다.

LRU 알고리즘을 구현한다면, 어떻게 구현할 수 있을까요?

연결리스트와 해시맵을 조합하여 구현할 수 잇다.

• 해시맵을 사용하여 각 페이지를 O(1)로 찾을 수 있게 한다.
• 연결 리스트를 사용하여 페이지의 사용 순서를 기록한다.
• 페이지가 참조될 때마다 해당 페이지를 연결 리스트의 앞으로 이동시킨다.
• 페이지가 새로 로드되면 가장 오래된 페이지는 연결리스트 뒷부분에서 제거하여 교체한다.

LRU 알고리즘의 단점을 설명해 주세요. 이를 해결할 수 있는 대안에 대해서도 설명해 주세요.

LRU 알고리즘의 단점

공간 복잡도

LRU를 사용하려면 연결리스트와 해시맵을 동시에 사용해야 하기 때문에 많은 메모리를 차지한다.

성능 문제

LRU는 페이지 참조가 많을 때 모든 페이지를 추적하고 이동시키는 시간이 필요하다. 또한 연결 리스트로 구현하면 삽입과 삭제에 많은 시간이 소요될 수 있다.

LRU 알고리즘의 대안

Segmented LRU

두 개 이상의 LRU 리스트를 사용해서 페이지들을 그룹화하고, 그룹마다 다른 방식으로 교체하여 성능을 개선한다.

LFU(Least Frequently Used)

LRU는 페이지의 사용 시간을 기반으로 교체하지만, LFU는 사용 빈도에 따라서 교체한다. LFU는 자주 사용되는 페이지를 남겨 두는 방식으로 LRU가 가진 단기적인 패턴의 한계를 보완할 수 있다.