[운영체제] 페이지 교체 알고리즘

패스트캠퍼스 운영체제 강의와 쉽게 배우는 운영체제 교재에 대한 TIL입니다.

 

저번 포스팅은 메모리 관리 작업 중 메모리 가져오기(Fetch) 정책에 관한 것이었다면, 이번 포스팅은 메모리 재배치(Replacement) 정책에 관한 것이다.

페이지 교체 알고리즘의 종류

페이지 교체 알고리즘의 핵심은 메모리에서 앞으로 사용할 가능성이 적은 페이지를 대상 페이지로 선정하여 페이지 부재를 줄이고 시스템의 성능을 향상하는 것이다. 따라서, 이에 대한 구현 방식에 따라 아래와 같은 여러 종류의 페이지 교체 알고리즘이 만들어졌다.

앞으로 소개될 모든 페이지 교체 알고리즘은 아래 그림과 같은 메모리 접근 순서를 사용하고 물리 메모리는 3개의 프레임을 가졌다고 가정할 것이므로 참고하고 읽어주길 바란다. 페이지는 번호 대신 알파벳을 사용한다.

무작위 페이지 교체 알고리즘(Random)

가장 간단하게 구현할 수 있는 알고리즘이다. 스왑 아웃될 대상 페이지를 특별한 로직 없이 무작위로 선정한다. 당연히 성능이 좋지 않아 거의 사용되지 않는다.

FIFO 페이지 교체 알고리즘(First In First Out)

시간상으로 물리 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정하여 스왑 아웃시킨다. 페이지 부재일 때는 F, 원하는 페이지가 메모리에 있는 경우는 S로 표시되어 있다.

큐로 구현되어 있어, 새로운 페이지는 항상 맨 아래에 삽입되는데, 이때, 메모리가 꽉 차면, 맨 위의 페이지가 스왑 아웃되고 나머지 페이지들이 위쪽으로 이동하여, 새로운 페이지가 맨 아래로 들어온다.

이 그림에서는 총 열 번의 페이지 요구에 대해 세 번만 성공하고, 페이지 부재는 일곱 번 발생했다. 페이지 교체 알고리즘에서는 앞으로 사용하지 않을 페이지를 스왑 아웃시키는 것이 중요한데, FIFO 알고리즘은 그렇지 않다. 따라서, 성능이 떨어진다.

최적 페이지 교체 알고리즘(Optimal)

앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정 시점부터 사용 시점까지 가장 멀리 있는 페이지, 즉 앞으로 사용하지 않을 가능성이 제일 높은 페이지를 대상 페이지로 선정한다.

4번 시점에서 이후에 A와 B 페이지가 사용될 것을 알고 있기 때문에 C 페이지를 대상 페이지로 선정해 스왑 아웃시킨다.

하지만, 최적 페이지 교체 알고리즘은 어디까지나 이상적인 방법이므로 실제로는 미래의 접근 패턴을 알고 구현할 수가 없다. 따라서, 다음에 소개될 알고리즘들은 최적 페이지 교체 알고리즘에 근접하는 방법을 연구한 결과로 나온 알고리즘들이다.

이러한 알고리즘들은 과거의 데이터를 바탕으로 미래의 접근 패턴을 추정하기 때문에 최적 근접 알고리즘(Optimal Approximation Algorithm)이라고 부른다.

LRU 페이지 교체 알고리즘(Least Recently Used)

메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑 아웃시키는 알고리즘이다. 가장 오랫동안 사용되지 않은 페이지를 판단하는 방법에 따라 구현 방식은 여러 가지이다.

 

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

가장 간단하게 판단하는 방법은 페이지에 접근한 시각을 기록하여 판단하는 것이다.

 

 

메모리를 추가적으로 사용해서 각 페이지에 접근한 시각을 기록한다. 4번 시점에서 가장 페이지 접근 시간이 적은 페이지는 A이다. 따라서, 페이지 A를 대상 페이지로 선정하여 스왑 아웃시키고 그 자리에 페이지 D를 스왑 인시킨다.

 

카운터에 기반한 구현

가장 오랫동안 사용되지 않은 페이지를 판단하는 다른 방법으로는 카운터를 사용하여 구현할 수도 있다. 즉, 메모리를 추가적으로 사용해서 페이지에 접근한 시각이 아닌, 몇 번째로 접근했는지를 기록하는 것이다.

 

사실상, 페이지 접근 시간을 기록하는 방식이랑 다를 바가 없다. 이 두 가지 방식 모두 메모리 공간이 추가로 더 들어간다는 단점이 존재한다.

 

참조 비트 시프트 방식

각 페이지에 일정 크기의 참조 비트를 만들어 사용하는 것이다. 참조 비트의 초깃값은 0이며 페이지에 접근할 때마다 1로 바뀐다. 또한, 참조 비트는 주기적으로 한 칸씩 오른쪽 시프트(>>) 된다.

 

 

이와 같은 방식으로 참조 비트를 갱신하다가 대상 페이지를 선정할 필요가 있으면 참조 비트 중 가장 작은 값을 대상 페이지로 선정한다. 위 그림에서 (c) 시점에서 대상 페이지를 선정하려고 하면 당연히 C < A < B이므로 C가 대상 페이지가 된다.

 

참조 비트 시프트 방식은 다음에 나올 가장 적은 접근 횟수를 갖는 페이지를 대상 페이지를 선정하는 LFU 페이지 교체 알고리즘과 혼동하기 쉽다. 

 

 

하지만, 위 그림을 보면 엄연히 LFU 알고리즘과는 다르다는 것을 알 수 있다. 가장 많은 페이지 접근 횟수를 가진 페이지 C임에도 불구하고 페이지 A, B보다 오랫동안 접근되지 않았다는 것을 참조 비트 값으로 알 수 있기 때문에 대상 페이지로 페이지 C가 선정된다.

 

참조 비트 시프트 방식도 다른 두 가지 구현 방식과 똑같이 추가적으로 메모리 공간이 필요하다. 따라서, 구현 방식에 상관없이 LRU 페이지 교체 알고리즘은 메모리가 추가로 필요하여 낭비되는 메모리 공간이 많아진다는 단점을 가지고 있다.

 

LFU 페이지 교체 알고리즘(Least Frequently Used)

페이지가 몇 번 사용되었는지를 기준으로 대상 페이지를 선정한다. 즉, 현재 프레임에 있는 페이지마다 그동안 사용된 횟수를 세어 횟수가 가장 적은 페이지를 스왑 아웃시킨다.

 

 

위 그림에서 프레임 안에서 알파벳 아래의 숫자는 사용 빈도를 나타낸다. 이때, 사용 빈도가 같은 경우에는 FIFO, LRU, 무작위와 같은 추가 기준 알고리즘을 사용하여 대상 페이지를 선정하지만, 이 교재에서는 간단하게 맨 위의 페이지를 대상 페이지로 선정한다고 가정했다.

 

따라서, 4번 시점에서는 페이지 A가 대상 페이지로 선정되고, 6번 시점에서는 페이지 A와 C의 사용 빈도가 가장 적고 같아 페이지 A가 대상 페이지로 선정되었다.

 

알고리즘의 성능은 LRU 알고리즘과 비슷하다고 알려져 있다. 그러나, 페이지 접근 횟수(빈도)를 표시하는 데 LRU 알고리즘과 마찬가지로 메모리의 추가 공간이 필요하므로 낭비되는 메모리 공간이 많다는 단점이 존재한다.

 

NUR 페이지 교체 알고리즘(Not Used Recently)

LRU, LFU 페이지 교체 알고리즘과 성능이 거의 비슷하면서도 불필요한 메모리 공간 낭비 문제를 해결한 페이지 교체 알고리즘이다. NUR 페이지 교체 알고리즘에서는 추가적인 메모리 공간을 사용하지 않고 저번 포스팅에서 언급했던 PTE의 접근(참조) 비트, 변경 비트를 이용해서 대상 페이지를 선정한다.

 

접근 비트는 페이지에 접근, 즉 읽기(read)나 실행(execute) 연산이 되면 1이 되고, 변경 비트는 페이지가 변경, 즉 쓰기(write)나 추가(append) 연산이 되면 1이 된다. 따라서, 초기 상태 (0, 0)에서부터 시작하여 '접근'이 발생하면 (1, 0), '변경'이 발생하면 (0, 1)이 된다. 또한, 두 가지 연산이 다 발생하면 (1, 1)이 된다.

 

 

위 그림은 NUR 알고리즘에서 대상 페이지를 선정하는 순서를 보여준다. 순서를 보면 알 수 있듯이 우선 고려 대상은 접근(참조) 비트이다. 접근 비트가 0인 페이지를 먼저 찾고, 없으면 변경 비트가 0인 페이지를 찾는다.

 

만약, 같은 비트의 페이지가 여러 개라면 무작위, FIFO 등 다양한 방식의 추가 기준을 사용하여 대상 페이지를 선정한다. 또한, 흔한 상황은 아니지만 만약 모든 페이지가 (1, 1)이라면 모든 페이지 비트를 (0, 0)으로 초기화한다. 아래 그림은 NUR 페이지 교체 알고리즘 동작 과정이다. 같은 비트의 페이지가 여러 개일 때 맨 위 페이지를 대상 페이지로 선정한다는 가정을 참고하고 봐주길 바란다.

 

 

알고리즘의 성능은 LRU, LFU 알고리즘과 비슷하지만 낭비되는 메모리 공간이 없다는 장점이 있다. 이 교재에서는 NUR이 이러한 장점 때문에 널리 사용되고 있다고 했지만, 실제로는 LRU 알고리즘을 많이 사용하고 있다고 한다.

 

NUR 알고리즘을 채택하지 않는 이유는 각 페이지의 참조를 유지 및 업데이트하고 비트를 수정하기 위해 추가적인 하드웨어 지원이나 소프트웨어 오버헤드가 필요하기 때문이라고 한다. 반면에, LRU는 LFU, NUR보다 구현이 비교적 쉽고 오버헤드가 적기 때문에 많이 사용되는 알고리즘이라고 한다.

 

FIFO 변형 알고리즘

FIFO 페이지 교체 알고리즘을 기본, 즉 큐를 사용하되 페이지 접근할 때마다 순서의 변화를 주어 성능을 향상한 알고리즘들이다.

 

2차 기회 페이지 교체 알고리즘(Second Chance)

특정 페이지에 접근하여 페이지 부재 없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동하여 대상 페이지에서 제외, 즉 성공할 기회를 한 번 더 주는 알고리즘이다. 큐의 맨 뒤로 옮기면 대상 페이지로 선정될 확률이 줄어드는 특징을 이용했다.

 

 

5번 시점에서 페이지 부재가 일어나지 않았으므로 큐의 맨 앞에 있던 페이지 B를 맨 뒤로 보내는 것을 확인할 수 있다.

 

성능은 LRU, LFU, NUR 알고리즘보다 약간 낮고, FIFO 알고리즘보단 약간 높다고 한다. 하지만, 큐를 유지하는 비용이 높고, 페이지가 성공하면 큐의 중간에 있는 값을 맨 뒤로 이동시키는 작업이 추가된다는 단점이 있다.

 

 

시계 알고리즘

원형 큐를 사용해서 대상 페이지를 선정하는 페이지 교체 알고리즘이다.

 

 

시계 알고리즘에서는 위 그림과 같이 대상 페이지를 가리키는 포인터를 사용하는데, 이 포인터가 큐의 맨 아래로 내려가면 시계처럼 다음번에는 다시 큐의 처음을 가리키게 된다.

 

 
위 그림은 시계 알고리즘의 동작 과정을 나타낸 것이다. 시계 알고리즘은 PTE의 접근(참조) 비트를 사용하는데, 메모리에 있는 페이지를 성공적으로 참조되면 0에서 1로 변경된다.

 

4번 시점처럼 메모리가 꽉 찼을 경우 대상 페이지를 가리키는 포인터가 스왑 인이 되었을 경우 밑으로 이동한다. 이때, 9번 시점처럼 참조 비트가 1인 페이지는 0으로 바꿔놓고 건너뛴다.

 

참고로 Linux, Windows, macOS와 같은 대표적인 운영체제들은 LRU 알고리즘과 시계 알고리즘을 혼용해서 페이지 교체를 한다고 한다. 가장 오랫동안 사용되지 않는 페이지를 찾는 데에 효과적이고, 최근에 참조된 페이지를 보존하는 데에 효과적인 두 알고리즘의 장점을 조합하여 페이지 교체의 효율성을 높였다고 한다.