Want processes to co exist Consider multiprogramming on physical memory What happens if pintos needs to expand If emacs needs more memory than is on the machine If pintos has an error and writes to address 0x7100 When does gcc have to know it will run at 0x4000 What if emacs isn t using its memory 1 36 Issues in sharing physical memory Protection A bug in one process can corrupt memory in another Must somehow prevent process A from trashing B s memory Also prevent A from even observing B s memory ssh agent Transparency A process shouldn t require particular memory locations Processes often require large amounts of contiguous memory for stack large data structures etc Resource exhaustion Programmers typically assume machine has enough memory Sum of sizes of all processes often greater than physical memory 2 36 Virtual memory goals Give each program its own virtual address space At run time relocate each load and store to its actual memory So app doesn t care what physical memory it s using Also enforce protection Prevent one app from messing with another s memory And allow programs to see more memory than exists Somehow relocate some memory accesses to disk 3 36 Virtual memory advantages Can re locate program while running Run partially in memory partially on disk Most of a process s memory will be idle 80 20 rule Write idle parts to disk until needed Let other processes use memory for idle part Like CPU virtualization when process not using CPU switch When not using a page switch it to another process Challenge VM extra layer could be slow 4 36 Idea 1 load time linking Link as usual but keep the list of references Fix up process when actually executed Determine where process will reside in memory Adjust all references within program using addition Problems 5 36 Idea 1 load time linking Link as usual but keep the list of references Fix up process when actually executed Determine where process will reside in memory Adjust all references within program using addition Problems How to enforce protection How to move once in memory Consider data pointers What if no contiguous free region fits program 5 36 Idea 2 base bounds register Two special privileged registers base and bound On each load store Physical address virtual address base Check 0 virtual address bound else trap to kernel How to move process in memory Change base register What happens on context switch OS must re load base and bound register 6 36 Idea 2 base bounds register Two special privileged registers base and bound On each load store Physical address virtual address base Check 0 virtual address bound else trap to kernel How to move process in memory Change base register What happens on context switch OS must re load base and bound register 6 36 Definitions Programs load store to virtual or logical addresses Actual memory uses physical or real addresses Hardware has Memory Management Unit MMU Usually part of CPU Accessed w privileged instructions e g load bound reg Translates from virtual to physical addresses Gives per process view of memory called address space 7 36 Address space 8 36 Base bound trade offs Advantages Cheap in terms of hardware only two registers Cheap in terms of cycles do add and compare in parallel Examples Cray 1 used this scheme Disadvantages 9 36 Base bound trade offs Advantages Cheap in terms of hardware only two registers Cheap in terms of cycles do add and compare in parallel Examples Cray 1 used this scheme Disadvantages Growing a process is expensive or impossible No way to share code or data E g two copies of bochs both running pintos One solution Multiple segments E g separate code stack data segments Possibly multiple data segments 9 36 Segmentation Let processes have many base bounds regs Address space built from many segments Can share protect memory on segment granularity Must specify segment as part of virtual address 10 36 Segmentation mechanics Each process has a segment table Each VA indicates a segment and offset Top bits of addr select segment low bits select offset PDP 10 Or segment selected by instruction or operand means you need wider far pointers to specify segment 11 36 Segmentation example 2 bit segment number 1st digit 12 bit offset last 3 Where is 0x0240 0x1108 0x265c 0x3002 0x1600 12 36 Segmentation trade offs Advantages Multiple segments per process Allows sharing how Don t need entire process in memory Disadvantages Requires translation hardware which could limit performance Segments not completely transparent to program e g default segment faster or uses shorter instruction n byte segment needs n contiguous bytes of physical memory Makes fragmentation a real problem 13 36 Fragmentation Fragmentation Inability to use free memory Over time Variable sized pieces many small holes external frag Fixed sized pieces no external holes but force internal waste internal fragmentation 14 36 Alternatives to hardware MMU Language level protection Java Single address space for different modules Language enforces isolation Singularity OS does this Hunt Software fault isolation Instrument compiler output Checks before every store operation prevents modules from trashing each other Google Native Client does this with only about 5 slowdown Yee 15 36 Paging Divide memory up into small pages Map virtual pages to physical pages Each process has separate mapping Allow OS to gain control on certain operations Read only pages trap to OS on write Invalid pages trap to OS on read or write OS can change mapping and resume application Other features sometimes found Hardware can set accessed and dirty bits Control page execute permission separately from read write Control caching of page 16 36 Paging trade offs Eliminates external fragmentation Simplifies allocation free and backing storage swap Average internal fragmentation of 5 pages per segment 17 36 Simplified allocation gcc physical memory emacs Disk Allocate any physical page to any process Can store idle virtual pages on disk 18 36 Paging data structures Pages are fixed size e g 4K Least significant 12 log 4K bits of address are page offset Most significant bits are page number Each process has a page table Maps virtual page numbers to physical page numbers Also includes bits for protection validity etc On memory access Translate VPN to PPN then add offset 19 36 Example Paging on PDP 11 64K virtual memory 8K pages Separate address space for instructions data I e can t read your own instructions with a load Entire page table stored in
View Full Document
Unlocking...