[운영체제(OS)] 가상 메모리 - (4) 페이지 교체 알고리즘

0.🚶들어가며

[운영체제(OS)] 가상 메모리 - (3) 요구 페이징(Demand Paging)

지난 글에서는 요구 페이징, 페이지 부재, 지역성 등에 대한 개념을 살펴보았습니다. 이번 글에서는 페이지 부재를 최소화하기 위해서 사용하는 페이지 교체 알고리즘의 개념과 종류를 알아보도록 하겠습니다.

---

1.📖페이지 교체 알고리즘이란?

프로세스가 요구한 페이지가 메모리에 없을 경우 페이지 부재가 발생합니다. 만약 메모리까지 꽉 차있는 상황이라면 대상 페이지를 정하고 이를 쫓아낸 뒤 요구한 페이지를 메모리에 올려야 합니다. 이때 대상 페이지를 정하는 알고리즘을 페이지 교체 알고리즘이라고 합니다. 페이지 교체 알고리즘에 따라 시스템 성능이 달라질 수 있죠.

---

2.📚무작위 페이지 교체 알고리즘

무작위 페이지 교체 알고리즘은 대상 페이지를 특별한 로직 없이 무작위로 선정하는 방식입니다. 이 방식은 지역성과 같이 성능에 영향을 주는 요소를 고려하지 않습니다. 거의 사용되지 않는 알고리즘이죠.

---

3.📃FIFO 페이지 교체 알고리즘

FIFO 페이지 교체 알고리즘은 시간상 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정하는 방식입니다. 간단한 알고리즘이죠.

 

시간 지역성을 고려했을 때 메모리에 올라온 지 오래된 페이지는 대상 페이지로 선정하는 것이 합리적이다 라고 생각할 수 있지만 메모리에 올라온 지 오래되었더라도 자주 사용되는 페이지가 있을 수 있습니다. 이에 대한 고려가 전혀 이루어지지 않기 때문에 성능이 떨어지는 알고리즘입니다.

---

4.⏰최적 페이지 교체 알고리즘

최적 페이지 교체 알고리즘은 앞으로 사용하지 않을 페이지를 대상 페이지로 선정합니다. 앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정 시점부터 가장 멀리 있는 페이지를 대상 페이지로 정하는 것이죠.

 

최적 페이지 교체 알고리즘은 이상적인 알고리즘입니다. 애초에 가정했던 "앞으로 사용할 페이지를 미리 살펴보고" 부분은 미래의 접근 패턴을 알고 있다는 뜻인데 이는 불가능한 일입니다.

 

최적 페이지 교체 알고리즘은 다른 교체 알고리즘의 비교 척도로써의 역할을 합니다. 최적 페이지 교체 알고리즘과 성능이 비슷하게 나온다면 성능면에서 좋은 알고리즘이라고 생각할 수 있는 것이죠.

---

5.🕣LRU 페이지 교체 알고리즘

LRU 페이지 교체 알고리즘은 Least Recently Used의 줄임말입니다. 즉, 가장 오랫동안 사용되지 않은 페이지를 대상 페이지로 선정하는 것이죠. 이를 구현하는 방식은 다양할 수 있습니다. 이번 글에서는 두 가지를 살펴보도록 하겠습니다.

1) 페이지 접근 시간에 기반한 구현

LRU 방식의 가장 간단한 형태입니다. 페이지에 접근한 시간을 기록하여 구현하는 것이죠. 기록한 내용을 바탕으로 페이지에 접근한 지 가장 오래된 페이지를 대상 페이지로 선정합니다. 이 방식은 시간을 기록해야 하기 때문에 메모리 오버헤드가 생긴다는 것이 단점입니다.

3) 참조 비트 시프트 방식

참조 비트 시프트 방식을 사용하여 LRU를 구현하는 방식입니다. 특정 크기의 비트열을 준비하고 페이지에 접근하면 왼쪽 비트에 1을 추가합니다. 또한 참조 비트를 주기적으로 오른쪽으로 한 칸씩 이동시킵니다. 이런 방식을 사용하면 참조 비트열에 총합이 가장 작은 페이지가 선정 대상이 되는 것입니다. 시간을 기록하는 방식보다 메모리를 아낄 수 있는 방식이죠.

 

LRU 페이지 교체 알고리즘은 최적 근접 알고리즘이긴 하지만 메모리 낭비가 생기는 교체 알고리즘입니다. 시간을 어떻게든 기록해야 하기 때문이죠.

---

6.🏡LFU 페이지 교체 알고리즘

LFU 페이지 교체 알고리즘은 Least Frequently Used의 줄임말입니다. 최소 빈도 사용 알고리즘이라고도 하죠. 대상 페이지가 되는 페이지는 페이지가 몇 번 사용됐는지를 기반으로 합니다. 사용 횟수가 가장 적은 페이지를 스왑 영역으로 내보내는 것이죠.

 

이 역시 LRU와 마찬가지로 최적 근접 알고리즘이지만 페이지 접근 횟수를 표시하는데 추가 공간이 필요하므로 메모리 낭비가 생깁니다.

---

7.🎯NUR 페이지 교체 알고리즘

NUR 페이지 교체 알고리즘은 Not Used Recently의 줄임말입니다. LRU, LFU와 비슷한 성능을 내면서도 공간 낭비 문제를 해결한 방식이죠.

 

페이지를 접근한 횟수가 100회, 102회인 페이지 두 개가 있다고 가정해봅시다. 접근 횟수 차이가 적게 나는 페이지끼리는 대상 페이지를 선정하는 데 있어서 큰 의미를 가지지 않을 수도 있습니다. 이러한 사고 하에 생겨난 알고리즘인 것이죠.

 

NUR은 두 개의 추가 비트만을 사용하여 미래를 추정합니다. 참조 비트와 변경 비트이죠. 각각은 페이지가 접근했는지, 페이지가 변경되었는지를 체크하는 비트입니다.

 

두 비트를 사용하면 페이지마다 (0, 0), (0, 1), (1, 0), (1, 1) 넷 중 하나의 정보를 가지고 있을 것입니다. 이 정보의 순서대로 대상 페이지 선정을 하게 됩니다. 

---

8.🎪FIFO 변형 알고리즘

FIFO 알고리즘은 자주 사용하는 페이지를 고려하지 않기 때문에 성능이 좋지 않다고 하였습니다. 이러한 단점을 개선한 FIFO 변형 알고리즘이 있는데 한 예시만 살펴보겠습니다.

1) 2차 기회 페이지 교체 알고리즘

2차 기회 알고리즘은 FIFO 페이지 교체 알고리즘과 마찬가지로 큐를 사용합니다. 하지만 특정 페이지에 접근하는 것이 페이지 부재 없이 이루어진다면 해당 페이지를 큐의 가장 맨 뒤로 이동시켜줍니다. 메모리에서 살아남을 수 있도록 한 번 더 기회를 주는 방식이죠.

 

2차 기회 페이지 교체 알고리즘은 LRU, LFU, NUR보다는 성능이 약간 낮고 FIFO보다는 높은 것으로 알려져 있습니다.

---

9.💨나가며

이번 글에서는 대상 페이지를 선정하는 페이지 교체 알고리즘에 대해 알아보았습니다. 페이지 교체 알고리즘을 배우면서 프로세스 스케줄링의 내용과 비슷한 흐름으로 배우고 있다는 생각이 들었는데 어느 점에서 차이가 있었는지에 대해 짚고 넘어간다면 더 명확하게 이해할 수 있을 것 같습니다.

 

다음 글에서는 스레싱과 프레임 할당에 대한 내용을 살펴보도록 하겠습니다.