Recap Example of page access string and different algorithms Example of distance string and determining how many page faults at different number of frames Belady s Anomoly more frames fewer faults Demand Paging Global vs Local PRA Page Size Large good for I O Prefetch Small has less fragmentation better locality Moran OS Lecture 8 1 Stack Algorithms Recall Balady s Anomaly 012301401234 FIFO with 3 frames vs FIFO with 4 Stack PRAs don t risk this Stack PRA is one where the set of pages in memory with N frames is a subset of the set of pages in memory with N 1 frames LRU and Optimal are Stack PRAs More frames means fewer faults Moran OS Lecture 8 2 Implementation Issues 2 Page Faults what really happens Hardware traps to the kernel save some state Save state and call the OS assembly language If we know which page is needed fine otherwise we need to figure it out from the instruction being executed Check whether address is valid if not kill process Find a frame if it is dirty schedule a write Block the process Also keep anyone else from using the frame When the frame is clean schedule a read to populate the frame The process is still blocked When the read has completed restart the instruction Put the process in the ready state When the process is ready to run again asm routine runs to restore state Moran OS Lecture 8 3 Pages for Processes How to decide how many page frames a process gets we don t want to thrash Basic answer is that we want to give every process the number of pages in its working set Page Fault Frequency Keep track of the number of faults compared to the number of references using a time decay If the process has too high a rate give it more frames If not all processes can be satisfied reduce the level of multi programming by swapping some out Moran OS Lecture 8 4 Working Set PRA Basic idea is to keep track of the working set and fault out pages not in the working set Keep track for each PTE virtual time of last use and a referenced bit Scan all pages any page with R 1 gets the last use updated to now Any page with R 0 compare last use time to now if the difference is big enough grab that frame If we get no pages doing this and there were any pages with R 0 fault out the one used longest ago Otherwise if none are R 0 fault one out at random Moran OS Lecture 8 5 WSClock Arrange the PTEs as in Clock with a reference bit a modify bit and a last use time like working set Scan like clock if R 0 and it is old then if it is not modified grab it if it is modified schedule a write and continue If we get back to the start if no writes have been scheduled grab a page that is clean otherwise keep going until we get to a clean page Moran OS Lecture 8 6 Segmentation We have been assuming that the virtual address space is contiguous This doesn t work very well when a process has two or more dynamically growing regions With two regions we can start them on opposite sides of the virtual address space stack and heap Alternatively we could have a number of virtual address spaces that start at address 0 Called segments Will be user visible Makes sharing and protection somewhat easier Moran OS Lecture 8 7 Segmentation vs Paging Consideration Demand Paging Segmentation Programmer Aware of Addr Spaces VA size PA size Protection No 1 Yes Pages Yes Many Yes Procedures Accommodate elems Changing size Ease Sharing Internal Fragmentation External Fragmentation Placement Question Replacement Question No Yes No Yes No No Yes Yes No in theory Yes Yes Yes Moran OS Lecture 8 8 General Segmentation Allows fine grained sharing and protection Segments can be variable sized Addresses become Segment Offset Memory layout All segments in memory to run a program Demand segmentation Combine with demand paging Moran OS Lecture 8 9 Number of Segments 1 One Segment We covered this in Multiprogramming with variable partitions Two Segments One shared text segment read only One private data segment writable Permissions on each When a segment has to be evicted swapping out the shared segment may hurt multiple processes however the shared segment is read only so it is cheap to swap it out Moran OS Lecture 8 10 Number of Segments 2 Three Segments Shared text segment execute only Data segment Stack segment Traditional Unix systems looked very similar to this Moran OS Lecture 8 11 Segments with Paging Virtual Address is now Segment Page Offset Segment Table Entries point at page tables Segments are variable size with a fixed maximum Protection and sharing information kept on a per segment basis Replacement and placement decisions done on pages Segments are shared by sharing the page table Two good examples in the book Moran OS Lecture 8 12 Memory Management Recap 1 Why multiprogramming Multiprogramming with fixed partitions Multiprogramming with variable partitions How we place things in holes first fit next fit worst fit best fit quick fit etc Fragmentation internal vs external Virtual Memory Pages Page Frames Page Tables Multilevel page tables Moran OS Lecture 8 13 Memory Management Recap 2 Page Replacement Algorithms Optimal FIFO LIFO Random Not Recently Used 2nd Chance Clock Least Recently Used Not Frequently Used Working Set WSClock Why these work Working Set Locality Global vs Local Allocation Implementation Issues Segmentation More Granular Moran OS Lecture 8 14 File Systems Requirements for Data Storage Size we need to store very large amounts of data Persistence the data needs to stay around after the creating process terminates Access multiple processes can access the data at the same time Store data in files The part of the OS that manages the files is called the file system Moran OS Lecture 8 15 File Names 1 How does a user or program refer to and find the collection of data the file The file system provides a way to name the files Not every file will have a unique name Often the file name will consist of two parts of the form XXXXXXX YYY where the YYY part is called the file extension The file extension is usually used to tell what kind of file it is com or exe on a DOS or Windows box Moran OS Lecture 8 16 File Names 2 Unix doesn t enforce the naming conventions Many applications do C compilers usually demand a c suffix Compression utilities with z Z gz etc html with net browsers This isn t OS behavior though Length and forms of names Valid characters 8 3 in DOS 14 in some Unix Unlimited or 255 in most Unix Moran OS Lecture 8 17 What is in a File 1 A Stream of Bytes OS doesn t care about the contents Unix