[운영체제] 9. Paging Schemes : Smaller page tables

1. 기존 linear table의 문제
   1. 프로세스 당 page table 소유 : 프로세스 당 4MB, 용량 이슈 존재
   2. 그렇다고 page size를 높여서 page table을 작게 만드는 것은 internal fragmentation
2. 해결법 A : page table을 segment마다 만들기 (stack에 대한 page table, heap에 대한 page table 등)
   1. 여전히 heap에 대한 page table은 크게 잡히게 됨; 동적으로 할당되므로
   2. 영역의 크기가 제각각이므로 또 다시 external fragment가 생김 → segment마다 page table으을 관리해야 하므로
3. 해결법 B : linear table을 multi-level page table로 만들기 (B+-tree 구현 등을 통해)
   1. page table을 page 단위로 자른다
   2. page table entry들의 모든 page가 invalid하면 → 전부 할당하지 않는다
   3. page table의 page의 유효성 여부를 확인하기 위해 page directory 사용
   4. 장/단점
      1. 장점
         1. page table이 차지하는 공간 줄일 수 있음
         2. segment 방식에 비해 단순함 : External Fragment 줄일 수 있다
      2. 단점
         1. time-spcae trade off: 시간을 주고 공간을 샀다
         2. 복잡성 : Paging 방식처럼 memory access 역시 증가
   5. Multi-level Page Table Control Flow

      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 // perform the full multi-level lookup
      	PDIndex = (VPN & PD_MASK) >> PD_SHIFT
      	PDEAddr = PDBR + (PDIndex * sizeof(PDE))
      	PDE = AccessMemory(PDEAddr)
      	if(PDE.Valid == False)
      		RaiseException(SEGMENTATION_FAULT)
      	else // PDE is Valid: now fetch PTE from PT
      		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()​

   6. Inverted Page Tables
      1. system의 각 physical page의 entry를 하나의 single page table로 둘 것
      2. 이 entry는 어떤 프로세스가 이 페이지를 쓰고, 어떤 프로세스의 virtual page가 이 physical page와 mapping되어 있는지 알려줌