페이지 교체 알고리즘과 LRU 상세 설명

페이지 교체 알고리즘

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

LRU (Least Recently Used) 알고리즘의 특성

LRU 알고리즘은 "시간 지역성"이라는 개념에 기반한다. 시간 지역성은 최근에 접근된 데이터는 가까운 미래에 다시 접근될 가능성이 높다는 메모리 접근의 패턴을 나타낸다. LRU는 이러한 패턴을 이용하여, 가장 오랫동안 사용되지 않은 페이지를 교체 대상으로 선정하여, 활발히 사용되는 데이터를 메모리에 유지한다.

LRU 알고리즘의 구현 방법

LRU 알고리즘을 효과적으로 구현하는 방법은 여러 가지가 있다. 주로 사용되는 방법은 다음과 같다:

1. 더블 링크드 리스트 (Double Linked List): 이 리스트는 각 페이지를 노드로 가지며, 가장 최근에 접근된 페이지가 리스트의 앞쪽에 위치하고, 가장 오래전에 접근된 페이지가 리스트의 뒤쪽에 위치한다. 페이지에 접근할 때마다 해당 페이지를 리스트의 앞으로 옮긴다. 페이지 교체가 필요할 때는 리스트의 끝에 있는 페이지를 제거한다.

2. 해시 테이블: 페이지 번호와 해당 페이지를 가리키는 포인터를 저장하는 해시 테이블을 사용한다. 이 구조는 더블 링크드 리스트와 결합되어 페이지의 찾기와 이동을 빠르게 처리한다.

LRU 알고리즘의 단점 및 대안

단점:

• 메모리와 CPU 사용량: LRU의 주된 단점은 각 페이지의 사용 정보를 지속적으로 업데이트하는 데 필요한 CPU 시간과 메모리 사용량이다. 큰 메모리 크기나 높은 접근 빈도를 가진 시스템에서는 이 오버헤드가 상당할 수 있다.
• 구현 복잡성: LRU 알고리즘의 구현은 복잡하며, 오류가 발생하기 쉬워 정확한 구현이 요구된다.

대안:

• Clock 알고리즘: LRU의 단점을 해결하기 위해 고안된 Clock 알고리즘은 각 페이지에 사용 비트를 두고, 포인터가 원형으로 페이지를 순회하면서 사용되지 않은 페이지(사용 비트가 0인 페이지)를 교체한다. 이 방법은 LRU와 유사한 성능을 제공하면서 구현이 더 간단하고, 자원 사용이 더 적다.
• 2Q 알고리즘: 이 알고리즘은 두 개의 큐를 사용하며, 하나는 최근에 사용된 페이지를 다른 하나는 오래전에 사용된 페이지를 관리한다. 이 구조는 LRU보다 메모리와 CPU 오버헤드를 줄이면서 비슷한 페이지 교체 성능을 제공한다.