use efficient page maps too translate virtual to physical addresses kick things off to disk when memory runs out Every process has its own page map. demand paging Key idea: physical representation of virtual memory does not have to be on actual memory. if memory fills out, kick a page to disk if the program asks for memory again, kick another page to disk and load its memory back Keep in memory the information that’s being used, kick the rest to swap space/"paging file". Ideally: we have a performance of main memory and capacity of disk. demand fetching most modern OSes start with no pages loaded—load pages only when referenced; this is tempered by the type of page that’s needed: read only code pages (program code, doesn’t change) — do NOT save to swap; executable will always be there so you can just reload from disk program will expect code pages too contain executable data initialized data pages — save to swap because contents may have changed frorm initial values program expects them to contain data on load, so we need to load them ahead of time unitialized data pages save to swap no initial content Page Type Need Content on First Load Save to Swap (“Swap?”) code yes no (read from exe) data yes yes stack/heap no yes We only write to disk if its dirty. using swap to get extra memory pick a page to kick out write kicked page to disk mark the old page entry as not present give the physical address to the new virtual page If we ever ask for the old page back, trigger page fault: page fault (to recover a page that’s on swap) check with swap for the data get new physical page (perhaps kicking out another page) load data into page update page map as present and with new address choosing what to swap thrashing downside of demand paging When the pages being actively used don’t fit in memory: you will have to get the page, kick it out immediately, get it back again, etc. This basically make memory as fast as disk; which is really slow. Solution: download more RAM. “buy more memory, or use task manager” - nick page map A page map, to keep track of something is valid/invalid, we have to store information about EVERY PAGE for EVERY PROCESS. Each entry in the page: Index Physical Address Writable Present/Mapped? Last Access Kernel Dirty 0 0x2023 1 0 0 0 0 1 0x0023 1 1 1 0 0 Dirty: the content matters and it needs to be written out. This is, of course, very big if stored densely. Consider 36 bit page numbers, 8 byte entries, it requires 2^{36} \cdot 8 = 512GB worth of space per process. This is sad. PRESENT simply means if the segment of memory is MAPPED. ITs possible for a not present index to be in SWAP instead. page map tree implementation To resolve this, we have entry for RANGES of virtual pages; there’s about 4 levels. If everything is invalid in a range, we just consider the whole range invalid using one row. Therefore, we lazily make space for this tree.