[운영체제/OS] 여러가지 페이지 교체 정책에 대해

0. 들어가면서

지난 시간에 가상 메모리의 기본적인 개념에 대해 공부했고, 한정된 물리 메모리에 많은 양의 논리 메모리를 로드하기 위한 디맨드 페이징(Demand Paging) 전략에 대해 살펴봤습니다.

 

디맨드 페이징(Demand Paging)은 필요한 페이지만 물리 메모리에 올려두고, 물리 메모리에 가용한 공간이 없으면 스와핑(Swapping)을 통해 페이지를 교체하는 컨셉을 가진 방법이었습니다.

 

[운영체제/OS] 메모리 관리 - 디맨드 페이징(Demand Paging)과 Page Fault Issue

 

그런데 문제는 여기서 페이지 부재(Page fault)가 필연적으로 발생할 수밖에 없다는 것인데요. 이번 시간에는 이러한 페이지 부재(Page fault)를 어떻게 핸들링 할 것인가? 즉, 어떤 페이지를 스와핑할 것인가에 대한 페이지 교체 정책(Page Replacement)에 대해 알아보겠습니다.

 

💡 1.  문제

Page fault를 핸들링하는 것은 간단한 일이 아닙니다. 왜 그럴까요?

 

잘 생각해보면, 어떤 페이지를 Swap-Out 할 것인가에 대한 기준은 정말 모호합니다. 사실, 딱 정할수가 없죠.  개념적으로 생각하면 앞으로 쓸 일이 거의 없는 페이지 혹은 미래에 Page fault를 최소로 일으키게 하는 녀석을 아웃시켜야 하지만 현실적으로는 미래에 프로세스가 어떻게 동작할 지 완벽히 예측하는 것은 불가능하기 때문입니다.

 

이전에 CPU 스케줄링 때 했던 이야기의 맥락과 비슷한데요. 그래서 우리는 몇 가지 기준들을 가지고 페이지 교체 알고리즘을 설계해보고, 각 알고리즘의 성능을 비교해보면서 어떤 정책이 어떤 이유에서 좋고 나쁜지를 공부해보겠습니다.

 

 

📖 2. 다양한 페이지 교체 정책들

페이지 교체 정책이라는 것은 곧 "어떤 페이지를 현재 물리 메모리에서 아웃시킬 것인가?"를 결정하는 정책입니다.

 

기본적으로는 '앞으로 정말 오래 안 쓸 것 같은 페이지를 희생양으로 쫓아내자'는 아이디어가 있을 수 있는데요. Belady라는 분이 실제로 가장 오래 안 쓸 것 같은 페이지를 지금 쫓아내는 것이 미래에 페이지 폴트를 가장 적게 일으키는 방법임을 증명하는 데 성공했습니다.

 

✅ 1) Optimal Algorithm

Optimal Algorithm

이 방법이 위 그림의 Optimal Algorithm인데요. 서두에서 이야기했다시피, 이 방법은 정말 이상적이지만...미래에 프로세스가 어떤 페이지를 필요로 하는지 100% 예측할 수 없기 때문에 현실적인 방법은 아닙니다. * Optimal 정책이라고 해서, 미래에 페이지 폴트가 한 번도 일어나지 않는다는 뜻은 아닙니다!

 

✅ 2) FIFO Algorithm

FIFO 알고리즘도 매우 간단합니다. 페이지 폴트가 발생하면 물리 메모리에 가장 먼저 들어온 페이지부터 희생양으로 삼습니다.

 

그런데 FIFO 알고리즘은 내 프로세스에 더 많은 프레임을 할당하더라도, 페이지 폴트가 줄어들지 않을 수 있는 치명적인 약점이 존재하는데요. 애초에 페이지 폴트가 한정된 프레임의 숫자 때문인데, 내 프로세스에 프레임을 더 많이 할당해도 페이지 폴트가 줄어들지 않으니...음 쓰면 안될 것 같은 알고리즘입니다.

FIFO Algorithm

위 그림을 보면 프로세스에 프레임을 3개 할당했을 때와 4개 할당했을 때 페이지 폴트의 수가 줄어들지 않는 것을 볼 수 있습니다.

 

 

✅ 3) LRU(Least Recently Used) Algorithm

💡 LRU 알고리즘은 실제로 Linux OS에서도 발전시켜서 사용하는 정말 중요한 페이지 교체 정책입니다.

 

이 방식은 현재 시점을 기준으로 가장 오랫동안 쓰지 않았던 녀석을 희생양으로 삼는 방법인데요. 이전 시간에 말한 Locality에 기반한 정책이라고 볼 수 있습니다. 

LRU Algorithm

위 그림을 보면 time = 5일 때, e가 들어오기 위해서는 c가 Swap-out 됩니다. c가 가장 오랫동안 사용되지 않았기 때문이죠.

 

한편, LRU 알고리즘에는 중요한 이슈가 하나 있는데요. "어떻게 가장 오랫동안 쓰이지 않은 페이지를 기록할 것인가?"입니다. 아래에서 이어서 설명해보겠습니다.

 

🗒 * 스택(Stack)을 이용한 LRU Implementation

아래 그림처럼 가장 최근에 사용한 페이지들을 기록하기 위해 스택을 사용할 수 있습니다. 스택의 맨 위에는 가장 최근에 사용한 페이지가 존재하고, 스택의 바닥에는 가장 오래 쓰이지 않은 페이지가 존재합니다. 이 방식을 채택한다면, 어떤 페이지에 대한 접근이 일어날 때마다 스택을 계속 업데이트 해주면 되는데요. 이미 스택에 있는 페이지였다면 맨 위로 올려주고, 그 외 페이지들을 아래로 한 칸씩 밀어주면 됩니다.

 

만약, 어떤 시점에 페이지 폴트가 발생한다면, 요구되는 페이지를 스택의 맨 위에 삽입하고, 맨 아래에 존재하는 가장 오래된 페이지를 아웃시키면 됩니다.

Stack을 이용한 LRU

위 그림을 보면  Time = 5 시점에 e라는 페이지가 필요합니다. 그러면 아래 스택에서 가장 밑에 있던 c 페이지를 제거하는 것을 볼 수 있습니다.

 

✅ 4) Counting Algorithm

카운팅 알고리즘(Counting Algorithm)은 각 페이지가 참조될 때마다 해당 페이지의 카운트 값을 1 증가시킵니다.

 

그리고 해당 카운트 값을 바탕으로 LFU(Least Frequently Used) 정책을 적용하는데요. 현재 물리 메모리에 올라와있는 페이지들 중에서 카운트 값이 가장 적은(가장 적게 사용한) 페이지를 아웃시키는 정책입니다.

 

그런데 LFU가 아닌 MFU(Most Frequently Used) 정책을 적용할 수도 있는데요. 이 경우에는 오히려 카운트 값이 큰 녀석을 페이지 교체 대상으로 삼습니다. 이미 제일 많이 사용했기 때문에 앞으로는 거의 쓰지 않을 거라는 예측 때문이죠.

 

✅ 5) Sampled LRU

이전 포스팅에서 페이지 테이블에는 단순히 페이지와 프레임의 매핑 정보, Offset 뿐만 아니라 몇 가지 Bit들이 존재한다고 했는데요. 여기서 Reference bit은 페이지 교체 정책에서 유용하게 쓰이는 녀석입니다.

 

Sampled LRU는 아래 그림처럼 각 페이지마다 계속해서 Reference bit을 기록해나갑니다. 즉, 일정한 시간 간격마다 인터럽트를 걸고 OS가 각각의 페이지에 대한 Reference bit을 읽는데요.

 

이 때, 각 페이지의 현재 Reference bit을 Reference bytes라는 별도의 메모리에 기록해놓고 LSB(Least Significant Bit)의 값을 갱신해주는 방식입니다. 그리고 만약 페이지 폴트가 발생하면 각 페이지의 Reference bytes를 체크해서 그 값이 가장 작은 녀석을 아웃시킵니다.

 

약간 헷갈릴 수 있는데, 아래 그림을 보겠습니다.

 

그림을 보면 왼쪽이 페이지 테이블이고, 페이지 테이블에는 Reference bit이 기록되어 있습니다. 그리고 오른쪽은 Reference Bytes라는 별도의 메모리인데요. 여기에는 일정한 시간 간격마다 갱신되는 Reference bit가 쌓이게 됩니다.

 

만약 시간 간격이 0.1초라고 해볼까요? 그러면 0.1초마다 OS는 CPU에게 인터럽트를 걸고 현재 물리 메모리에 올라와있는 페이지들의 Reference bit들을 검사합니다. 그리고 이 Reference bit을 Reference Bytes의 LSB 자리에 넣고 MSB 자리는 날려버립니다. 한참 오래된 정보는 필요없다는 뜻이죠!

 

그리고 검사가 끝나는 동시에 각 페이지 테이블의 Reference bit은 0으로 초기화해주는데요. "일정 시간동안 이 페이지를 쓴 적 있는가?"를 체크하기 위함입니다. 

 

그래서 결국 일정 시간동안 페이지를 많이 주기적으로 참조한 녀석은 살아남게 됩니다.

 

✅ 6) 클락 알고리즘(Clock Algorithm)

Clock Algorithm은 LRU Clock 또는 Second-Chance 알고리즘이라고도 불립니다. 이 알고리즘은 FIFO 개념과 LRU 개념을 약간 섞어 놓은 느낌인데요.

 

어떤 페이지에 대해 레퍼런스가 발생할 때마다 페이지의 Reference bit을 1로 설정합니다. 그리고 페이지 폴트가 발생하면 Clock이라고 하는 녀석이 원형으로 배치된 페이지들을 쓸고 지나가면서 Reference bit가 0인 녀석을 날려버리고 1인 녀석은 한 번 살려주면서 Reference bit을 다시 0으로 바꿔놓습니다. 그리고 이후에 일정 시간을 두고 다시 Clock이 한 바퀴를 돌려고 왔을 때 여전히 Reference bit이 0인 녀석은 "그동안 쓸모가 없었구나"라고 인식하여 아웃시켜버리죠.

 

물론 그동안 한 번이라도 사용된 녀석은 Reference bit이 다시 1로 설정되어 있기 때문에 살아남게 됩니다.

Clock Algorithm

한편 Clock hand가 2개인 Two-handed Clock Algorithm도 존재합니다. 이 방법은 기본적인 Clock algorithm과 개념은 똑같은데 쓸고 지나가는 시계침이 두 개라고 생각하면 됩니다.

 

그러니까 먼저 Fronthand가 페이지들을 지나가면서 reference bit를 0으로 설정하고, 그 다음에 backhand가 도착했을 때 여전히 reference bit가 0이면, 위와 마찬가지로 날려버리는 것이죠.

Two-handed Clock Algorithm

 

---

3. 나가면서

이번 포스팅에서는 몇 가지 페이지 교체 정책에 대한 작동 방식에 대해 살펴봤는데요.

 

다음 글에서는 실제로 프로세스에게 얼마만큼의 프레임을 할당해야 하는가에 대한 내용과 페이지 폴트와 관련된 몇 가지 현상들에 대해 정리해보겠습니다.

 

감사합니다.