Virtual MemoryFacts about Memory UseObjective of Virtual MemoryPowerPoint PresentationVirtual Memory (How ?)Main problem : Instructions with Multiple AddressesPerformance of Demand Paging (Effective Access Time)Slide 8Reducing e.a.tPage Replacement AlgorithmsSlide 11Slide 12Optimal Page Replacement AlgorithmOPT vs FIFOProblem with OPTSlide 16Implementation of LRUApproximating LRUAllocation AlgorithmStatic Allocation AlgorithmDetermining the Degree of Multu-programmingTrashingPrevention of TrashingHow many frames are enough to a process ?Dynamic Allocation AlgorithmSummary of Memory ManagementSummary of Virtual Memory01/14/19 Operating Systems Virtual Memory 1Virtual Memory01/14/19 Operating Systems Virtual Memory 2Facts about Memory Use•The entire program is not needed to be in memory•The program’s demand on memory may change in run-time•Users would like to have their logical address space unbounded01/14/19 Operating Systems Virtual Memory 3Objective of Virtual Memory•Separation of user logical memory from physical memory–Very large logical (virtual) memory–Efficient use of physical memory•Implementation–Demand paging: only bring in a page when it is demanded (data or instruction referenced)01/14/19 Operating Systems Virtual Memory 4ABCDEFiii13 v0 v vAFC0123B EAC FDLogicalMemoryPage TablePhysicalMemorySecondary storage01234501234501/14/19 Operating Systems Virtual Memory 5Virtual Memory (How ?)•After a memory reference (data or code)Hardware1. Check the process’ page table to see if the page is in memory.2. If it is not (page fault), interrupt to OS (trap)3. a) Suspend the (offending) processb) Locate a free frame in memory (how?)c) Locate the missing page from disk.4. Bring in the missing page into memory (meanwhile, other processes may use the CPU)5. Update page table6. a) Reset the process’s PC so that we restart with the offending instruction.b) Change the status of process from “wait” to “ready”01/14/19 Operating Systems Virtual Memory 6Main problem : Instructions with Multiple Addresses•Page fault occurs in the middle of the execution•Solutions:–Determine if there would be a page fault before any modification occurs–Hold results temporiraly until it is certain there is no page fault. Then, proceed with modification.01/14/19 Operating Systems Virtual Memory 7Performance of Demand Paging(Effective Access Time)•Definition : average time taken by a memory access :–Ma : (average) time for a memory access without page fault (e.g. ma = 100 nanoseconds)–Page fault time:(average) time taken by a page fault:•O.S. service time when a page fault is detected 100 s•Time by disk to read the page into memory 25 milliseconds•Time to restart the process (around 100 s)Total of page fault time is about 25,000,000 ns01/14/19 Operating Systems Virtual Memory 8P : probability that a page fault occurs when a memory reference is madeEffective Access Time = (1-p)*ma + p*page fault time = 0.100 + 25,000 p (s)10-110-610-3100101pe.a.t01/14/19 Operating Systems Virtual Memory 9Reducing e.a.t•Reduce the page fault rate–Use a better page replacement algorithm–Allocate more pages to a process (in the main memory)01/14/19 Operating Systems Virtual Memory 10Page Replacement Algorithms•FIFO : replace the page which comes earliestPage ReferencedMemoryStatePage Fault ?7y7--0y70-1y7012y2010n2013y2310y2304y4302y4203y42301/14/19 Operating Systems Virtual Memory 11Page Replacement Algorithms•FIFO : replace the page which comes earliest•Another example : total pages for the process =3Page Ref.Me.StatePage Fault ?1y1--2y12-3y1234y4231y4132y4125y5121n5122n5123y532Page fault rate = 9/124y5345n53401/14/19 Operating Systems Virtual Memory 12Page Replacement Algorithms•FIFO : replace the page which comes earliest•Another example : total pages for the process =4Page Ref.Me.StatePage Fault ?1y1--2y12-3y1234y1231n1232n1235y5231n5132n5123y512Page fault rate = 10/12 !!! While the number of pages increased, the p.f.r increases as well ! This is called Belady’s anomaly !4y4125n452- - - 4 4 4 4 4 4 3 3 301/14/19 Operating Systems Virtual Memory 13Optimal Page Replacement Algorithm•Why does not FIFO work well ?–It counts when the page is brought into the memory, ignoring how the page has been and will be used.•The Optimal algorithm (OPT)–Replace the page that will not be used for the longest time (psychic !!!)•OPT counts when the page is to be used.01/14/19 Operating Systems Virtual Memory 14OPT vs FIFO7y7--0y70-1y7012y2010n2013y2310y2304y4302y4203y42377--070-17012201020132030203424322433243OPTFIFOy y y y n y n y n n01/14/19 Operating Systems Virtual Memory 15Problem with OPT•Need knowledge of future references•Approximation Assumption:–A page used recently is likely to be used in the near future (temporal locality).–A page unused recently is unlikely to be used in the near future.•The Least Recently Used Algorithm (LRU):–Replace the page that has not been used for the longest period. Solution : approximation01/14/19 Operating Systems Virtual Memory 16OPT vs LRU7y7--0y70-1y7012y2010n2013y2030n2034y4032y4023y43277--070-17012201020132030203424322433243OPTLRUy y y y n y n y n n01/14/19 Operating Systems Virtual Memory 17Implementation of LRU•Time-of-use register in every entry of page table.•Stack of page numbersFrame base addressTime-of-usePage iReference string :4 7 1 0 1 2 1 2 7 1210747210401/14/19 Operating Systems Virtual Memory 18Approximating LRU•Use of reference bit–Each entry in page table has a reference bit.–Each time a page is accessed, the bit is set.–Periodically, O.S cleans reference bits.–The pages with their bits reset have higher priority to be replaced.•Use of reference bit and modification bit•Ad hoc algorithm used in VAX/VMS.01/14/19 Operating Systems Virtual Memory 19Allocation Algorithm•Problem : determine how many frames a processcan have.–Let M=size of physical memory–Di = the number of frames allocated to Pi–Si=the size of virtual memory of Pi•Minimum number of frames:–Di : maximum number of frames involved in an instruction.•Maximum number of frames:–Di ≤min(M,Si)01/14/19 Operating Systems Virtual Memory 20Static Allocation Algorithm•Equal algorithm : Di = M/n where n is the number of processes.•Proportional algorithm–Di = M *Si/S, where S = Sum Si01/14/19 Operating Systems Virtual