Paging: Introduction PDF

18. Paging: Introduction Operating System: Three Easy Pieces Youjip Won 1 Concept of Paging  Paging splits up address space into fixed-sized units called a page.  Versus Segmentation: variable size of logical segments(code, stack, heap,...

18. Paging: Introduction Operating System: Three Easy Pieces Youjip Won 1 Concept of Paging  Paging splits up address space into fixed-sized units called a page.  Versus Segmentation: variable size of logical segments(code, stack, heap, etc.)  With paging, physical memory is also split into some number of pages called a page frame.  Page table per process is needed to translate the virtual address to physical address. Youjip Won 2 Advantages Of Paging  Flexibility: Supporting the abstraction of address space effectively  Don’t need assumption how heap and stack grow and are used.  Simplicity: ease of free-space management  The page in address space (virtual) and the page frame (physical) are the same size.  Easy to allocate and keep a free list – fragmentation not an issue.` Youjip Won 3 Example: A Simple Paging  128-byte physical memory with 16 bytes page frames (8 page frames)  64-byte address space with 16 bytes pages (4 pages) 0 page frame 0 of reserved for OS physical memory 16 (unused) page frame 1 32 0 (page 0 of page 3 of AS page frame 2 16 the address space) 48 (page 1) page 0 of AS page frame 3 32 64 (page 2) (unused) page frame 4 48 80 (page 3) 64 page 2 of AS page frame 5 96 A Simple 64-byte Address Space (unused) page frame 6 112 page 1 of AS page frame 7 128 64-Byte Address Space Placed In Physical Memory Youjip Won 4 Address Translation  Two components in the virtual address  VPN: virtual page number VPN = 2 bits (22 = 4, the number of pages in the process  Offset: offset within the page space) offset = 4 bits (24 = 16, the size of each page) VPN offset Va5 Va4 Va3 Va2 Va1 Va0  Example: virtual address 2110 (101012) in 64-byte address space VPN offset 0 1 0 1 0 1 Youjip Won 5 Example: Address Translation  The virtual address 2110 in 64-byte address space 0 page frame 0 of VPN offset reserved for OS physical 16 memory (unused) page frame 1 Virtual 0 1 0 1 0 1 32 Address page 3 of AS page frame 2 48 page 0 of AS page frame 3 Address 64 Translation (unused) page frame 4 80 page 2 of AS page frame 5 96 Physical 1 1 1 0 1 0 1 (unused) page frame 6 Address 112 page 1 of AS page frame 7 PFN offset 128 Physical Memory Youjip Won 6 Example: Page Table in Kernel Physical Memory 0 page table page frame 0 of physical memory 3752 16 (unused) page frame 1 32 page 3 of AS page frame 2 48 page 0 of AS page frame 3 64 (unused) page frame 4 80 page 2 of AS page frame 5 96 (unused) page frame 6 112 page 1 of AS page frame 7 128 Physical Memory Youjip Won 7 Where Are Page Tables Stored?  Page tables can get awfully large  32-bit address space with 4-KB pages, 20 bits for VPN   Page tables for each process are stored in memory. 232 = 4,294,967,296 232/4096 = 1,048,576 (1Gig) pages log2(1,048,576) = log10(1,048,576)/log10(2) = 20 20 bits to keep track of 1 gig pages Youjip Won 8 What Is In The Page Table?  The page table is just a data structure that is used to map the virtual address to physical address.  Simplest form: a linear page table, an array VP0 PTE VP1 PTE VP2 PTE VP3 PTE  The OS indexes the array by VPN, and looks up the page-table entry. Youjip Won 9 Common Flags Of Page Table Entry  Valid Bit: Indicating whether the particular translation is valid.  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 Youjip Won 10 Example: x86 Page Table Entry 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 PWT R/W PCD U/S PAT PFN D G A P An x86 Page Table Entry(PTE)  P: present  R/W: read/write bit  U/S: supervisor  A: accessed bit  D: dirty bit  PFN: the page frame number Youjip Won 11 Paging: Too Slow  To find a location of the desired PTE, the starting location of the page table is needed.  For every memory reference, paging requires the OS to perform one extra memory reference. Youjip Won 12 Accessing Memory With Paging 1 // Extract the VPN from the virtual address 2 VPN = (VirtualAddress & VPN_MASK) >> SHIFT 3 4 // Form the address of the page-table entry (PTE) 5 PTEAddr = PTBR + (VPN * sizeof(PTE)) [Page Table Base Register] 6 7 // Fetch the PTE 8 PTE = AccessMemory(PTEAddr) (here is our extra memory access) 9 10 // Check if process can access the page 11 if (PTE.Valid == False) 12 RaiseException(SEGMENTATION_FAULT) 13 else if (CanAccess(PTE.ProtectBits) == False) 14 RaiseException(PROTECTION_FAULT) 15 else 16 // Access is OK: form physical address and fetch it 17 offset = VirtualAddress & OFFSET_MASK 18 PhysAddr = (PTE.PFN > 4 = 000001.  OFFSET_MASK = 001111 (0x0f) – Mask out the VPN bits  If Virtual Address = 010101, then 010101 & OFFSET_MASK = 0101 Youjip Won 14 A Memory Trace  Example: A Simple Memory Access int array;... for (i = 0; i < 1000; i++) array[i] = 0;  Compile and execute prompt> gcc –o array array.c –Wall –o prompt>./array  Resulting Assembly code 0x1024 movl $0x0,(%edi,%eax,4) 0x1028 incl %eax 0x102c cmpl $0x03e8,%eax 0x1030 jne 0x1024 Youjip Won 15 Assumptions  Address Space = 64KB  Page Size = 1KB  Number Virtual Pages = 64  Linear Page Table located at Physical Address 1024 Youjip Won 16 A Virtual(And Physical) Memory Trace Page Table 1224 3 1174 Page Table(PA) Page Table 1124 1074 1 5 7 9 1024 40100 7132 Array(VA) Array(PA) mov 40050 7282 4 40000 7232 1124 4196 Code(VA) mov inc cmp jne Code(PA) 1074 4146 2 6 8 10 1024 4096 0 10 20 30 40 50 Memory Access Youjip Won 17  Disclaimer: This lecture slide set was initially developed for Operating System course in Computer Science Dept. at Hanyang University. This lecture slide set is for OSTEP book written by Remzi and Andrea at University of Wisconsin. Youjip Won 18