페이지 교체 알고리즘과 LRU

페이지 교체 알고리즘

페이지 교체 알고리즘은 가상 메모리 시스템에서 필수적으로 사용된다. 시스템의 물리 메모리가 제한되어 있을 때, 모든 프로세스의 전체 페이지를 메모리에 적재할 수 없기 때문에, 필요할 때마다 페이지를 교체해야 한다. 이때 어떤 페이지를 메모리에서 제거하고 새 페이지를 적재할지 결정하는 방식이 페이지 교체 알고리즘에 의해 정의된다. 가장 일반적인 페이지 교체 알고리즘은 FIFO(First In First Out), LRU(Least Recently Used), 그리고 LFU(Least Frequently Used) 등이 있다.

LRU 알고리즘의 특성

LRU(Least Recently Used) 알고리즘은 "시간 지역성"의 특성을 이용한다. 시간 지역성이란 최근에 접근된 데이터는 가까운 미래에 다시 접근될 가능성이 높다는 메모리 접근의 패턴을 말한다. LRU 알고리즘은 가장 오랫동안 사용되지 않은 페이지를 교체 대상으로 선택하여, 활발히 사용되는 데이터를 메모리에 유지한다.

LRU 알고리즘의 구현 방법

LRU 알고리즘을 구현하는 데는 여러 가지 방법이 있으나, 가장 일반적인 방법은 연결 리스트와 해시 테이블을 결합하는 것이다:

• 연결 리스트: 이 리스트는 각 페이지를 노드로 가지며, 가장 최근에 접근된 페이지가 리스트의 앞쪽에 위치하고, 가장 오래전에 접근된 페이지가 리스트의 뒤쪽에 위치한다. 페이지에 접근할 때마다 해당 페이지를 리스트의 앞으로 이동시킨다. 페이지 교체가 필요할 때는 리스트의 끝에 있는 페이지를 제거한다.

• 해시 테이블: 페이지 번호를 키로 하고, 해당 페이지의 연결 리스트 노드에 대한 포인터를 값으로 가지는 해시 테이블을 사용한다. 이를 통해 어떤 페이지가 메모리에 있는지 빠르게 확인하고, 연결 리스트에서 해당 페이지를 빠르게 찾아 접근할 수 있다.

LRU 알고리즘의 단점 및 대안

단점: LRU 알고리즘은 구현이 복잡하고, 페이지의 참조 정보를 유지하기 위해 추가적인 메모리와 처리 시간이 요구된다. 큰 메모리와 빈번한 페이지 접근이 있는 시스템에서는 오버헤드가 상당할 수 있다.

대안: LRU의 단점을 해결하기 위한 대안으로는 Approximate LRU가 있다. 이 방법은 LRU의 정확한 동작을 근사치로 구현하여 오버헤드를 줄인다. 예를 들어, Clock 알고리즘은 각 페이지에 사용 비트를 설정하고, 이 비트를 사용하여 LRU와 유사한 교체 결정을 내리되, 구현은 훨씬 단순하고 빠르다. Clock 알고리즘은 원형 큐를 사용하며, 교체 대상 페이지를 찾기 위해 비트를 체크하고 업데이트하는 방식으로 작동한다.