이 글은 건국대학교 2024년 1학기 운영체제 수업과 『Operating Systems: Three Easy Pieces』 를 참고하여 작성되었습니다.

『Operating Systems: Three Easy Pieces』
21장. Beyond Physical Memory: Mechanisms
22장. Beyond Physical Memory: Policies

Demand Paging

현재까지 살펴봤던 메모리 가상화는 모두 물리 메모리 자원이 부족하다는 가정 하에 이루어졌습니다. 하지만 현실에선 물리 메모리가 한정적이고, 모든 프로세스의 가상 주소 공간의 합에 비하면 턱없이 부족합니다. 이를 보완하기 위해 물리 메모리에서 사용하지 않는 것은 디스크와 같은 저장 장치에 옮겨 놔야 합니다. 그리고 페이지에 대한 요청이 있을 때, demand paging을 통해서 해당 페이지를 메모리에 적재합니다.

메모리에 적재되지 않은 페이지에 접근하면 page-fault가 발생하고, OS의 page-fault handler가 이를 처리합니다. 초반에 적재되어 있는 페이지가 아예 없으면 잦은 page-fault가 발생하여 성능을 떨어뜨리므로 OS는 prefetching을 수행합니다. prefetching이란 VPN이 n인 페이지에 접근하여 page-fault가 발생했을 때, n+1에도 추후에 접근할 것이라 가정하고 n과 n+1 페이지를 함께 매핑해주는 것입니다. (지역성이라는 특성을 이용)

Swapping

swap space

demand-paging, 필요한 페이지만 그때그때 가져오는 시스템을 구현하기 위해서 OS는 페이지를 swap space라고 하는 disk 공간에 저장합니다. 메모리에서 디스크로 페이지를 옮기는 것을 swap-out, 그 반대를 swap-in 이라고 합니다. OS는 페이지 단위로 swap-out 과 swap-in 을 수행하며 swap space에 페이지의 데이터를 읽고 씁니다.

page fault

접근하고자 하는 페이지가 물리 메모리에 적재되어 있지 않으면 page fault가 발생합니다. OS는 PTE의 present bit가 0일 때, 이 페이지가 메모리에 없다는 것으로 인지합니다. page fault가 발생하면 OS의 page-fault handler가 이를 처리합니다.
page-fault handler가 swap in을 처리하는 과정에서 disk I/O가 발생합니다. I/O 작업은 시간이 오래걸리므로, OS는 page-fault를 발생시킨 프로세스를 blocked state로 바꾸고 다른 프로세스를 실행시킵니다.

Q. OS는 찾고자하는 페이지가 swap space의 어디에 위치해 있는지 어떻게 알까?
A. swap out이 발생하면 OS는 페이지만 swap space라 하는 디스크 공간으로 이동시키고, page table은 계속 물리 메모리에 상주하고 있습니다. 이 때 OS는 해당 페이지와 매핑되어 있는 PTE의 present bit를 0으로 바꿔주고 PFN영역에 'swap space에서의 페이지 위치'를 적어줍니다. 따라서 page-fault가 발생했을 때 PTE의 PFN 영역을 통해 페이지의 위치를 알고 이를 swap in 할 수 있습니다.

Page Fault Control Flow (Hardware)

else 		// TLB miss
	PTEAddr = PTBR + (VPN * sizeof(PTE))    
	PTE = AccessMemory(PTEAddr)
	if (PTE.Valid == False)
		RaiseException(SEGMENTATION_FAULT)
	else
		if (CanAccess(PTE.ProtectBits) == False)
			RaiseException(PROTECTION_FAULT)
			
		else if (PTE.Present == True)          // PTE가 메모리에 존재  
			TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
			RetryInstruction()
		else if (PTE.Present == False)		   // PTE가 메모리에 존재하지 않음
			RaiseException(PAGE_FAULT)      

TLB hit일 때의 분기문은 앞선 게시물에서 봤던 코드와 유사하여 따로 다루지 않았습니다.
PTEAddr를 구하는 과정에서 PTIndex 없이 PTBR과 VPN을 통해서 바로 알아내는 것을 보고 해당 CPU는 linear page table을 사용하는 것을 알 수 있습니다.

메모리에 접근하여 PTE를 가져온 후에, PTE의 valid bit를 통해 유효한 것을 확인합니다. 이후 protection bit를 확인하여 권한을 확인하고 present bit를 확인합니다. present bit이 0일 때, 즉 페이지가 메모리에 존재하지 않을 때, CPU는 RaiseException(PAGE_FAULT) 을 발생시키고, 발생한 page-fault exception을 처리하기 위해 OS의 page-fault handler가 실행됩니다.

Page Fault Control Flow (software)

PFN = FindFreePhysicalPage()      // 1. 빈공간 찾기
if (PFN == -1)                    // 2. 빈공간 없으면 쫓아내기
	PFN = EvictPage()
    
DiskRead(PTE.DiskAddr, PFN)       // 3. swap in

PTE.present = True                // 4. PTE 정보 갱신
PTE.PFN = PFN                     
RetryInstruction()                // 5. retry

위의 코드는 page-fault handler가 실행된 후 어떻게 동작하는지를 보여줍니다. 첫번째로 OS는 물리 메모리에서 빈 공간, swap in 될 페이지가 적재될 공간을 찾습니다. 만약 물리 메모리에 공간이 없다면 존재하는 페이지 중 하나를 swap out 시킵니다. (EvictPage())

이렇게 찾은 빈 공간에 swap space에 있던 페이지를 swap in 시켜줍니다. (DiskRead()) 이 때 disk I/O가 발생해서 프로세스는 blocked state가 됩니다.

disk I/O 작업을 마친 후에 해당 페이지와 매핑되어 있는 PTE에서 present bit와 PFN 정보를 갱신해주고 TLB_Lookup 과정부터 다시 실행시킵니다. retry가 되면 TLB miss가 발생하고, 메모리에 있는 PTE를 찾아서 TLB에 추가한 뒤 다시 retry를 하여 TLB hit가 되는 과정을 거칩니다. (retry가 2번 발생)

swap entry의 구성

• 메모리에 적재된 페이지의 PTE 구조
  

• swap out된 페이지의 PTE 구조
  

disk의 공간은 메모리보다 훨씬 크기 때문에 disk에서의 주소를 표현하려면 PFN보다 더 많은 수의 비트가 필요합니다. 따라서 위에서는 사용하지 않았던 비트도 모두 사용함으로써 더 큰 공간을 표현할 수 있습니다.
type을 통해 페이지가 어떤 파일에 존재하는지를 나타내고, offset을 통해 페이지가 한 파일에서 어느 위치에 있는지를 나타냅니다. swap space에 $2^6$ 개의 파일이 있고, 하나의 파일이 $2^2$$^4$ * 4KB(페이지 하나의 크기) = 64GB 크기라는 것을 통해 swap space의 크기가 메모리보다 훨씬 크다는 것을 알 수 있습니다.
0번째 인덱스에 있는 1개의 비트는 present bit입니다.

Page Replacement Policy

page-fault가 난 페이지를 swap in하려고 했는데 메모리에 빈 공간이 없다면 사용중인 메모리 공간을 뺏어야 합니다. 이 때 사용되는 evict 알고리즘의 OS의 성능에 중대한 영향을 미치기 때문에, 효율적으로 설계되어야 합니다.

1. Optimal replacement policy
해당 알고리즘은 미래에 가장 나중에 접근될 페이지를 교체하는 알고리즘입니다. 예측이 불가능하기 때문에 비현실적입니다.

2. FIFO
이 알고리즘은 제일 먼저 적재된 페이지가 가장 먼저 교체되는 알고리즘입니다. 큐의 사이즈가 커질수록 효율적일 것 같지만, 예상과 달리 큐의 사이즈가 커질수록 page-fault 비율이 증가합니다.

3. Least-Frequently-Used(LFU) and Least-Recently Used(LRU)
LFU는 가장 적게 사용되는 페이지를, LRU는 가장 오래 전에 사용된 페이지를 교체하는 알고리즘 입니다. 두 알고리즘 모두 페이지의 최근 히스토리를 기반으로 동작하는데, 각 PTE마다 히스토리를 저장하는 것은 오버헤드가 크다는 단점이 있어 정확히 구현하기가 어렵습니다.

4. Approximating LRU
따라서 페이지 교체 정책은 LRU의 근사 구현인 clock 알고리즘을 사용합니다. 이는 PTE의 reference bit를 활용하여 구현되었습니다.

페이지가 처음 메모리에 적재되면 reference bit는 1로 설정됩니다. 이후 메모리 공간이 부족하여 어떤 페이지를 쫓아내야하는 상황이 발생하면, 바늘이 시계방향으로 돌면서 reference bit가 0인 페이지를 찾습니다. 이 때 reference bit이 1인 페이지를 만난다면 0으로 바꿔줍니다. 0인 페이지를 만나면 그 페이지를 swap space로 쫓아내고, 그 자리에는 swap in 된 페이지가 들어옵니다. 만약 메모리에 적재된 페이지에 재접근한다면 reference bit를 1로 만들기 때문에 최근에 접근한 페이지가 eviction 대상에서 빠져나갈 수 있습니다.

- dirty pages
page replacement가 발생하면, disk I/O 작업은 swap out 될 때 write 작업 1번, swap in 될 때 read 작업 1번, 이렇게 총 2번 발생합니다. 따라서 disk I/O의 횟수를 줄이기 위해 수정이 불가능한 페이지를 주로 eviction 시킵니다.
만약 페이지가 code segment처럼 read, execute만 가능하여 수정될 수 없는 페이지라면, swap out 발생 시 disk에 write하는 작업 없이 교체할 수 있습니다. 해당 code 페이지가 다시 필요하면 기존에 디스크에 저장되어 있던 executable 파일에서 다시 가져올 수 있기 때문입니다.
따라서 페이지 교체가 필요한 상황에서 OS는 가급적 수정이 불가능한 페이지를 evict 함으로써 I/O 횟수를 줄이려고 노력합니다.