New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Operating Systems

by: Roman McCullough

Operating Systems CMPSCI 377

Roman McCullough
GPA 3.57

Mark Corner

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Mark Corner
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 8 page Class Notes was uploaded by Roman McCullough on Friday October 30, 2015. The Class Notes belongs to CMPSCI 377 at University of Massachusetts taught by Mark Corner in Fall. Since its upload, it has received 8 views. For similar materials see /class/232265/cmpsci-377-university-of-massachusetts in ComputerScienence at University of Massachusetts.


Reviews for Operating Systems


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: 10/30/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 dis 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 dis 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 access se uence 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 CMPSCI 377 Operating Systems Paging and Virtual Memory ln modern operating systems applications do not access physical memory directly instead they use virtual memory Each application has the illusion of having the whole address space to itself starting from address 0 to 2GB or more Notice that while programs manage memory at the level of bytes the OS manages the memory in groups of bytes called pages typically of 4kB or SkB in size Handling memory in uniformly sized chunks makes it easier to manage the whole memory think of playing Tetris with all squaresi Both the virtual and the physical memory are treated this way ie by being divided into pages To keep the discussion unambiguous we generally refer to virtual pages as pages and physical pages as page frames or simply as framesi Every virtual page has a virtual address which is mapped to a page frame in the physical RAMi When some application needs to access a virtual page the system translates its virtual address into a real physical address and then the actual data might be read andor written Notice that some virtual pages do not map to any actual physical memory address because not all virtual pages are necessarily being used at any given time these unused virtual pages are called invalidi If a program ever tries to access an invalid page the CPU traps to the operating system causing a Segmentation Fault or Access Violationi 1 So far we only know that virtual memory is somehow mapped into physical memory But why do we need virtual memory Some of the reasons for using it are the following 0 Each individual program to have the illusion of having the whole address space for itself 0 The address space used by each process is isolated from other applications iiei applications cannot damage other applications Notice that since each program thinks it has the whole memory to itself programs can use a lot of virtual memory in fact a computer might use huge amounts of virtual memory much more than the amount of actual physical memory available Of course this is no magic trick Using much more virtual memory than actual physical RAM works because in practice processes use only a small portion of their virtual address space lf however all processes suddenly decide to use more virtual memory than can be mapped into physical memory then we need to use some other mechanism such as paging discussed later Typical operating systems use a virtual address space layout which includes a stack a mmap region a heap and the programs coder Because the stack grows towards the heap if the program calls a recursive function too deeply the stack could over ow into the heap region which will generally cause the program to crash 201 The Memory Management Unit MMU When a program issues a memory load or store operation the virtual addresses VAs used in those operations have to be translated into real physical memory addresses PAS The MMU Memory Management Unit a portion of the CPU performs these translations The MMU uses a page table eigi big hash table that maps VAs into PAsi Since memory accesses happen all the time the MMU must be really fast and is thus 1Notice that although arrays are contiguous in virtual memory parts of it can be mapped into nonecontiguous physical memory addresses 22 Chapter 2 Paging and Virtual Memory implemented in hardware Notice however that mapping every single byte of virtual memory to a physical address would require a huge page table one entry per byte of virtual address space lnstead the MMU maps virtual pages to physical pages Also since we want to isolate each program s address space from other applications address spaces the MMU must keep a separate page table for each process Thus multiple different processes use the same virtual address to refer to their own data which is not a problem since these addresses would be mapped into different physical addresses The page table also marks all virtual pages that are allocated and therefore are being used so that it is possible to know which ones pages have valid mappings into PAs Virtual pages that are not being mapped into a physical address are marked as invalid a CPU exception occurs when a program tries to reference or access a virtual address that is not valid Besides valid bits entries in the page table also store lots of other information such as read and write bits to indicate which pages can be readwritten 202 Virtual addresses Virtual addresses are made up of two parts the rst one contains a page number and the second one contains an offset inside that page Suppose our pages are 4kB 4096 bytes long and that our machine uses 32 bit addresses Then we can have at most 232 addressable bytes of memory therefore we could t at most 232212 220 pages This means that we need 20 bits to address any single page Thus the rst part of the virtual address is formed by its 20 most signi cant bits These bits are used to index into the page table The 32 7 20 12 least signi cant bits of the VA are used as an offset inside the page Of course with 12 bits of offset we can address 212 4096 bytes which is exactly what we expect in order to address every byte inside our 4kB pages 203 Page Table Structure Each process has its own separate page table A page table with 220 entries each entry consuming 4 bytes requires 4MB of memory While this seems like very little on modern machines with gigabytes of RAM a system with 80 processes would need more than 300 megabytes just for storing page tables Modern systems solve this problem by using multi level page tables This approach hierarchically divides the virtual address space so that the rstlevel table points to secondlevel tables and so on Previously we described a llevel system which split the virtual address into two parts Consider a 2level system which divides the VA into three parts an offset into the page 12 bits a levell page table index 10 bits and a level0 page table entry 10 bits Then if we use the 10 most signi cant bits of a virtual address we obtain an index in the level0 page table if we follow the pointer given by that entry we get a pointer to a levell page table The entry to be accessed in this page table is given by the middle 10 bits of the virtual address We can again follow the pointer speci ed on that levell page table entry and nally arrive at a physical page The last 10 bits of the VA gives us the offset within that frame Using this structure the system consumes much less physical memory to store page tables for processes which consume small amounts of virtual address space For example a process which maps only a single virtual page needs 210 1024 bytes of memory for its level0 page table and another 1024 bytes for a single levell page table in this case only one entry in the Olevel table is used the rest of the entires are invalid and do not point to levell tables What about 64bit systems If the system used at tables it would require 252 entries in the page table Even if a twolevel scheme were used the level0 index would require 64 7 10 7 l2 42 bits thus requiring a 242 entry tablel Thus 64 bit systems use page tables with higher depth eg 4 level tables A drawback of using this hierarchical approach is that for every load or store instruction we have to perform Chapter 2 Paging and Virtual Memory 23 several indirections which of course makes everything slowerl Modern systems reduce this overhead by several orders of magnitude using something called the Translation Lookaside Buffer TLB The TLB is a fast fully associative memory that caches mappings from virtual page numbers to physical frame numbersl Typically TLBs can cache from 8 to 2048 page table entries Some systems such as IBM s Power4 have 2level TLBs similar to having L1 and L2 caches in the CPU for memory Finally notice that if the total virtual memory in use ie the sum of the virtual memory used by all processes is larger than the physical memory the OS must put some of the excess somewhere In this case the disk is used to store memory pages that must be removed to make room for other active pages We call this page eviction When these pages are accessed again the OS restores them to physical RAM from the disk possibly evicting other pages If processes continually access pages swapped to disk then the system will spend most of its time moving data around from RAM to disk This situation is called thrashing as the system does lots of work but makes no useful progressl


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


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'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Jennifer McGill UCSF Med School

"Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.