Outline for EECS 678 with Professor Kulkarni at KU 3
Outline for EECS 678 with Professor Kulkarni at KU 3
Popular in Course
Popular in Department
This 49 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Kansas taught by a professor in Fall. Since its upload, it has received 91 views.
Reviews for Outline for EECS 678 with Professor Kulkarni at KU 3
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: 02/06/15
5 Virtual Memory Outline I Background l Demand Paging l CopyonWrite l Page Replacement l Allocation of Frames l Thrashing l MemoryMapped Files I Allocating Kernel Memory l Other Considerations l OperatingSystem Examples EECS 678 Introduction to Operating Systems 7 Sp ng 2009 5 Background l Virtual memory separation of user logical memory from physical memory 0 only part of the program needs to be in memory for execution o logical address space can therefore be much larger than physical address space 0 allows address spaces to be shared by several processes 0 allows for more efficient process creation I Benefits of not requiring the entire program in memory before execution 0 programs can be larger than the physical address space 0 more programs can be resident in memory at the same time o faster program startup EECS 678 Introduction to Operating Systems 7 Sp ng 2009 If I Space between heap and stack is not used unless the heap or stack grows l Shared memory Virtualaddress Space Max stack virtual memory does not require physical pages for such holes pages can be easily shared by virtual memory shared libraries can be mapped readonly into address space of heap each process data shared memory IPC can be implemented easily code parent pages can be shared with 0 child during fork EECS 678 Introduction to Operating Systems 7 Spring 2009 QShared Library Using Virtual Memory stack stack shared shared library pages shared library heap heap data data code code EECS 678 Introduction to Operating Systems 7 Spring 2009 4 Demand Paging l Bring a page into memory only when it is needed 0 less lO needed 0 less memory needed 0 faster response 0 more applications simultaneously resident in memory I Page is needed gt reference to it 0 invalid reference gt abort O notinmemory gt bring to memory I Lazy swapper never swaps a page into memory unless page will be needed I Swapper that deals with pages is a pager EECS 678 Introduction to Operating Systems 7 Sp ng 2009 9 Demand Paging System program A program B swap out 0D1El 2D 3D main memorv 415 55 ea 75 8D 9I1011I 12D13D14D15D swapin 16D17 18 19 20 D21 I322 D23 II EECS 678 Introduction to Operating Systems 7 Spring 2009 ValidInvalid Bit l Each page table entry associated with a valid invalid bit 0 v gt inmemory i gt notinmemory I initially set to invalid for all page table entries I Example of a page table snapshot Frame validinvalid bit page table I Valid invalid bit in page table set to i during address translation causes a page fault EECS 678 Introduction to Operating Systems 7 Sp ng 2009 7 13 Page Table When Some Pages Are Not in Main Memory 0 1 O A 2 valid invalid 1 B frame bit 3 2 C o 4 v 4 A 3 D 1 i 5 2 6 v 4 E 3 i 6 C 5 r 4 i 7 5 9 V 8 G 6 i s 7 H 7 i 9 F logical Page 1abe 10 memory 11 12 13 14 15 thsical memow EECS 678 huroduction to Opemiing Systems 7 111ng 2009 Steps in Handling a Page Fault operating system reference 6 load M 1 restart instruction re i page table 5 set page table page is on backing store free frame physical memory GD bring in missing page EECS 678 Introduction to Operating Systems 7 Spring 2009 5 Steps in Handling a Page Fault 2 N 9015 First reference to data or instructions on a page occurs Memory access traps to the OS with a page fault 0 operating system looks at another table to decide gt invalid reference gt abort orjust not in memory Find a free frame in physical memory Read page from disk into free frame Update page table validinvalid bit to 39v39 Restart the instruction that caused the page fault EECS 678 Introduction to Operating Systems 7 Sp ng 2009 10 5 Performance of Demand Paging l Page Fault Rate 0 s p s 10 o ifp 0 no page faults o ifp 1 every reference is a fault I Effective Access Time EAT EAT 1 p x memory access p page fault overhead swap page out swap page in restart overhead EECS 678 Introduction to Operating Systems 7 Sp ng 2009 11 Demand Paging Example I Memory access time 200 nanoseconds l Average pagefault service time 8 milliseconds l EAT 1 p x 200 p 8 milliseconds 1 p x 200 p x 8000000 200 p x 7999800 I If one access out of 1000 causes a page fault then EAT 82 microseconds This is a slowdown by a factor of 40 EECS 678 Introduction to Operating Systems 7 Sp ng 2009 12 Process Creation CopyonWrite l Original process creation 0 fork system called duplicates parent address space for child 0 demand paging with copyonwrite allow sharing address spaces l CopyonWrite COW allows both parent and child processes to initially share the same pages in memory 0 shared pages marked as copyonwrite pages 0 if either process modifies a shared page then the page is copied 0 only the modified pages are copied l COW allows more efficient process creation as only modified pages are copied l Free pages are allocated from a pool of zeroedout pages EECS 678 Introduction to Operating Systems 7 Sp ng 2009 13 3 Process 1 Modifies Page C physical process1 memory processg page A Before PageB page C physical process1 memory process2 page A After page B page C Copy of page C EECS 678 Introduction to Operaling Systems 7 Spring 2009 14 5 Need For Page Replacement l Review of demand paging c separates logical memory from physical memory 0 allows logical address space gt physical address space 0 enables a greater degree of multiprogramming gt higher CPU utilization and throughput 0 allows fast process startup l Drawbacks of demand paging 0 may increase later individual memory access times 0 potential for overallocation of physical memory I Overallocation of memory 0 currently active processes may reference more pages than room in physical memory 0 pages from active processes may need to be replaced EECS 678 Introduction to Operating Systems 7 Sp ng 2009 15 Page Replacement l Page replacement is needed when a page fault occurs and there are no free frames to allocate O terminate user process O swap out an entire process I find some page in memory hopefully not really in use and swap it out l Same page may be brought into memory several times EECS 678 Introduction to Operating Systems 7 Sp ng 2009 16 5 Basic Page Replacement 1 Find the location of the desired page on disk 2 Find a free frame If there is a free frame use it If there is no free frame use a page replacement algorithm to select a victim frame 3 Bring the desired page into the newly free frame update the page and frame tables 4 Restart the process I Reducing page fault overhead 0 use modify bit to with each frame 0 only copy the replacement page to memory if modified EECS 678 Introduction to Operating Systems 7 Sp ng 2009 17 5 Basic Page Replacement 2 frame valid invalid bit 1 swap out change victim 0 i to invalid Page f v N f victim reset page 7 table for page table new page Swap desired page in physical memory EECS 678 Introduction to Operating Systems 7 Spring 2009 Page Replacement Algorithms l Criteria 0 get the lowest page fault rate I Page replacement schemes 0 first in first out FIFO 0 optimal page replacement 0 least recently used LRU o LRU approximation algorithms 0 counting based replacement I Evaluation of replacement algorithm 0 simulate it on a particular string of memory page references 0 compute the number of page faults on the reference string I In all our examples the reference string is 7 012 0 3 04 2 3 0 3 212 017 01 EECS 678 Introduction to Operating Systems 7 Sp ng 2009 19 Expected Graph of Page Faults Versus The Number of Frames LA b0 N 74 number of page faults ES thm 1 2 3 4 5 6 number of frames EECS 678 Introduction to Operating Systems 7 Spring 2009 20 J FirstlnFirstOut FIFO Algorithm l Simplest page replacement algorithm 0 each page associated a time when it was brought in memory 0 replace the oldest page during page replacement 0 implemented using a FIFO queue of all pages 0 replacement page found from the head ofthe queue 0 new page added to the tail of the queue reference string 7012030423032 1201 III Eli I I I El page frames EECS 678 Introduction to Operating Systems 7 Spring 2009 21 E Belady39s Anomaly I For some page replacement algorithm the page fault rate may increase as the number of frames increases 0 can happen with FIFO replacement scheme I Example 0 reference string 1 2 3 4 1 2 5 1 2 3 45 0 FIFO replacement algorithm 1e 14 12 10 number of page faults NPCDGJ 1 2 3 4 5 6 7 number of frames EECS 678 Introduction to Operating Systems 7 Spring 2009 3 Optimal Page Replacement l Algorithm with the lowest page fault rate 0 replace the page that will not be used for the longest period 0 provany optimal 0 does not sufferfrom Belady39s anomaly 0 needs future information reference string 70120304230321201701 I ll II page frames EECS 678 Introduction to Operating Systems 7 Spring 2009 23 aLeast Recently Used LRU Algorithm l Approximate the optimal page replacement algorithm 0 detect and store when each page is used 0 replace page that has not been used for the longest period 0 a very good replacement policy 0 requires hardware support to be accurate and fast 0 does not suffer from Belady39s anomaly reference string 4 2 3 7012080 0321201701 I IEEE E HE E I II page frames EECS 678 Introduction to Operating Systems 7 Spring 2009 24 5 LRU Implementation l Counter implementation 0 every page table entry has a timeof use field 0 copy the clock into the timeof use field on every page access 0 for replacement find the page with the smallest timeof use field 0 replacement algorithm requires search of the full page table 0 each memory access needs additional write to timeof use field 0 counter overflow EECS 678 Introduction to Operating Systems 7 Spn39ng 2009 25 5 LRU Implementation 2 I Stack implementation 0 keep a stack of page numbers in a linked list 0 move page to top of stack when referenced 0 nd replacement page from bottom of stack 0 each update is more expensive due to stack operations 0 no search for replacement reference string 4707101212712 2 7 i i a b 1 2 0 1 7 O 4 4 stack stack before after a b EECS 678 Introduction to Operating Systems 7 Spring 2009 26 LRU Approximation Algorithms l Reference bit algorithm 0 associate reference bit with each page 0 set bit when page is references clear all bits occasionally 0 replace page that has reference bit 0 if one exists 0 cannot store the order of accesses in one bit l Record reference bit algorithm 0 each page associated with a 8 bit field for recording reference bit 0 at regular intervals gt right shift 8 bit field gt move reference bit into highest order bit 0 page with lowest value in 8 bit field is the LRU page 0 Example reference bit 8 bit field gt 110101100s 01101110 gt 0 11001101 0 01100110 EECS 678 Introduction to Operating Systems 7 Sp ng 2009 27 I LRU Approximation Algorithms 2 I Second chance algorithm single reference RF bit basic FIFO replacement algo find replacement page gt proceed if RFO gt give page 2nd chance if RF1 and move onto next page clear reference bit circular queue of pages pointer indicates next replacement page what is all bits are set EECS 678 Introduction to Operating Systems 7 Spring 2009 next victim reference bits 0 pages eeee 4 k circular queue of pages a reference bits pages O eeee 4 U circular queue of pages 0 28 I Keep a counter of the number of references that have been made to each page I Least frequently used I replace page with the smallest count 0 most active page should have largest count I Most frequently used I replace page with the largest count 0 page with smallest count was brought in last and will be accessed next I Not very popular algorithms CountingBased Algorithms EECS 678 Introduction to Operating Systems 7 Sp ng 2009 29 Page Buffering Algorithms l Optimizations by maintaining a list of victim frames l Scheme 1 0 bring new page into one of victim frame slots 0 then copyout the replacement page to memory 0 memory access to new page does not wait for copyout l Scheme 2 o copyout modified pages to disk when paging device is idle 0 replacement is now faster I Scheme 3 o remember which page is in each victim frame 0 if new page is in one of victim frame then use directly 0 works well if replacement algorithm replaces a page that is needed after afterwards EECS 678 Introduction to Operating Systems 7 Sp ng 2009 30 5 Allocation of Frames I How many frames in physical memory should the OS allocate to each process l Minimum number of frames 0 is there a minimum number of frames a process needs 0 depends of the maximum number of pages any instruction in the ISA can reference at a time gt what can happen if we do not provide this minimum 0 direct addressing loadstore need 2 frames gt one for instruction and one for memory reference 0 onelevel indirect addressing needs 3 frames gt one for instruction one for address and one for memory reference 0 PDP11 needs 6 frames IBM 370 needs 8 frames 0 should there be a maximum number EECS 678 Introduction to Operating Systems 7 Sp ng 2009 31 Frame Allocation Algorithms l Equal allocation 0 divide m frames equally among n processes 0 each process gets about mn frames 0 may give some process more frames than it needs l Proportional allocation 0 each process may need different amounts of memory 0 allocate memory proportional to process size 0 Example m 64 s 2 size of process p s 10 S 2 s 32 127 m total number of frames a1 EX 64 z 5 s 137 a allocation for p E x m 127 a2 x 642 59 137 EECS 678 Introduction to Operating Systems 7 Sp ng 2009 32 5 Other Frame Allocation Issues l Global Vs local allocation 0 global replacement process selects a replacement frame from the set of all frames gt one process can take a frame from another gt process cannot control its own pagefault rate 0 local replacement each process selects from only its own set of allocated frames gt may hinder progress by not allowing highpriority process access to frames of lowpriority process I Nonuniform memory access 0 memory may be distributed on multiprocessor systems 0 how to assign frames in such situations o assign memory which is close to where a process is running EECS 678 Introduction to Operating Systems 7 Spn39ng 2009 33 5 Thrashing l A process is thrashing if it spends more time paging than executing 0 process keeps swapping active pages in and out 0 leads to a very high page fault rate I Causes of thrashing behavior 0 process does not have enough pages I Vicious cycle of thrashing 0 not having enough frames cause more page faults O lowers CPU utilization 0 operating system thinks that it needs to increase the degree of multiprogramming 0 another process added to the system even less frames per process leads to more page faults 0 cycle continues EECS 678 Introduction to Operating Systems 7 Sp ng 2009 34 is Thrashing 2 I Thrashing becomes more likely with increasing degree of multiprogramming thrashing CPU utilization degree of multiprogramming I Can we prevent thrashing by using a local replacement algorithm EECS 678 Introduction to Operating Systems 7 Spring 2009 35 Preventing Thrashing Behavior I Give a process as many frames as it needs 0 how to know how many frames a process needs l WorkingSet model 0 based on the locality model of process execution gt each process phase uses a small set of memory references frames gt execution moves from one program phase to another 0 the number of frames required for each phase is called the working set 0 Implementation gt assume a particular workingset window A gt WSS working set of Process P total number of pages referenced in the most recent A gt D 2 W88 2 total demand frames gt If D gt m gt Thrashing then suspend one of the processes EECS 678 Introduction to Operating Systems 7 Sp ng 2009 36 53 Working Sets and Page Fault Rates l Page faults spike at the start of every new program working set also called a phase 0 page fault rate falls until the next program phase 0 behavior repeats working set page fa u It rate time EECS 678 Introduction to Operating Systems 7 Spring 2009 is Preventing Thrashing Behavior 2 I PageFault frequency scheme 0 working set model is needs several assumptions and is complicated 0 measure the page fault rate routinely o establish acceptable pagefault rate gt If actual rate too low process loses frame or increase processes gt If actual rate too high process gains frame or suspend processes increase number of frames upper bound pagefault rate lower bound decrease number of frames number of frames EECS 678 Introduction to Operating Systems 7 Spring 2009 l Memorymapped file lO allows file lO to be treated as routine memory access by mapping a disk block to a page In memory 0 removes the need to read write system calls I converts disk access to memory access 0 simplifies disk access for the user I Mechanism details 0 a file is initially read using demand paging O a pagesized portion of the file is read from the file system into a physical frame 0 subsequent readswrites tofrom the file are treated as ordinary memory accesses MemoryMapped Files EECS 678 Introduction to Operating Systems 7 Sp ng 2009 39 g5 Memory Mapped Files 2 l Allows several processes to map the same file allowing the pages in memory to be shared I 1 39 2 I r r39f39 3 1 l I l 4 Ir I 2 II 3 4 II 5 3 l39quot l39quot 39rfrr 5 4 r1 I l I I 5 quot1739 I gt 5 39 6 JI I l i Ill 39 39 I 39 IIILgt 1 J processA quot39 gt I I processB r I r quotquot 5 39 I VirtualmemoryI I IIVIrtual memory I I I I 39 L 4 39i l quotI 2 u a physical memory 1 I 1 2 3 4 5 6 disk le EECS 678 Introduction to Operating Systems 7 Spling 2009 40 i l Examples of OS using memorymapped files 0 Solaris Unix and Linux provide the mmap system call to create a memorymapped file 0 files accessed using open read write are mapped to kernel address space in Solaris 0 Windows NT and XP use memory mapped files to accomplish shared memory MemoryMapped Files 3 EECS 678 Introduction to Operating Systems 7 Spn39ng 2009 41 MemoryMapped IIO l Special lO instructions may be available to transfer data and control messages to the lO controller I Memorymapped HO O lO device registers mapped to logical memory address spaces 0 convenient and fast I There may be a control bit to indicate if data is available in the data register 0 if CPU polls the control bit then method of operation is called programmed IIO 0 if device sends interrupt to CPU to indicate data availability then mode of operation is interrupt driven IIO EECS 678 Introduction to Operating Systems 7 Sp ng 2009 42 l Kernel memory often allocated from a free memory pool 0 not using demand paging l Reasons for treating kernel memory allocation differently 0 some kernel memory needs to be contiguous o attempt to minimize memory waste due to internal fragmentation gt kernel requests memory for structures of varying size Allocating Kernel Memory gt do not use paging system I Strategies for managing free memory 0 buddy system 0 slab allocator EECS 678 Introduction to Operating Systems 7 Sp ng 2009 43 3 I Powerof2 allocator 0 satisfies requests in units sized as power of 2 0 request rounded up to next highest power of 2 0 when smaller allocation needed than is available current chunk split into two buddies of next lower power of 2 gt continue until appropriate sized chunk available I Example 0 21 kb requested from 256kb Buddy System physically contiguous pages 256 KB 128 KB 128 KB 64 KB BL 64 KB 32 KB 32 KB CL CR EECS 678 Introduction to Operating Systems 7 Spring 2009 44 5 Slab Allocator l Slab contains several physically contiguous pages I Cache consists of one or more slabs l Single cache for each unique kernel data structure 0 cache filled with instantiations of the data structure objects I Slab allocation algorithm 0 create cache of objects in contiguous space mark as free 0 store objects in free slots mark as used 0 if current slab is full of used objects allocate next object from empty slab 0 if no empty slabs go to free slots in the next slab l Benefits 0 no fragmentation 0 fast memory request satisfaction EECS 678 Introduction to Operating Systems 7 Sp ng 2009 45 Slab Allocation 2 kernel objits caches slabs 3 KB objects physical contiguous pages 7 KB objects EECS 678 Introduction to Operating Systems 7 Spring 2009 46 l Prepaging 0 reduce page faults at process startup o prepage all or some process pages before they are referenced gt HO and memory wasted if prepaged pages are unused l Issues in deciding a page size 0 internal fragmentation gt small page size preferred to reduce memory lost on the final page 0 page table size gt large page size preferred to reduce size of page table I lO overhead gt large page size preferred to reduce disk latency and seek time o Page faults gt large page size reduces number of generated page faults Other Virtual Memory Issues EECS 678 Introduction to Operating Systems 7 Sp ng 2009 47 Other Virtual Memory Issues 2 l TLB Reach 0 amount of memory accessible from the TLB o TLB Reach TLB Size X Page Size 0 ideally the working set of each process is stored in the TLB o improving TLB reach gt increase the page size gt provide multiple page sizes I lO interlock 0 pages must sometimes be locked into memory 0 consider IO Pages that are used for copying a file from a device must be locked from being selected for eviction by a page replacement algorithm 0 provide a lock bit with every page frame EECS 678 Introduction to Operating Systems 7 Sp ng 2009 48 5 Other Virtual Memory Issues 3 I Program structure 0 being aware of the paging structure can help performance 0 example Intl28128 data 0 Each row is stored in one page 0 program 1 128 128 16 384 page faults for j 0 j lt128 j for i O i 128 i dataij 0 0 Program 2 128 page faults for i O i lt 128 i for j 0 j lt 128 j dataij O EECS 678 Introduction to Operating Systems 7 Sp ng 2009
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'