[OS] 메모리에서 교체할 Page를 결정하는 방법 - OS 공부 16

안녕하세요 Pingu입니다.

 

지난 글에 이어 이번 글에서는 메모리에 할당된 page들 중 어떤 page를 swap 공간으로 교체할 것인가에 대한 방법들과 여러 방법 중 어떤 방법으로 page를 교체하는 것이 효율적으로 paging 기법을 구현할 수 있을지에 대해 알아보려고 합니다! 제가 공부할 때 참고하고 있는 OSTEP 책에서는 Chapter 22 Swapping: Policies 부분입니다!

Beyond Physical Memory: Policies

만약 메모리의 크기가 너무 커서 이번 글에서 알아볼 page 교체를 하지 않아도 모든 프로세스를 수행할 수 있다면 지금부터 알아볼 것들이 모두 필요가 없겠지만... 안타깝게도 실제로는 메모리가 부족한 상황이 자주 발생하기 때문에 page 교체 정책이 필요합니다. 하지만 메모리에 존재하는 많은 page들 중 어떤 page를 교체해야 할까요? 아무렇게나 page를 교체하게 된다면 빈번한 page fault 발생으로 성능이 많이 저하될 수 있기 때문에 교체할 page를 결정하는 방법이 중요합니다! 따라서 이번 글에서는 여러 가지 page 교체 policy(정책)에 대해 알아보려고 합니다.

Cache Management

Page 교체 정책에 대해 알아보기 전에 일단 이러한 방법들로 어떤 문제를 해결할 것인지에 대해 먼저 살펴보겠습니다. 메모리는 모든 page의 정보를 담고 있다는 점에서 가상 메모리에 대한 일종의 cache(캐시)로 볼 수 있습니다. Page 교체 정책들의 목적은 cache miss를 최소화하는 것입니다. 이는 cache hit을 최대화하는 것과 동일한 의미로 어떤 page를 요청했을 때 page가 메모리에 존재할 때 cache hit 되었다고 합니다.

 

이러한 cache hit, miss의 수를 안다면 프로그램의 average memory access time(평균 메모리 접근 시간: AMAT)를 계산할 수 있습니다.

위와 같이 계산할 수 있습니다. 여기서 Phit + Pmiss = 1입니다. 메모리에 1회 접근하는 시간은 100nm이며 디스크에 1회 접근하는 시간은 10ms(10000000 ns)라고 가정하여 몇 가지 상황을 계산해보겠습니다.

위와 같이 Phit의 값을 증가시켜보며 계산을 해보면 속도 차이가 많이 나는 것을 볼 수 있습니다. Phit가 50% 일 때는 5ms나 걸리던 작업은 Phit가 99% 일 때는 0.1ms 만에 수행할 수 있는 것이죠. 따라서 Phit의 값을 높이는 page 교체 정책을 개발해서 이러한 성능 저하를 막아야 합니다. 이제 왜 page 교체 정책이 중요한지 느꼈을 거라고 생각하고 몇 가지 page 교체 정책을 살펴보도록 하겠습니다.

The Optimal Replacement Policy

가장 먼저 알아볼 교체 정책은 가장 최적의 교체 정책인 Belady가 만든 Optimal 정책입니다. 따라서 Optimal 정책은 전체적으로 가장 적은 miss가 발생하도록 합니다. 이는 교체를 해야 할 시점에 메모리에 존재하는 page 중 가장 나중에 사용될 page를 교체하는 방법입니다. 하지만 미래에 어떤 page가 요청되는지는 알 수 없기 때문에 이 방법은 이후에 알아볼 다른 방법들이 얼마나 Optimal 정책에 근접하게 동작하는지에 대한 비교대상으로 알아보려고 합니다. 그럼 간단하게 어떻게 동작하는지 예를 보며 이해해보겠습니다.

 

캐시, 즉 메모리에는 3개의 page가 최대 할당량이라고 할 때 어떤 프로그램이 0,1,2,0,1,3,0,3,1,2,1의 순서로 page를 요청한다고 가정해보겠습니다.

위와 같이 동작하게 됩니다. Optimal 정책에서는 위의 상황이 5/11의 miss율을 발생했습니다. 우선 간단히 과정을 설명하자면 처음 프로그램이 page를 요청할 때는 당연하게도 메모리에 아무런 정보가 없습니다. 따라서 처음 3번까지의 miss는 발생할 수밖에 없는 것이죠. 이러한 miss를 compulsory miss(강제 미스)라고 합니다. 이후에 발생하는 miss를 살펴보면 캐시에 0,1,2가 존재하는데 3번 page를 요청합니다. 따라서 page falut가 발생하여 page를 교체해야 하는 상황이죠. Optimal에서는 page fault가 발생한 시점에서 가장 나중에 사용되는 page를 교체합니다. 위의 예에서는 2번 page가 가장 나중에 사용되기 때문에 교체되게 됩니다. 그다음 발생하는 miss에서는 0,3 중에 아무거나 교체해도 되는데 랜덤 하게 3을 교체한 예입니다.

 

앞으로 위의 예제를 계속해서 사용할 텐데 가장 최적의 방법에서 5/11의 miss율을 나타낸 것을 기억하며 다른 방법들과의 차이를 살펴보면 좋을 것 같습니다.

A Simple Policy: FIFO

이번에 알아볼 page 교체 정책은 아주 간단한 방법인 FIFO(First In First Out)입니다. 말 그대로 가장 먼저 사용된 page를 miss가 발생했을 때 교체하겠다는 것이죠. 아까 살펴본 동일한 상황에서 FIFO가 어떻게 동작하는지 살펴보겠습니다.

강제 miss가 발생한 이후의 miss부터 살펴보면, 3번 page를 요청할 때 miss가 발생합니다. 그래서 당시 가장 먼저 들어온 page인 0번 page를 교체합니다. 이후에도 동일한 방법으로 교체를 진행하며 FIFO를 사용하면 miss 율이 7/11입니다. 아까 Optimal 정책은 5/11이었으니 나빠진 것을 볼 수 있습니다.

 

FIFO는 단순하게 구현할 수 있는 장점이 있지만 대부분의 경우 성능이 좋지 못합니다. 또한 일반적으로 캐시의 크기 즉 여기서는 메모리의 크기가 커지면 성능이 향상될 것으로 예상되지만 FIFO의 경우엔 더 나빠집니다.

Another Simple Policy Random

이번에 알아볼 page 교체 정책은 또 다른 단순한 방법인 Random입니다. 이름에서 알 수 있듯 캐시에 있는 아무 page나 바꿔버리겠다는 것이죠. 간단하게 아까의 예에 적용해보면 다음과 같습니다.

Random 방법으로 실행했을 때 miss 율은 6/11이 나오는군요. 근데 Random 방식은 다양한 결과가 발생할 수 있고 위의 경우는 그중 하나에 불과합니다. 즉 운이 좋으면 성능이 좋아지고 운이 나쁘면 성능이 나빠지는 것이죠.

Using History: LRU

이번에 알아볼 page 교체 정책은 Least Recently Used(LRU)입니다. 아까 Optimal은 미래를 보고 교체할 page를 정했다면 LRU는 과거를 보고 교체할 page를 선택합니다. 최근에 접근된 page는 곧 또 접근될 것이다!라는 것이 LRU의 아이디어입니다. 이는 locality(지역성)을 활용한 방법입니다.

 

간단하게 말하자면 LRU는 가장 과거에 사용한 page를 교체하자는 것입니다. 지금까지와 동일한 예를 LRU로 실행해보겠습니다.

우선 Miss율을 보면 5/11로 Optimal 정책과 동일합니다! 강제 Miss 이후의 첫 Miss인 3번 page를 요청한 부분을 보겠습니다. 해당 위치에서 가장 과거에 사용된 page는 2번입니다. 따라서 2번 page를 교체하게 됩니다. 여기서 하나 더 살펴볼 것은 cache의 상태입니다. 교체할 page는 cache의 맨 앞에 위치한 page이며 교체된 page는 cache의 마지막에 위치한 것을 볼 수 있습니다. 마지 queue와 같이 작동하는 것이죠.

Workload Examples

이번엔 지금까지 알아본 정책들이 어떤 상황에서 어떠한 성능을 보이는지 알아보도록 하겠습니다.

위의 workload에는 지역성이 없고 총 page 수가 100개일 때의 결과입니다. 즉 page의 요청이 랜덤 하게 발생할 때의 결과입니다. 위와 같이 지역성이 적용되지 않았을 경우에는 Optimal, LRU, FIFO, Random 방법의 결과가 크게 다르지 않습니다. 또한 캐시 크기가 총 page의 수인 100에 근접해지면 miss율이 0%에 수렴되는 것도 알 수 있습니다.

위의 Workload는 지역성이 있는 "80-20 workload"입니다. 이는 참조의 80%가 20%의 page에서 발생할 때를 가정한 것입니다. 위의 결과에서 볼 수 있듯 FIFO, Random보다 LRU가 지역성을 적용한 정책이므로 더 나은 결과를 보여주는 것을 알 수 있습니다. 지금까지의 결과만 본다면 Random, FIFO보다 LRU가 더 나은 게 맞나? 싶기도 합니다. 하지만 page fault를 처리하는 비용이 커지면 커질수록 조금의 개선도 큰 성능 향상으로 이어질 수 있습니다.

마지막으로 살펴볼 workload는 반복적으로 참조하는 것으로 0~49 page까지 순서대로 50개의 page를 참조하는 것을 반복하는 상황에서의 workload입니다. 당연하게도 캐시의 크기가 50을 넘어가게 되면 모든 정책에서 hit가 100%로 나타납니다. 하지만 캐시 크기가 50 미만일 때는 LRU, FIFO가 모두 최악의 경우인 hit율 0%를 보입니다. 이에 비해 Random은 어느 정도 성능이 나오는 것을 볼 수 있는데, 이것이 Random 방법의 장점으로 예외가 없다는 점입니다.

Implementing Historical Algorithms

지금 까지 알아본 FIFO, Random 방법은 LRU 방법과는 다르게 중요한 page라도 그냥 교체해버립니다. 하지만 단순함이 장점이죠. 그렇다면 LRU가 어떤 page를 교체할지 알아내는 비용이 커진다면 LRU방법이 더 좋다고 할 수도 없지 않을까요? 따라서 LRU 방법을 사용하기 위해서는 어떤 page를 교체할지 알아내는 비용을 최소화하는 방법으로 구현해야 합니다.

 

LRU에서 page에 접근할 때 해당 page를 목록의 맨 앞으로 이동시켜야 합니다. 즉 가장 최근에 사용되었다는 것을 추적하기 위해 이러한 작업을 해줘야 하는데, 이를 효율적으로 하기 위해서는 하드웨어의 지원을 받는 것이 좋습니다. 예를 들어 시스템은 page 접근에서 메모리의 시간 정보를 업데이트할 수 있습니다. 프로세스 별 페이지 테이블이나 메모리에 별도로 저장하여 시간 정보를 기록하여 가장 적게 사용된 page를 찾는 것입니다. 하지만 메모리의 크기가 커져서 page수가 너무 많아지면 LRU 페이지를 찾는데 소요되는 시간이 너무 커집니다.

Approximating LRU

따라서 최신 시스템에서는 완벽한 LRU를 사용하는 것이 아닌 LRU에 근사하게 만드는 것을 사용하고 있습니다. 이를 위해서는 하드웨어의 도움을 받아 use bit라는 것이 필요하게 됩니다. Page 하나당 use bit가 존재하며 page가 참조될 때마다 1로 업데이트됩니다.

 

그럼 이러한 use bit를 사용하여 어떻게 LRU를 구현할까요? 간단한 접근 법은 clock 방법입니다. 시스템의 모든 page가 시계처럼 원형 배열로 있다고 상상해보겠습니다. 시곗바늘이 이 원형 배열의 특정 page를 가리키게 됩니다. 교체가 발생할 때는 현재 가리키는 page의 use bit를 조회하여 1이라면 최근에 사용되었다고 판단하고 0으로 바꾼 뒤 다른 page를 찾습니다. 이러다 use bit가 0인 page를 찾으면 해당 page를 교체합니다.

Clock 알고리즘을 사용하면 실제 완벽한 LRU보다는 못하지만 거의 근사한 성능을 보여주는 것을 볼 수 있습니다.

Considering Dirty Pages

메모리에 page가 있는 동안 page가 수정되었는지에 대해서도 알아야 합니다. 수정된 page를 교체하려고 한다면 Disk에 다시 기록해야 해서 비용이 많이 들기 때문입니다. 수정되지 않은 page를 교체할 때는 I/O 없이 사용할 수 있지만 수정된 page는 그렇지 못합니다. 따라서 이를 알 수 있도록 하드웨어가 dirty bit를 지원합니다. Dirty bit는 page가 수정될 때마다 업데이트되어 page 교체 정책에 적용합니다. 이를 통해 교체 정책이 수행될 때 수정되지 않은 page를 먼저 교체하도록 만들어줍니다.

Other VM Policies

Page 교체는 VM 하위 시스템이 사용하는 유일한 정책은 아닙니다. OS는 page를 메모리로 가져올 시기도 결정해야 합니다. Page selection Policy라고도 하는 이러한 정책은 OS에 몇 가지 옵션을 제공합니다.

 

대부분의 page에서 OS는 demand paging(수요에 의한 페이징)을 사용합니다. 즉 프로세스가 page를 요청할 때 해당 페이지를 메모리로 로드하는 것이죠. 이와 다르게 OS가 page가 사용될 것이라고 예측하고 가져오는 것을 prefetching이라고 합니다.

 

또 다른 정책은 OS가 page를 Disk에 저장하는 방법을 결정합니다. 한 번에 하나씩 작성할 수도 있지만 이렇게 하는 것은 비효율적이므로 후에 배울 delayed write(지연 쓰기)를 통해 page에 대한 정보를 어느 정도 모아 한 번에 disk에 저장합니다.

Thrashing

이번에는 한 가지 상황을 생각해보겠습니다. 만약 실행 중인 프로세스들이 요구하는 메모리의 크기가 실제 메모리의 크기보다 큰 경우에 OS는 어떻게 처리할까요? 이 경우 시스템은 계속해서 page fault를 발생 시키며 이를 thrashing이라고 합니다.

 

현재 시스템 중 일부는 메모리 과부하에 대해 엄격하게 처리합니다. 예를 들어 일부 Linux 버전은 메모리가 과도하게 사용된다면 out of memory killer를 실행하여 메모리 집약적인 프로세스를 선택하여 종료시킵니다. 이렇게 하면 메모리 부족은 해결할 수 있지만 중요한 프로세스를 강제 종료하게 되면 큰 문제가 발생할 수 있는 문제점이 있습니다.

Summary

이번 글에서는 모든 OS의 VM 하위 시스템의 일부인 page 교체 정책에 대해 알아봤습니다. LRU는 루프 워크로드에서 최악의 경우로 동작하므로 이를 방지하기 위해서 실제로 사용되는 정책들은 Clock 알고리즘과 같은 LRU에 근사한 결과를 보이는 방법들이었습니다. 이번 글을 끝으로 메모리 가상화에 대하여 알아봤습니다. 다음 글에서부터는 Concurrency(동시성), 즉 여러 개의 프로그램을 동시에 동작하도록 하는 방법에 대해 알아보도록 하겠습니다!

 

감사합니다.