Operating Systems Design & Construction
Operating Systems Design & Construction CMPSC 473
Popular in Course
Popular in ComputerScienence
verified elite notetaker
This 0 page Class Notes was uploaded by Isabel Eichmann on Sunday November 1, 2015. The Class Notes belongs to CMPSC 473 at Pennsylvania State University taught by Staff in Fall. Since its upload, it has received 20 views. For similar materials see /class/233061/cmpsc-473-pennsylvania-state-university in ComputerScienence at Pennsylvania State University.
Reviews for Operating Systems Design & Construction
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 11/01/15
M Operating Systems CMPSC 473 Virtual Memory March 18 2008 Lecture 16 Instructor Trent Jaeger Last Class Paging Today Virtual Memory What if programs require more memory than available Virtual Memory physical memory Use overlays Dif cult to program though Virtual Memory Supports programs that are larger than available physical memory Allows several programs to reside in physical memory or at least the relevant portions of them Allows non contiguous allocation without making programming dif cult Page Faults If a Page table mapping indicates an absence of the page in physical memory hardware raises a Page Fault OS traps this fault and the interrupt handler services the fault by initiating a disk read request Once page is brought in from disk to main memory page table entry is updated and the process which faulted is restarted May involve replacing another page and invalidating the corresponding page table entry Page Table When Some Pages Are Not in Main Memory 0 1 7 2 7 frame l 3 4 A 5 5 C 7 B 7 9 F logical Page table 10 memory 7 1 1 12 7 13 7 14 7 15 7 Dh ical memory Page Fault If there is a reference to a page first reference to that page will trap to operating system page fault Operating system looks at another table to decide Invalid reference abort Just not in memory Get empty frame Swap page into frame Reset tables Set validation bit I V Restart the instruction that caused the page fault Steps in Handling a Page Fault page is on backing store operating ystem reference restart instruction page table free frame reset page bring in table missing page physical memorv Performance of Demand Paging Page Fault Rate O s p s 10 ifp 0 no page faults ifp 1 every reference is a fault Effective Access Time EAT EAT I 1 p X memory access p page fault overhead swap page out swap page in restart overhead Demand Paging Example Memory access time I 200 nanoseconds Average page fault service time I 8 milliseconds EAT I 1 p X 200 p 8 milliseconds I 1 p X 200 p X 8000000 I 200 p X 7999800 If one access out of 1000 causes a page fault then EAT I 82 microseconds This is a slowdown by a factor of 40 Putting it all together in r A2K in r B 2 39 firm i quot1 VAS before execution All Point To Null i e fault The first 0x00 PC Heap Poi n39l39er No Page Table 39i39ime Entries here Stack Pointer Oxf Page Table Mallocfree first manipulate this space using buddy If out of Space call 05 To allocate more Stack PT entries using sbrk 0x00 PC gt gt These gt re still Nu and remain so gt Until you access a Heap Pointer 39 No Page table Entries here Pointer gt Page here Oxf Page Table L Note you are not allocating physical memory using malloc Page Replacement When bringing in a page something has to be evicted 39 What should we evict page replacement algorithm Optimal Page Replacement Algorithm 39 Why optimal No other algorithm can have of page faults lower than this for a given page reference stream 39 Algorithm At any point amongst the given pages in memory evict the one Whose first reference from now is the furthest An example of OPT Reference String 3 3 5 2 4 3 2 AT this point Current Physical Memory what do we replace 5 3 gtEvic r Problem with OPT Not implementable Requires us to know the future But it has the best page fault behavior How do we approach OPT 1 First in First out Maintain a linked list of pages in the order they were brought into PM On a page fault evict the one at the head Put the newly brought in page from disk at tail of this list Problems Reference String 123411511 Page fault at 5 would replace 1 l Need to know what is in recent use 2 Not Recently Used Referenced bit set on each Read write by h W Modi ed set on each write by h W On startup set both R and M bits to 0 Periodically using clock interrupts the R bit is cleared On a page fault examine the state of a page ClassORM0 Class 1R0M 1 ClassZR1 M20 Class3R1 M21 NRU replaces a page chosen at random from the lowest nurnbered nonempty class 3 Second Chance Replacement or Clock Algorithm 39 Same as FIFO except you skip over the pages Whose reference bit is set resetting this bit and moving those pages to end of list 39 Implementation mmEl 1 El Em gt 4 Least Recently Used Order the list of physical memory pages in decreasing order of recency of usage Replace the page at the tail Problem This list will need to be updated on each memory reference Asking the hW to do this is ridiculous Solution Approximate LRU Keep a counter for each Phys page Initially set to O At the end of each time interval interval to be determined shift the bits right by one position Copy the reference bit to the MSB of counter and reset reference For a page replacement pick the one with the lowest counter value It is an approximation of LRU because we do not differentiate between references that occured in the same tick the history is limited by the size of the counter Summary of page replacement algorithms 39 OPT FIFO NRU second chance clock LRU approximate LRU 39 In practice OSes use second chance clock or some variations of it Belady s Anomaly 39 Normally you expect number of page faults to decrease as you increase physical memory size 39 However this may not be the case in certain replacement algorithms Example of Belady s Anomaly FIFO replacement Algorithm Reference string 012301401234 3 physical frames of faults I 9 4physical frames FFFF FFFFFF of faults I 10 Algorithms which do NOT suffer from Belady s anomaly are called stack algorithms Eg OPT LRU Modeling Paging Paging behavior Characterized by Reference string Physical memory size Replacement algorithm eg A B C and D Visualize it as a stack are Virtual Pages say XVI Where a page that is referenced is brought to the top of M the stack from ovel A Down Wherever it is D When C is referenced 39 Whatever is in recent use is on the top of M and the ones that are not in recent use are at the bottom In fact the top P entries of M represent the pages in physical memory Where P is the of physical frames In memory On Disk 39 Distance String For each element of reference string this represents the distance of that element from the top of stack in M An example of how M Changes with 5 Virtual pages Reference String Distance String De ne vector C 6 39 Ci represents the number of times 1 appears in the distance string Reference String Distance String 0 C22 3 C5 O C1 2 C4 5 1 mm CC C vector 0 M C De ne Vector F is the number of page faults that will occur for the given reference string with j physical frames C 1 C 2 C 3 COO It is now straightforward to prove LRU does not suffer from Belady s anomaly The M vector tracks What is in physical memory in the top P slots for LRU Note that vector Ci is independent of physical memory size When you go from physical memory With frames to x frames note that the number of C vector terms in the RHS of equation for F decreases gt Page faults can only decrease if at all Paging Issues Keep the essentials of What you currently need working set in physical memory When something you need is not in memory bring it in from disk On demand demand paging Ahead of need pre paging Programs need to exhibit good locality to avoid thrashing of pages in memory This usually requires good programming skills Fragmentation in paging 39 Note that there is only internal fragmentation and that too only in the last allocated page 39 Smaller the page smaller the internal fragmentation 39 However this reduces spatial locality Page size trade offs Average process size s bytes Page size p bytes Page Table entry I e bytes 39 Overhead sep p2 To minimize p sqrt2se Summary Page Replacement Virtual memory Page faults Optimal page replacement not achievable Variety of algorithms Anomalies 39 Next time Virtual memory issues
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'