AdministriviaPagingWorking set modelPaging challengesRe-starting instructionsWhat to fetchSelecting physical pagesSuperpagesStraw man: FIFO evictionStraw man: FIFO evictionBelady's AnomalyOptimal page replacementOptimal page replacementLRU page replacementLRU page replacementStraw man LRU implementationsClock algorithmClock alg. (continued)Other replacement algorithmsNa"i ve pagingPage bufferingPage allocationThrashingReasons for thrashingMultiprogramming & ThrashingDealing with thrashingWorking setsCalculating the working setTwo-level schedulerSome complications of paging64-bit address spacesRecall typical virtual address spaceEarly VM system callsMemory mapped files exttt {mmap} system callMore VM system callsExposing page faultsExample: OpenBSD/i386 siginfoVM tricks at user level4.4 BSD VM system href {http://proquest.safaribooksonline.com/9780768685275/ch05lev1sec4}{[McKusick]}Pmap (machine-dependent)layerExample usesWhat happens on a fault?Administrivia• Project 2 due Thursday- As before, free extension to midnight if you come to class• Use the newsgroup!- Lots of similar questions to cs140-staff- TAs are too polite to tell people to ask on newsgroup- But everyone benefits if these questions are answered in public- Plus Ben Pfaff answers questions on newsgroup• Midterm one week from today- Open book, open notes (but not open notebook computer)• Review section for midterm this Friday• Section for Project 3 next F riday1/41Paging• Use disk to simulate larger virtual than physical mem2/41Working set model• Disk much, much slower than memo ry- Goal: Run at memory, not disk speeds• 90/10 rule: 10% of memory gets 90% of memory refs- So, keep that 10% in real memory, the other 90% on disk- How to pick which 10%?3/41Paging challenge s• How to resume a process a fter a fault?- Need to save state and resume- Process might have been in the middle of an instruction!• What to fetch?- Just needed page or more?• What to eject?- How to allocate physical pages amongst processes?- Which of a particular process’s pages to keep in memory?4/41Re-starting instructions• Hardware provides kernel w. info about page fault- Faulting virtual address (In %cr2 reg on x86—may have seen itif you modified Pintos page fault and used fault addr)- Address of instruction that caused fault- Was the access a read or write? Was it an instruction fetch?Was it caused by user access to kernel-only memory?• Hardware must allow resuming after a fa ult• Idempotent instructions are easy- E.g., simple load or store instruction can be restarted- Just re-execute any instruction that only accesses one address• Complex instructions must be re-started, too- E.g., x86 move string instructions- Specify srd, dst, count in %esi, %edi, %ecx registers- On fault, registers adjusted to resume where move left off5/41What to fetch• Bring in page that caused page fault• Pre-fetch surrounding pages?- Reading two disk blocks approximately as fast as reading one- As long as no track/head switch, seek time dominates- If application exhibits spacial locality, then big win to store andread multiple contiguous pages• Also pre-zero unused pages in idle loo p- Need 0-filled pages for stack, heap, anonymously mmappedmemory- Zeroing them only on demand is slower- So many OSes zero freed pages while CPU is idle6/41Selecting physica l pag e s• May need to eject some pages- More on eviction policy in two slides• May also have a choice of physical pages• Direct-mapped physical caches- Virtual → Phy sical mapping can affect performance- Applications can conflict w ith each other or themselves- Scientific applications benefit if consecutive virtual pages to notconflict in the cache- Many other applications do better with random mapping7/41Superpages• How should OS make use of “larg e ” mappings- x86 has 2/4MB pages that might be useful- Alpha has even more choices: 8KB, 64KB, 512KB, 4MB• Sometimes more pages in L2 cache than TLB entries- Don’t want costly TLB misses going to main memory• Or have two-level TLBs- Want to maximize hit rate in faster L1 TLB• OS can transparently support superpages[Navarro]- “Reserve” appropriate physical pages if possible- Promote contiguous pages to superpages- Does complicate evicting (esp. dirty pages) – demote8/41Straw man: FIFO eviction• Evict oldest fetched page in system• Example—reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5• 3 physical pages: 9 page faults9/41Straw man: FIFO eviction• Evict oldest fetched page in system• Example—reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5• 3 physical pages: 9 page faults• 4 physical pages: 10 page faults9/41Belady’s Anomaly• More phys. mem. doesn’t alwa ys mean fewer faults10/41Optimal page repla c e ment• What is optimal (if you knew the future)?11/41Optimal page repla c e ment• What is optimal (if you knew the future)?- Replace page that will not be used for longest period of time• Example—reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5• With 4 physical pages:11/41LRU page replac e ment• Approximate optimal with least recently used- Because past often predicts the future• Example—reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5• With 4 physical pages: 8 page faults• Problem 1: Can be pessimal – exa m ple?• Problem 2: How to implement?12/41LRU page replac e ment• Approximate optimal with least recently used- Because past often predicts the future• Example—reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5• With 4 physical pages: 8 page faults• Problem 1: Can be pessimal – exa m ple?- Looping over memory (then want MRU eviction)• Problem 2: How to implement?12/41Straw man LRU implementat io ns• Stamp PTEs with timer value- E.g., CPU has cycle counter- Automatically writes value to PTE on each page access- Scan page table to find oldest counter value = LRU page- Problem: Would double memory traffic!• Keep doubly-linke d list of pages- On access remove page, place at tail of list- Problem: again, very expensive• What to do?- Just approximate LRU, don’t try to do it exactly13/41Clock algorithm• Use accessed bit supported by most hardware- E.g., Pentium will write 1 to A bit in PTE on first access- Software managed TLBs like MIPS can do the same• Do FIFO but skip acces s e d pages• Keep pages in circular FIFO list• Scan:- page’s A bit = 1, set to 0 & skip- else if A == 0, evict• A.k.a. second-chance
View Full Document
Unlocking...