[운영체제 아주 쉬운 세 가지 이야기 - Virtualization] 22. Swapping - Policies
이 글은 제 개인적인 공부를 위해 작성한 글입니다.
틀린 내용이 있을 수 있고, 피드백은 환영합니다.
개요
가상 메모리 관리자의 입장에서 비어 있는 메모리가 많을수록 일은 쉬워진다. 페이지 폴트가 발생하면 빈페이지 리스트에서 비어 있는 페이지를 찾아서 폴트를 일으킨 페이지에게 할당하면 된다.
불행하게도 빈 메모리 공간이 거의 없으면 일이 더 복잡해진다. 그런 경우 운영체제는 메모리 압박(memory pressure)을 해소하기 위해 다른 페이지들을 강제적으로 페이징 아웃하여 활발히 사용 중인 페이지들을 위한 공간을 확보한다. 내보낼(evict) 페이지 선택은 운영체제의 교체 정책(replacement policy) 안에 집약되어 있다. 과거의 시스템들은 물리 메모리의 크기가 작았기 때문에 초기 가상 메모리 시스템의 가장 중요한 역할 중 하나가 바로 이 교체 정책이었다.
그렇다면 운영체제는 메모리에서 내보낼 페이지를 어떻게 결정할 수 있을까? 이 결정은 시스템 교체 정책에 의해서 내려진다. 교체 정책은 보편 타당한 원칙들을 따르지만 코너 케이스를 피하기 위한 수정 사항들도 포함되어 있다.
캐시 관리
정책에 대해서 논하기 전에 먼저 해결하고자 하는 문제에 대해 좀 더 상세히 설명하도록 하겠다. 시스템의 전체 페이지들 중 일부분만이 메인 메모리에 유지된다는 것을 가정하면, 메인 메모리는 시스템의 가상 메모리 페이지를 가져다 놓기 위한 캐시로 생각될 수 있다.
이 캐시를 위한 교체 정책의 목표는 캐시 미스의 횟수를 최소화하는 것이다. 즉, 디스크로부터 페이지를 가져오는 횟수를 최소로 만드는 것이다.
한편으로 캐시 히트의 횟수를 최대로 하는 것도 목표로 할 수 있다. 즉, 접근된 페이지가 메모리에 이미 존재하는 횟수를 최대로 하는 것이다.
캐시 히트와 미스의 횟수를 안다면 프로그램의 평균 메모리 접근 시간(average memory access time, AMAT)을 계산할 수 있다.
\[AMAT = (P_{Hit} * T_{M}) + (P_{Miss} * T_{D})\]- $P_{Hit}$: 캐시 히트 확률
- $P_{Miss}$: 캐시 미스 확률
- $T_{M}$: 메모리 접근 비용
- $T_{D}$: 디스크 접근 비용
$P_{Hit}$와 $P_{Miss}$는 0.0에서 1.0 사이의 값을 가지며, $P_{Hit} + P_{Miss} = 1.0$이다.
예를 들어, 어떤 컴퓨터가 4KB의 작은 메모리를 가지고 있고, 페이지 크기는 256바이트라고 하자. 가상 주소는 4비트 VPN(최상위 비트)과 8비트 오프셋(최하위 비트)의 두 부분으로 구성된다. 그러므로 이 예제에서 한 프로세스가 2^4 또는 총 16개의 가상 페이지들에 접근할 수 있다.
프로세스는 가상 주소 0x000, 0x100, …, 0x900의 메모리를 가리키고 있다. 이 가상 주소들은 주소 공간의 첫 열 개 페이지들의 첫 번째 바이트를 나타낸다. 각 가상 주소들의 첫 16진수 숫자가 페이지 번호를 나타낸다.
또한, 가상 페이지 3을 제외한 모든 페이지가 이미 메모리에 있다고 가정하자. 주어진 순서의 메모리 참조는 다음과 같은 동작을 보일 것이다.
히트,히트,히트,미스,히트,히트, 히트, 히트, 히트, 히트.
히트율을 계산하면 90%가 되고, 미스율은 10%가 된다. ($P_{Hit} = 0.9$, $P_{Miss} = 0.1$)
AMAT을 계산하기 위해서 $T_{M}$이 약 100 nsec이라 하고, $T_{D}$가 약 10 ms이라고 하자. AMAT은 0.9 * 100 ns + 0.1 * 10ms 이고 계산하면 0.9ns + 1ms or 1.0009ms or 약 1ms가 된다. 만약 히트율이 99.9%였다면 AMAT가 약 100배 더 빨라지고, 히트율에 100%에 가까워질수록 AMAT는 100ns에 가까워진다.
현대 시스템에서 디스크 접근 비용이 너무 크기 때문에 아주 작은 미스가 발생하더라도 전체적은 AMAT에 큰 영향을 주게 된다. 컴퓨터가 디스크 속도 수준으로 느리게 실행되는 것을 방지하기 위해서는 당연히 미스를 최대한 줄여야 한다. 이를 위해서는 좋은 정책을 잘 만드는 것이다.
최적 교체 정책
교체 정책의 동작 방식을 잘 이해하기 위해서는 최적 교체 정책(The Optimal Replacement Policy)과 비교하는 것이 좋다. 최적 교체 정책은 미스를 최소화하고, 가장 나중에 접근될 페이지를 교체하는 것이 최적이며, 가장 적은 횟수의 미스를 발생시킨다는 것을 증명하였다. 이 정책은 간단하지만 구현하기는 어려운 정책이다.
만약 페이지 하나를 내보내야 한다면 지금부터 가장 먼 시점에 필요하게 될 페이지를 버리는 것이 좋지 않을까? 핵심은 가장 먼 시점에 필요한 페이지보다 캐시에 존재하는 다른 페이지들이 더 중요하다는 것이다. 이 주장이 참인 이유는 간단하다. 가장 먼 시점에 접근하게 될 페이지보다 다른 페이지들을 먼저 참조할 것이기 떄문이다.
아래 간단한 예제는 프로그램이 0, 1, 2, 0, 1, 3, 0, 3, 1, 2, 1 순으로 가상 페이지를 접근한다. 캐시에서 세 개의 페이지를 저장할 수 있다고 가정할 때 그림은 최적 기법의 동작을 보여준다.
캐시는 처음에 비어 있는 상태로 시작하기 때문에 첫 세 번의 접근은 당연히 미스이다. 이러한 종류의 미스는 때로는 최초 시작 미스(cold-start miss) 또는 강제 미스(compulsory miss)라고 한다.
그 다음에 페이지 0, 1을 참조하면 캐시에서 히트되지만 페이지 3을 참조하면 미스를 만나게 되고 캐시가 가득 차있기 때문에 교체 정책이 실행되어야 한다.
이 때, 어떤 페이지를 교체해야 할까? 최적 기법의 경우 캐시에 현재 탑재되어 있는 각 페이지들(0, 1, 2)의 미래를 살펴본다. 그러면 0은 거의 즉시 접근이 되고, 1은 약간 후에, 2는 가장 먼 미래에 접근이 될 것이다. 그러므로 최적기법은 2를 내보내고 결과적으로 캐시에는 0, 1, 3이 남게 된다.
이런 식으로 진행이되어 캐시의 히트율을 계산할 수 있다. 캐시 히트가 6번, 미스가 5번이었으므로 히트율은 히트/(히트 + 미스) = 6/(6+5) = 6/11 = 약 54.5%가 된다. 페이지가 처음 미스된 강제 미스들을 제외한 히트율을 계산한다면 85.7%의 히트율을 얻는다.
불행하게도 스케줄링 정책을 만들 때도 보았지만, 미래는 일반적으로 미리 알 수 없다. 그렇기 때문에 범용 운영체제에서는 최적 기법의 구현은 불가능하다. 내보낼 페이지를 결정하기 위한 실제적이고 배포가 가능한 정책을 만들기 위해 다른 방법을 찾는 것에 집중할 것이다. 최적 기법은 비교 기준으로만 사용될 것이며, 이를 통해 정답에 얼마나 가까운지 알 수 있다.
여담 : 캐시 미스의 종류 (세 개의 C)
- 강제 미스(compulsory miss) 또는 최초 시작 미스(cold-start miss) : 캐시가 비어 있었고 그 항목을 처음으로 참조할 때 발생
- 용량 미스(capacity miss) : 캐시의 공간이 충분하지 않을 때 발생
- 충돌 미스(conflict miss) : 세트 연관 매핑(set-associativity)이라고 불리는 것 때문에 하드웨어에서 발생. 페이지 캐시는 완전 연관 매핑(fully associative)으로 되어 있기에 운영체제에서는 발생하지 않는다.
간단한 정책 : FIFO
FIFO는 먼저 들어온 것이 먼저 나간다, 선입 선출 교체 방식이다. 이 방법은 시스템에 페이지가 들어오면 큐에 삽입되고, 교체를 해야 할 경우 큐의 tail에 있는 먼저 들어온 페이지가 내보내진다.
FIFO는 매우 구현하기 쉽다는 장점이 있지만, 최적의 경우와 비교하면 눈에 띄게 성능이 안 좋다. 동일한 예제로 보면 히트율은 36.4%이고, 강제 미스를 제외해도 57.1%가 된다.
FIFO는 블럭들의 중요도를 판단할 수가 없다. 페이지 0이 여러 차례 접근이 되었더라도 단순히 메모리에 먼저 들어왔다는 이유로 FIFO는 페이지 0을 내보낸다.
간단한 정책 : 무작위 선택
이 방식은 페이지를 무작위로 선택하여 교차한다. FIFO와 유사하게 구현하기 쉽지만 내보낼 블럭을 제대로 선택하려는 노력을 하지 않는다.
물론 무작위 선택 정책은 선택할 때 얼마나 운이 좋은지에 전적으로 의존하여 성능은 그때그때에 따라 달라진다.
과거 정보의 사용 : LRU
불행하게도 FIFO 또는 무작위 선택 방식처럼 단순한 정책들은 중요한 페이지 혹은 바로 다시 참조하게 될 것들을 내보낼 수 있다는 비슷한 문제를 겪게 된다. FIFO와 무작위 선택 방식 그리고 그와 유사한 정책들은 최적 기법의 성능을 따라갈 수가 없기 때문에 좀 더 정교한 방식이 필요하다.
스케줄링 정책에서와 같이 미래에 대한 예측을 위해서 과거 사용 이력을 활용해보자. 예를 들어 어떤 프로그램이 가까운 과거에 한 페이지를 접근했다면 가까운 미래에 그 페이지를 다시 접근하게 될 확률이 높다.
페이지 교체 정책에 활용될 수 있는 과거 정보 중 하나는 빈도수(frequency)이다. 만약 한 페이지가 여러 차례 접근되었다면, 분명히 어떤 가치가 있기 때문에 교체되면 안될 것이다.
좀 더 자주 사용되는 페이지의 특징은 접근의 최근성(recency)이다. 더 최근에 접근된 페이지일수록 가까운 미래에 접근될 확률이 높을 것이다.
이러한 류의 정책은 지역성의 원칙(principle of locality)이라고 부르는 특성에 기반을 둔다. 이 원칙은 프로그램의 행동 양식을 관찰하여 얻은 결과이고, 이 원칙이 말하는 것은 단순하다. 프로그램들은 특정 코드들과 자료 구조를 상당히 빈번하게 접근하는 경항이 있다는 것이다.
코드의 예로는 반복문 코드를 들 수 있으며, 자료 구조로는 그 반복문에 의해 접근되는 배열을 들 수 있다. 과거의 현상을 보고 어떤 페이지들이 중요한지 판단하고, 내보낼 페이지를 선택할 때 중요한 페이지들은 메모리에 보존하는 것이다.
그리하여 과거 이력에 기반한 교체 알고리즘 부류가 탄생하게 되었다. Least-Frequently-Used (LFU) 정책은 가장 적은 빈도로 사용된 페이지를 교체한다. Least-Recently-Used (LRU) 정책은 가장 오래 전에 사용하였던 페이지를 교체한다.
상태를 유지하지 않는 랜덤이나 FIFO 정책에 비해 과거 정보를 사용하는 정책들이 더 좋은 성능을 보인다.
반대로 Most-Frequently-Used (MFU)와 Most-Recently-Used (MRU)와 같은 알고리즘도 존재하지만, 대부분의 경우 잘 동작하지 않는다. 지역성 접근 특성을 오히려 무시하기 떄문이다.
워크로드에 따른 성능 비교
이번에는 짧은 흐름 대신 더 복잡한 워크로드를 살펴보자.
첫 번째 살펴볼 워크로드에서는 지역성이 없다. 즉, 페이지들의 집합에서 페이지가 무작위적으로 참조된다.
100개의 페이지들이 일정 시간 동안 계속 접근하는 워크로드를 사용하고, 접근되는 페이지는 무작위적으로 선택되며 페이지들이 총 10,000번 접근된다.
캐시의 크기는 매우 작은 것부터 모든 페이지들을 담을 수 있는 크기까지 증가시켰으며, 각 정책이 캐시 크기에 따라 어떻게 동작하는지 살펴보자.
그림에서 보면 알 수 있듯이 워크로드에 지역성이 없다면 어느 정책을 사용하든 상관이 없다. LRU, FIFO, 무작위 선택 정책 모두 동일한 성능을 보이며 히트율을 정확히 캐시의 크기에 의해서 결정된다. 그리고 캐시가 충분히 커서 모든 워크로드를 다 포함할 수 있다면 역시 어느 정책을 사용하든지 상관 없다. 마지막으로, 최적 기법이 구현 가능한 기타 정책들보다 눈에 띄게 더 좋은 성능을 보인다. 미래를 알 수 있다면 교체 작업을 월등히 잘할 수 있다.
다음으로 살펴볼 워크로드는 80대 20 워크로드라고 불린다. 20%의 인기 있는 페이지에서 80%의 참조가 발생하고, 나머지 80%의 비인기 페이지들에 대해서 20%의 참조만 발생한다. 인기 있는 페이지들에 대한 참조가 실험 시간의 대부분을 차지한다.
그림에서 볼 수 있듯이 랜덤과 FIFO 정책이 상당히 좋은 성능을 보이지만, 인기 있는 페이지들을 캐시에 더 오래 두는 경향이 있는 LRU가 더 좋은 성능을 보인다. 인기 있는 페이지들이 과거에 빈번히 참조되었기 때문에 그 페이지들은 가까운 미래에 다시 참조되는 경향이 있기 때문이다. 최적 기법은 여전히 더 좋은 성능을 보이고 있으며, 이는 LRU의 과거 정보가 완벽하지는 않다는 것을 보여준다.
그렇다면 FIFO 방식과 무작위 선택 방식보다 LRU가 훨씬 대단한 것인가? 대답은 항상 그렇듯이 “상황에 따라 다르다”이다. 만약 각 미스로 인해 매우 비싼 값을 치러야 한다면 히트율이 약간만 증가하더라도 성능에 큰 차이를 만들어 낼 수 있다. 만약 그렇지 않다면 LRU로 인해 얻을 수 있는 장점은 당연히 그렇게 중요하지 않게 된다.
마지막으로 순차 반복 워크로드를 살펴보자. 이 워크로드는 50개의 페이지들을 순차적으로 참조한다.
0번 페이지 참조 -> 1번 페이지 참조 -> … 49번 페이지 참조 -> 0번 페이지 참조를 반복한다.
여러 응용 프로그램에서 흔하게 볼 수 있는 이 워크로드는 LRU와 FIFO 정책에서 가장 안좋은 성능을 보인다. 순차 반복 워크로드에서 이 알고리즘들은 오래된 페이지들을 내보낸다. 불행하게도 워크로드의 반복적인 특성으로 인해서 오래된 페이지들은 정책들이 캐시에 유지하려고 선택한 페이지들보다 먼저 접근된다. 실제로, 캐시의 크기가 49라고 할지라도 50개의 페이지들을 순차 반복하는 워크로드에서는 캐시 히트율이 0%가 된다.
무작위 선택 정책의 성능이 눈에 띄게 좋게 보이는 것처럼, 무작위 선택 정책의 장점 중 하나가 이상한 코너 케이스가 발생하지 않는다는 것이다.
과거 이력 기반 알고리즘의 구현
FIFO와 무작위 선택 정책들보다 LRU와 같은 알고리즘이 더 좋은 성능을 보인다. 그렇다면 과거 정보에 기반을 둔 정책을 어떻게 구현할 것인가?
LUR를 예로 들어보자. 이를 완벽하게 구현하기 위해서는 많은 작업을 해야 한다. 특히, 각 페이지 접근마다 해당 페이지가 리스트의 가장 앞으로 이동하도록 자료 구조를 갱신해야 한다. FIFO와 비교하면 FIFO 리스트는 어떤 페이지의 제거 혹은 삽입에만 접근된다. LRU에서는 어떤 페이지가 가장 최근에 또는 가장 오래 전에 사용되었는지를 관리하기 위해서 모든 메모리 참조 정보를 기록해야 한다.
이 작업을 효율적으로 하는 방법은 약간의 하드웨어 지원을 받는 것이다. 예를 들어 페이지 접근이 있을 때마다 하드웨어가 메모리의 시간 필드를 갱신하도록 할 수 있다. 이렇게 하여 페이지가 접근되면 하드웨어가 시간 필드를 현재 시간으로 설정한다. 페이지 교체 시에 OS는 가장 오래 전에 사용된 페이지를 찾기 위해 시간 필드를 검사한다.
하지만 시스템의 페이지 수가 증가하면 페이지들의 시간 정보 배열을 검색하여 가장 오래 전에 사용된 페이지를 찾는 것은 매우 고비용의 연산이 된다.
완벽한 LRU를 구현하는 것은 비싼 비용이 든다는 것을 전제로, 어떻게 LRU에 가까운 선택을 하고 유사한 행동을 보이는 정책을 구현할까? 가장 오래된 페이지를 꼭 찾아야만 할까? 대신 비슷하게 오래된 페이지를 찾아도 되지 않을까?
LRU 정책 근사하기
연산량이라는 관점에서 볼 때, LRU를 근사하는 식으로 만들면 구현이 훨씬 쉬워진다. 실제로 현대의 많은 시스템이 이런 방식을 택하고 있다.
이 개념에는 use bit 또는 reference bit라고 불리는 약간의 하드웨어 지원이 필요하다. 시스템의 각 페이지마다 하나의 use bit이 있으며, 이 비트는 메모리 어딘가에 존재한다. (구현에 따라 프로세스마다 가지고 있는 페이지 테이블에 있을 수도 있고, 또는 어딘가에 배열 형태로 존재할 수도 있다)
페이지가 참조될 때마다 하드웨어에 의해서 use bit이 1로 설정된다. 하드웨어는 이 비트를 절대로 0으로 설정하지 않고, 0으로 바꾸는 것은 운영체제의 몫이다.
운영체제는 LRU에 가깝게 구현하기 위해서 use bit을 어떻게 활용할까? 간단한 활용법이 시계 알고리즘(clock algorithm)이다.
시스템의 모든 페이지들이 환형 리스트를 구성한다고 가정하자. 시계 바늘(clock hand)이 특정 페이지를 가리킨다고 해 보자. 페이지를 교체해야 할 때 운영체제는 현재 바늘이 가리키고 있는 페이지 P의 use bit가 1인지 0인지 검사한다. 만약 1이라면 페이지 P는 최근에 사용되었으며 바람직한 교체 대상이 아니라는 것을 뜻한다. P의 use bit는 0으로 설정되고, 시계 바늘은 다음 페이지 P+1로 이동한다. 알고리즘은 use bit가 0으로 설정되어 있는, 최근에 사용된 적이 없는 페이지들 찾을 때까지 반복된다.
이 방법 외에도 use bit를 사용하여 LRU를 근사하는 다른 방법이 존재한다. 주기적으로 use bit를 지우고, 교체 대상 페이지 선택을 위해 use bit가 1과 0인 페이지를 구분할 수 있으면 된다.
시계 알고리즘 동작이 아래 그림에서 나와 있다. 완벽한 LRU만큼 좋은 성능을 보이지는 못하지만 과거 정보를 고려하지 않는 다른 기법들에 비해서는 성능이 좋다.
갱신된 페이지 (Dirty Page)의 고려
많은 곳에서 실제 사용되고 있는 시계 알고리즘에 대한 추가 개선 사항을 논의하고자 한다. 운영체제가 교체 대상을 선택할 때 메모리에 탑재된 이후에 변경되었는지를 추가적으로 고려하는 것이다.
만약에 어떤 페이지가 변경되어 더티(dirty) 상태가 되었다면, 그 페이지를 내보내기 위해서는 디스크에 변경 내용을 기록해야 하기 때문에 비싼 비용을 지불해야 한다. 만약 변경되지 않았다면 내보낼 때 추가 비용은 없다. 해당 페이지 프레임은 추가적인 I/O 없이 다른 용도로 재사용될 수 있다. 때문에 어떤 VM 시스템들은 더티 페이지 대신 깨끗한 페이지를 내보내는 것을 선호한다.
이와 같은 동작을 지원하기 위해서 하드웨어는 modified bit 또는 dirty bit를 포함해야 한다. 페이지가 변경될 때마다 이 비트가 1로 설정되므로 페이지 교체 알고리즘에서 이를 고려하여 교체 대상을 선택한다. 예를 들어, 시계 알고리즘은 교체 대상을 선택할 때 사용되지 않은 상태이고 깨끗한 두 조건을 모두 만족하는 페이지를 먼저 찾도록 수정된다. 만약 그런 페이지가 없다면, 수정되었지만 한동안 사용되지 않았던 페이지를 찾는다.
다른 VM 정책들
페이지 교체 정책이 VM 시스템이 채택하는 유일한 정책은 아니다. (그 중에 가장 중요한 것이기는 하다) 예를 들어, 운영체제는 언제 페이지를 메모리로 불러들일지 결정해야 한다. 페이지 선택(page selection) 정책은 운영체제에게 몇 가지 다른 옵션을 제공한다.
운영체제는 대부분의 페이지를 읽어 들일 때 요구 페이징(demand paging) 정책을 사용한다. 이 정책은 말 그대로 “요청된 후 즉시”, 즉 페이지가 실제로 접근될 때 운영체제가 해당 페이지를 메모리로 읽어 들인다.
운영체제는 어떤 페이지가 곧 사용될 것이라는 것을 대략 예상할 수 있기 떄문에 미리 메모리로 읽어 들일 수도 있다. 이와 같은 동작을 선반입(prefetching)이라고 하며 성공할 확률이 충분히 높을 때에만 해야 한다. 예를 들어, 어떤 시스템은 코드 페이지 P가 메모리에 탑재되면 P+1이 접근될 확률이 높기 때문에 P가 탑재될 때 P+1도 함께 탑재되어야 한다고 가정할 수 있을 것이다.
또 다른 정책은 운영체제가 변경된 페이지를 디스크에 반영하는 데 관련된 방식이다. 한 번에 한 페이지씩 디스크에 쓸 수 있지만, 많은 시스템은 기록해야 할 페이지들을 메모리에 모은 후, 한 번에 디스크에 기록한다. 이와 같은 동작을 클러스터링(clustering) 또는 단순하게 쓰기 모으기(grouping of writes)라고 부르며 효과적인 동작 방식이다. 왜냐하면 디스크 드라이브는 여러 개의 작은 크기의 쓰기 요청을 처리하는 것보다 하나의 큰 쓰기 요청을 더 효율적으로 처리할 수 있는 특성을 갖고 있기 때문이다.
쓰래싱(Thrashing)
마지막으로 메모리 사용 요구가 감당할 수 없을 만큼 많고 실행 중인 프로세스가 요구하는 메모리가 가용 물리 메모리 크기를 초과하는 경우에 운영체제는 어떻게 해야 하는가? 이런 경우 시스템은 끊임없이 페이징을 할 수 밖에 없고, 이와 같은 상황을 쓰래싱(thrashing)이라고 부른다.
몇몇 초기 운영체제들은 쓰래싱이 발생했을 때, 이의 발견과 해결을 위한 상당히 정교한 기법들을 가지고 있었다. 예를 들면 다수의 프로세스가 존재할 때, 일부 프로세스의 실행을 중지시킨다. 실행되는 프로세스의 수를 줄여서 나머지 프로세스를 모두 메모리에 탑재하여 실행하기 위해서이다. 워킹 셋(working set)이란 프로세스가 실행 중에 일정 시간 동안 사용하는 페이지들의 집합이다. 일반적으로 진입 제어(admission control)라고 알려져 있는 이 방법은 많은 일을 엉성하게 하는 것보다는 더 적은 일을 제대로 하는 것이 나을 때가 있다고 말한다.
일부 최신 시스템들은 메모리 과부하에 대하여 과감한 조치를 취하기도 한다. 예를 들면, 일부 버전의 Linux는 메모리 요구가 초과되면 메모리 부족 킬러(out-of-memory killer)를 실행시킨다. 이 데몬은 많은 메모리를 요구하는 프로세스를 골라 죽이는, 그다지 교묘하지 않은 방식으로 메모리 요구를 줄인다. 메모리 요구량을 줄이는데는 성공적일지 몰라도, 이 방법은 문제가 될 수 있다.
요약
- 최적 교체 정책 : 가장 먼 미래에 접근될 페이지를 교체하는 방식. 이론상 최고의 성능을 보이지만, 미래를 예측하기 어려우므로 실제 구현은 힘들다. 다른 정책들의 성능을 평가하기 위한 비교 기준으로 사용할 수 있다.
- FIFO(First-In-First-Out) 교체 정책 : 가장 먼저 메모리에 들어온 페이지를 교체한다. 구현은 간단하지만 페이지의 중요도를 고려하지 않아 성능이 좋지 않다.
- 무작위 교체 정책 : 임의의 페이지를 교체한다. 구현이 간단하고 코너 케이스를 피할 수 있다.
- LRU(Least-Recently-Used) 교체 정책 : 가장 오래 전에 사용된 페이지를 교체한다. 일반적으로 좋은 성능을 보인다.
- LRU 근사 정책 : 완벽한 LRU 구현은 비용이 많이 들기 때문에, 시계 알고리즘과 같은 근사 방법을 사용하여 구현한다.
- Use Bit : 페이지 접근 시 하드웨어가 1로 설정. 운영체제가 0으로 초기화한다.
- 시계 알고리즘 : 환형 큐와 포인터를 사용해 use bit가 0인 페이지를 찾아 교체한다.
- Dirty Bit or Modified Bit : 페이지가 메모리에 올라온 후 내용이 변경되었는지 나타내는 비트. 디스크 쓰기 비용을 비하기 위해 0인 페이지를 우선 교체하는데 사용될 수 있다.
- 요구 페이징 (Demand Paging) : 페이지가 실제로 접근될 때(폴트 발생 시) 메모리로 가져오는 정책
- 선반입 (Prefetching) : 앞으로 사용될 페이지를 미리 예측하여 가져오는 정책
- 클러스터링 (Clustering) : 여러 페이지 쓰기를 한번에 모아서 처리하여 디스크 I/O 효율을 높인다.
- 쓰래싱 (Thrashing) : 메모리가 과도하게 요구되어 시스템이 페이지 교체에만 시간을 소모하고 실제 작업을 거의 수행하지 못하는 상태. 진입 제어나 메모리 부족 킬러 등의 해결책이 있다.
- 진입 제어 (Admission Control) : 일부 프로세스의 실행을 중지시켜 적은 프로세스라도 실행할 수 있도록 하는 쓰래싱 해결 방법
- 메모리 부족 킬러 (Out-of-Memory Killer) : 다수의 메모리를 요구하는 프로세스를 강제로 종료시켜 메모리 요구를 줄이는 쓰래싱 해결 방법
참고