Beyond Physical Memory: Mechanisms
- Assumption
지금까지는 모든 running process들의 address space가 메모리에 들어간다는 가정을 했다.
하지만 이는 비현실적이고, 따라서 memory hierarchy를 더 추가하려 한다.
많은 페이지를 저장할 수 있을 만큼 큰 메모리는 hard disk drive이다. 하드 디스크는 느리지만 매우 크며, 이는 과거의 memory overlay와 대조된다.
Swap Space
디스크에 페이지를 저장하고 가져올 수 있는 장소가 필요한데 이를 swap space라고 부른다.
디스크를 읽고 쓰기 위해 OS는 주어진 페이지의 disk address를 알고 있어야 한다. 사용할 수 있는 페이지의 최대 개수와 연관 있는 swap space의 크기도 중요하지만, 우선 아주 크다고 가정하자.
아래 그림은 swap space를 사용하는 단적인 예시이다.
4개의 물리 주소 공간과 8개의 swap space가 있다. Proc 3은 모든 페이지가 swap space에 있으므로 running 중이지 않다는 것을 알 수 있다.
The Present Bit
memory references가 발생해서 H/W가 address translation을 한다고 가정하자. (instruction fetch나 data access라고 가정)
H/W는 VPN을 추출하고 TLB에 있는지 확인할 것이다. 만약 TLB miss가 발생하면 H/W는 page table base register과 VPN을 index 삼아 PTE를 찾을 것이다. 페이지가 valid하고 physical memory에 존재하면, 해당 PTE에서 PFN을 추출해서 TLB hit를 발생시킬 것이다.
하지만 page를 disk에서 swap할 것이라면 몇 가지 과정이 추가되어야 한다.
H/W가 PTE를 살펴볼 때 페이지가 실제 메모리에 있는지 없는지 present bit로 판단한다. present bit가 0이면 page가 physical memory에 없다는 의미이고, page fault가 발생한다. page fault가 발생하면 OS는 page-fault handler를 호출한다.
The Page Fault
present가 0이어서 TLB miss(1)가 발생했다고 가정해보자. 그러면 OS는 page-fault handler를 handle 해야 한다.
page swap을 위해 OS는 PTE의 일부 bit를 사용할 수 있다. OS가 페이지에 대한 페이지 fault를 받으면 PTE에서 주소를 찾고 페이지를 메모리로 fetch 하기 위해 디스크에 요청을 한다. Disk I/O가 끝나면 OS는 page table의 해당 page에 present bit를 마크한다.
PTE의 PFN field를 update 하고 새로 fetch 한 page의 in-memory location을 기록하며, 같은 instruction을 재실행 한다.(S/W)
그러면 TLB miss(2)가 한 번 더 발생한다.(OS kernel의 trap handler가 retry instruction), 이 TLB miss가 translation 정보를 TLB에 기록할 것이다.(이번 miss에서 TLB를 update. 그리고 다시 실행해서 TLB hit)
알다시피 I/O 처리 중인 process는 block 상태이다. 그리고 page fault가 처리되는 동안 다른 ready 프로세스가 run 할 수 있다.
I/O는 cost가 많이 들기 때문에 I/O(page fault)와 다른 프로세스의 overlap은 multiprogramming system에서 효율적이다.
Page Fault Control Flow
아래 코드는 H/W가 address translation 하고, OS가 page fault를 처리하는 control flow이다.
- Page-Fault Control Flow Algorithm (Hardware)
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True) // TLB Hit
if (CanAccess(TlbEntry.ProtectBits) == True)
Offset = VirtualAddress & OFFSET_MASK
PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
Register = AccessMemory(PhysAddr)
else
RaiseException(PROTECTION_FAULT)
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)
// assuming hardware-managed TLB
TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
RetryInstruction()
else if (PTE.Present == False)
RaiseException(PAGE_FAULT)TLB miss가 발생했을 경우 크게 세 가지 분기로 나뉜다.
먼저 present와 valid bit가 모두 true인 TLB miss이다. 이 경우는 앞서 많이 다뤘던 것처럼 PTE에서 PFN을 뽑아내고 instruction을 다시 실행해 TLB hit를 발생시킨다.
두 번째로 valid하지만 present bit가 fault인 경우이다. 이 경우는 page-fault handler가 실행되어야 한다. page는 valid하지만 physical memory에 존재하지 않는 겨우이다.
세 번째로 invalid 페이지에 access 하는 경우이다. 이 경우는 PTE의 다른 bit를 보지 않고 H/W가 invalid access를 trap 하고 난 뒤 프로세스를 종료한다.
다음은 S/W가 page fault를 처리하는 알고리즘이다.
- Page-Fault Control Flow Algorithm (Software)
PFN = FindFreePhysicalPage()
if (PFN == -1) // no free page found
PFN = EvictPage() // run replacement algorithm
DiskRead(PTE.DiskAddr, pfn) // sleep (waiting for I/O)
PTE.present = True // update page table with present
PTE.PFN = PFN // bit and translation (PFN)
RetryInstruction() // retry instruction먼저 OS는 soon-to-be-faulted-in page가 상주할 physical frame을 찾아야 한다.
만약 그런 공간이 없으면 replacement policy에 따라 page out을 하고 free 해야 한다.
Physical frame을 찾으면 handler는 swap space에서 page를 읽기 위해 I/O 요청을 보낸다.
마지막으로 실행이 끝나면 OS는 page table을 update 하고 instruction을 다시 실행한다.
그러면 TLB miss가 발생할 것이고, 다시 retry 할 때 TLB hit가 발생할 것이다.
When Replacements Really Occur
작은 memory를 free 하는 것을 유지하기 위해, OS는 page를 언제 제거할지 결정하는 데 도움이 되는 HW(High Watermark)와 LW(Low watermark)를 사용한다.
OS가 필요한 page 수가 LW page 보다 적으면 free를 담당하는 swap daemon(= page daemon)이라고 불리는 스레드가 백그라운드에서 실행된다.
swap daemon은 HW가 사용가능한 page가 있을 때까지 페이지를 제거하고 sleep 상태가 된다.
한 번에 replacement를 여러 번 수행하면 새로운 성능 최적화가 가능해진다.
예를 들어 많은 시스템에서 여러 페이지를 clustering하거나 grouping해서 swap partition에 한 번에 기록해 disk 효율이 향상된다.
Summary
present bit를 이용해 page가 physical memory에 있는지 확인한다.
Physical memory에 page가 없으면 OS는 page fault를 처리하기 위해 page-fault handler를 처리해야 한다. Disk에서 memory로 page를 옮기기 위한 공간을 찾고, 필요하다면 replace도 한다.
Uploaded by Notion2Tistory v1.1.0