Josh Rogan Operating Systems Notes I Fall 2014 Website http people cs pitt edu jmisurda teaching cs1550 htm Review Memory Management Translating Memory o Breaking up the memory into chunks pages that refers to a page Table item that stores a frame number We don t need all the bits but we are going to use for other things o 32 bit order space 4KB pages 4B Page table entry 4MB Valid Bit Some pages are in RAM and some pages aren t in RAM The valid bit will tell us if it is a valid mapping 1 means there is a copy in RAM 0 means it isn t o How can we decrease 4MB Is our data structure sparse or dense Yes Our virtual memory is going to be larger than our RAM because we usually don t have as much RAM as virtual memory Since this is true we can use a linked list to reduce time This will result in a page linked list o Each linked list will have a page number a frame number and a link o Problem with linked list is access time is now linear rather than constant It also requires a lot more memory lookups to move through the link list expense operation o Not the data structure for us Page Tree o Binary Search Tree Still requires logn memory look ups We don t want it to be based on n at all o Constant Depth Tree Depth of two One root node that points to leaves Leaves will store page table entries Size SizeOfRoot n sizeOfLeaf N is where we save size due to sparseness R and L Sizes Drawing a line in the page number 210 and 210 o We need to only save one leaf to make it better Algorithm Input is virtual address output is physical address Look up some address into the leaf Look into the leaf to get the Framenumber which will get the physical address Page Size offset o Offset VA PageSize How do we save a leaf We have to have an entire leaf with 0 valid bit entries Josh Rogan Operating Systems Notes I Fall 2014 We need L contiguous invalid bits Space between stack and heap 4MB MUST BE ALIGNED 64 Bit Systems o Multi level Page Table 5 would be too many reference look ups However this is the actual solution o Two level would take up too much space per process o of Total Pages in the system of Total frames Total number of pages is the ofPages VA Page Size number of processes of Frames Amount of RAM Valid Pages Page Frames o If all we really care about is the valid maps why can t we build a page table for every valid frame Inverted Page Table Stores the inverse If on the page table index 0 7 that means that page 7 is loaded at frame 0 o Don t have to store invalid entries o Problem Width of the table has to include Who s process this is o Only have one table per system now How can the MMU handle this o Input VA PID o Output PA Page VA Page Size Offset VA Page Size NOW We have to search the array Too expensive PA Frame Page Size Offset BEFORE F pageTable page Can t really make the search smarter Adding more RAM makes the computer slower We got something as compact as possible but too slow to use o Caching Temporal Locality If we use it now we probably will use it soon again Spatial Locality If we use a location now we will probably use its neighbors soon What in the MMU process has locality When fetching an instruction from address space we usually move upwards from the program counter 4 This means they are very likely they will be in the same page Only differing by their offset This means it was the last frame number we got or recently Because they are near each other they will have temporal locality The whole point of a cache is to remember things instead of looking them up again Josh Rogan Operating Systems Notes I Fall 2014 A cache miss will happen the first time and we will search the table and put the result in the cache Normally we hash the entries in the cache to faster lookup Compulsory Translations we haven t seen before Conflicting Hashing missing Make the cache small will get rid of it Capacity Losing things that don t fit How can we make this constant time Build it in hardware and do the computation with multiple comparators Translation Lookaside Buffer TLB Inverted page table would be ridiculous without the TLB Two types software and hardware managed one o Software Save and restore the TLB for each process Typically o Hardware Use all the space for all the processes Usually smaller double in size Virtual Memory o Page Table Entry Valid Bit Is the mapping in RAM Referenced Bit Has this page been read or written since it has been loaded Dirty Bit Have we written to the frame since we loaded it It has been modified Clean bit will very likely be code Protection Bits RWX bits Having a stack the isn t executable would avoid the buffer overflow vulnerability How do I assign a frame to a page in memory o Handling a Page Fault o Page Fault Exception raised by the MMU indicating a requested virtual address is not Determine faulting address If the page is invalid grow stack or heap alternatively SEGFAULT on error load only the memory we need If physical memory is full choose a frame to evict By denying RAM we can prevent execution most of the time doesn t happen Write frame to disk if dirty SWAP space Sometimes done as a file or as a partition Load requested page into no empty frame o Page faults are always going to happen some are good some are bad Good We haven t loaded this pages code into a frame of RAM yet Compulsory miss It will then try to give you some frame in RAM Bad Making a mistake usually with pointers not something we should actually load Terminate the program SIGSEGV o What would it mean to load a program Load it s starting address into the program counter and say go Josh Rogan Operating Systems Notes I Fall 2014 Page Replacement Algorithms o How do we choose a frame to swap out Choose at page fault time by either looking at the entire RAM or some subset and determine what should happen o What is the optimal page replacement algorithm In terms of what May need to write to disc Determine good or bad page fault Minimize our page fault rate It should only be run when memory is actually full o Worst possible way Every instruction page faults as many time as possible Replace the next instructions page with the new page Guaranteeing a page fault happens next every time o Possible good ways Make page faults happen as rare as possible Kick out …