운영체제는 프로세스가 메모리를 효율적으로 이용할 수 있도록 필요하지 않은 페이지들을 보조기억장치로 내보낼 수 있어야 하며, 프로세스들에게 적절한 프레임을 할당하여 페이지를 할당할 수 있게 해야합니다.
📌 요구 페이징
프로세스를 메모리에 적재할 때, 필요한 페이지만을 메모리에 적재하는 기법을 요구 페이징(Demand Paging)이라고 합니다.
아무런 페이지도 메모리에 적재하지 않고 실행부터 할 수 있는데, 이럴 경우 페이지 폴트가 계속 발생하게 됩니다. 실행에 필요한 페이지가 적재되면서 페이지 폴트 발생 빈도가 떨어지는데, 이를 순수 요구 페이징(Pure Demand Paging)기법 이라고 합니다.
이러한 요구 페이징 기법을 사용하여 페이지들을 적재하다 보면 메모리가 가득 찰 것입니다.
이때, 적재된 페이지 중에서 어떤 페이지를 보조기억장치로 내보내는 것이 최선일지 결정하는 방법이 페이지 교체 알고리즘입니다.
📌 페이지 교체 알고리즘
이 페이지 교체 알고리즘을 통해 고른 페이지를 보조기억장치로 Swap Out했을 때, 페이지 폴트가 자주 발생하면 좋은 알고리즘은 아닙니다.
당연히 페이지 폴트 빈도가 자주 발생하지 않는다면 컴퓨터의 성능 저하를 방지하는 좋은 알고리즘으로 평가할 있습니다.
그래서, 페이지 교체 알고리즘은 페이지 폴트 횟수를 알 수 있어야 하며, 페이지 폴트 횟수는 페이지 참조열을 통해 알 수 있습니다.
페이지 참조열은 CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열을 의미합니다.
예를 들어, 아래와 같이 CPU가 순서대로 페이지에 접근했다고 가정하겠습니다.
2 2 2 3 5 5 5 3 3 7아래와 같이 연속된 페이지를 생략한 페이지열이 페이지 참조열입니다.
2 3 5 3 7🔎 연속된 페이지를 생략하는 이유?
중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않기 때문입니다.
그러면 각 알고리즘들을 살펴보겠습니다.
⚡ FIFO 페이지 교체 알고리즘
FIFO은 가장 간단한 페이지 교체 알고리즘입니다. 가장 먼저 Page-In한 페이지를 먼저 Page-Out시키는 방식으로 동작합니다.
이 FIFO 방식은 아이디어와 구현은 간단하지만, 프로그램 실행 초기에 적재된 페이지 속에는 프로그램 실행 초기에 잠깐 실행되다가 이후에 사용되지 않을 페이지도 있겠지만, 프로그램 실행 내내 사용될 내용을 포함하고 있을 수도 있습니다.
이런 페이지들은 메모리에 먼저 적재되었다고 해서 Page-Out시키면 오히려 성능이 더 나빠질 수 있습니다.
⚡ 최적 페이지 교체 알고리즘
최적 페이지 교체 알고리즘은 CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘입니다.
이 알고리즘은 가장 오랫동안 사용하지 않을 페이지를 선택하여 보조기억장치로 Page-Out하는 방식으로 동작합니다.
이름 그대로 가장 낮은 페이지 폴트율을 보장하는 알고리즘입니다.
페이지 참조열을 바탕으로 테스트해보면 다른 페이지 교체 알고리즘에 비해 페이지 폴트 발생 빈도가 가장 낮습니다.
하지만 이 최적 교체 알고리즘은 비현실적인 알고리즘입니다.
실제 컴퓨터 환경에서는 미래에 어떤 프로세스가 사용되는지 알 수 없기 떄문입니다. 그래서 어느 프로세스가 가장 오래 사용안되는 지를 계산할 수 없습니다.
이 최적 교체 알고리즘은 주로 다른 페이지 교체 알고리즘의 이론상 성능을 평가하기 위한 목적으로 사용됩니다.
⚡ LRU 페이지 교체 알고리즘
이 LRU 알고리즘이 나오게된 이유는 최적 페이지 교체 알고리즘은 최적해를 구할 수 있지만 미래를 알 수 없으므로 현실적으로 불가능한 방법이었습니다.
최적의 해는 아니더라도 근사의 해를 구하기 위해서 LRU가 나왔습니다.
최적 페이지 교체 알고리즘은 가장 오랫동안 사용되지 '않을' 페이지를 교체하는 알고리즘이라면, LRU는 가장 오랫동안 사용되지 '않은' 페이지를 교체하는 알고리즘입니다.
LRU는 최근에 사용되지 않으면 나중에도 사용되지 않을 것이라는 개념으로 과거의 페이지 기록을 통해 보조기억장치로 Page-Out할 페이지를 선택하는 방식으로 동작합니다.
FIFO 방식보다 페이지 폴트가 적게 일어나기 때문에 현재 대부분 환경에서는 LRU를 사용하고 있습니다.
이상으로 페이지 교체 알고리즘에 대해서 간단히 알아봤습니다.
참고
- KOCW - 운영체제, 양희재 교수님
- 혼자 공부하는 컴퓨터구조 + 운영체제
