Intro to OS - Virtual Memory 1 Printable PDF

The Operating System PART TWO Virtual Memory What you have all been waiting for! What we covered last time Virtualization ○ Taking a physical shared device and giving each process the illusion of its own separate, non-shared device. How the Operat...

The Operating System PART TWO Virtual Memory What you have all been waiting for! What we covered last time Virtualization ○ Taking a physical shared device and giving each process the illusion of its own separate, non-shared device. How the Operating System Virtualizes the CPU ○ Interrupts (ie timer) ○ Saving/Restoring process context ○ Scheduler “Refresher” on Virtualization: Another Analogy Two virtual cokes The physical coke Virtualizing the CPU gives the illusion that each process runs alone on it’s own CPU. OS virtualizes CPU via time sharing and scheduling! Virtualizing Memory gives the illusion that each process has its own address space. Physical Memory “Byte Addressable” memory hardware Process’s View of Memory (aka the illusion) “Address Space” Ranging from 0x00 to 0xff (some max address which depends on the size of the address space) mov [0x54261], 3 ○ All assembly instructions we have seen are VIRTUAL addresses The Problem p1 p2 p3 p4 We want to support many process address spaces with our single physical memory. Attempt 1: Place them in non-overlapping regions! But what happens when the CPU executes a memory lookup? proc 3 mov [0x54261], 3 ?? Also, what happens when, (via timesharing), we switch and start running another process? Attempt 1: Address Translation The MMU is a piece of hardware physical_address = in CPU. virtual_address + base CPU (running Assert that virtual address is proc3) WITHIN the bound. virtual Memory Management Marks the addr. Unit start of proc3 (MMU) VAS. base physical bound addr. Marks the end of proc3 VAS.  Physical Memory 0x0 When the OS Now we have: 0x1a switches running Proc 3 addr space processes, it When OS runs proc 3, it sets must save and the BASE register to: 0x2b restore 0x1a base/bound … register in It sets the BOUND register 0x30 MMU. to: 0x2b Proc 1 addr space Just like OS save/restores If proc3 accesses address: 0x41 … other context! 0x03, it goes to physical 0xee address: 0x1a + 0x03 = 0x1d Proc 2 addr space 0xff Free Space Management When the OS sees a request to start new process, it needs to find FREE space for that process’s memory. To do so the OS: Maintains free list: an internal data structure to track what physical memory is FREE. Dynamic Relocation: Move around other processes’ address spaces to get bigger chunks of free space. ○ hanging the base/bound register allows us to dynamically move around in physical memory, where our program’s memory resides! ○ The OS can freely optimize the free space in memory (unlike malloc) Good Properties of Address Translation FAST (occurs in hardware via MMU) Isolated Address Spaces ○ Processes CAN’T write/read in other processes’ address spaces! Process CAN’T tell it’s addresses are being translated! Are we done? Are there any issues? How big is the Virtual Address Space of a Process on our computer? How much RAM do we have? (experiment time!) Issue: Wasted Space… Unused space! Bottom of stack = 0x7fff38b0d134 Code = 0x5dd5e9531189 Difference = 37 terabytes? INTERNAL FRAGMENTATION! Idea: Segmentation Can we segment up our address space, and allocate each dynamic section separately? - I.e. three sets of base/bounds registers, one for static (data/text), one for stack, one for heap. - On mmap adjust base/bound of heap section - When stack grows to be large, adjust base/bound of stack section. Problems: - Too many assumptions about address space, not generalizable. - Difficult to manage variable sized pieces of memory floating around Attempt 2: Paging Let’s not allocate the entire virtual address space in physical memory when the process starts. Instead, let’s allocate physical memory in chunks, as needed! Paging Paging Break up virtual address space and physical memory into fixed-sized chunks called “pages”. Map virtual pages to a corresponding physical page. Create mapping Demand Paging Only allocate the page when it is actually used by the process. Mini Example 64 byte Virtual Address Space 128 byte Physical Address Space 16 byte pages  Mapping VPN to PPN: The Page Table What will map VPN to PPN? ○ A page table! The OS manages/sets up the page table, which the MMU uses to perform translation. VPN PPN 0 3 1 7 2 5 3 2 How to do Address Translation now? MMU replaces virtual page number with physical page 0x15 number (from page table), to get physical address. 64 bit address space. Need to represent 0 - 63 in binary. ○ 6 bit virtual addresses! Have 128 bytes of physical 0x75 memory… ○ 7 bit physical addresses! A Note on Offset PPN 7 The offset bits tell us WHERE in the 0x0 A 0x1 B page to grab our byte. 0x2 C 0x3 D 4 bits of offset, indicates 24 = 16 byte 0x4 E 0x5 F pages. 0x6 G 0x7 H What is the value of the byte at 0x8 I 0x9 J the below physical address 0xa K access? 0xb L 0xc M 0xd N 0xe O 0xf P What’s in a Page Table? Let’s imagine that the Page Table lives in physical memory. The OS manages the page table. The MMU now contains a register to point to the page table. Linear Page Table uses VPN as an array index to find PPN. Page Table Entry Includes also: Resident (or Present/Valid) bit. Dirty bit (if page has been modified/written). Could also have permission bits, etc! Let’s Zoom Out – Multiple Running Processes MMU Example 256 bytes/page VPN R D PPN 16 virtual pages 8 physical pages 0 1 0 2 12-bit VA (4 bits of vpn, 8 1 0 – – bits offset) 11-bit PA (3 bits of ppn, 8 2 1 0 4 offset). 3 1 0 1 Virtual Address: 0x3c8 4 1 0 0 0 0 1 1 1 1 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 0 0 Problem: Our memory is SMALL! Fix 1: Only allocate page on demand. (pretty good!) But… Let’s say we have an array of 100.bmp images = 1 GB of memory. 33 processes and our computer crashes? Additional Modification: Page Swapping Disk has a LOT of storage (1 TB). Plan: Swap pages from and then onto disk! Back into play: the Resident bit and dirty bit! Resident Bit = 0 when the page is in storage, =1 when it is in memory Dirty bit = 1 when we have modified a page in memory (might need to change it in storage) vpn vpn vpn 1 3 1 What happens when we pp4 (5) pp6 (0) access a page not in pp8 (13) physical memory? Page Fault! 1. Let’s say we access page VPN 5. We see it is not resident, but instead on Disk. a. PAGE FAULT →MMU invokes OS handler 2. If memory is full, replace a page (say VPN 1), PPN 4. a. Update page table, write page to disk if dirty. Replacement Policy How to decide which page to kick back into storage? For this class: LRU. (Mark the least recently used page, and swap that page back into storage) Bonus: Locality! Cons: Expensive. (Time to scan for LRU, dirty pages take longer to swap) Neat Bonuses of Page Tables Finally, a side effect that is not negative! mmap ○ Explicitly tell OS to map file on disk (in storage) to a region in process VAS. FAST!! Sharing ○ Can map the SAME physical memory into multiple processes virtual memory to SHARE memory. ○ More efficient– 100 copies of the same running process can have ONE physical memory page corresponding to the instructions for that process Next Time How many memory lookups do we need to perform everytime we access memory? Hint: the page table itself resides where? 2 Memory lookups (one to get the page table entry and one with physical address) ○ Memory access is SLOW So… How to make page tables faster? Examining Virtual Memory through Examples Address Sizes are Tied to the Size of the Addressable Space they describe. If you have 210 bytes of space. You need 10 bit addresses. If you have 12 bit addresses. You can have 212 bytes of memory! This holds true in physical memory OR virtual memory. i.e. 10 bit virtual addresses, means you have 210 bytes in address space. 10 bit physical addresses, means you have 210 bytes of physical memory. The math of page tables. Physical Address: PPN + offset physical_address_size = log2(number_of_physical_pages) + log2(page_size) physical_memory_size = number of physical pages * page size Virtual Address: VPN + offset virtual_address_size = log2(number of virtual pages) + log2(page size) virtual_address_space_size = number of virtual pages * page size