Virtual Memory
이화여자대학교 반효경 교수님의 2014년 Operating System 강의를 시청한 후 정리한 내용이다.
http://kocw.net/home/cview.do?cid=3646706b4347ef09
운영체제
운영체제는 컴퓨터 하드웨어 바로 위에 설치되는 소프트웨어 계층으로서 모든 컴퓨터 시스템의 필수적인 부분이다. 본 강좌에서는 이와 같은 운영체제의 개념과 역할, 운영체제를 구성하는 각
www.kocw.net
Demand Paging
Demand Paging(요구 페이징)은 프로세스 실행 중 필요한 페이지를 물리 메모리로 올리는 것을 말한다. 요구 페이징은 프로세스가 실제로 필요한 페이지만 올리므로 물리 메모리를 비교적 적게 사용할 수 있고, 여유 메모리 공간이 확보되므로 더 많은 프로그램을 동시에 실행시켜 multi-programming degree를 증가시킬 수 있다. 또한 대부분의 프로그램이 실행하는 코드는 일부이므로, 필요할 때마다 페이지를 올리기 위해 반복적으로 swapping하는 동작이 줄어 I/O 빈도가 감소하고, 이에 따라 프로그램의 응답 속도도 빨라진다.
Page Fault
주소 변환 시, 해당 page의 물리 메모리 상의 frame을 찾기 위해 page table을 사용한다. table에는 valid/invalid bit이 있는데, 페이지 (논리 주소) 영역이 사용되지 않거나 frame이 물리 메모리에 없으면 invalid bit으로 설정된다. 그리고 table이 생성되는 시점에는 모든 entry에 invalid bit로 초기화되고, page들을 올리면서 valid bit으로 설정한다.
만약 CPU가 특정 논리 주소에 접근하여 주소 변환을 할 때 table의 valid/invalid bit을 확인하는데, 만약 invalid bit으로 설정되어 있으면, 유효하지 않은 page를 접근하려고 했으므로 하드웨어가 trap을 일으키는데, 이 경우를 Page Fault라고 한다. page fault가 발생하면 시스템은 아래와 같은 순서로 동작한다.
- 하드웨어가 일으킨 trap을 처리하기 위해, CPU는 user mode에서 kernel mode로 변경한다.
- kernel 내부의 page fault handler가 실행된다. 해당 handler는 아래 두 가지 경우를 고려하여 동작한다.
- 접근하려던 page가 사용하지 않는 논리적 영역일 경우, abort를 발생시키며 프로세스를 강제 종료한다.
- Swapping: Disk I/O, CPU preempt (block state)
a. 접근하려던 page의 frame이 물리 메모리에 없는 경우, empty frame을 얻어 swap in한다.
b. 만약 empty frame이 없는 경우 강제로 다른 frame을 빼앗는데, 기존 frame의 page는 swap out되어 backing store에 저장된다. 이때 swap out되는 page가 물리 메모리 상에서 write된 적이 있으면, swap out하면서 backing store에 있는 원본 page에 변경 사항을 적용한다. - 2에서 b의 경우, 해당 page의 valid/invalid bit을 valid bit으로 수정하며, entry에 swap in한 frame을 기록한다. 그리고 swapping으로 CPU를 뺏긴 프로세스를 다시 ready queue에 넣는다.
- CPU를 얻으면, 중단되었던 명령을 다시 실행한다.
Performance of Demand Paging
EAT = (1 - p) × memory access
+ p × (OS & HW page fault overhead + [swap out if needed] + swap in + OS & HW restart overhead)
Page Fault Rate p (0 ≤ p ≤ 1.0) (if p = 0, no page faults)
※ user mode에서 kernel mode로 바뀌는 과정, handler 동작 및 swapping에서의 disk I/O 등이 SW, HW의 overhead이다.
Page Replacement Algorithm
swap in될 page를 위한 free frame이 없으면, 다른 page가 있는 frame을 뺏어야 하는데, 어느 frame을 victim으로 선정할 지는 접근 빈도와 올라온 시점 등을 고려해야 한다. 최대한 사용되지 않는 page를 선정하는 것이 좋으며, victim을 잘못 정할 경우 동일한 page가 계속 swapping되는 것을 반복할 수도 있다. 결국 page fault의 빈도를 최소화하는 것이 victim을 선정하는 알고리즘의 목표이다. 알고리즘의 평가는 페이지들이 참조되는 순서대로 번호가 저장된 page reference string을 주었을 때 page fault의 빈도 수로 조사한다.
Belady's Optimal Algorithm
MIN, OPT라고도 불리는 이 알고리즘은 미래에 참조될 페이지들을 파악한 상황에서 가장 먼 미래에 참조되는 page를 swap out한다. 위 그림에서 7-0-1이 차례대로 적재되어 있는 시점을 보자. 저 상황에서 2번 page가 swap in이 되어야 하므로, 7/0/1번 page 중 하나가 victim으로 선정되어야 한다. 그런데 7번page가 3개의 page 중 가장 나중에 참조되므로, 이 page를 victim으로 선정하여 swap out된다. 따라서 swapping 이후에는 메모리에 2-0-1이 적재된다.
이 알고리즘은 특정 page가 미래에 언제 참조될 지를 미리 알고 있으므로, 실제 시스템에서는 사용 불가한 Offline Algorithm이다. 그러나 이 알고리즘보다 최적인 알고리즘이 존재하지 않는 Optimal Algorithm이므로, 실제 시스템에서 적용 가능한 알고리즘 성능에 대한 Upperbound를 제공한다.
FIFO Algorithm
FIFO 알고리즘은 먼저 메모리에 올라온 page를(First In) victim으로 선정한다(First Out). 위 그림에서 메모리가 7-0-1로 적재된 상황을 보면, 먼저 메모리에 올라온 7번 page가 swap out되고 2번 page가 swap in된 것을 볼 수 있다. 그러나 이 알고리즘은, page frame을 늘릴수록 page fault의 빈도가 증가하는 문제를 갖고 있는데, 이 문제를 FIFO Anomaly (Belady's Anomaly)라고 하며, frame 수의 증가가 page fault 빈도 수를 낮추지 못하는 문제를 말한다.
LRU (Least Recently Used)
LRU 알고리즘은 가장 오래 전에 참조한 page를 swap out하는 알고리즘이다. 왼쪽에서 세 번째 7-0-1이 적재된 물리 메모리 상태에서, 가장 오래 전에 참조된 7번 page를 swap out하는 것을 볼 수 있다.
LFU (Least Frequently Used)
LRU와 다르게, LFU는 참조 횟수가 가장 적은 page를 swap out한다. 만약 참조 횟수가 최저인 page가 여러 개가 있다면, LFU에서는 특별히 어느 page를 선택하는지는 명시하지 않지만, 성능 향상을 위해 그들 중에서 가장 오래 전에 참조된 page를 victim으로 선정하도록 구현할 수도 있다.
Example of LRU & LFU
위 그림에서, 우측의 timestamp는 각 page 요청 시점을 화살표로 나타내고 있고, 현재 시점에서의 page frame 상태와 reference string을 보여주고 있다. 현 시점에서는 5번 page를 요청했는데, LRU 알고리즘에서는 가장 오래 전에 참조한 page를 victim으로 선정하므로, 1번 page를 swap out할 것이다. 그러나 LFU 알고리즘은 가장 적은 수로 참조된 page를 swap out하므로 4번 page를 고를 것이다.
그러나 위 예제에서 LRU와 LFU의 문제점을 알 수 있는데, LRU는 1번 page가 비록 오래 전에 참조되었지만, 참조 당시에는 많은 요청이 있었다는 사실을 고려하지 않았다. 반면에 LFU는 현 시점까지 아직 한 번 밖에 참조되지 않은 4번 page를, 나중에 해당 page의 요청이 들어올 수 있는 가능성을 고려하지 않았다.
Implementation of LRU
LRU는 doubly linked list를 이용하여 구현할 수 있는데, 가장 최근에 참조된 page에 대한 reference를 head로 배치한다. 따라서 자연스럽게 오랫동안 참조가 안 될수록 tail에 가까워지고, 결국 tail이 가리키는 page가 swap out 대상이 된다. 이 알고리즘은 그저 현 시점에서 참조된 page에 대한 reference를 head로 옮기면 되므로, 시간 복잡도는 O(1)이다.
Implementation of LFU
만약 LFU도 doubly linked list로 구현하면, 참조가 되면 바로 그 reference를 head로 옮기는 LRU와 달리, 물리 메모리에 배치된 이후 참조 횟수를 다른 page들과 고려해야 하므로 시간 복잡도가 O(N)이 된다. 따라서 LFU를 doubly linked list로 구현하는 것은 비효율적이다.
대신 min-heap을 사용하면 O(logN)으로 가장 참조 횟수가 적은 page를 탐색하는 것이 가능하다. 이 경우 min-heap 자료구조 상 값이 가장 작은 node가 root에 위치하므로, 그것이 victim이 된다.
Caching
CPU와 memory 사이에 cache memory를 두어, CPU 연산에 필요한 데이터를 cache에 저장해 두었다가 사용함으로써 반복적인 memory 접근을 최소화하는 방식을 Caching 기법이라 하고, paging system이나 buffer caching, web caching에서 사용한다.
그러나 cache에서 원하는 데이터를 탬색하는 시간이 불필요하게 오래 걸리면 서비스가 원할하게 제공되지 않을 수 있으므로, caching을 이용하는 서비스마다 시간 제약조건이 있다. 예를 들어, LFU의 node 탐색 시간은 doubly linked list로 구현할 경우 O(N)이므로 swapping시 신속하게 victim을 찾을 수 없다. 그러나 탐색 시간이 O(logN)인 min-heap을 이용하면 swapping 시간이 줄어 page fault를 비교적 신속하게 해결할 수 있다.
LRU & LFU in Real Paging System
그런데 LRU와 LFU 알고리즘은 실제 Paging System에서 사용 가능할까? 결론적으로 불가능하다. paging system에서 page에 해당하는 frame을 찾고 주소 변환을 하는 작업은 모두 하드웨어가 담당한다. 즉, page fault가 발생하지 않는 이상 OS가 개입하지 않는다. 따라서 page fault가 발생하지 않는다고 하면, 해당 page가 물리 메모리에 언제 올라왔는지, 몇 번 참조되었고 언제 참조되었는지에 대한 정보를 OS가 알 수 없으므로, LRU와 LFU 알고리즘에 필요한 정보를 수집할 수 없다. 결국 OS는, page fault가 발생하여 CPU 제어권이 OS로 넘어갈 때 물리 메모리에 올라오는 page의 시간 정보 정도만 파악할 수 있다.
Clock Algorithm
Second Chance, NRU(Not Recently Used)로 불리는 이 알고리즘은 실제 시스템에 사용하지 못하는 LRU 알고리즘을 근사한 알고리즘이다. reference bit을 이용하여 참조 여부를 파악해 victim을 선정하고, modified bit을 이용하여 swap out 시 수정 여부를 확인한다.
위 그림에서 포인터(hand)가 page를 가리키고 있고, 각 page에는 (reference bit(used bit), modified bit(dirty bit))이 있다. reference bit은 해당 page가 참조되었을 경우 1, 그렇지 않으면 0으로 나타낸다. page fault가 발생할 경우 clock algorithm은 포인터가 가리키는 page의 reference bit을 확인한다.
- Reference Bit = 1: 0으로 바꾸고 포인터를 다음 페이지로 옮긴다.
- Reference Bit = 0: reference bit이 0인 경우는, 이전에 포인터가 이 page를 가리켰을 때 0으로 바꾼 후, 다시 포인터가 한 바퀴 돌아 또 그 page를 가리킬 때까지 해당 page는 참조된 적이 없는 것이다. 따라서 이 page를 victim으로 정하고 swap out한다.
만약 이 알고리즘이 victim을 선정해 swap out할 경우, modified bit을 확인한다. 이 bit는 page가 물리 메모리에 올라온 이후 수정이 되었으면 1, 그렇지 않으면 0으로 설정된다.
- Modified Bit = 1: 해당 page에서 수정이 일어났었으므로, swap out할 때 backing-store에 있는 원본 page에 변경된 사항을 반영한다. 이때 disk I/O가 발생한다.
- Modified Bit = 0: 이 page에서 수정한 부분이 없으므로, swap out할 때 물리 메모리에서 삭제하고, disk에 write하지 않는다.
Allocation of Page Frame
어떤 프로그램은 최소로 할당받아야 하는 frame 수가 있고, Loop를 갖는 프로그램은 동시에 여러 frame을 받아야 page fault의 수를 줄일 수 있다. 결국 프로그램마다 할당받아야 하는 frame의 수는 다른데, 이를 결정하는 방식은 크게 3가지가 있다.
- Equal Allocation: 모든 프로세스에게 같은 수의 frame을 할당
- Proportional Allocation: 프로세스의 크기에 비례하여 할당
- Priority Allocation: 프로세스의 우선 순위에 따라 다르게 할당
Global vs. Local Replacement
- Global Replacement: swap out의 대상을 다른 프로세스의 frame으로 선정할 수 있다. FIFO, LRU, LFU 알고리즘을 global replacement로 구현하거나, Working set, PFF 알고리즘을 사용하면 된다. Global Replacement를 사용하면 위의 3가지 allocation 방식을 적용하지 않아도 자동적으로 프로세스마다 메모리 할당량이 조절된다.
- Local Replacement: swap out의 대상을 자신이 할당 받은 frame으로만 결정한다. FIFO, LRU, LFU 알고리즘에서 프로세스 별로 운영하는 것으로 구현 가능하다.
Thrashing
위 그래프의 가로 축은 얼마나 많은 프로세스가 동시에 실행되는지, 즉 메모리에 올라간 프로세스들의 수를 나타낸 것이고, 세로 축은 CPU 이용률을 나타낸 것이다. degree of multiprogramming가 낮은 상황에서는 메모리에 올라간 프로세스의 수가 비교적 적은므로, 그만큼 CPU가 하는 일이 많지 않게 된다. 반대로 프로세스의 수가 증가하면 그만큼 CPU가 바빠지게 되므로, CPU 이용률도 증가한다. 그러나 메모리에 올라간 프로세스의 수가 증가하면 각 프로세스마다 할당 받는 frame의 수는 적어지고, page fault의 발생 수는 증가하여 I/O 빈도 또한 증가함에 따라, CPU의 이용률도 낮아진다. 이 상황을 Thrashing이라 한다. 그런데 CPU 이용률이 낮아지면, OS는 동시에 실행중인 프로세스의 수가 적어 MPD1를 높여야 한다고 판단한다. 따라서 더 많은 프로세스들이 메모리에 올라가고, 할당받는 frame의 수는 더 적어질 것이다. 결국 문제가 악순환되어 throughput이 낮아진다.
Thrasing 해결하기 위해서는, 동시에 실행하는 프로세스의 수를 조절하여 각 프로세스가 어느 정도의 frame을 할당받을 수 있게 해야 하는데, 이때 사용하는 알고리즘이 Working-Set Model과 PFF(Page Fault Frequency)이다.
Working-Set Model
프로세스는 특정 시간 동안 특정 구역을 집중적으로 참조하는 경향이 있는데 이를 Locality of Reference라고 하고2, 집중적으로 참조되는 page들의 집합을 Locality Set이라 한다. 이 locality set이 한꺼번에 물리 메모리 위에 있는 것을 보장해야 page fault의 발생 횟수를 줄일 수 있다.
locality에 따라, 특정 프로세스가 일정 시간동안 원할하게 수행되기 위해 물리 메모리에 한꺼번에 올라와야 하는 page들의 집합을 Working-Set이라 한다. 만약 이 프로세스가 working set의 page들을 모두 올릴 수 있을 만큼의 frame을 할당받지 못하는 상황이 되면, 현재 올려져 있는 자신의 page를 swap out하고 frame을 반납하며, suspend 상태로 변한다. 이로써 MPD를 조절하여 Thrashing을 방지할 수 있다.
Working-Set Algorithm
이 알고리즘에서 working-set을 과거 ∆시간 만큼 참조된 page들로 추정하는데, 이때 이 ∆시간을 Working-Set Window라고 한다. 이때 working set은 [t - ∆, t]에서 참조된 page들로 구성된다.
위 그림을 보면, t1에서 working-set window의 크기는 10으로, 그 시간 내에 참조된 1, 2, 5, 6, 7번 page를 working-set으로 추정한다. 따라서 이 working-set 내의 모든 page들에게 frame을 할당할 수 있으면 전부 메모리에 올리고, 그렇지 않다면 갖고 있는 frame마저 반납하고 해당 프로세스의 page를 모두 disk로 swap out시키며 suspend 상태로 돌입한다. 그런데 t2에서는 같은 working-set window 크기에 의해 working-set이 3, 4번 page로 구성되므로, 3번과 4번 page에게 모두 frame을 할당할 수 있을 경우에만 메모리에 올린다.
working-set algorithm은 프로세스가 실행 중, working-set의 page들이 각각 참조 시점부터 window size = ∆시간동안 frame을 할당받는 것을 보장하는데, 결국 이 page들은 각각 참조된 이후 ∆시간만큼 메모리를 할당받다가 swap-out된다. 위 예제에서, (t1 - ∆)시간에 2번 page가 참조되는데, 이때 이 page는 working-set에 들어간다. 그리고 t1시간까지 2번 page가 working-set에 있으므로 물리 메모리를 할당받다가, (t1 + 1)시간에 working-set에서 제외되므로 frame을 반납하고 swap-out하게 된다.
PFF (Page Fault Frequency) Scheme
PPF scheme는 직접 page fault의 발생 빈도를 확인하여, frame 할당 수를 조절한다. 만약 특정 프로세스의 page fault rate가 상한선을 넘으면, 이 프로세스에게 frame을 더 할당하여 rate를 줄이도록 한다. 이때 빈 frame이 없다면 다른 프로세스로부터 frame을 빼앗는다. 그러나 rate가 하한선보다 낮으면, 이 프로세스에게 frame이 불필요하게 많이 할당되었음을 파악하고 할당하는 frame 수를 줄인다.
Page Size
지금까지 paging system에 대해 기술할 때 page 크기를 4KB로 가정하고 설명했는데, 이 page 크기를 더 축소하면 다음과 같은 현상이 발생한다. 따라서 보통 page 크기를 줄이기보다는 키운다.
- Page 수의 증가: 동일 크기의 메모리 공간에서 더 작게 쪼갰으므로, page의 수는 증가한다.
- Page Table의 크기 증가: page수가 증가함에 따라 entry가 증가했으므로, 이를 담는 table 또한 커진다.
- Internal Fragmentation의 감소: 같은 프로세스를 좀 더 작게 나누어 필요한 내용만 메모리에 올릴 수 있으므로 internal fragmentation은 감소한다.
- Disk Transfer 효율성 감소: disk header가 seeking하는 시간은 상당히 오래 걸린다. 따라서 한 번 seek하면 되도록 많은 데이터들을 I/O하는 것이 좋으나, page의 크기가 작아진 만큼 seek를 해도 비교적 적은 양의 데이터를 I/O하므로 disk 측면에서는 비효율적이다.
- Locality 효율성 감소: 더욱 잘게 쪼개어 필요한 만큼의 정보만을 메모리에 올릴 수 있으므로 메모리 이용 측면에서는 효율적이나, 한 page에 들어가는 정보가 비교적 적어지므로, 한 page 내에 필요한 정보가 모두 담겨있지 않을 수 있다.따라서 page fault에 의해 필요한 page가 올라와도, 그 크기가 작은 page 하나만으로 필요한 내용들을 충족시킬 수 없으므로 계속 page fault가 발생할 것이다. 이는 특정 메모리 영역을 집중적으로 참조하는 locality에 적절하지 않다3.
참고한 자료
>> book
Abraham Silberschatz, Operating System Concepts 10th edition