2-15장. 물리 메모리 크기의 극복 : 정책

빈 메모리 공간이 거의 없는 경우 운영체제는 메모리 압박을 해소하기 위해 다른 페이지들을 강제적으로 페이징 아웃(paging out)하여 활발히 사용 중인 페이지들을 위한 공간을 확보한다. 내보낼 페이지 선택은 운영체제의 교체 정책(replacement policy) 안에 집약되어 있다.

 

과거의 시스템들은 물리 메모리의 크기가 작았기 때문에 초기 가상 메모리 시스템의 가장 중요한 역할 중 하나가 교체 정책이었다. 다양한 교체 정책들을 통해 내보낼 페이지는 어떻게 결정하는지에 대해 알아보도록 하겠다. 

 

캐시 관리

정책에 대해 설명하기에 앞서서 해결하고자 하는 문제에 대해서 좀 더 상세히 알아보자. 전체 페이지들 중 일부만이 메인 메모리에 존재하는 경우, 메인 메모리는 시스템의 가상 메모리 페이지를 가져다 놓기 위한 캐시로 생각할 수 있다.

 

이 캐시를 위한 교체 정책의 목표는 캐시 미스의 횟수를 최소화하는 것이다. 즉, 디스크로부터 페이지를 가져오는 횟수를 최소로 만드는 것이다.(캐시 히트 횟수를 최대로 하는것) 

 

캐시 히트와 미스의 횟수를 안다면 프로그램의 평균 메모리 접근 시간(Average Memory Access Time, AMAT)을 계산할 수 있다. AMAT는 다음과 같은 식으로 계산할 수 있다.

 

T(M)은 메모리 접근 비용을 나타내고, T(D)는 디스크 접근 비용, P(Hit)는 캐시에서 데이터 항목을 찾을 확률(히트)을 나타내며, P(Miss)는 캐시에서 데이터를 못찾을 확률(미스)을 나타낸다. 둘은 각각 0.0에서 1.0사이의 값을 가지며 P(Miss) + P(Hit) = 1.0을 만족한다.

 

현대 시스템에서는 디스크 접근 비용이 너무 크기 때문에 아주 작은 미스가 발생하더라도 전체적인 AMAT에 큰 영향을 주게 된다. 그렇기 때문에 느리게 실행되는 것을 방지하기 위해서는 당연히 미스를 최대한 줄여야 한다. (즉, 좋은 정책이 필요하다)

 

최적 교체 정책

교체 정책의 동작 방식을 잘 이해하기 위해서 최적 교체 정책과 비교하는 것이 좋다. 최적 교체 정책은 미스를 최소화한다. 이 정책을 통해 가장 나중에 접근될 페이지를 교체하는 것이 최적이며, 가장 적은 횟수의 미스를 발생시킨다는 것을 증명하였다. 정책은 간단하지만 구현은 어려운 정책이다.

 

간단한 예제를 통해 최적 기법의 동작을 살펴보자. 프로그램이 0, 1, 2, 0, 1, 3, 0, 3, 1, 2, 1의 순서대로 가상 페이지들을 접근한다고 하자. 캐시에 세 개의 페이지를 저장할 수 있다고 가정하면 다음 그림은 최적의 기법 동작을 보여준다.

 

캐시는 처음에 비어 있는 상태로 시작하기 때문에 첫 세 번의 접근은 당연히 미스이다. 이런 종류의 미스는 최초 시작 미스 또는 강제 미스라고 한다. 그 다음 페이지 0과 1을 참조하면 캐시에서 히트된다. 페이지 3에서 미스를 만나게 된다. 그렇지만 이때는 캐시가 가득 차있기 때문에 교체 정책이 실행되어야 한다! 

 

이때 다음과 같은 질문이 나온다. 어떤 페이지를 교체해야 하는가? 최적 기법의 경우 캐시에 현재 탑재되어 있는 각 페이지(0, 1, 2)들의 미래를 살펴본다. 그러면 0은 거의 즉시 접근 될 것이고 1은 약간 후, 그리고 2는 가장 먼 미래에 접근이 될 것이라고 알 수 있다. 그러므로 최적 기법은 페이지 2를 내보내고 결과적으로 캐시에는 페이지 0, 1, 3이 남게 된다. 그 후 세번의 참조는 히트된다. 그리고 오래 전에 내보냈던 페이지 2를 만나서 또 한 번 미스가 난다. 여기서 최적 기법은 다시 캐시 내의 각 페이지들(0, 1, 3)의 미래를 검사한다. 그리고 페이지 3을 내보냈다. 최종적으로 페이지 1이 히트되고 종료된다.

 

캐시 히트율을 계산할 수 있다. 캐시 히트가 6번 미스가 5번이었으므로 히트율은 6 / (6 + 5) = 54.5%가 된다. 강제 미스들을 제외한 히트율로는 85.7%의 히트율을 얻는다.

 

불행하게도 미래는 일반적으로 미리 알 수 없다.(CPU가상화때 언급을 했었다) 그렇기 때문에 범용 운영체제에서는 최적 기법의 구현은 불가능하다. 결국은 실제적이고 배포가 가능한 정책을 만들기 위해 다른 방법을 찾는데에 집중할 것이다. 이 최적 기법은 그저 비교 기준으로만 사용될 것이며, 이를 통해 얼마나 "정답"에 가까운지 알 수 있을 것이다.

 

간단한 정책 : FIFO

일부 시스템에서는 FIFO(선입선출, 먼저 들어온 것이 먼저 나감) 교체 방식을 사용하였다. 시스템에 페이지가 들어오면 큐에 삽입되고, 교체를 해야 하는 경우 큐에 먼저 들어온 페이지가 내보내진다. FIFO는 매우 구현하기 쉽다는 장점을 가진다.

 

FIFO가 어떻게 동작하는지 살펴보자. 처음에는 역시 페이지 0, 1, 2에 대한 강제 미스로 시작한다. 이후에 페이지 0, 1은 히트되고 3에서 미스를 일으킨다. FIFO 특성상 "첫 번째"로 들어온 페이지인 0을 선택한다. 불행하게도 다음 접근은 페이지 0이라서 또 다른 미스를 만들어내고 교체가 필요하다. 그 후에는 페이지 3에서 히트가 되지만 1과 2는 미스가 되며, 끝으로 3은 히트된다.

 

최적의 경우와 비교하면 FIFO는 눈에 띄게 성능이 안 좋다. 히트율은 36.4%가 된다.(강제미스 제외시 57.1%) FIFO는 블럭들의 중요도를 판단할 수가 없다. 

 

BELADY의 역설

BELADY의 역설은 할당된 물리 프레임수가 커질수록 페이지 적중률이 올라갈 것 같지만, FIFO에 의해 오히려 떨어지는 현상을 말한다.

 

또 다른 간단한 정책 : 무작위 선택

또 다른 교체 정책은 무작위 방식이다. 이 방식은 메모리 압박시 페이지를 무작위로 선택하여 교체한다. 이 역시 구현은 쉽지만 내보낼 블럭을 제대로 선택하지 않는다.

 

물론 무작위 선택 정책은 선택할 때 얼마나 운이 좋은지에 전적으로 의존한다. 위에서 사용한 FIFO 보다 약간 더 좋은 성능을 보일수도 혹은 더 나쁜 성능을 보일수도 있다. 무작위 선택 정책이 어떻게 동작하는지 살펴보자.

 

일반적인 성능을 알아보기 위해 실험을 수천 번 반복해 볼 수 있다. 다음 그림은 서로 다른 랜덤 시드를 가지는 실험을 만 번 수행했을 때 무작위 선택 방식이 몇 번의 히트를 얻었는지를 나타낸다.

 

어떤 때는 무작위 선택 방식이 최적 기법만큼 좋은 성능을 보이며, 때로는 매우 안 좋은 성능을 인다. 즉 무작위 선택 방식은 그때그때에 따라 달라진다.

 

과거 정보의 사용 : LRU

불행히도 FIFO 또는 무작위 선택 방식처럼 단순한 정책들은 다시 참조하게 될 페이지들을 내보낼 수 있다는 문제를 겪게 된다. 이는 최적 기법의 성능을 따라갈 수가 없기 때문에 좀 더 정교한 방식이 필요하다.

 

미래에 대한 예측을 위해 과거 사용 이력을 활용해보자. 예를 들어 어떤 프로그램이 가까운 과거에 한 페이지를 접근했다면 가까운 미래에 그 페이지를 다시 접근할 확률이 높다.

 

페이지 교체 정책이 활용할 수 있는 과거 정보 중 하나는 빈도수(frequency)이다. 한 페이지가 여러 차례 접근되었다면, 분명히 어떤 가치가 있기 때문에 교체되면 안될 것이다. 좀 더 자주 사용되는 페이지 특징은 접근의 최근성(recency)이다. 더 최근에 접근된 페이지일수록 가까운 미래에 접근될 확률이 높을 것이다.

 

이런 류의 정책은 지역성의 원칙(principle of locality)라 불리는 특성에 기반을 둔다. 이 원칙은 프로그램의 행동 양식을 관찰하여 얻은 결과이다. 이 원칙이 말하는 것은 단순하다. 프로그램들은 특정 코드들과 자료 구조를 상당히 빈번하게 접근하는 경향이 있다는 것이다. 예를 들면 반복문 코드와 그 반복문에 의해 접근되는 배열이라고 할 수 있다. 과거의 현상을 보고 어떤 페이지들이 중요한지 판단하고, 내보낼 페이지를 선택할 때 중요한 페이지들은 메모리에 보존하는 것이다.

 

그리하여 과거 이력에 기반한 교체 알고리즘 부류가 탄생하게 되었다.

 

 LRU가 어떻게 동작하는지 알아보자. 

 

그림을 보면 앞에 두 정책에 비해 LRU가 더 좋은 성능을 보임을 알 수 있다. 이 예제에서 LRU는 처음으로 페이지를 교체해야 할 때 페이지 2를 내보낸다. 왜냐하면 0과 1이 최근에 사용되었기 때문이다. 그 후 0을 교체한다. 1과 3이 더 최근에 접근되었기 때문이다. 두 경우 모두 과거 정보를 활용하였고, 그 결정이 옳았다는 것을 알 수 있다. LRU는 거의 최적 기능에 가까운 성능을 보여주고 있다.

 

워크로드에 따른 성능 비교

지금까지 살펴본 정책들을 더 잘 이해하기 위해 몇 가지 예를 살펴보자. 좀 더 복잡한 워크로드를 살펴볼 것이다. 

 

첫 번째 살펴볼 워크로드에서는 지역성이 없다. 즉, 접근되는 페이지들의 집합에서 페이지가 무작위적으로 참조된다는 것을 의미한다. 이 예제에서는 100개의 페이지들이 일정 시간 동안 계속 접근하는 워크로드를 사용한다. 접근되는 페이지는 무작위적으로 선택되며 페이지들이 총 10000번 접근된다. 캐시의 크기를 매우 작은 것부터 모든 페이지들을 담을 수 있을 크기까지 증가 시켰으며, 이를 통해 각 정책이 캐시 크기에 따라 어떻게 동작하는지 살펴보겠다.

 

그림에서는 최적의 방법과 LRU, 랜덤, 그리고 FIFO 방식을 사용하였을 때의 실험결과를 나타낸다. 그림의 y축은 히트율을, x축은 캐시 크기의 변화를 나타낸다.

 

그림에서 몇 가지 결론을 얻을 수 있다. 먼저, 워크로드에 지역성이 없다면 어느 정책을 사용하든 상관이 없다. LRU와 FIFO 그리고 무작위 선택 정책은 모두 동일한 성능을 보이며, 히트율은 정확히 캐시의 크기에 의해 결정된다. 두 번째로, 캐시가 충분히 커서 모든 워크로드를 다 포함할 수 있다면 역시 어느 정책을 사용하든지 상관없다. 참조되는 모든 블럭들이 캐시에 들어갈 수 있다면 모든 정책들은 히트율 100%에 도달한다. 마지막으로, 최적 기법이 구현 가능한 정책들보다 눈에 띄게 더 좋은 성능을 보인다. 미래를 알 수 있다면 교체 작업을 월등히 잘할 수 있게된다.

 

다음으로 살펴볼 워크로드는 "80대 20" 워크로드라고 부른다. 20% 페이지들에서 80%의 참조가 발생(즉, 인기있는 페이지)하고 나머지 80%의 페이지들에 대해서 20%의 참조만(즉, 인거없는 페이지) 발생한다. 위 예제와 마찬가지로 100개의 페이지들이 있다. 

 

그림에서 볼 수 있듯이 랜덤과 FIFO 정책이 상당히 좋은 성능을 보이지만, 인기 있는 페이지들을 캐시에 더 오래두는 경향이 있는 LRU가 더 좋은 성능을 보인다. 인기 있는 페이지들이 과거에 빈번히 참조되었기 때문에 그 페이지들은 가까운 미래에 다시 참조되는 경향이 있기 때문이다. 최적 기법은 여전히 좋은 성능을 보이고 있다. 이 말인 즉슨, LRU의 과거 정보가 완벽하지 않다는 것을 보여준다.

 

이런 의문이 들 수도 있다. 무작위 선택 방식과 FIFO 방식을 개선하여 만든 LRU가 그렇게 대단한 것인가? 이 질문의 대답은 "상황에 따라 다르다"이다. 미스로 인해 매우 비싼 값을 치러야 하는 경우 히트율이 약간만 증가하여도 성능에 큰 차이를 만들어낸다. 만약 미스로 인한 영향이 크지 않다면, LRU로 얻을 수 있는 장점은 별로 중요하지 않게된다.

 

마지막으로 하나의 워크로드를 더 살펴보자. 이 워크로드를 "순차 반복" 워크로드라고 부른다. 이 워크로드는 50개의 페이지들을 순차적으로 참조한다. 0 ~ 49번째 페이지까지 참조한 후에 처음으로 돌아가 접근 순서대로 다시 반복한다. 50개의 개별 페이지들을 총 10000번 접근한다. 

 

여러 응용 프로그램에서 흔히 볼 수 있는 이 워크로드는 LRU와 FIFO 정책에서 가장 안좋은 성능을 보인다. 순차 반복 워크로드에서 이 알고리즘들은 오래된 페이지들을 내보낸다. 워크로드의 반복적인 특성으로 오래된 페이지들은 정책들이 캐시에 유지하려고 선택한 페이지들보다 먼저 접근된다. 실제로, 캐시의 크기가 49라고 할지라도 50개의 페이지들을 순차 반복하는 워크로드에서는 캐시 히트율이 0%가 된다. 흥미롭게도 무작위 선택 정책은 눈에 띄게 좋은 성능을 보인다. 적어도 히트율이 0%는 아니다. 이렇게 무작위 선택 정책은 몇 가지 좋은 특성을 가지고 있다는 것을 알 수 있다. 그 중 하나가 이상한 코너 케이스가 발생하지 않는다는 것이다.

 

과거 이력 기반 알고리즘 구현

앞에서 봤듯이 FIFO, 무작위 정책보다는 LRU가 더 좋은 성능을 보인다. 하지만 과거 정보에 기반을 둔 알고리즘은 새로운 문제점이 있다. 이런 정책을 어떻게 구현할 것인가?

 

LRU를 예로 들어보자. 이를 완벽히 구현하기 위해선 많은 작업이 필요하다. 특히, 각 페이지 접근마다 해당 페이지가 리스트에 가장 앞으로 이동하도록 자료 구조를 갱신해야 한다. FIFO 방식과 비교해 보자. FIFO 리스트는 어떤 페이지의 제거 또는 새로운 페이지의 삽입 시에만 접근된다. LRU는 어떤 페이지가 가장 최근에 또는 오래 전에 사용되었는지를 관리하기 위해 모든 메모리 참조 정보를 기록해야 한다. 세심한 주의 없이 정보를 기록하면 성능이 크게 떨어질 수 있다.

 

이 작업을 좀 더 효율적으로 하는 방법은 하드웨어의 도움을 받는 것이다. 페이지 접근이 있을 때마다 하드웨어가 메모리의 시간 필요를 갱신하도록 할 수 있다. 이렇게 하여 페이지가 접근되면 하드웨어가 시간 필드를 현재 시간으로 설정한다. 페이지 교체 시에 운영체제는 가장 오래 전에 사용된 페이지를 찾기 위해 시간 필드를 검사한다.

 

페이지 수가 증가하면 페이지들의 시간 정보 배열을 검색하여 가장 오래전에 사용된 페이지를 찾는 것은 매우 고비용의 연산이다. 4GB 메모리를 가지는 현대의 기기에서 4KB 페이지들로 나눈 것을 상상해 보라. 그런 기계는 백만 개의 페이지들을 가지고 있다. LRU 정책의 교체 대상 페이지를 찾는 데 현대의 CPU 속도라 할지라도 오랜 시간이 걸린다. 다음과 같은 질문이 떠오른다. 과연 오래된 페이지를 꼭 찾아야만 할까? 비슷하게 오래된 페이지를 찾아도 되지 않을까?

 

LRU 정책 근사하기

LRU 정책에 가까운 구현이 불가능하지는 않다. 연산량이라는 관점에서 볼 때, LRU를 "근사"하는 식으로 만들면 구현이 훨씬 쉬워진다. 실제로 많은 현대의 시스템이 이런 방식을 택하고 있다. 이 개념에는 use bit라고 하는 약간의 하드웨어 지원이 필요하다. 시스템의 각 페이지마다 하나의 use bit가 있으며, 이 use bit는 메모리 어딘가에 존재한다. 페이지가 참조될 때마다 하드웨어에 의해 use bit가 1로 설정된다. 하드웨어는 이 비트를 절대로 지우지 않는다.(즉, 0으로 설정하지 않는다) 0으로 바꾸는 것은 운영체제의 몫이다.

 

시계 알고리즘

운영체제는 LRU에 가깝게 구현하기 위해 use bit를 어떻게 활용할까? 간단한 활용법이 시계 알고리즘(clock algorithm)에 제시되었다. 시스템의 모든 페이지들이 환형(동그라미) 리스트를 구성한다고 가정하자. 시계 바늘이 특정 페이지를 가리킨다고 해 보자. 페이지를 교체해야 할 때 운영체제는 현재 바늘이 가리키고 있는 페이지 P의 use bit가 1인지 0인지 검사한다. 만약 1일 경우 페이지 P는 최근에 사용되었으며 바람직한 교체 대상이 아니라는 것을 뜻한다. P의 use bit는 0으로 설정되고 시계 바늘은 다음 페이지 P + 1로 이동한다. 알고리즘은 use bit가 0으로 설정되어 있는 페이지를 찾을 때까지 반복된다. (모든 페이지를 사용한 적이 있어서 모든 페이지들의 use bit를 전부 0으로 설정해야 할 수도 있다)

 

 

변형된 시계 알고리즘의 워크로드는 다음과 같다. 이 변형 방식은 교체할 때 페이지들을 랜덤하게 검사한다. use bit가 1로 설정되어 있는 페이지를 만나게 되면 비트를 지운다. use bit가 0으로 설정되어 있는 페이지를 만나면 그 페이지를 교체 대상으로 선정한다.

 

 완벽한 LRU 만큼 좋은 성능을 보이지는 않지만 과거 정보를 고려하지 않는 다른 기법들에 비해 성능이 더 좋다는 것을 알 수 있다.

 

갱신된 페이지(dirty bit)의 고려

여기서는 시계 알고리즘에 대한 추가 개선 사항을 논의한다. 운영체제가 교체 대상을 선택할 때 메모리에 탑재된 이후에 변경되었는지를 추가적으로 고려한다. 이것이 필요한 이유는 다음과 같다.

 

만약 어떤 페이지가 변경(modified)되어 더티(dirty) 상태가 되었다면, 그 페이지를 내보내기 위해서는 디스크에 변경 내용을 기록해야 하기 때문에 비싼 비용을 지불해야 한다. 만약 변경되지 않았다면, 내보낼 때 추가 비용은 없다. 해당 페이지 프레임은 추가적인 I/O없이 다른 용도로 재사용 될 수 있다. 떄문에 더티 페이지 대신 꺠끗한 페이지를 내보내는 것을 선호한다.

 

이와 같은 동작을 지원하기 위해 하드웨어는 modified bit(= dirty bit)를 포함해야한다. 페이지가 변경될 때마다 이 비트가 1로 설정되므로 페이지 교체 알고리즘에서 이를 고려하여 교체 대상을 선택한다. 이로써 시계 알고리즘은 교체 대상을 선택할 때 사용되지 않은 상태(use bit = 0)이고 깨끗한 페이지(dirty bit = 0)를 먼저 찾도록 수정된다. 페이지 검색에 실패하면, 수정되었지만(dirty bit = 0) 한동안 사용되지 않았던 페이지를 찾는다.

 

다른 VM 정책들

페이지 교체 정책만이 VM 시스템에서 채택하는 유일한 정책은 아니다. 운영체제는 언제 페이지를 메모리로 불러들일지 결정해야 한다. 이 정책은 운영체제에게 몇 가지 다른 옵션을 제공한다. 이 정책은 때로 페이지 선택(page selection) 정책이라고 불린다.

 

선반입(prefetching)

운영체제는 대부분의 페이지를 읽어 들일때 요구 페이징 정책을 사용한다. 이 정책은 말 그대로 "요청된 후 즉시", 즉 페이지가 실제로 접근될 때 운영체제가 해당 페이지를 메모리로 읽어 들인다. 운영체제는 어떤 페이지가 곧 사용될 것이라는 것을 대략 예상할 수 있기 때문에 미리 메모리로 읽어 들일 수도 있다. 이와 같은 동작을 선반입(prefetching)이라고 한다. 이 동작은 성공할 확률이 충분히 높을 때에만 해야한다. 아래 그림을 보면 Page 1을 불러 들일때 그 옆에 있는 Page 2도 곧 사용될 것을 예상하고 같이 읽어 들인다.

 

 

클러스터링(clustering), 모으기(grouping)

또 다른 정책은 운영체제가 변경된 페이지를 디스크에 반영하는 데 관련된 방식이다. 한 번에 한 페이지씩 디스크에 쓸 수 있지만, 많은 시스템은 기록할 페이지들을 메모리에 모은 후, 한꺼번에 디스크에 기록한다. 이를 클러스터링(clustering) 또는 단순하게 모으기(grouping)라고 부르며 효과적인 동작 방식이다. 왜냐하면 디스크 드라이브는 여러 개의 작은 크기의 쓰기 요청을 처리하는 것보다 하나의 큰 쓰기 요청을 더 효율적으로 처리할 수 있는 특성을 가지고 있기 때문이다. 

 

 

쓰래싱(Thrashing)

메모리 사용 요구가 감당할 수 없을 만큼 많고 실행 중인 프로세스가 요구하는 메모리가 가용 물리 메모리 크기를 초과하는 경우에 운영체제는 어떻게 해야 할까? 이런 경우 시스템은 끊임없이 페이징을 할 수 밖에 없고, 이와 같은 상황을 쓰래싱(thrashing)이라고 부른다.

 

초기 운영체제들은 쓰래싱이 발생했을 때, 이의 발견과 해결을 위한 상당히 정교한 기법들을 가지고 있었다. 예를들어 다수의 프로세스가 존재할 때, 일부 프로세스의 실행을 중지시킨다. 실행되는 프로세스의 수를 줄여 나머지 프로세스를 모두 메모리에 탑재하여 실행하기 위해서다. 

워킹 셋(working set)이란 프로세스가 실행 중에 일정 시간 동안 사용하는 페이지들의 집합이다. 운영체제는 이 워킹 셋이 물리 메모리 크기에 맞도록 조정한다.