DOC PREVIEW
Berkeley COMPSCI 162 - Page Allocation and Replacement

This preview shows page 1-2-15-16-17-32-33 out of 33 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS162 Operating Systems and Systems Programming Lecture 15 Page Allocation and ReplacementReview: Demand Paging MechanismsReview: Software-Loaded TLBReview: Transparent ExceptionsGoals for TodaySteps in Handling a Page FaultDemand Paging ExampleWhat Factors Lead to Misses?Page Replacement PoliciesReplacement Policies (Con’t)Example: FIFOExample: MINAdministriviaWhen will LRU perform badly?Graph of Page Faults Versus The Number of FramesAdding Memory Doesn’t Always Help Fault RateImplementing LRUClock Algorithm: Not Recently UsedNth Chance version of Clock AlgorithmClock Algorithms: DetailsClock Algorithms Details (continued)Second-Chance List Algorithm (VAX/VMS)Second-Chance List Algorithm (con’t)Free ListDemand Paging (more details)Allocation of Page Frames (Memory Pages)Fixed/Priority AllocationPage-Fault Frequency AllocationThrashingLocality In A Memory-Reference PatternWorking-Set ModelWhat about Compulsory Misses?SummaryCS162Operating Systems andSystems ProgrammingLecture 15Page Allocation and ReplacementOctober 24, 2005Prof. John Kubiatowiczhttp://inst.eecs.berkeley.edu/~cs162Lec 15.210/24/05 Kubiatowicz CS162 ©UCB Fall 2005•PTE helps us implement demand paging–Valid  Page in memory, PTE points at physical page–Not Valid  Page not in memory; use info in PTE to find it on disk when necessary•Suppose user references page with invalid PTE?–Memory Management Unit (MMU) traps to OS»Resulting trap is a “Page Fault”–What does OS do on a Page Fault?:»Choose an old page to replace »If old page modified (“D=1”), write contents back to disk»Change its PTE and any cached TLB to be invalid»Load new page into memory from disk»Update page table entry, invalidate TLB for new entry»Continue thread from original faulting location–TLB for new page will be loaded when thread continued!–While pulling pages off disk for one process, OS runs another process from ready queue»Suspended process sits on wait queueReview: Demand Paging MechanismsLec 15.310/24/05 Kubiatowicz CS162 ©UCB Fall 2005Review: Software-Loaded TLB•MIPS/Snake/Nachos TLB is loaded by software–High TLB hit rateok to trap to software to fill the TLB, even if slower–Simpler hardware and added flexibility: software can maintain translation tables in whatever convenient format•How can a process run without hardware TLB fill?–Fast path (TLB hit with valid=1):»Translation to physical page done by hardware–Slow path (TLB hit with valid=0 or TLB miss)»Hardware receives a “TLB Fault”–What does OS do on a TLB Fault? »Traverse page table to find appropriate PTE»If valid=1, load page table entry into TLB, continue thread»If valid=0, perform “Page Fault” detailed previously»Continue thread•Everything is transparent to the user process:–It doesn’t know about paging to/from disk–It doesn’t even know about software TLB handlingLec 15.410/24/05 Kubiatowicz CS162 ©UCB Fall 2005Review: Transparent Exceptions•Hardware must help out by saving:–Faulting instruction and partial state –Processor State: sufficient to restart user thread»Save/restore registers, stack, etc•Precise Exception  state of the machine is preserved as if program executed up to the offending instruction–All previous instructions completed–Offending instruction and all following instructions act as if they have not even started–Difficult with pipelining, out-of-order execution, ...–MIPS takes this position•Modern techniques for out-of-order execution and branch prediction help implement precise interruptsLoad TLBFaultingInst 1FaultingInst 1FaultingInst 2FaultingInst 2Fetch page/Load TLBUserOSTLB FaultsLec 15.510/24/05 Kubiatowicz CS162 ©UCB Fall 2005Goals for Today•Page Replacement Policies–Clock Algorithm–Nth chance algorithm–Second-Chance-List Algorithm•Page Allocation Policies•Working Set/ThrashingNote: Some slides and/or pictures in the following areadapted from slides ©2005 Silberschatz, Galvin, and GagneLec 15.610/24/05 Kubiatowicz CS162 ©UCB Fall 2005Steps in Handling a Page FaultLec 15.710/24/05 Kubiatowicz CS162 ©UCB Fall 2005Demand Paging Example•Since Demand Paging like caching, can compute average access time! (“Effective Access Time”)–EAT = Hit Rate x Hit Time + Miss Rate x Miss Time•Example:–Memory access time = 200 nanoseconds–Average page-fault service time = 8 milliseconds–Suppose p = Probability of miss, 1-p = Probably of hit–Then, we can compute EAT as follows:EAT = (1 – p) x 200ns + p x 8 ms = (1 – p) x 200ns + p x 8,000,000ns = 200ns + p x 7,999,800ns•If one access out of 1,000 causes a page fault, then EAT = 8.2 μs:–This is a slowdown by a factor of 40!•What if want slowdown by less than 10%?–200ns x 1.1 < EAT  p < 2.5 x 10-6–This is about 1 page fault in 400000!Lec 15.810/24/05 Kubiatowicz CS162 ©UCB Fall 2005What Factors Lead to Misses?•Compulsory Misses: –Pages that have never been paged into memory before–How might we remove these misses?»Prefetching: loading them into memory before needed»Need to predict future somehow! More later.•Capacity Misses:–Not enough memory. Must somehow increase size.–Can we do this?»One option: Increase amount of DRAM (not quick fix!)»Another option: If multiple processes in memory: adjust percentage of memory allocated to each one!•Conflict Misses:–Technically, conflict misses don’t exist in virtual memory, since it is a “fully-associative” cache•Policy Misses:–Caused when pages were in memory, but kicked out prematurely because of the replacement policy–How to fix? Better replacement policyLec 15.910/24/05 Kubiatowicz CS162 ©UCB Fall 2005Page Replacement Policies•Why do we care about Replacement Policy?–Replacement is an issue with any cache–Particularly important with pages»The cost of being wrong is high: must go to disk»Must keep important pages in memory, not toss them out•FIFO (First In, First Out)–Throw out oldest page. Be fair – let every page live in memory for same amount of time.–Bad, because throws out heavily used pages instead of infrequently used pages•MIN (Minimum): –Replace page that won’t be used for the longest time –Great, but can’t really know future…–Makes good comparison case, however•RANDOM:–Pick random page for every replacement–Typical solution for TLB’s. Simple hardware–Pretty unpredictable – makes it hard to make real-time guaranteesLec 15.1010/24/05


View Full Document

Berkeley COMPSCI 162 - Page Allocation and Replacement

Documents in this Course
Lecture 1

Lecture 1

12 pages

Nachos

Nachos

41 pages

Security

Security

39 pages

Load more
Download Page Allocation and Replacement
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Page Allocation and Replacement and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Page Allocation and Replacement 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?