페이지 교체(page-replacement) 알고리즘
요구 페이징 시스템은 프로세스가 특정 페이지를 요구할 때 해당 페이지를 물리 메모리에 로딩한다.
medium.com
#Demand paging
: 앞선 단원에서 요청하는 프로세스가 physical memory에 없을 경우, disk로부터 프로세스를 읽어들여서 physical memory로 로딩하는 swapping에 대해 배웠다. 이 때, swapping이 핸들링 하는 단위는 전체 프로세스 단위이다.
=> 하지만, 이번 단원부터는 관점을 바꿔서, 다루는 단위를 page로 바꿔보도록 하자.
: 현재에는 요청이 있는 페이지만 physical memory로 로딩하는 demand paging 기법이 훨씬 많이 쓰인다.
따라서 swapping보다는 paging을, swapper보다는 pager라는 용어를 기억해두도록 하자.
- Pager == Lazy swapper
: pager를 주로 lazy swapper라고도 하는데, 이는 요청이 올 때까지 최대한 뒤로 미뤄서 메모리로 로딩하기 때문이다.
: 요청이 없는 페이지는 아예 physical memory에 접근할 일이 없게 된다.
그림에서 확인할 수 있듯이, swap in/out되는 단위가 페이지 단위이고, 요청이 없는 페이지는 아예 swapin 되지 않는다.
: Process 전체는 여러 페이지로 구성되고, 일부 페이지는 physical memory에 로딩되고, 일부 페이지는 physical memory에 로딩됮 않을 수도 있다. 따라서 어떤 페이지가 physical memory에 존재하는지 여부를 table을 통해서 정리해 두게 된다.
- 가장 초기에는 table은 모두 invalid bit로 세팅되어있다. 특정 시간에 swap-in 된 프로세스는 valid bit로 바뀌게 된다.
=> invalid bit이면 단순히 메모리에 없는가? 아니면 애초에 접근이 illegal한 주소인가를 알아야 하는데,
이는 이를 구분하는 별도의 internal table을 lookup하면서 알수 있게 된다.
=> 위 그림의 예시를 살펴보면, 현재 physical memory에 로딩되어있는 페이지는 A,C,F 페이지이다.
따라서, 만약 physical memory에 없는 페이지를 요청하게 되면 page fault가 발생하게 되고, 비어있는 frame을 찾아 해당 frame으로 로딩하게 된다. page fault가 어떻게 이루어지는지 살펴보자.
=> page fault는 software interrupt인 trap으로 처리된다. page fault를 통해 page가 swap in되는 과정을 살펴보자.
1. OS는 internal table을 살펴봄으로써 해당 페이지가 단순히 memory에 없는건지, 아니면 애초에 invalid한 주소로 접근한 것인지 결정한다.
2. 만약 단순히 메모리에 없는것이라면 비어있는 프레임을 확보한다.
3. 그리고 메모리에 page를 swap-in 한다. 이때, swap-in은 disk I/O가 일어나고 있다는 의미이므로, process는 waiting state에 머물게 된다.
4. 그리고 page table을 업데이트 하고, validation bit를 세팅한다.
5. trap에서 빠져나와 해당 문맥부터 재수행하게 된다.
# Pure Demand paging vs Pre-paging
: paging에서는 가능한 한 page fault를 줄이는게 중요하다. page fault가 일어날 때마다 disk에 접근하기 때문이다.
=> disk에 접근한다는 말은, 단순히 메모리를 참조하는 것보다 access time이 훨씬 크다는 말을 의미한다.
- Pure paging
: 처음엔 다 invalid하므로 무조건 page fault가 발생한다. => 따라서 multiple page fault가 발생할 수 밖에 없다.
: 프로그램이 수행되면 multiple page fault가 계속 발생하면 메모리 접근 시간이 더 늘어나게 된다.
=> Paging을 진행하면서, 일종의 패턴이 발생하게 된다.
- 특정 페이지만 집중적으로 접근하던가 (Spacial Locality)
- 시간적으로 근접한 기간에 접근하는 페이지들이 일정하다는 등 ( Temporal Locality)
Locality가 발생하게 된다. 따라서 해당 페이지들을 예측해서 메모리에 로딩해 두면, Demand page를 사용하더라도
page fault가 많이 발생하지 않고, 합리적인 성능을 나타나게 된다.
#Performance of Demand Paging
- page fault가 발생할 확률을 p라고 하자.
- EAT는 (fault가 발생하지 않을 확률) * 메모리 접근 시간 + (fault가 발생할 확률 ) * (page fault를 처리하는 총 시간)
만큼 걸리게 된다.
=> Memory access time은 200ns만큼 걸리고, 평균적으로 page fault를 처리하는데 걸리는 시간은 8ms 이다.
거의 4만배가 차이가 나는것을 확인할 수 있다. 따라서, page fault를 매우 줄여야 하는 것을 확인할 수 있다.
- 애초에 page fault service time을 줄이면, swap 속도도 빨라지므로, Swap space를 관리하여 disk 접근 시간을
줄여볼 수 있다.
: disk의 일부 공간이 swapping을 위해 할당되는데, 이 backing store (swap하기 위해서는 backing store에 있는 페이지에 접근해야함 )에 접근하는 시간을 더 줄여 볼 수 있다.( 8ms 자체를 줄여볼 수 있다 )
: swap space block을 크게 하는 등...
그렇지만, disk 접근 시간 자체를 줄이는 것은 한계가 존재한다.
=> 따라서, page fault를 줄이는 게 가장 중요하고, 미래에 많이 접근된 페이지를 예측하여 메모리로 올리는게 필요하다.
#Page Replacement
: page replacement는 memory management에서 가장 중요한 이슈로, 빈 프레임이 없을 경우에, 원래 페이지를 swap-out 하고, 새로운 page를 swap-in 하는 기법이다.
: 따라서, 이때 가장 중요한 목표는 바로 Page fault를 줄이는 것이다.
=> 애초에 메모리 공간이 많아서 다른 페이지를 위한 빈 프레임을 쉽게 찾을 수 있다면 전혀 문제가 되지 않는다.
=> 그렇지만, 빈 프레임이 없을 경우, 반드시 Page Replacement가 필요하다.
1) 우선 disk에서 올리고자 하는 페이지의 위치를 찾아야 한다.
2) 페이지를 올릴 빈 프레임을 찾아야 한다.
: 만약 빈 프레임이 있다면, 그것을 이용한다.
: 하지만, 빈 프레임이 없다면 page replace algorithm을 이용해 swap-out될 victim frame을 선정한다.
3) 그리고, 요청된 페이지 를 빈 프레임으로 로딩한후, page 와 frame table을 update하게 된다.
4)그 후, 프로세스를 재시작 하게 된다.
- Page replacement를 위해서는 victim page를 swap out하고, desired page를 swap in 하게 된다.
=> 이때 swap out하면 disk에 write하는 연산이고, swap in은 disk로부터 읽어들이는 read 연산이다.
- 따라서 두번의 디스크 연산이 필요한데, victim page는 이미 disk에도 있는 상태이고, 만약 해당 페이지가 수정이 되지 않았다면, 디스크에 이미 존재하는 victim page를 다시 copy하여 disk에 적재할 필요가 없다.
: 따라서 modify되지 않고, page가 그대로라면, swap out하지 않고 그냥 버리게 된다.
- 만약 modify bit가 1이라면, 페이지의 내용이 수정된 상태이기 때문에 disk에 있는 page의 내용과 다르다. 따라서 swap-out을 시켜주게 된다.
- 하지만, modify bit가 0이라면 swap out시킬 필요가 없고, Disk I/O 연산을 줄임으로써 overhead를 감소할 수 있다.
=> Page replacement algorithm을 실행하는 가장 큰 목표는 page-fault rate를 최소한으로 하는 것이다.
=> 해당 reference string을 통해 각 알고리즘의 성능을 비교해 보도록 하자.
#FIFO Algorithm
: Demand Paging의 일종으로, 가장 먼저 swap in된 페이지를 먼저 쫓아낸다.
: 해당 page가 이미 physical memory에 있다면, swap 해줄 필요가 없다.
=> 보통은 frame을 늘리면 page fault가 덜 발생할 거라고 예측한다.
: 하지만, FIFO algorithm에서는 frame을 늘릴수록 page fault가 더 발생하는 기현상이 발생한다.
# Optimal Algorithm
: 최적의 알고리즘으로, 더 좋은 알고리즘은 존재하지 않는다.
=> 가장 오랫동안 접근 안될 page를 쫓아내게 된다.
- 그렇다면, 미래에 어떤 페이지를 reference할지 어떻게 예측할 수 있는가?
: 알수 없기 때문에 사용이 불가능한 알고리즘이다. algorithm 개발 시에 어떤 성능을 나타내는지에 대한 지표로만 활용가능하다.
- Page fault가 일어나면, 미래의 reference들을 살펴보고, 가장 접근이 안되는 페이지를 victim 페이지로 결정한다.
#LRU algorithm < Least Recently used>
: 미래에 사용될 reference를 알 수 없기 때문에 사용되는 알고리즘이다.
=> 따라서, 가장 덜 최근에 사용된 page를 victim page로 삼게 된다.
=> 계속 가장 예전에 사용된 page를 victim page로 삼아서 swap-in/out을 진행한다.
: LRU는 주로 좋은 성능을 보여준다. 하지만, 구현이 복잡하다는 단점이 있다.
-> Counter/ stack implementation 두가지 방법이 있다.
- Counter Implementation
: 각 page entry에 counter를 두고, 페이지가 reference될 때마다, counter에 시간을 기록한다.
: 만약 page replacement가 필요하면, counter 값이 가장 작은 page를 쫓아 내면 된다.
=> page마다 counter라는 논리적 시간을 기록해두고, 가장 counter 값이 작은 page를 쫓아낸다.
: 가장 counter값이 작은 페이지를 search해야 한다.
- Stack Implementation
: page가 reference되면, 해당 페이지를 top으로 이동한다. ( 따라서, 가장 top에 있는 페이지가 가장 최근 reference됨)
=> 따라서, LRU page를 찾기 위해 따로 search할 필요 없이 가장 bottom에 있는 페이지가 victim page가 된다.
-하지만, top으로 옮기려면 다른 page의 index도 바꿔야 하므로, stack의 형태를 유지하기 위한 overhead가 발생한다.
#LRU-approximation algorithm
: LRU가 구현이 복잡하므로, LRU보단 못하지만 유사한 성능의 algorithm또한 존재한다.
: Reference bit를 활용해 각 page가 예전에 참조되었는가를 확인한다.
- Reference bit
: 각 페이지들은 reference bit를 갖고 있고, 0 으로 초기화 된 상태이다.
=> 만약 page가 reference 되었다면, bit를 1로 세팅한다.
=>Page를 교체해야 하는 시점에서, 만약 bit가 0인 페이지가 있다면, 참조가 안된 것이므로 LRU일 확률이 높다.
=>하지만, 0인 페이지가 여러개이면 어떤 페이지가 LRU인지 순서를 아는 것이 불가능하다.
1. Additional-Reference-bits algorithm
-> 따라서, reference bit를 여러개 두고, bit를 하나씩 shift하면서 더 최근에 reference된 페이지가 무엇인지 살펴본다.
100ms를 주기로 두고, 만약 0~100ms에서 reference되었다면, 가장 앞 비트를 1로 setting한다.
그리고 그 다음 주기에서 또 reference되었다면, 비트를 하나씩 오른쪽으로 shift하고, 가장 앞 비트를 1로 세팅한다.
=> 따라서, 가장 최근에 reference된 bit가 더 예전인 page가 victim이 된다.
페이지를 swap in 하려고 11000100과 01110111 두개를 비교했을 때, 앞 페이지는 이전 단계에서 reference되었지만,
뒤 페이지는 전전단계에서 reference되었다. 따라서 두번째 페이지가 victim이 된다.
2. Second-chance algorithm
- clock hand가 rotation하면서 가장 처음 만나는 reference bit가 0인 페이지를 교체한다.
-만약 reference bit가 1이라면, 최근에 참조된 것이므로 0으로 바꿔서 한번 더 기회를 준다.
따라서, 11page->8page를 거쳐 가장 처음 만나는 reference bit가 0인 page 5를 victim으로 삼고, reference bit를 1로 세팅하게 된다. 그리고 계속 clock hand를 rotation한다.
- frame별로 1개의 reference bit
- clock hand가 이동하면서 1->0으로 한번 더 기회를 주던가, 필요에 따라 victim page를 선택하는 clock replacement 정책을 사용하게 된다.
#Enhanced Second Chance Algorithm
: frame당 원래는 reference bit 한개만 갖고 있었지만, enhanced second chance algorithm에서는 추가적으로 modify bit를 갖고 있다.
=> reference bit와 modify bit에 따라서 페이지들을 네개의 class로 구별하고, 가장 낮은 클래스에 있는 페이지중 가장 처음 만나는 페이지를 victim page로 삼는다.
# Counter- Based Algorithm
: 해당 페이지를 몇번 접근했는지 count값에 근거한다.
-LFU : 가장 적게 접근한 page를 replace한다.
-MFU : 가장 많이 접근한 page를 replace한다.
#Thrashing
: frame 개수가 적고, 메모리 공간이 적어지면 먼저 swap된 페이지를 쫓아내므로 page fault rate가 늘어나게 된다.
=> 따라서 Disk I/O를 많이 수행하게 되면서 프로세스가 수행이 안되고, swappin에만 시간을 다 쓰게 되어 CPU utilization rate가 떨어지게 된다.
=> 이때, CPU는 오히려 돌리는 프로세스의 양을 늘려야 겠다고 생각하고, 프로세스를 추가하게 되고, 이는 메모리가 부족한 상황에서 오히려 멤swapping 할 object를 늘린 것이므로, 이는 상황을 더 악화시킨다.
: 따라서, Thrashing은 프로세스가 동작해야 하는데 메모리 공간 부족 때문에 swapping하느라 바쁜 상황을 말한다.
=> Thrashing이 발생하면, multiprogramming으로 프로세스 개수를 늘려봐도, 오히려 CPU utilization rate는 감소한다.
- Thrashing 방지
: thrashing을 방지하기 위해서는 우리는 프로세스가 얼마만큼의 메모리를 요구하는지 알고 있어야 한다.
ex) 예를 들어, process가 5개가 있고, 각 프로세스가 100mb씩을 요구한다면 총 500mb가 필요하다.
=> 하지만 우리는 demand paging 방식을 사용하므로 이 중 일부의 메모리만 확보해도 된다.
: 프로세스의 모든 페이지가 동시에 돌아가는게 아니므로, 500mb 전부를 확보해놓는것은 메모리 공간을 낭비하는 것이다. => 따라서 실제 각 프로세스는 100mb 보다 적은 용량을 사용한다.
- 하지만, 각 프로세스가 어느 정도의 용량을 사용할지는 파악이 쉽지 않다.
이때, Locality model이라는 것을 이용해 프로세스가 실제로 요구하는 메모리 크기를 산정 가능하다.
: 프로세스들은 한 locality에서 다른 locality로 이동한다. 각 시점에서의 locality를 봐야 한다.
Locality model이란 특정시점에 집중적으로 접근하는 페이지들을 분석해서 프로세스가 요구하는 메모리 크기를 산정할수 있도록 하는 모델이다.
-Thrashing은 Size of locality의 합 > Total memory size일 때 발생한다.
이때, size of locality의 합은 프로세스의 크기의 합이 아닌, 특정 시점에 active하게 이용되는 페이지의 크기이다.
#Working set model
: Working set model이란 locality의 크기를 detection 할 수 있는 모델이다.
=> Locality 모델을 기반으로 특정 시간에 실행되는 프로그램이 최근 참조했던 페이지의 총 개수가 Working set이 된다.
: 이 때, '특정 시간'은 Working set window라는 것을 참조하게 되는데, 이는 특정 시점으로부터 이전페이지를 몇개나 lookup 할지를 기준으로 삼는 페이지 개수이다. 예를 들어 working set window가 7개라면, 특정시점 이전으로부터 참조된 페이지 7개를 분석해 몇개의 페이지나 참조되었는지 확인한다.
- Working set window가 너무 작다면, 충분한 양의 locality를 포함하지 못할 것이다.
- 만약 window가 크다면, 여러 locality를 포함하게 될 것이고, 만약 window의 크기를 무한으로 한다면, 모든 프로그램을 포함할 것이다.
여기서 D라는 변수는 frame들에 요구되는 총 메모리양인데, 만약 Demand되는 양이 physical memory size보다 크다면 Thrashing이 발생하게 되고, 주로 프로세스들 중 하나를 정지시킨다.
해당 예시에서는 working set model의 window크기를 10으로 잡고, 시점을 하나 정하고 그 시점으로부터 과거 10개의 페이지를 분석해 최근에 reference된 페이지의 집합을 구하게 된다.
=> 두번째 예시를 통해 각 wss에서 몇개의 페이지들이 reference되었는지 확인해 보자.
wss1에서는 6개, wss2에서는 5, wss3에서는 4 개의 페이지들이 reference되었다. 총 15개의 프레임이 요구된다.
: 이때, 만약 physical memory의 총 frame개수가 14라면 thrashing이 detect된다.
=> window size가 커지면 커질수록 thrashing을 detect할 확률이 높아지게 된다.
# Thrashing이 발생하면 swapping -in /out 하느라 바빠서 cpu utilization이 낮아지게 된다. 따라서 Locality의 총합을 파악해야 한다. 과거 window size만큼 reference된 페이지들의 개수를 파악함으로써 Thrashing을 detect할 수 있다.
#Allocating Kernel Memory
: Kernel도 일종의 프로그램이기 때문에 메모리를 할당/해제해줄 필요가 있다.
이때, Malloc/ free함수를 통해 주로 메모리를 할당/해제하곤 한다.
: Kernel memory는 일반 user program과는 다르게 관리된다.
: 가끔 free memory pool에서 할당되곤 하는데, 커널들은 다양한 사이즈의 구조체형 메모리를 요구할 수 있다.
: 또는, 일부 kernel memory들은 contiguous한 할당이 필요하다.
- Kernel memory를 allocating하는 방식에는 Buddy System과 Slab allocator의 두가지 방법을 다룬다.
# Buddy system
: 연속적인 메모리 공간을 할당할 때에 매우 유용하다. fixed-size의 physically-contiguous page들을 할당한다.
- Memory들은 주로 2^n 개의 연속적인 페이지들을 할당하게 된다. (반올림된다)
만약 7개의 페이지를 요청한다면, 7개보다 많은 2^3= 8개의 페이지를 할당하게 된다.
- 만약 그 이후에 더 작은 양의 페이지 할당이 필요하다면, 현재의 chunk가 두 개의 buddy들로 분할하게 된다.
: 3개를 요청한다면, 8개 페이지 짜리 chunk가 4개로 나누어진다.
512 page의 memory pool 에서, 다양한 크기의 자료형의 list가 존재한다.
: 만약 253page를 요청한다면, 512page의 자료형이 256 page로 쪼개지게 된다.
: 만약 124페이지를 요청한다면, 256page의 자료형이 128page로 각각 쪼개지게된다.
만약 그 이후로, 128이라는 자료형을 다 사용하고 나서 release하게 되면, 128 자료형이 병합되어 256 자료형 크기를 갖게 된다. : Buddy system에서는 가능한한 연속적인 큰 메모리를 유지하려고 한다.
이미 메모리들이 각각 할당된 상태에서, 128 개를 다시 할당하면, A' 페이지가 256으로 쪼개지고, 한쪽 256 짜리 자료형을 다시 128로 쪼개서 할당한다. 그리고 C를 release하고, D를 release하고 난 후에는 하나의 256 크기를 가진 B' 블록으로 합병이 된다.
: Buddy System에서는 2^n개의 자료형을 유지하면서 할당/ 해제를 반복하게 되고, 이 과정에서 최대한 연속적인 큰 자료형을 유지하려고 한다.
# Slab allocation
slab allocation의 목적은 internal fragmentation을 없애고, 메모리 낭비를 막는 것이다.
: 메모리 object의 크기는 주로 4kb인데, 커널에서 자주 생성되는 object로는 주로 semaphore가 있다.
Sempahore의 크기는 2kb인데, sempahore를 4kb의 페이지 단위로 하나씩 할당해야 한다. 그럼 당연히 Internal fragmentation이 발생하게 된다.
두번째 목표는 메모리 할당을 빠르게 하는 것이다.
: 메모리를 미리 할당해 놓으면 빠르게 메모리 할당이 가능하다.
=> 각 semaphore, kernel object마다 slab을 할당해 놓는다.
: cache에는 하나 이상의 slab을 포함하고 있다.
: 각 kernel object마다 slab에 할당하고, 페이지를 다 사용하는게 아닌, 원하는 크기만큼만 페이지를 할당하고, 다음 object는 바로 이어서 해당 object의 크기만큼 할당된다. (fragmentation 발생 X)
- Cache는 같은 type의 object를 모아놓는 공간이다. 각 캐시에 필요할 때마다 원하는 object의 크기만큼의 slab이 미리 할당되게 되고, 필요할 때마다 slab의 해당 주소를 가져다 사용하면 된다.
- 각 kernel object의 크기만큼 비어있는 free object 부분들을 남겨놓는다. semaphore cache라면 원래 할당되는 2^n
크기인 8kb가 아니라, semaphore의 크기와 꼭 맞는 7kb만 연속적으로 따닥따닥 할당됨으로써 internal fragmentation 부분을 최소화할수 있게 된다.
: 미리 slab을 할당해놓기 때문에, 따로 메모리 공간을 확보할 필요 없이 빠른 allocation 역시 가능하다.
=> 새로운 object가 들어올 시에, 이미 사용되고 있는 partial slab을 다 채우고 empty slab으로 넘어간다.
'Computer Science > Operating system' 카테고리의 다른 글
| Ch 11. Mass Storage structure (0) | 2020.06.10 |
|---|---|
| 9-2) Memory Management strategies (0) | 2020.06.10 |
| Ch.9-1) Memory Management Strategies (0) | 2020.06.10 |
| Chapter 8. Deadlock (0) | 2020.06.05 |
| Chapter 7. Classic Problems & POSIX API (0) | 2020.06.05 |