Paging : Linear Tables
: 모든 process마다 page table이 하나씩 있음.
page table : 4byte entry
-> Page table은 너무 큼
Paging : Smaller Tables
: 16KB 페이지와 4byte page table entry가 있다고 가정 (page 하나를 위한 entry하나)
-> Big pages는 internal fragmentation 유발
Problem
- process의 entries address space를 위한 single page table
: 대부분의 page table들은 사용되지 않음
Hybrid Approach : Paging and Segments
- Segmentation
- virtual address space를 segments로 나눔
- 각 segment는 다양한 length 가질 수 있음
- Paging
- segment를 고정된 크기의 pages로 나눔
- 각 segment는 page table 구성
- 각 segment는 해당 segment에 대한 physical address, limit를 추적함
-> page table의 의미없는 공간 줄이기 : Segmentation, Paging
Simple Example of Hybrid Approach
- 각 process는 3개의 page table이 연결되어 있음
: VPN에서 상위 두개를 빼서 seg
TLB miss on Hybrid Approach
- HW는 page table에서 physical address로
- HW는 segment bit(SN)를 사용해 사용할 base and bound 쌍을 결정
- HW는 physical address를 가져와 VPN과 결합하고 Page Table Entry의 주소를 형성
SN = (VirtualAddress & SEG_MASK) >> SN_SHIFT
VPN = (VirtualAddress & VPN_MASK) >> VPN_SHIFT
AddressOfPTE = Base[SN] + (VPN * sizeof(PTE))Problem of Hybrid Approach
- 크기가 크지만 잘 쓰지 않는 heap이 있으면 page table 낭비 많이 발생 가능
-> external fragmentation이 다시 발생하는 원인 (할당해놓고 안쓰는게 많음)
Multi-level Page Tables
- linear page table을 tree와 같은 것으로 바꿈
: page table을 page-sized units로 쪼갬,
- 모든 page table entries의 page들이 유효하지 않은 경우 page table의 해당 page를 할당하지 않음
- page table의 page가 유효한지 여부 보려면 page directory 사용
Multi-level Page Tables : Page directory
: Linear Page Table의 PFN 203 & 203은 invalid하기 때문에 할당되지 않았음 -> page table을 page크기의 단위로 나누고 해당 page table의 page invalid하다면 메모리에 할당하지 않음
- page directory에는 page table의 page 당 하나의 entry가 포함됨 (page directory entries로 구성됨)
- PDE에는 유효한 비트 및 PFN이 있음
Multi-level Page Tables : Advantage & Disadvantage
- Advantage
- 사용 중인 address space의 양에 비례해 page table 공간 할당
- OS는 page table을 할당하거나 확장해야 할 때 다음 free page를 잡을 수 있음
- Disadvantage
- Multi-level table은 time-space trade-off의 예시임
- 복잡함
A Detailed Multi-level Example
: address space가 16KB(2^4, 2^10 -> 14bits),
page size가 64bytes(6bit) ->
offset도 6bits, VPN = 14-6 = 8bits
A Detailed Multi-level Example : Page Directory Idx
: page directory는 page table의 page마다 하나의 Entry 필요함.
page directory의 entry가 invalid하면 예외 발생
-> page directory entry가 valid하다면 이 PDE가 가리키는 page table의 page에서 page table entry 가져옴
-> 그때부터 page table index를 그 page table을 가리키는 index로 사용할 수 있음 !!!
- page directory는 모두 할당되어야 함
Two-level Page Table Scheme
- 32bit Processor의 address translation
- logical address은 20bits(page number), 12bits(page offset)
- page table자체가 page이기 때문에 page number가 더 나뉘어져 있음
- 10bits(page directory - outer page table), 10bits(page table - inner page table)
Three-level Page Table Scheme
Multi-level Page Table Control Flow
VPN = (VirtualAddress & VPN_MASK) >> SHIFT // Virtual Page Number를 추출해냄
(Success,TlbEntry) = TLB_Lookup(VPN) // TLB가 이 VPN에 대한 translation을 보유하고 있는지 확인
if(Success == True)
if(CanAccess(TlbEntry.ProtectBits) == True)
// if문 만족 시 해당 TLB 항목에서 page frame number, 원하는 physical address와 access memory를 추출
Offset = VirtualAddress & OFFSET_MASK
PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
Register = AccessMemory(PhysAddr)
else RaiseException(PROTECTION_FAULT);
else // full multi-level lookup 수행
else // Page Directory Index를 추출
PDIndex = (VPN & PD_MASK) >> PD_SHIFT
PDEAddr = PDBR + (PDIndex * sizeof(PDE))
// Page Directory Entry를 가져옴
PDE = AccessMemory(PDEAddr)
if(PDE.Valid == False)
// if문 만족 시 : Page Directory Entry의 valid flag를 체크해 true가 되면, page table로 부터 page table entry를 가져옴
RaiseException(SEGMENTATION_FAULT)
else // PDE가 valid (PTE를 Page table에서 가져옴)Translation Process : Remember TLB !
PTIndex = (VPN & PT_MASK) >> PT_SHIFT
PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))
PTE = AccessMemory(PTEAddr)
if(PTE.Valid == False)
RaiseException(SEGMENTATION_FAULT)
else if(CanAccess(PTE.ProtectBits) == False)
RaiseException(PROTECTION_FAULT);
else
TLB_Insert(VPN, PTE.PFN , PTE.ProtectBits)
RetryInstruction()Inverted Page Table
[page table은 process마다 page table가지고 있어야 함. 사용되지 않는 page가 있어도 page 최대 개수만큼 page table entry가 있어야함]
-> Inverted Page Table 등장
- page frame마다 page table 하나 (process마다가 아님), page table entry개수가 physical memory의 frame 개수와 동일함
- 각 page table저장하는데 필요한 memory는 감소하지만 순차 탐색하기 때문에 탐색에 많은 시간이 소요
