Note for CMPSCI 377 at UMass
Note for CMPSCI 377 at UMass
Popular in Course
Popular in Department
This 5 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 14 views.
Reviews for Note for CMPSCI 377 at UMass
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 02/06/15
CMPSCI 377 Operating Systems Paging amp Replacement Algorithms 31 Demand Paging amp Eviction Virtual memory gives processes the illusion of having much more available memory than may actually be physically present in the systemi lf processes allocate more pages than are physically available the OS must evict other pages to disk to make room for the new pages The system keeps extra metadata in its page tables to keep track of which pages are resident in main memory ie not on disk Just as the system detects invalid memory references via the validinvalid bits it can detect when a process accesses a page that was previously evictedi Modern operating systems read pages from disk on demand that is upon the rst reference to the page Thus pages begin in a nonresident state In order to bring in a page the OS must allocate a physical frame for the page In some cases such as when the machine is newly booted the system may still have some free physical frames However as the system runs it will ll all of the physical memory with running processes and cached data from les Thus the OS must evict some page from physical memory and store it on disk In order to evict a page the OS must ensure that the on disk contents match the latest in memory version In some cases such as program code the memory contents will not have changed since they were loaded from the disk In that case the OS can simply discard the in memory contents since it can restore the page from the original location on disk However many pages such as those containing program data may not be resident on disk Other pages may exist on disk but the in memory contents have changed Such a page that has been modi ed in memory is called dirty because it is no longer up to date The process of converting dirty pages to clean pages by writing the memory contents to disk is called page launden39ng iiei converting dirty pages to clean pagesi Prior to evicting a dirty page the OS launders the page ensuring that the disk contents match the most recent memory contentsi However handling a page fault is much cheaper if the OS can evict a clean page rather than a dirty page If there is a clean page it can evict it can simply read the contents of the evicted page into the memory of the clean page and update the page tables invalidating the overwritten page s entry and creating one for the restored page However if there are only dirty pages it must write the contents to disk before reading the contents of the evicted page thus causing the page fault cost to double In order to avoid evicting dirty pages the OS launders pages periodically in the background By performing laundering the OS attempts to keep a certain number of clean pages in order to ensure that page faults can be handled as quickly as possible 3 1 32 Chapter 3 Paging 75 Replacement Algorithms 32 Swap Space The portion of the disk reserved for holding evicted pages is known as the swap space On some operating systems such as Windows the swap space is a le in the lesystem On others such as Linux the swap space is stored on a separate partition on disk The swap space is the backing store for the physical RAM That is the RAM acts as a cache of the swap space on the disk Virtual memory allows processes to allocate more virtual address space than the system has physical memory However all allocated virtual address space must be backed by swap So the amount of swap space determines the maximum amount of allocated virtual memory across all processes 3201 File caching If we consider the contents of the virtual address space of a process some of this memory contains program data such as the stack and the heap However other parts of virtual memory contain program code which is read directly from the program executable le on disk Such virtual memory is called a mapped le What happens when the OS needs to evict a page containing a mapped le If the contents have not changed ie the page is not dirty the OS need not write the contents of the page into swap space Why not When the page is subsequently accessed the OS can simply restore the contents from the original le on disk rather than swap 3202 Page Protection What if the program tries to write to a page mapped to a le rather than swap In the case of an executable program we don7t want the program to corrupt executable by allowing the write and updating the disk copy when the page is laundered Otherwise a program error like a buffer over ow could corrupt a program or even a shared library Thus the OS marks such pages readonly In order to support readonly and other types of protection the MMU supports bits in the page table known as access bits All systems have R and W bits read and write privileges For program data such as the stack the pages have both bits set so they can be both read and written For pages mapped into program les the OS will mark the pages as readonly only the R bit set 321 A Day in the Life ofa page Suppose your program allocates some memory with malloc what happens in this case is that the allocator gives part of a memory page to your program The OS then updates the corresponding page table in order to mark the virtual address of that page as valid by doing so it will later on be able to tell that that page is indeed being mapped to a real physical page If that page is modi ed it is marked as being dirty If the OS ever needs to evict the page where the data is it has to copy that page to disk ie it swaps it out then that page is marked valid nonresident nonreadable and nonwritable If we ever touch that page again ie if we try to read or write it the OS may have to evict some other page in order to bring our page back to RAM One obvious implication of this is that page faults are slow to resolve since disk accesses are performed Thus one possible optimization is for the OS when idle to write dirty pages to disk by doing so when it comes the time to really evict those pages the OS won t have to write them to disk and therefore will be able to kick them out much faster Chapter 3 Paging amp Replacement Algorithms 33 33 Tricks with Page Tables As you know page tables map virtual page addresses to physical page addresses One of the advantages of using virtual memory is that we can achieve complete separation between processes in terms of address spaces However in some cases we donlt want the processes to have completely independent memory areas in these cases we can do some tricks with page tables to allow shaiing of some portion of physical memory Sharing memory usually reduces memory requirements Suppose for example you have two instances of the same program running at the same time although they are in practice different processes they share a lot of common components program code shared libraries etc So in this case the use of sharing reduces memory requirements Even between different programs some data can be shared such as libci The rst important concept related to memory sharing is known as COW or Copy On Writer COW is based on the idea of sharing pages by default until they become different Whenever a new process is created we actually clone an old process by making a copy of its page tables and marking all referenced pages as readonlyli Whenever either of the processes the parent or the child tries to write to the page the OS allocates a new page and changes the mapping in one of the page tables After this new mapping has been created the processes no longer share the mapping to the same physical address However if neither of the processes ever tries to modify a memory location the processes will share the same readonly pages forever Notice that the idea of cloning processes and sharing their pages unless someone tries to modify them is pretty interesting when it comes to shared libraries Since a lot of programs use the same libraries eigi libc they can share those libraries without each having to load its own copy again and again In other words COW tiies to maximize the amount of shaiing at all times 34 Allocating new pages How does the allocation of pages work Remember that processes have valid and invalid entries on their page tables The valid entries all point to somewhere real eg a physical page or some portion of diskiin case of nonresident pages etc But what about the entries that donlt point anywhere Well those are exactly the entries that we will use when allocating a new page The allocation of new pages can be done in two ways either via sbrk or via mmapi If you want to increase the size of the heap ie the number of valid pages you can use sbrki Mmap on the other hand maps a process7 address space to a le In the allocator you implemented for example you used mmap to map memory addresses to the le devzeroi This means that each time you called mmap you were sort of allocating memory from devzeroi Remember that whenever you read something from dev zero you get only zeroes but after having mmapled it if you ever try to write to the memory being mapped to devzero the OS intervenes and clones the corresponding page Then instead of actually writing to devzero you end up writing to a new memory page This COW behavior happens both because devzero is a readonly le and because mmap was called with the parameter MAPJE RIVATE Now suppose you mmap 3 pages to devzeroi Right after you do this the process7 page table contains three mappings to devzeroi These are all COW mappings to a same single page in memory which itself maps to devzer02i However the rst time some of these pages is modi ed a new page is created and the corresponding mapping in one of the page tables is modi ed Notice that we could have used mmap with any other le instead of devzero say an MP3 le In this case whenever we mmapld we would be actually mapping memory addresses to portions of the MP3 le If we then tried to write to those areas of memory we would be indirectly overwriting the le Notice however that we could be careful enough and 1In fact in Unix all processes spawn in this way from a single process called init 2This implies that if you were to map 6 gibabytes but never touch those all you7d have really allocated is 4kb bytes 7 the 4kb corresponding to the single shared page on memory that maps to devzero 34 Chapter 3 Paging amp Replacement Algorithms used the mmap parameter MAPPRIVATE then we would still be able to read from the MP3 le but all writings to it would be done using Copy On Write 35 Replacement policies Suppose we have to evict some page from memory in order to bring back a page that is on disk how do we choose which page to evicts There are several possible algorithms One interesting idea in order to assess their performances is to compare them with the best possible algorithm called Optimal Replacement Policy OPT The idea of OPT is that we evict the page accessed furthest in the future but how can we predict the future We canltl But that doesnlt matter since we are not really trying to implement OPT All we re doing is trying to get as close to its performance as possible Now getting back to reality let s discuss LRU LeastRecently Used LRU evicts the page not used for the longest time It approximates OPT whenever the recent past is a decent prediction of the future Notice that variants and approximations of the LRU policy are currently used in all real operating systems What about evicting the MostRecently Used page For one thing this does very well on LRUls worst case loops that exceed RAM size but in general MRU is not a good idea Another possibility is to evict the oldest page this is accomplished by a Firstin7 Firstout FIFO policy In theory FlFO is as competitive as LRU but in practice it performs miserably since it ignores temporal locality suppose pages ABCAD are in memory then when hitting D a FlFO algorithm would evict Al 351 Implementation So how do we actually implement LRU One idea is to mark everything the program touches with a times tamp Whenever we need to evict a page we select the oldest page ie the leastrecently used page It turns out that this simple idea is dif cult to implement ef ciently Why Because for every memory load we would have to read contents of the clock and perform a memory storel So it is clear that keeping timestamps would make the computer at least twice as slow Another idea is to keep a list Every time we touch something we move that page to the beginning of the list Whenever we need to evict a page we evict the last element of the queue Now we don7t need to use timestamps but we still have to do some pointer manipulation Notice however that trying to do that for every load or store operation is actually even worse than using timestamps A third idea using a hash table In this case the problem is that on every memory access we have to compute a hash function Bad idea Final idea let s approximate LRU by maintaining reference bits for every page in hardware On each memory access we set the page s reference bit to l A page replacement algorithm periodically resets the reference bits Whenever we need to evict a page we select one that has a reference bit not set Thus a page with a set bit has been used since the last time the bits were cleared This algorithm considers whatever is zeroed to be old enough then although we can t know exactly what is the leastrecently used we do know that whatever is marked is a least more recent than something not marked However if many pages have zero reference bits the system cannot tell which are the least recently used pages so it must choose randomly between them Thus it might evict a page that was used 1 minute ago over a page used 1 hour ago 3Notice that we are usually interested in studying best asymptotic worstecase algorithms Notice also that the worst case for leasteused policy is that every page access causes a page fault this can be accomplished if we construct on purpose a terrible page access sequence Since this case is not really saying much useful about the algorithm we will try to focus not so much on the theoretical worstecase but on the practical characteristics of each algorithm Chapter 3 Paging amp Replacement Algorithms 35 Now let us discuss two other algorithms for deciding which pages to evict The clock algon39thm is one of the most popular choices it works by keeping frames in circular list and keeping a pointer to the list the clock hand which points to a page When a page fault occurs it checks the reference bit of the frame pointed to by the clock hand If that bit is 0 it evicts that page and sets its bit to 1 if the reference bit is 1 the algorithm sets the bit to 0 and advances the pointer to next frame For more details please refer to http enwikipedia orgwikiPagerep1acementa1gorithmi This algorithm has the advantage that it only does work aside from the MMU setting bits which is free for all practical purposes when a page is evicted The algorithm only clears bits when it evicts a pager Thus when the eviction rate is low the clock hand will move around the list very slowly ensuring that evicted pages have not been accessed in a long time Linux uses a hybrid system called a segmented queue This type of algorithm divides all resident pages into two sets A third of all pages the pages that are the most active iiei least recently used reside on the active list and use the a clock algorithmi The remaining pages reside on a inactive list which is managed by exact LRUi When clock evicts a page from the active list the page moves to the inactive list This way we approximate LRU for the frequentlyreferenced pages 13 of the page frames fast clock algorithm and at the same time use exact LRU on the infrequently accessed pages 23 of page frames 352 Drawbacks The question of fairness regarding page eviction is a hard one How do we decide what is fair We can put all pages from all processes into one list and then manage it using a segmented queuei This approach is easy to implement but has a considerable drawbacki To understand it suppose you have a computer running both minesweeper and a nuclear reaction control programi The nuclear program does not run very often and thus is paged out constantly even though it is more important since it is constantly paged out it always runs sloweri Is that fair Of course not In general the problem of fairness is that processes that are greedy or wasteful are rewarded processes with poor locality end up squeezing out those with good locality because they steal memoryi There is no simple solution to this problemi