[운영체제] Swapping
Demand paging
os brings the page into memory when it is accessed
프로세스가 실행하면서 메모리에 접근하는 페이지에 대해서만 메모리로 가져오고 그것을 위한 페이지 테이블 엔트리들을 만듭니다. 접근하지 않는 페이지의 경우 invalid 상태로 남아있게 됩니다.
page fault
invalid 한 페이지에 접근할 때 page fault 이 발생합니다.
prefetching
초반에 모든 페이지에 접근하면서 page fault가 많이 발생할 수 있습니다. 이것을 해결하기 위해 prefetching 이라고 하는것을 운영체제가 구현합니다. 가장 기본적인 방법으로 예를들어 VPN : P라고 하는 페이지에 접근한다고 하면 P+1 도 곧 접근 한다고 가정하고 미리 메모리에 mapping 해주는 것입니다.
Swapping
이전까지 physical memory 가 각 프로세스를 위해 충분히 제공될 수 있다고 가정했습니다. 하지만 실제로는 pyhsical memory 는 한정적이고 각 프로세스마다 제공되는 Address space 는 상당히 큽니다. 그렇기 때문에 우리가 한정적인 physical memory 를 갖고 큰 address space 를 갖는 여러개의 프로세스를 동시에 실행시키기 위해서 여러가지 방법들이 필요합니다. 이러한 방법으로 운영체제는 메모리 hierarchy 에 추가적인 저장장치 레벨을 요구합니다. 운영체제가 이러한 추가적인 저장장치를 이용해서 마치 물리메모리 자원을 상당히 많이 갖고 있으며 큰 Address space 를 갖는 프로세스들이 그것을 활용할 수 있다고 환상을 심어주는 것이 Swapping 기법 입니다.
Swap space
- 스왑 스페이스는 disk 에 존재합니다.
- swap out : 당장 필요하지 않는 페이지를 빼내 저장합니다.
- swap in : 또 필요할 경우 다시 메모리로 불러옵니다.
address translation 을 할때 우리는 현재의 페이지가 메모리에 있는지 swap out 되어 있는지 알아야 합니다. 이를 present bit 을 통해 알 수 있습니다.
address translation in swapping
present bit 이 0으로 설정되어 있을 때, 즉 페이지가 disk에 적재되어 있고 해당 페이지에 access 하려고 하면 page fault 를 발생시킵니다. 이 경우 page-fault handler 에 의해서 swap in 을 수행해 줍니다.
- PFN을 적는 공간에 swap space 안에서의 주소값을 저장합니다. = swap 공간 안에서의 offset.
- 기본 단위는 4킬로 바이트 입니다. 이유는 swap 되는 단위가 페이지 단위이기 때문입니다.
단점 및 해결책
디스크에 접근하는만큼 page fault 가 발생할 때마다 overhead 가 발생하고 CPU가 낭비될 수 있습니다. 그러므로 page fault 를 발생시킨 프로세스는 잠시 blocked state 로 두고 ready state 중 프로세스를 선택해서 CPU에게 할당합니다.
swapping 이 일어나는 시기
만약 메모리가 꽉찰 때마다 기다리면다면 swapping이 지속적으로 발생하고 성능이 낮아질 수 있습니다. 이를 해결하게위해 운영체제는 swap deamon 이라고 하는 것을 만들어서 페이지의 수가 lower watermark 보다 적을 때 성능적으로 여유롭다고 판단하고 higher watermark 의 페이지 수가 가능할 때까지 페이지들을 eviction 합니다.
page replacemennt policy
만약 memory 가 full 한 상태이고, 추가적으로 페이지가 메모리에 적재되어야 한다면 현재 메모리에 들어있는 페이지를 swap out 해주어야 합니다. 이 때, 어떤 페이지를 swap out 해줄 것인가에 대한 정책에 대한 설명입니다.
- optimal replacement policy : 미래에 가장 적게 사용될 페이지를 replace 합니다.
- FIFO : First In First Out 으로 Eviction 해줍니다.
- LFU : 사용빈도가 가장 낮은 페이지를 eviction 해줍니다.
- LRU : 가장 최근에 사용되지 않은 페이지를 eviction 해줍니다.
LFU 혹은 LRU 같은 historical algorithms 의 경우 기록들을 PTE 에 따로 저장해두어야 하는데, 기록들의 사이즈가 너무 크므로 해당 방법이 쉽지 않습니다. 그러므로 LFU 혹은 LRU 알고리즘의 경우 정확히 구현하기가 어렵습니다. 그래서 등장한것이 Approximation LRU 입니다.
Approximation LRU
Clock algorithm 입니다. 이 방법은 page table entry 의 reference bit 을 이용하는 것 입니다. Clock algorithm 은 해당 포스트에서 따로 설명하진 않겠습니다.
Considering dirty pages
만약 페이지가 수정되지 않았다면 (예를들어, read only) 따로 swapping 작업 없이 해당 페에지가 다시 사용될 수 있습니다. 즉, 운영체제가 가급적 수정이 되지 않은 페이지를 선택하는 것을 병행하도록 하여야 합니다.