Memory Management 4: Page Replacement

Swapping

  Swapping은 프로세스가 실행되어야 하는데 physical memory가 충분하지 않을 때, 현재 쓰이지 않는 것들을 스토리지(HDD, SSD, ...)에 옮겨놓은 뒤에 거기에 필요한 데이터를 로드하는 것이다. 당연히 이후에 스토리지에 저장되었던 것을 다시 불러오는 과정이 필요하다.

  다르게 말하면 physical memory가 스토리지의 캐시역할을 한다고 생각하면 된다. 기존의 프로그램이 디스크에 위치하고 이것이 실행되면 메모리로 로드가 된다. 이때 사용되는 방법이 이전에 다뤘던 demanding paging이었다. 프로세스가 실행되는 순간에는 전체 주소 공간 중 극히 일부만이(page 단위로) 사용되기 때문에 한번에 모든 주소 공간을 다 가져올 필요가 없다. 그렇기 때문에 나머지는 스토리지에 저장했다가 이후에 불러오면 프로세스를 실행하는데는 문제가 없는 것이다.

How to Swap

  그렇다면 이러한 swapping을 어떻게 할 수 있을까? 다음과 같은 3가지 방법을 생각해볼 수 있다.

• Overlays: 프로그래머가 직접 필요한 코드나 데이터를 가져오고 내보내는 과정을 구현하는 것. 그렇기에 OS의 도움이 필요하지 않지만 메모리의 현황을 일일이 파악해야하므로 구현이 어렵다.
• Process-level swapping: 하나의 프로세스 전체를 기준으로 swap을 하는 것이다. 즉 프로세스 단위로 스토리지로 이동했다가 이후 필요할 때 메모리로 돌아온다. 하지만 이때 프로세스의 모든 page가 로드되어야 하므로 오버헤드가 큰 편이다.
• Page-level swapping: page 단위로 swap이 발생하는 것이다. 현재 실행하는데 필요한 page만 메모리에 넣어두고 나머지는 스토리지에 위치시킨다.

Where to Swap

  그렇다면 이러한 swap이 어느 공간에서 일어나는걸까? 스토리지의 일부 공간(swap space)을 예약해놓고 거기에 page들이 왔다갔다하게 하는 방법이 있다. 그리고 이러한 공간의 크기는 경우마다 다르겠지만 보통 메모리의 크기와 비슷하게 설정한다고 한다. 물론 더 커질 수도 있겠지만 그것은 많은 프로세스들의 page들이 스토리지를 왔다갔다 한다는 것이고 이는 비용이 많이드는 과정이기 때문에 이때는 윗단에서 load balacing을 하거나 메모리를 늘리는 식으로 해결해야 한다.

  그리고 스토리지의 swap space는 block이라는 단위로 다뤄지는데 이는 page와 같은 크기이므로 동일하게 생각하면 된다. 

fig 1

  fig 1을 보면 메모리에는 3개의 프로세스에 대한 page들이 파편적으로 존재한다. 사용되고 있는 page(block)들은 physical memory에 올라와있는 상태이고 사용되지 않는 블럭들은 swap space에 위치하고 있다. 이러다가 만약 PID 0의 VPN 1의 page를 필요로 한다면 이 block을 phyiscal memory로 불러오거나 사용되지 않는 다른 page를 swap space의 free 항목으로 내리고 그 자리를 차지할 수 도 있다.

  만약 VM에서 PID 2(VPN 1)에 접근하고자 한다면 어떤 일이 발생할까? 해당 page에 접근하면 이에 해당하는 physical address가 있어야 한다. 하지만 해당 page가 메모리가 아닌 swap space에 있다면 우선은 page fault를 발생시킬 것이다. 이에 대한 헨들링으로 OS가 접근하려는 page를 메모리에 올려놓은 뒤에 page table을 갱신한다.

When to Swap

  이러한 swap은 당연히 메모리가 부족할 때 발생한다. 하지만 부족해진 순간 swap을 해주는 것은 사실 늦은 조치이다. 왜냐하면 swap하기 위해서는 어떤 것을 스토리지로 쫓아내야 하는데(swap out) 이것을 선정한 뒤에 스토리지에 쓰는 시간도 있고, 스토리지에서 메모리에 로드할(swap in) page를 들고오는 시간도 있기 때문이다. 그러므로 어떠한 기준을 두고 swap을 수행하는 것이 좋을 것 같다. 

  우선 OS가 메모리의 작은 부분을 free 상태로 두고 high(HW), low(LW)라는 두개의 threshold 값을 설정한다. 이것을 기준으로 메모리가 일정 이상 채워지기 시작하면 이때 swap을 해야하는 것으로 인지하는 것이다. 만약 free page의 수가 LW보다 적다면 physical memory에 있는 페이지들을 쫓아내야 한다는 것이고 이러다 보면 사용가능한 메모리 공간이 점점 늘어날 것이다. 이것이 HW이상 커진다면 이제 더 이상 swap을 할 필요가 없다.

  이러한 메모리를 free하게 해주는 작업은 OS에 있는 swap daemon(or page daemon)이 수행한다. 리눅스에서는 kswapd라는 서비스가 이를 수행한다.

  만약에 메모리를 요청(할당)하는 속도가 메모리를 비우는 속도보다 빠르다면 어떻게 될까? 일단 메모리가 부족해지니 page fault가 자주 발생할 것이다. 그렇게 되면 시스템은 page를 자주 올렸다 내렸다 하는 작업만 수행하게 되고 그러다가 'out of memory' 오류가 발생하게 된다. 이것에 대해서는 뒤에서 다시 알아보쟈.

What to Swap

fig 2

  그렇다면 swap을 해야하는 대상은 무엇일까? 우선 커널에서 사용하는 코드나 데이터, 커널/사용자 프로세스(and 스레드)에 대한 page table은 swap의 대상으로 삼지 않는다. 커널 같은걸 실행하려고 할 때 이것이 page out되어 있으면 커널이 실행되는데 많은 시간이 걸리고 특정 코드나 page table은 연속적으로 위치해야 하기 때문에 swap을 하면 안된다.

  반면 사용자 코드/데이터는 swap되거나 drop되기도 한다. 사용자 코드 같은 경우에는 애초에 스토리지에 위치하기 때문에 동일한 내용을 굳이 swap하여 내릴 필요는 없기 때문이다. 반면 데이터는 불러오고 난 뒤 update 되지 않으면 버려도 되지만 그렇지 않을 경우에는 swap을 해야한다. page의 update 여부는 PTE의 modify bit(dirty bit)를 이용해 알 수 있다.

  그리고 사용자 힙/스택은 프로그램이 실행되면서 동적으로 만들어지기 때문에 swap을 해줘야 한다. 그리고 아직 다루지는 않았지만 프로세스와 맵핑된 파일, page cache(사용된 파일의 내용을 저장해 놓는 곳 read나 open시 속도에 이점) pages는 drop하거나 파일시스템에 접근하여 파일을 수정한다.

  이제 어떤 page를 쫓아낼지(evict) 결정하는 page replacement policy에 대해 알아보자.

 

Page Replacement

fig 3

  page replacement는 (1)내릴 page(victim)를 스토리지에 내려놓고, (2)이 page에 대한 PTE의 valid bit를 'invalid'로 바꿔준다. (3)그 다음 새로운 page를 메모리에 가지고 온 뒤, (4)이것에 대해서 PTE의 valid bit를 'valid'로 설정해준다.

  victim이 선정되었을 때 여기에 dirty bit가 설정되어 있다면 이것은 스토리지로 내려야 하고, 그렇지 않다면 해당 데이터가 스토리지나 swap space에 있다는 뜻이니깐 그냥 버리면 된다. 어쨌든 이후 스토리지의 block을 메모리에 올리게 되는데, 여기서는 CPU cache의 direct-mapped, set-associative는 사용하지 않는다. 그 이유가 뭘까?

  cpu에서 fully-associative를 사용하게 되면 찾고자하는 데이터가 어디있는지에 대한 정보가 없기 때문에 cache를 모두 확인해봐야한다. 하지만 page의 경우에는 어디에 위치했는지에 대한 정보를 page table이 알고 있다. 그렇기 때문에 메모리에 page를 위치시킬 때는 fully associative를 사용해도 바로 찾을 수 있다. 다시 말하지만 page table이 있기 때문에 어느 곳에 위치하든 바로 찾아낼 수 있기 때문이다.

  이렇게 page replacement가 발생하는데 어떤 page를 swap하거나 버릴건지에 대한 policy의 목표는 page fault를 최소화하는 것이다. 왜냐하면 page fault가 발생하여 스토리지에 접근하는 cost가 메모리를 접근하는 cost보다 훨씬 크기 때문이다. 이렇한 miss rate를 줄이는 방법엔 어떤게 있을까?

fig 4

  우선 가장 쉽게 miss rate를 줄이는 방법은 메모리의 크기를 늘리는 것이다. fig 4를 보면 frame의 수가 증가할 수록 page fault가 일어나는 횟수가 눈에 띄게 줄어드는 것을 볼 수 있다. 하지만 우리가 생각해봐야 할 것은 주어진 frame 내에서 어떻게 page fault를 줄일지 생각해봐야 한다.

FIFO

  가장 단순한 방법은 메모리에 올라온 시간이 가장 긴 page부터 victim으로 선정하는 방법이다. 올라온지 가장 오래된 page가 이제는 잘 사용되지 않을 확률이 높을 것이라는 생각에 기인한 것이다. 하지만 어떤 page들은 항상 필요로 하기 때문에 간단하고 이상적으로 보일 수 있지만 최적의 방법은 아님을 알 수 있다.

fig 5

  fig 5에서 reference string은 다음과 같은 번호의 page들을 참조할 것이라는 뜻이다. 메모리는 3개의 frame으로 이루어진 상황이다. 이때 reference string의 순서로 참조하게 되면 15번의 page fault가 발생한다. 3번째까지는 단순히 free한 공간에 page들을 가져오기만 하면 되고, 이후에는 page fault마다 replacement가 발생한다. 이때 가장 오랫동안 있던 page가 victim으로 선정되는 걸 확인할 수 있다.

  여기서 만약 reference string이 '1 2 3 4 1 2 5 1 2 3 4 5'로 이뤄져있을 때 frame의 수가 3개일 때와 4개일 때의 page fault수의 차이를 구해보자. 당연히 4개일 때 page fault가 더 적게 일어날 것이라 생각했지만 막상 해보면 3개일 때는 9번, 4개일 때는 10번의 page fault가 발생한다. 이것은 좀전에 'frame 수가 늘어날 수록 page fault가 감소한다'라는 말과 반대되는 상황이다.

fig 5

  이것을 Belady's Anomaly라고 하는데, 몇몇 replacement 알고리즘은 frame 수를 늘렸음에도 fault rate가 증가하는 현상이다. FIFO도 여기에 해당하는 것이다.

Optimal case

fig 6

  그럼 가장 이상적인 page replacement policy는 무엇일까? 당연히 앞으로 사용될 page와 오랫동안 사용되지 않을 page들에 대한 정보를 알고 victim을 선정하는 것이다. 하지만 미래를 정확히 예측할 수 없으므로 이것은 말그대로 이상적인 case일 뿐이다. 하지만 이것을 기준으로 다른 policy들이 얼마나 효율적인지를 판단할 수는 있다.

LRU (Least Recently Used)

fig 7

  이 방법은 가장 오랫동안 사용되지 않은 page를 victim으로 선정하는 방법이다. 위의 optimal case 처럼 미래를 예측할 순 없지만 과거의 정보를 기준으로 오랫동안 사용되지 않는 page가 앞으로도 사용되지 않을 것이라는 locality에 기반한 방법이다. 이를 위해 각각의 page마다 가장 최근에 사용되었던 시간을 기록할 필요가 있다. 이 방법은 일반적으로 FIFO보다는 좋고 Opitmal case보다는 나쁜 fault rate를 가지고 보편적으로 좋은 알고리즘으로 여러 곳에서 많이 사용된다.

  여기서 생각해봐야 할 것은 이것을 '어떻게 구현해야 하는지'이다.

Counter implementatioin

  이 방법은 각각의 page entry들이 counter를 가져서 여기에 clock 정보를 넣는 것이다. 예를 들어 clock이 시작되고 0, 1, 2, ... 이렇게 흘러가는데 '2'에서 사용된 page에는 2가, '5'에서 사용된 페이지에는 5가 기록되는 것이다. 이후 replacement가 일어날 때 가장 작은 값을 가진 page를 선택하면 된다. 이 방법은 간단하긴 하지만 page들의 counter의 값을 탐색하는데 소요가 발생한다

Stack implementation

fig 8

  이 방법은 새로운 page가 들어오면 stack(double link로 구성)의 top으로 올리다가 기존 page가 update되면 이 page를 stack의 top으로 옮기는 것이다. 이렇게 되면 자연스레 잘 사용되지 않는 page들은 스택의 밑에 위치하게 된다. 이것은 정확한 LRU는 아닌 근사적인 LRU이긴 하지만 따로 탐색의 과정이 없기 때문에 이것에 이점이 있다.

SW/HW approach

  이러한 LRU를 구현할 때 reference time을 page frame에 기록하고 이를 정렬하면 어떤 것을 victim으로 할지 쉽게 알 수 있지만 SW적으로 구현하려면 메모리 참조가 일어날 때마다, OS가 개입이 되어야 한다. 이것은 오버헤드가 너무 큰 작업이다. 그래서 이러한 방법은 사용되지 않는다.

  그렇기 때문에 HW적으로 구현이 되는데, 각각의 page frame마다 timestamp를 기록해놓고 HW가 이러한 정보를 instruction을 실행할 때마다 넣어준다고 생각하면 된다. 메모리 참조 시 발생하는 소요는 HW가 처리해서 괜찮지만 replacement시 탐색이 필요하므로 메모리 크기가 커질수록 replacement는 느려진다.

LRU Approximation

  LRU를 정확하게 구현하기 위해서는 접근할 때마다 이 정보를 기록하고 이후 이를 바탕으로 누가 가장 오랫동안 접근되지 않았는지 파악해야 한다. 이런 LRU를 완벽하게 구현하기에는 복잡성이 크기 때문에 approximate한 방법을 사용한다. 이를 위해 HW적으로 각각의 page마다 reference bit를 사용한다.

  처음에는 각각의 reference bit가 OS에 의해 '0'으로 설정되어 있다가 특정 interval 이후에 reference bit를 확인하면 '1'로 바뀔 수 있다.  이것은 HW에 의해서 reference bit가 0에서 1로 설정된 것이고 이것으로 해당 page가 접근되었다는 것을 알 수 있다. 그러므로 이 방법은 정확한 LRU는 아니지만 특정 구간에 이 page가 접근되었는지를 판단하면서 '이 구간에서 접근되지 않은 page들은 앞으로도 접근되지 않을 확률이 높다'라고 판단하는 것이다.

Clock

fig 9

  위와 같은 LRU Approximation을 구현하기 위한 방법으로는 clock이라는 기법의 알고리즘이 있다. 각각의 PTE마다 있는 reference bit를 활용한다. fig 9처럼 A~L까지의 page를 하나의 큰 원 형태로 정리한 다음에 clock hand가 victim을 고른다. 이후의 과정은 다음과 같다.

• page fault가 발생하면, 현재 clock hand가 가리키고 있는 page가 확인된다. 
• 만약 해당 page의 reference bit가 1이었다면, 이 page는 interval안에 접근이 되었다는 것을 의미한다. 그렇기 때문에 reference bit를 0으로 변경한 뒤에 clock hand는 다음 page로 접근한다.
• 위와 같은 과정을 계속하다가 page의 reference bit가 0인 page를 만나면 해당 page를 evict한다.

  만약 자주 접근되는 page라면, 이 page는 HW에 의해 계속해서 reference bit가 1이므로, evict되지 않을 것이다. 그렇지 않고 reference bit가 clock에 의해 1에서 0으로 바뀐 뒤에 접근되지 않는다면 이 page는 해당 interval 이후에 victim으로 선정될 수 있을 것이다.

 

Physical Memory Allocation Polices

 이번에는 physical memory를 할당하는 policy에 대해 알아보자. policy에는 Fixed-space allocation policy와 Variable-space allocaiton policy가 있다.

  fixed-space policy는 각각의 프로세스마다 사용할 수 있는 page frame의 limit을 설정하는 것이다. 그러다가 사용되는 page frame들이 limit에 도달한다면 자신의 page frame들끼리 replace가 일어난다. local replacement라고 부르기도 하는데, VM 같은데서는 적절하지만, 대부분의 프로세스에는 적절치 못한 방법이다.

  그래서 variable-space allocation policy가 많이 사용된다. 이 방법은 위와 다르게 프로세스의 data frame들이 필요에 따라 증가하거나 감소할 수 있는 것이다. 즉 하나의 프로세스가 전체 메모리 공간을 모두 사용할 수도 있고 여러개의 프로세스가 비슷하게 메모리 공간을 차지할 수도 있다. 그래서 이 방법은 global replacement라고도 불린다. 

 

Thrashing

  Thrashing이란 physical memory가 모든 프로세스의 working sets을 돌리기에 충분하지 않은 것이다. 여기서 working set이라는 것은 현재 각 프로세스의 address space에서 active하게 사용되는 page들이다. 다르게 말하면 각 프로세스들이 현재 많이 접근하고 필요로 하는 메모리 영역이 있고 이들의 합이 working set이라고 할 수 있다.

  그렇다면 이러한 working set이 physical memory보다 크다면 어떤 일이 발생할까? working set을 한번에 수용하지 못하므로 매우 빈번하게 swapping이 발생한다. 그래서 프로세스를 실행하지 못하고 대부분의 시간을 swapping에 할해하므로 우리가 흔히 말하는 '렉'처럼 컴퓨터가 버벅거리게 된다.

fig 10

  원래는 multiprogramming의 degree가 올라갈수록, 즉 한번에 많은 프로세스들을 실행시키려 할수록 어떤 프로세스가 CPU를 사용하지 않을 때 다른 프로세스가 CPU를 사용하면서 CPU utilization이 상승하지만 어느 순간 이것이 급격하게 감소한다. 이것은 thrashing이 발생하여 결국 CPU가 swapping에 많은 시간을 소요하기 때문이다.

  이것을 해결하기 위해서는 결국에는 어떤 프로세스를 kill하거나 메모리의 크기 자체를 늘려주는 방법을 사용해야 한다.

Demand Paging and Thrashing

fig 11

  fig 11에서 x축은 시간, y축은 메모리 주소를 의미한다. 빨간 원을 살펴보면, 주어진 시간동안 특정 구역을 계속해서 접근하거나(temporal locality), 특정 구역을 반복해서 접근하는(spartial locality) 모습을 볼 수 있다.

  정리를 해보자. 우선 왜 demading paging이 동작할 수 있을까? demanding paging은 필요로 하는 메모리 영역에 대해서만 메모리에 올려놓고 연산을 시작하게 한다. 이것은 위에서 살펴본 것 처럼 locality가 존재하기 때문에 잘 동작할 수 있는 것이다.

  그리고 thrashing이 발생하는 조건을 'locality의 크기 > 전체 메모리 크기'이라고 할 수도 있다. 이렇게 되는 것을 막기 위해 local or priority page replacement를 사용할 수도 있다.

Working-Set Model

  그런데 working set의 크기 즉 locality의 크기를 정확히 얼마만큼이라고 정의할 수는 없다. 얼마만큼의 시간동안 얼마만큼 접근될 때의 page를 working set에 포함할지는 주관적이기 때문이다. 그렇기 때문에 working set에 대한 정의는 사용되는 시스템에 따라 유동적으로 바뀔 수 있다.

fig 12

  예를 들어 10,000개의 instruction을 수행하는 동안 얼마나 어떠한 page들이 접근되었나로 따질 수 있다. fig 12에서는 특정 working-set window(\(\Delta\)) 동안 접근되는 page들을 working set에 포함시키는 것을 확인할 수 있다.

Page-Fault Frequency

fig 13

  Working set 개념이외에도 직접적으로 시스템의 상황을 알 수 있는 개념인 page-fault frequency가 있다. page-fault frequency rate를 살펴보는데, 만약 현재 해당 rate가 매우 낮다는 것은 page fault가 적게 발생하고 현재 프로세스가 매우 많은 frame을 가지고 있다는 상황이므로 일부 frame을 반납하게 할 수 있다. 반면 해당 rate가 매우 높다는 것은 page fault가 빈번하게 발생하고 있는 상황이므로, 이 프로세스가 더 많은 메모리를 필요로 하므로 frame을 더 가져와야 한다.

---

• Operating System Concepts, Avi Silberschatz et al.
• Operating Systems: Three Easy Pieces
  • Remzi H.Arpaci-Dusseau andAndreaC.Arpaci-Dusseau
  • Available(withseveraloptions)athttp://ostep.org