08-Paging

in Computer Science on OperatingSystem, Os, Computer-science


Paging의 컨셉

  • 대부분의 space-management problem을 해결할 때 사용하는 두 접근법
    • Segmentation : variable size of logical segments(code,heap,stack,etc..) ⇒ external fragmentation ⇒ 시간이 갈수록 external fragmentation으로 새로운 allocation이 어려움
    • Paging : address space를 page라 불리는 fixed-size 단위로 분할
  • Paging으로, physical memory 또한 page frame으로 분할됨 ⇒ virtual address의 page와 physical address의 page frame은 size가 동일함

https://snowapril.github.io/assets/img/post_img/08-Paging%20f01b7c655d514ee798fcd73a61faecfc/Untitled.png

  • virtual address를 physical address로 변환하기 위해 process마다 page table이 하나씩 있어야함 ⇒virtual address space가 process마다 존재하니, 이를 변환하는 page table 또한 process마다 존재해야한다

Paging

  • process의 physical address space가 non-contiguous하도록 함 ⇒ virtual memory를 page 단위로 divide ⇒ physical memory도 page frame 단위로 divide ⇒ page size는 2의 승수여야함(보통 512B - 8KB)
  • memory management를 쉽게함 ⇒ OS가 모든 free page frames를 tracking 함 ⇒ $n$ pages 크기의 program을 실행하기 위해서 $n$ free frames를 찾음 ⇒ virtual address에서 physical address로의 변환을 위한 page table을 setup함 ⇒ external fragmentation이 없음

https://snowapril.github.io/assets/img/post_img/08-Paging%20f01b7c655d514ee798fcd73a61faecfc/Untitled%201.png

Simple paging example)

https://snowapril.github.io/assets/img/post_img/08-Paging%20f01b7c655d514ee798fcd73a61faecfc/Untitled%202.png

Advantage of paging

  • flexibility : address space의 abstraction을 효과적으로 지원 ⇒ heap과 stack이 어떻게 grow하고 사용되는지에 대한 가정이 필요없음
  • simplicity : ease of free-space management ⇒ address space의 page와 page frame은 size가 같음 ⇒ allocation이 쉽고, free list 관리하기도 쉬움

Address translation

https://snowapril.github.io/assets/img/post_img/08-Paging%20f01b7c655d514ee798fcd73a61faecfc/Untitled%203.png

Virtual address의 2가지 components

  • VPN : virtual page number
  • offset : page 안에서의 offset
  • VPN은 page table에서 index로 사용됨
  • offset의 bit수로 page size를 알 수 있고, VPN으로 page table에 PTE의 개수를 알 수 있음
  • Page table은 Page Frame Number(PFN)을 결정함
  • Physical address는 <PFN, offset>, virtual address는 <VPN, offset>
  • Page tables : ⇒ managed by OS ⇒ VPN to FPN mapping ⇒ virtual address space의 page 하나마다 하나의 page table entry(PTE)

https://snowapril.github.io/assets/img/post_img/08-Paging%20f01b7c655d514ee798fcd73a61faecfc/Untitled%204.png

Address translation example)

64-byte address space에서 virtual address 21의 translation

https://snowapril.github.io/assets/img/post_img/08-Paging%20f01b7c655d514ee798fcd73a61faecfc/Untitled%205.png

  • 64byte address space : 64byte == $2^6$byte ⇒ virtual address는 6bit
  • 16byte pages ⇒ offset이 4bit이고, VPN이 2bit임을 알 수 있음

Address translation example)

https://snowapril.github.io/assets/img/post_img/08-Paging%20f01b7c655d514ee798fcd73a61faecfc/Untitled%206.png

  • virtual address : 32bits ⇒ $2^{32}$bit address space
  • physical address : 20bits ⇒ $2^{20}$ bit
  • page size : 4KB ⇒ $2^{12}$ : offset이 12bit고 VPN이 20bit다
  • page table 하나의 page table entry 개수는 $2^{20}$

Where are page tables stored?

  • Page tables는 몹시 커질 수가 있음 ⇒ 32bit address space with 4KB pages, 20bits for VPN ⇒ $2^{20}$ * 4bytes per page table entry(계산을 위한 예제) = 4MB

Example : Page table in kernel physical memory

https://snowapril.github.io/assets/img/post_img/08-Paging%20f01b7c655d514ee798fcd73a61faecfc/Untitled%207.png

  • OS가 page table을 관리하고 process가 동작하는 동안은, 해당 process의 page table이 memory에 상주한다.

What is in the page table?

  • page table은 virtual address를 physical address로 mapping하는 data structure일 뿐이다. ⇒ simplest form : array
  • OS는 VPN으로 page table을 index하고, page-table entry를 look up 함

Common flags of page table entry

  • Valid bit : indicating whether the particular translation is valid ⇒ virtual address가 referenced 될 때마다 check하는 flag
  • Protection bit : indicating whether the page could be read from, written to, or executed from
  • Present bit : indicating whether this page is in physical memory or on disk(swapped out)
  • Dirty bit : indicating whether the page has been modified since it was brought into memory
  • Reference bit(Accessed bit) : indicating that a page has been accessed

x86 page table entry example)

https://snowapril.github.io/assets/img/post_img/08-Paging%20f01b7c655d514ee798fcd73a61faecfc/Untitled%208.png

Another problem of Paging: Too slow

  • 원하는 PTE의 위치를 찾기 위해서 page table의 starting location이 필요
  • 모든 memory reference마다, paging은 OS가 one more extra memory reference를 수행하게 만듬 ⇒ virtual address를 physical address로 바꾸기 위해 page table을 찾아야함 ⇒ page table의 주소를 참조하기 위해 memory 참조 한 번 ⇒ page table을 토대로 원하는 주소를 memory에서 참조를 또 한번
// extract the VPN from the virtual address
VPN = (VirtualAddress & VPN_MASK) >> VPN_SHIFT;
// From the address of page-table entry (PTE)
// PTBR : Page Table Base Register
PTEAddr = PTBR + sizeof(PTE) * VPN;
//! Fetch the PTE
PTE = AccessMemory(PTEAddr);
if (PTE.Valid == false) 
	RaiseException(SEGMENTATION_FAULT);
else if (CanAccess(PTE.Protection)== false)
	RaiseException(PROTECTION_FAULT);
else {
	// access is OK : form physical memory address and fetch it
	offset = VirtualAddress & OFFSET_MASK;
	PhysAddr = (PTE.PFN << PFN_SHIFT) | offset;
	Register = AccessMemory(PhysAddr);
}

Memory trace example)

int array[1000];
for (i = 0; i < 1000; ++i)
	array[i] = 0;

Resulting assembly code

0x1024 movl $0x0, (%edi, %eax, 4) #(%edi, %aeax, 4) == %edi + 4 * %eax
0x1028 incl %eax
0x102c cmpl $0x03e8, %eax
0x1030 jne 0x1024

https://snowapril.github.io/assets/img/post_img/08-Paging%20f01b7c655d514ee798fcd73a61faecfc/Untitled%209.png

assumption : 64KB address space, 1KB page

빨간 박스를 먼저 보자.

  1. CPU는 먼저 virtual address PC(1024)에 위치한 mov instruction을 fetch 해와야 함
  2. mov instruction fetch를 해오기 위해 page table reference 1번과 memory reference 1번으로 총 2번의 reference가 일어난다. ⇒ virtual address(1024) → physical address (4096)
  3. 다음으로, array[i] = 0을 수행하기 위해서, 즉, (%edi, %eax, 4)에 해당하는 virtual address translation을 위해서 또 2번의 reference가 일어남 ⇒ virtual address(40000) → physical address (7232)
  4. incl instruction fetch를 위해 2번의 reference ⇒ virtual address(1028) → physical address(4100)
  5. cmpl instruction fetch를 위해 2번의 reference ⇒ virtual address(102C) → physical address(4104)
  6. jne instruction fetch를 위해 2번의 reference ⇒ virtual address(1030) → physical address(4108)

정리하자면, page table을 memory에서 reference 하는 동작 때문에, memory reference의 횟수가 2배로 늘어났음

Demang paging 기법

  • 기본 concept : program을 실행할 때, 모든 data를 memory에 다 올려놓을 필요가 있을까? ⇒ 영화를 시청할 때, 영화의 ending credit에 해당하는 데이터를 처음 시작할때부터 메모리에 미리 들고올 필요가 있을까?
  • 필요할때마다 page를 memory에 들고옴
  • pages는 자기가 속한 physical memory frames에서 evicted 될 수 있다
  • page의 이동은 process에게는 transparent하다
  • Benefits ⇒ Less I/O needed ⇒ Less memory needed ⇒ faster response ⇒ More processes

Page fault (Demang paging의 문제점)

  • Invalid PTE를 접근하면 CPU가 raise exception(Valid bit로 check)
  • Major page faults(Page가 memory에 아예 존재하지 않을 때) ⇒ page가 valid한데 memory에 loaded되지 않았을 때 ⇒ disk I/O를 통해 읽어와야함
  • Minor page faults(원하는 page가 이미 memory에 올라와있는 경우) ⇒ ex) shared library의 경우, printf에 해당하는 virtual page가 존재하지 않지만, 다른 어떤 process가 printf를 쓰고 있을 수 있다. 그걸 가져옴 ⇒ disk I/O 없이 page fault를 해결할 수 있음 ⇒ prefetched page를 이용
  • Invalid page faults ⇒ segmentation violation : the page is not in use

Handling Page Faults

https://snowapril.github.io/assets/img/post_img/08-Paging%20f01b7c655d514ee798fcd73a61faecfc/Untitled%2010.png

Paging의 Pros & Cons

Pros

  • No external fragmentation
  • Fast to allocate and free ⇒ a list or bitmap for free page frames ⇒ allocation : no need to find contiguous free space ⇒ free : no need to coalesce with adjacent free space
  • Easy to “page out” portions of memory to disk ⇒ page size is chosen to be multiple of disk block sizes ⇒ use valid bit + present bit to detect reference to “paged-out” pages ⇒ can run process when some pages are on disk
  • Easy to protect and share pages

Cons

  • Internal fragmentation ⇒ Page크기가 커질 수록 wasted memory로 커진다
  • Memory reference overhead ⇒ instruction 마다 memory reference가 두배가 되었음 ⇒ solution : get hardware support (TLBs)
  • Storage needed for page tables ⇒ Needs one PTE for each page in virtual address space ⇒ solution : store valid PTEs only or page the page table



© 2020.11. by snowapril

Powered by snowapril