1CSC 4103 - Operating SystemsSpring 2007Tevfik KoşarLouisiana State UniversityMarch 20th, 2007Lecture - XIIIVirtual MemoryBackground• Virtual memory – separation of user logicalmemory from physical memory.– Only part of the program needs to be in memory forexecution.– Logical address space can therefore be much largerthan physical address space.– Allows address spaces to be shared by severalprocesses.– Allows for more efficient process creation.• Virtual memory can be implemented via:– Demand paging– Demand segmentationDemand Paging• Bring a page into memory only when it is needed– Less I/O needed– Less memory needed– Faster response– More users• Page is needed ⇒ reference to it– invalid reference ⇒ abort– not-in-memory ⇒ bring to memoryTransfer of a Paged Memory to Contiguous Disk SpaceValid-Invalid Bit• With each page table entry a valid–invalid bit is associated(1 ⇒ in-memory and legal, 0 ⇒ not-in-memory or invalid)• Initially valid–invalid bit is set to 0 on all entries• Example of a page table snapshot:• During address translation, if valid–invalid bit in page table entryis 0 ⇒ page fault1111000MFrame # valid-invalid bitpage tablePage Table When Some Pages Are Not in Main MemoryPage Fault• If there is ever a reference to a page, first reference willtrap toOS ⇒ page fault• OS looks at another table to decide:– Invalid reference ⇒ abort.– Just not in memory.• Get empty frame.• Swap page into frame.• Reset tables, validation bit = 1.• Restart instruction: Least Recently Used– block move– auto increment/decrement locationSteps in Handling a Page FaultWhat happens if there is no free frame?• Page replacement – find some page inmemory, but not really in use, swap it out– Algorithms (FIFO, LRU ..)– performance – want an algorithm which will resultin minimum number of page faults• Same page may be brought into memoryseveral timesPerformance of Demand Paging• Page Fault Rate 0 ≤ p ≤ 1.0– if p = 0 no page faults– if p = 1, every reference is a fault• Effective Access Time (EAT)EAT = (1 – p) x memory access+ p x (page fault overhead + [swap page out] + swap page in + restart overhead)Demand Paging Example• Memory access time = 1 microsecond• 50% of the time the page that is being replaced has been modifiedand therefore needs to be swapped out• Swap Page Time = 10 msec = 10,000 microsec• EAT = (1 – p) x 1 + p x (10,000 + 1/2 x 10,000) = 1 + 14,999 x p (in microsec)• What if 1 out of 1000 memory accesses cause a page fault?• What if we only want 30% performance degradation?Copy-on-Write• Copy-on-Write (COW) allows both parent and childprocesses to initially share the same pages in memoryIf either process modifies a shared page, only then isthe page copied• COW allows more efficient process creation as onlymodified pages are copied• Free pages are allocated from a pool of zeroed-outpages (zero-fill-on-demand pages)Page Replacement• Prevent over-allocation of memory by modifying page-fault service routine to include page replacement• Use modify (dirty) bit to reduce overhead of pagetransfers – only modified pages are written to disk• Page replacement completes separation betweenlogical memory and physical memory – large virtualmemory can be provided on a smaller physical memoryBasic Page Replacement1. Find the location of the desired page on disk2. Find a free frame:- If there is a free frame, use it- If there is no free frame, use a pagereplacement algorithm to select a victim frame3. Read the desired page into the (newly) freeframe. Update the page and frame tables.4. Restart the processPage ReplacementPage Replacement Algorithms• Want lowest page-fault rate• Evaluate algorithm by running it on aparticular string of memory references(reference string) and computing thenumber of page faults on that string• In all our examples, the reference string is1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5Graph of Page Faults Versus The Number of FramesFirst-In-First-Out (FIFO) Algorithm• Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5• 3 frames (3 pages can be in memory at a time perprocess)• 4 frames• FIFO Replacement – Belady’s Anomaly– more frames ⇒ more page faults1231234125349 page faults1231235124510 page faults44 3FIFO Illustrating Belady’s AnomalyOptimal Algorithm• Replace page that will not be used for longest period of time• 4 frames example 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5• How do you know this?• Used for measuring how well your algorithm performs12346 page faults45Least Recently Used (LRU) Algorithm• Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5• Needs hardware assistance• Counter implementation– Every page entry has a counter; every time page is referenced throughthis entry, copy the clock into the counter– When a page needs to be changed, look at the counters to determinewhich are to change12354435LRU Algorithm (Cont.)• Stack implementation – keep a stack of page numbersin a double link form:– Page referenced:• move it to the top• requires 6 pointers to be changed– No search for replacementUse Of A Stack to Record The Most Recent Page ReferencesLRU Approximation Algorithms• Reference bit– With each page associate a bit, initially = 0– When page is referenced bit set to 1– Replace the one which is 0 (if one exists). We do not know the order, however.• Additional Reference bits– 1 byte for each page: eg. 00110011– Shift right at each time interval• Second chance– Need reference bit– Clock replacement– If page to be replaced (in clock order) has reference bit = 1 then:• set reference bit 0• leave page in memory• replace next page (in clock order), subject to same rulesSecond-Chance (clock) Page-Replacement AlgorithmCounting Algorithms• Keep a counter of the number of referencesthat have been made to each page• LFU Algorithm: replaces page with smallestcount• MFU Algorithm: based on the argument thatthe page with the smallest count wasprobably just brought in and has yet to beusedAllocation of Frames• Each process needs minimum number of pages• Example: IBM 370 – 6 pages to handle SS MOVEinstruction:– instruction is 6 bytes, might span 2 pages– 2 pages to handle from– 2 pages to handle to• Two major allocation schemes– fixed allocation– priority allocationFixed Allocation• Equal allocation – For