목차
페이지 교체 정책
페이지 교체 정책은 가상 메모리 시스템을 활용하는 알고리즘을 의미합니다.
가상 메모리는 실제 물리적 메모리보다 더 큰 메모리 영역을 프로그램이 사용할 수 있도록 해주며, 이는 하드디스크의 일부를 메모리처럼 사용하는 것을 말합니다.
프로그램이 요구하는 메모리가 물리적 메모리의 용량을 초과할 때, 운영 체제는 페이지 교체 정책을 사용하여 필요한 데이터를 효율적으로 관리합니다.
페이지 교체 정책 종류
1. FIFO
FIFO는 가장 간단한 페이지 교체 알고리즘 중 하나입니다. 이 알고리즘은 큐를 사용하여 메모리에 적재된 페이지의 순서를 유지합니다. 새 페이지가 메모리에 적재될 필요가 있을 때, 큐의 가장 앞에 있는 페이지(가장 오래 전에 메모리에 적재된 페이지)를 제거합니다. 이 방식의 주요 단점은 오래된 페이지가 현재 매우 활발하게 사용되고 있더라도 교체될 수 있다는 것입니다.
2. LRU
LRU 알고리즘은 각 페이지가 마지막으로 사용된 시간을 추적하여 가장 오랜 시간 동안 사용되지 않은 페이지를 교체 대상으로 선택합니다. 이 방식은 최근의 사용 패턴을 반영하기 때문에, 자주 사용되는 페이지를 메모리에 유지하는 데 더 효과적입니다. 그러나, 각 페이지의 사용 시점을 정확하게 기록하기 위해서 추가적인 하드웨어 지원이 필요하거나 복잡한 자료구조가 필요할 수 있습니다.
3. Optimal Page Replacement
이상적인 페이지 교체 알고리즘으로, 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체합니다. 이 방법은 이론적으로 페이지 부재율을 최소화할 수 있으나, 미래의 메모리 접근 패턴을 예측할 수 없기 때문에 실제 시스템에서는 사용될 수 없습니다. 주로 학문적 연구나 다른 알고리즘의 성능 비교 기준으로 사용됩니다.
즉, 구현은 불가능하지만, 다른 알고리즘과의 비교를 위해 존재하는 이론적인 방법입니다.
4. Clock
Clock 알고리즘은 FIFO의 변형으로, 각 페이지에 추가적인 비트(참조 비트)를 사용하여 한 번 더 기회를 제공합니다. 시계바늘처럼 원을 돌며 각 페이지를 검사하고, 참조 비트가 설정된 페이지는 비트를 초기화하고 다음 페이지로 넘어갑니다. 참조 비트가 설정되지 않은 페이지를 교체합니다. 이 방식은 LRU의 근사치를 제공하면서 구현이 비교적 간단하고 효율적입니다.
클락 알고리즘과 향상된 클락 알고리즘 예시
클락 알고리즘
클락 알고리즘은 간단히 말해 FIFO와 Second Chance 알고리즘의 조합으로 볼 수 있습니다. 각 페이지에는 참조 비트가 할당되며, 메모리에 페이지가 처음 적재될 때 이 비트는 설정됩니다. 페이지 교체가 필요할 때, 클락 알고리즘은 순환 리스트(시계 모양)를 따라 이 비트를 검사합니다.
세컨드 찬스 알고리즘은 FIFO에서 반환되어야 할 페이지에 한 번 더 검사 기회를 제공하는 방식을 의미합니다.
작동 방식 예시
1.
페이지가 참조될 때마다 해당 페이지의 참조 비트를 1로 설정합니다.
2.
페이지를 교체해야 할 때, 클락 포인터가 참조 비트가 0인 페이지를 찾을 때까지 페이지들을 순차적으로 검토합니다.
3.
참조 비트가 1인 페이지를 만나면, 이를 0으로 설정하고, 클락 포인터를 다음 페이지로 이동시킵니다.
4.
참조 비트가 0인 페이지를 만나면, 그 페이지를 교체합니다.
향상된 클락 알고리즘
향상된 클락 알고리즘은 기본 클락 알고리즘을 더 발전시켜, 페이지의 참조 비트와 수정 비트(또는 더티 비트)를 모두 고려합니다. 수정 비트는 페이지가 수정되었는지 여부를 나타냅니다. 이 알고리즘은 메모리에서 교체될 페이지를 선택할 때, 페이지가 참조되었는지와 수정되었는지를 모두 고려하여 좀 더 세밀한 결정을 내릴 수 있습니다.
작동 방식 예시
1.
각 페이지는 참조 비트(R)와 수정 비트(M)을 갖습니다.
2.
페이지 교체가 필요할 때, 알고리즘은 두 단계의 검사를 수행합니다:
•
첫 번째 패스 : 클락 포인터가 순환하며 (R, M) = (0, 0)인 페이지를 찾습니다. 찾지 못하면, 참조된 페이지(R=1)의 R을 0으로 설정합니다.
•
두 번째 패스 : 첫 번째 패스에서 교체할 페이지를 찾지 못했다면, 다시 순환하며 (R, M) = (0, 0) 또는 (0, 1)인 페이지를 찾습니다. 여기서 수정되지 않은 페이지(더티 비트가 0인 페이지)를 우선적으로 교체합니다.
3.
이 과정은 메모리의 쓰기 작업을 최소화하고, 자주 사용되지 않는 페이지를 효과적으로 교체할 수 있도록 합니다.
