페이지 교체 정책 A to Z!

📌 들어가기 전에

Page replacement 가 필요한 이유

대전제

1 . RAM의 크기는 제한적이다.

2 . 그에 반해 RAM에 올라갈 페이지들은 많다.

지금의 환경은 멀티 프로세스 환경으로 한번에 여러 개의 프로세스가 메모리에 올라가야 한다. 게다가 램보다 용량이 큰 프로그램도 이제 적지 않게 찾아볼 수 있는 환경이다. 그래서 필요한 페이지만 램에 상주시키는 방식을 사용해서 이를 해결하지만 그럼에도 불구하고 램이 꽉 차거나 혹은 어느 일정 정해진 수준을 넘어서게 되면 보조 기억 장치와의 Swap 이 필요한다. 이때 램의 어떤 페이지를 교체하겠냐를 정할 때 필요한 정책이 replacement policy 이다.

이 글에서는 어떤 페이지를 swap out(ram -> disk) 할 것인가를 다룬 알고리즘을 나열하고 그 특성을 알아보려고 한다.

📌 효율성을 따지는 방법

어떤 알고리즘이 더 효율적인가를 따지기 위한 도구가 필요하다. 그래서 이 장에서는 어떤 도구로 효율성을 따지는 지에 대한 설명을 하려고 한다.

캐시 미스(Cache miss)

찾으려고 하는 페이지가 물리메모리에 존재하지 않을 때 캐시 미스라고 한다. 페이지 교체 정책의 목표는 당연히 이 캐시 미스의 횟수를 최소화하는데 있다.

캐시 히트(Cache hit)

접근한 페이지가 이미 메모리 위에 존재했을 때의 횟수를 캐시 히트라고 한다.

평균 메모리 접근 시간(average memory access time, AMAT)

캐시 미스와 캐시 히트의 정보를 안다면 AMAT는 다음과 같은 식으로 계산할 수 있다.

여기서 $T_{M}$은 메모리 접근 비용을 나타내고, $T_{D}$는 디스크 접근 비용, $P_{Miss}$는 캐시에서 데이터를 못찾을 확률(미스)를 나타낸다. $P_{Miss}$는 0.0에서 1.0 사이의 값을 갖는다.

여기서 알 수 있는 점은
1 . 메모리 접근 비용은 항상 지불해야한다.
2 . 메모리에서 데이터를 못 찾을 경우 디스크로부터 데이터를 가져오는 비용을 추가로 지불해야한다.

어떤 방식으로 알고리즘의 성능을 측정하는지도 알았으니 이제 알고리즘의 종류를 알아보자.

📌 최적 교체 정책

최적 교체 정책(The Optimal Replacement Policy)는 미국 컴퓨터 과학자 Belady에 의해 개발되었다. 이는 MIN Policy라고도 부른다.

방법

가장 나중에 접근될 페이지를 교체한다.

장점

가장 먼 미래에 접근될 페이지를 버림으로서 최근에 접근될 페이지를 접근할 때 캐시 미스가 나지 않는다. 앞으로 나올 어떤 알고리즘보다 높은 히트율을 갖는다.

한계

스케줄링 정책에서도 보았듯이 미래를 미리 알기 힘들다. 따라서 구현이 힘들다.

의의

다른 정책들의 비교기준으로 사용할 수 있다. 다른 정책들이 얼마나 이 정책의 히트율에 가까운지를 판별한다.

📌 FIFO

정책하면 가장 먼저 나오는 선입선출(first in first out, FIFO) 정책이다. 역시 먼저 들어온 페이지가 가장 먼저 나가게 되는 정책이다.

장점

FIFO는 매우 구현이 쉽다.

한계

공간지역성을 고려할 수 없다. 많이 참조가 되어 중요한 페이지 임에도 불구하고 먼저 들어왔다는 이유로 메모리에서 방출될 수 있다는 한계가 있다. 최적 교체 정책에 비해 매우 성능이 좋지 않다.

📌 Random selection

방법

이름에서 알 수 있듯이 페이지 교체가 필요할 때 메모리 상에 올라가있는 페이지 중에서 무작위로 선택해서 교체하는 방법이다.

장점

FIFO와 마찬가지로 구현하기 쉽다.

한계

선택할 때의 운에 의존하는 정책이다. 어떠한 때에는 좋은 성능을 보일 수도 있고 아닐 수도 있다.

📌 LRU, LFU

지역성의 원칙(principle of locality)에 기반을 둔 정책들이다. 과거에 사용했던 이력을 참조해서 교체할 페이지를 고르는 정책이다.

1 . LRU

LRU는 Least-Recently-Used 정책으로 가장 오래 전에 사용하였던 페이지를 교체한다. LRU의 경우에는 거의 최적 교체 정책과 비슷한 수준의 결과까지 보여줄 수도 있다.

2 . LFU

LFU는 Least-Frequently-Used 정책으로 가장 적은 빈도로 사용된 페이지를 교체하는 정책이다.

반대로

MFU(Most-Frequently-Used), MRU(Most-Recently-Used) 정책도 있다. LFU, LRU 와는 반대로 가장 자주 쓰인 페이지나 가장 최근에 쓰인 페이지를 교체하는 정책인데 이런 정책들은 잘 동작하지 않는다. 대부분의 프로그램에서 관찰되는 지역성의 원칙을 오히려 무시하는 정책이기 때문이다.

📌 NRU

Not Recently Used 알고리즘으로 LRU보다 적은 overhead로 비슷한 성능 달성을 목적으로한 정책이다.
LRU 와 달리 두개의 bit vector를 사용한다. Reference bit vector(r), 그리고 Update bit vector(m)을 사용한다. 그래서 교체하는데 우선순위가 생기게 되는데

교체 순서

1등 (r, m) = (0, 0)
2등 (r, m) = (0, 1)
3등 (r, m) = (1, 0)
4등 (r, m) = (1, 1)
숫자가 높을 수록 나중에 교체한다.
또한 일정 시간마다 모든 페이지 프레임의 reference bit를 0으로 초기화한다.

📌 LRU를 구현하기 위해서

1 . clock algoritm

페이지들이 환형 리스트라고 가정했을 때 시계 바늘(clock hand)이 특정 페이지를 가리킨다. 이때 페이지의 use bit(or reference bit)가 1이라면 최근에 사용했던 페이지라는 뜻이다. 이때, use bit을 0으로 바꾸고 다음 페이지로 넘어간다. 그리고 0인 페이지를 만났을 때 그 페이지를 교체한다.

이때 교체할 페이지를 찾기위해 모든 페이지를 경유해야하는 경우도 생길 수 있다. 주기적인 초기화는 없다.

2 . second chance algoritm

clock 알고리즘과 비슷해서 헷갈릴 수도 있다. 다만 clock 알고리즘과 다르게 NRU 알고리즘처럼 reference bit(r)와 update bit(m)를 모두 사용한다. 그래서 (r, m)이
(0, 0) 이면 교체 페이지로 결정하고
(0,1)이면 (0,0)으로 바꾼다. 이때 write-back list에 추가한 뒤에 이동한다.
(1,0)이면 (0,0)으로 바꾼 후에 이동한다.
(1,1)이면 (0,1)로 바꾼 후에 이동한다.

✏️ (추가)Belady's anomaly

벨라디의 역설은 FIFO 정책에서 물리 프레임의 양의 늘리면 직관적으로 성능이 더 좋아질 것 같은데 그렇지 않음을 알아낸 역설이다.

위 그림을 보면 왼쪽 그림은 memory frame이 세 개이고 오른쪽 그림은 4개로 늘린 상황이다. 하지만 페이지 폴트의 수는 오히려 늘어났음을 확인할 수 있다.

✏️ (추가)TLB에서의 교체정책

MMU에서의 TLB에서도 당연히 교체정책이 필요하다. 이때 위에서 공부한 LRU 방식으로 페이지 테이블 엔트리를 교체한다고 한다.

글을 마치며

이외에도 정책은 무척이나 많지만 대표적인 정책을 언급하면서 글을 마치려고 한다. 정책을 정리하다보니 프로세스 스케줄링과 문제 해결하는 방식이 유사하다는 것을 느꼈다. 컴퓨터 공학에서의 해결 대원칙을 알아내면서 공부하면 앞으로 현업에서의 문제를 해결하는데에도 분명 도움이 더 될 것이라고 생각한다.

도움받은 자료

책 / 운영체제 아주 쉬운 세 가지 이야기
Operating System (운영체제), CPA310, KOREATECH
Instructor: Duksu Kim (김덕수)