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


by: Ulises Graham Jr.


Ulises Graham Jr.
GPA 3.58


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

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 8 page Class Notes was uploaded by Ulises Graham Jr. on Saturday September 12, 2015. The Class Notes belongs to CSCI 4730 at University of Georgia taught by Hybinette in Fall. Since its upload, it has received 53 views. For similar materials see /class/202307/csci-4730-university-of-georgia in ComputerScienence at University of Georgia.




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: 09/12/15
Chapter 10 Virtual Memory Questions CSCI 4730 Operating Systems Virtual Memory 1735 Maria Hybinette UGA Operating System s Goals o What is virtual memory and when is it useful 0 What is demand paging 0 When should pages in memory be replaced 0 When should pages be put on disk 0 What is the working set model Maria Hybine te UGA Idea Virtual Memory 0 Support processes when there is not enough physical memory Single process with very large address space Multiple processes with combined address spaces 0 User code should be independent of amount of physical memory Correctness if not performance Maria Hybine te UGA Observations o Sequential memory accesses of a process are predictable and tend to have locality of reference Spatial reference memory addresses near previously referenced addresses in memory Temporal reference memory addresses that have referenced in the past 0 Processes spend majority of time in small portion ofcode Estimate 90 of time in 10 of code 0 Implication Process only uses small amount of address space at any moment Only small amount of address space must be resident in physical memory Maria Hybine te UGA 0 OS provides an illusion of more memory than is physically available Large logical space but really small physical memory 0 Why does this work Only part of the program needs to be in memory at a particular time for execution Relies on key properties of user processes workload and machine architecture hardware Maria Hybine te UGA m1 1I l Wm mu l quotquotquotquot3939ImnimnllH memory address willquot H Milillllllu mltl mmm mulllmimmllm ugllllllllll IIII lilllllll nIwill Lislllllllllllii page numbers execution time h Virtual Memory Policies Page Selection 0 OS needs to decide on policies on page faults concerning Page selection When should a page or pages on disk be brought into memory Two cases o When process starts code pages begin on disk o As process runs code and data pages may be moved to disk Page replacement Which resident page or pages in memory should be thrown out to disk 0 Goal Minimize number of page faults Page faults require milliseconds to handle reading from disk Implication Plenty of time for OS to make good decision Maria Hybine te UGA Page Selection Continued 0 When should a page be brought from disk into memory 0 Request paging User specifies which pages are needed for process Problems Manage memory by hand Users do not always know future references Users are not impartial 0 Demand paging Load page only when page fault occurs Intuition Wait until page must absolutely be in memory When process starts No pages are loaded in memory Advantage Less work for user Disadvantage Pay cost of page fault for every newly accessed page Maria Hybine te UGA Virtual Page Optimizations o Prepaging anticipatory prefetching OS loads page into memory before page is referenced OS predicts future accesses oracle and brings pages into memory ahead of time How Works well for some access patterns eg sequential Advantages May avoid page faults Problems 0 Hints Combine demand or prepaging with user supplied hints about page references User specifies may need page in future don t need this page anymore or sequential access pattern Example madvise in Unix Maria Hybine te UGA What happens if there is no free frame o Page replacement find some page in memory but not really in use swap it out 0 Observation Same page may be brought into memory several times a 3 3 Q U to E lmmme AO a E ffffff r2 Maria Hybine te UGA o CopyonWrite on process creation allow parent and child to share the same page in memory until one modifies the page process2 process1 memory proce532 procesq memory Page A page A Page B page B Page C page C Maria Hybine te UGA Page Replacement 0 Which page in main memory should selected as victim Write out victim page to disk if modified dirty bit set lf victim page is not modified clean just discard o OPT Replace page not used for longest time in future Advantage Guaranteed to minimize number of page faults Disadvantage Requires that OS predict the future Not practical but good for comparison 0 Random Replace any page at random Advantage Easy to implement Works okay when memory is not severely overcommitted Maria Hybine te UGA Page Replacement Continued Evaluate Page Replacement Algorithms o FIFO Replace page that has been in memory the longest Intuition First referenced long time ago done with it now Advantages Fair All pages receive equal residency Easy to implement circular buffer Disadvantage Some pages may always be needed 0 LRU Replace page not used for longest time in past Intuition Use past to predict the future Advantages With locality LRU approximates OPT Disadvantages Harder to implement must track which pages have been accessed Does not handle all workloads well Maria Hybine te UGA Example FIFO Page Replacement 0 Want lowest pagefault rate 0 Evaluate algorithm by running it on a particular string of memory references reference string and computing the number of page faults on that string 0 Convert address to page Example Assume 100 bytes per page and Assume the address sequence 0 0100 0210 0250 0300 0350 0380 0400 0160 0250 0505 0100 0110 0230 0350 0450 0450 0500 0500 Convert address to a reference string o 1 2 3 4 1 2 5 1 234 5 Maria Hybine te UGA Page Replacement Example reference string 70120304230321201701 HE an IEEE HE II ENE page frames o FIFO Replace page that has been in memory the longest Maria Hybine te UGA Page Replacement Add memory Page reference string ABCABDADBCB Three pages of physical memory 0 Add more physical memory what happens to performance Ideally the numbers of page faults should should decrease as number of available frames increases 1 2 3 4 1 2 5 1 2 3 4 5 If 1 page frame Number of page faults 12 page faults one fault for every page 11 faults If 12 frames Number of page faults 5 page faults 16 14 12 10 8 6 4 2 Maria Hybine te UGA OPT FIFO LRU ABC A B D A D E3 C E3 FirstInFirstOut FIFO Algorithm Add Memory 0 Reference string 1 2 3 4 1 2 5 1 2 3 4 5 3 frames 3 pages can be in memory at a time per process 4 1 2 5 3 4 4 frames II 5 1 2 3 4 5 FIFO Replacement Belady s Anomaly more frames gt less page faults Maria Hybine te UGA Page Replacement Comparison Implementing LRU 0 Add more h sical memo what ha ens to 39 S ware Perfect LRU p y ry pp OS maintains ordered list of physical pages by reference time 7 performance 39 When page is referenced Move page to front of list top LRU OPT Add more memory guaranteed to have When need victim Pick page at back of list bottom fewer or same number 0f page faUItS Tradeoff Slow on memory reference fast on replacement Smaller memory sizes are guaranteed to contain Hardware Perfect LRU a SUbset 0f larger memory Sizes Associate register with each page FIFO Add more memory usually have fewer page When page is referenced Store system clock in register faults When need victim Scan through registers to find oldest clock Belady s anomaly May actually have more page Tradeoff Fast on memory reference slow on replacement fauts especially as size of memory grows o In practice do not implement Perfect LRU LRU is an approximation anwvay so approximate more Goal Find an old page but not necessarily the very oldest Maria Hybine te UGA Maria Hybine te UGA Clock or Second Chance Algorithm Clock Algorithm Example refeg gce pages refeg gce pages 0 Hardware E a E 6 Keep use or reference bit for each page frame a E initialized to 0 e e When page is referenced set use bit 1 T37 E g 0 Operating System B E D Page replacement Look for pagewith use bit cleared 0 E i w i has not been referenced for awhile I g g g Implementation Keep pointer to last examined page frame a i Traverse pages in circular buffer V U Clear use bits while searching for replacement quot 39a39 fpages deuerq eepages Stop when find page with already cleared use bit replace this page 0 Worst Case All bits are set gt FIFO slow Clock ExtenSIons More Clock ExtenSIons 0 Replace multiple pages at once Add software byte wit g39giggfggeg g ESTquot replacement alger39thm and to Intuition Keep track of history when last used Find multiple victims each time 0 Implementation Reference bit 0 TWOhanded CIOCk With each page associate a bit initially 0 Intuition If takes long time for clock hand to sweep through pages When page IS referenced blt set to 139 then all use bits might be set Keep a history of reference bit in an 8 bit byte Traditional clock cannot differentiate between usage of different pages Allow smaller time between clearing use bit and testing First hand Clears use bit Second hand Looks for victim page with use bit still 01110111 cleared Shift reference bit for each page to high order bit and other bits right one bit 11000100 more recently used than below Maria Hybine te UGA Maria Hybine te UGA More Clock Extensions 0 Add software counter chance gtgt Intuition Better abili to differentiate across pages how nuch they are being accessed Increment software counter chance if u e h 0 gtgt Replace when chance exceeds some speci ed II it Manzwtamem ma Problems with LRUbased Replacement 0 Locality of reference Same pages referred frequently warm pages Example 2 1 3 2 4 2 4 1 5 6 2 o LRU takes advantage of this 0 Leading question Is a page that has been accessed once in the past as likely to be accessed in the future as one that has been accessed N times Mannawait ma Combine LRU and LFU o LRUK Combines recency and frequency attributes Idea Take into account history last K references classic LRU K1 Replace page with oldest LRU Kt reference or does not ve Kth reference Expensive to implement LRU2 used in databases Manzwtamem ma More Clock Extensions 0 Use dirty bit to give preference to dirty pages gtgt Intuition More expensive to replace dirty pages 7 Dirty ges must be written to disk clean Replace pag s do not es that have use hit and dirty hit cleared Manzwtamem ma Problems with LRUbased Replacement o Example2 1 3 2 4 2 4 1 5 6 2 0 Problem gtgt Dislodges warm pages if a long sequence of one time page reference ccur e In the above ex page 2 may get dislodged by the access pattern 4 1 5 6 es not consider frequency of accesses 0 Solution Track frequency of accesses to page gtgt Pure LFU Leastfrequentlyused replacement 0 Problem but LFU can never forget pages from the far pas Mannawait ma Combine LRU and LFU 20 More ef cient than LRU2 similar performance gtgt Intuition Instead of removing cold pages only admit hot pages to main buffer w Alixt for shortterm accesses nunaged with FIFO not ya proven hot n m for longterm accesses managed with LRU gtgt On rst page fault page enters min qu e gtgt On subsequent page faults page enters Am queue Alout pages not in buffer cache but remenbered Manzwtamem ma Allocating Memory across Questions P rocesses o How to allocate memory across competing processes 0 Problem 0 What is thrashing What is a working set 0 How to ensure working set of all processes i 2 processes and 25 free frames how are they divided up 0 Three General Approaches gtgt Global Replacement PerProcess Replacement PerUser Replacement Managing uca Managing uca Global Replacement 0 Global replacemen Perprocess replacement gtgt Pages from all processes lumped into single replacement ool Example Run clock over all page fram o Perprocess free pool of pa es gtgt Equal Fixed Allocation Fixed number of pages per process es 7 00 frames and 5 processes give each 20 pages gtgt Each process competes with other processes for frames 7 Fixed fraction of physical memory Advantages Proportional Allocati e Flexibility of allocation Proportional to size of address space Minimile to number of page fau s 7 Adjust size allocated ifa process have higher priority Disadvantages o Page fault in one process only replaces frame of that a One oryintensive process can hog memory hurt all rocess processes 7 Pagi g behavior of one process depends on the behavior of other processes 0 Advantage Relieves interference from other processes 0 Disadvantage Potentially inefficient allocation of sources mutttamer m Mamamale uca PerUser Replacement Over Committing Memory 0 Advantages Users running more processes cannot hog me o Disadvantage Inefficient allocation 0 When does the Virtual Memory illusion break 0 Example gtgt Set of processes frequently referencing 33 inportant pa es Physical memory can t 32 pages 0 What happens System Repeat e 7 Reference page not in memory 7 Replace a p 39 emory with newly referenced page 7 Replace another page right away again since all its pages are in active use Mammal ma Managing uca Thrashing o Thrashing Spends more time paging than execution ie system reading and writing pages instead of executing useful instructions Average memory access time equals to disk access time Illusion breaks Memory appears slow as disk rather than disk appearing fast as memory 0 Add more processes thrashing gets worse 0 System is reading and writing pages instead of executing useful instructions Implication Average memory access time disk access time Memory appears as slow as disk instead of disk appearing as fast as memory Maria Hybine te UGA Thrashing Solutions 0 Limit thrashing by using a local replacement Process does not steal frames from other and cause latter to thrash Average service time for a page fault will still increase 0 Admission Control Determine of much memory each process needs Longterm scheduling policy Run only processes whose memory requirement can be satisfied 0 What if memory requirement of one process is too high Observation a process moves through different localities through out is lifetime Locality Set of pages that are actively used together Solution Amortize page allocated so that a process get enough page for its current locality Maria Hybine te UGA Working Set o Informal definition Collection of pages the process is referencing frequently Collection of pages that must be resident to avoid thrashing 0 Formal definition Assume locality use recent past to predict future Pages referenced by process in last T seconds of execu on Working set changes slowly over time oExample T39 A 8 me AABCBBBCDCDEBBEEDFB FDBBEDB ABC BDEF Maria Hybine te UGA System does not know it is thrashing o If a process does not have enough pages the pagefault rate is very high This leads to low CPU utilization operating system thinks that it needs to increase the degree of multiprogramming another process added to the system 0 Why the CPU utilization decreases Suppose a process need more frames starts faulting removing frames from others in turn making the other processes fault Processes queue up for the paging device CPU decreases OS add processes that immediately need new frames further taking away pages from running processes I thrashing degree of multiprogramming Maria Hybine te UGA Motivation for Solution o Thrashing cannot be fixed with better replacement policies Page replacement policies do not indicate that a page must be kept in memory Only show which pages are better than others to replace 0 Student s analogy to thrashing Too many courses Solution Drop a course 0 OS solution Admission control Determine how much memory each process needs Longterm scheduling policy Run only those processes whose memory requirements can be satisfied What if memory needs of one process are too large Maria Hybine te UGA Balance Set 0 Motivation Process should not be scheduled unless working set is resident in main memory 0 Divide runnable processes into two groups Active Working set is loaded Inactive Working set is swapped to disk 0 Balance set Sum of working sets of all active processes 0 Interaction with scheduler If balance set exceeds size of memory move some process to inactive set Which process If balance set is less than size of memory move some process to active set Which process Any other decisions Maria Hybine te UGA Working Set Implementation Unresolved Questions o Leverage use bits as in clock algorithm 0 OS maintains idle time for each page Amount of CPU received by process since last access to page Periodically scan all resident pages of a process lf use bit is set clear page s idle time lf use bit is clear add process CPU time since last scan to idle time lf idle time lt T page is in working set Maria Hybine te UGA PageFault Frequency Scheme Maria Hybine te UGA How should value of T be configured What if T is too large How should working set be defined when pages are shared Putjobs sharing pages in same balance set What processes should compose balance set How much memory needed for a balanced system Balanced system Each resource eg CPU memory disk becomes bottleneck at nearly same time How much memory is needed to keep the CPU busy With working set approach CPU may be idle even with runnable processes Current Trends 0 Observation Thrashing has a high pagefault rate 0 Idea Control page faultrate by controlling frames that are allocated to a process Too high page fault rate process need more frames Too low process have to many frames 0 Approach Establish acceptable pagefault rate upper and lower bound If actual rate falls below lower limit process loses frame If actual rate exceeds upper limit process gains frame l increase number of frames upper bound lower bound decrease number of frames pagefault rate Maria Hybine te UGA numberof frames Maria Hybine te UGA VM code is not as critical Reason 1 Personal vs timeshared machine Why does this matter Reason 2 Memory is more affordable more memory Less hardware support for replacement policies Software emulation of use and dirty bits Larger page sizes Better TLB coverage Smaller page tables Disadvantage More internal fragmentation Multiple page sizes Maria Hybine te UGA Maria Hybine te UGA


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!"

Allison Fischer University of Alabama

"I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

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.