Introduction to Operating Systems

Introduction to Operating Systems

Outline Announcement Virtual memory Overview Page replacement algorithms You can pick up your graded Homework #3 now or after class week13-2.ppt 2001 Announcement Homework #5 will be due on Nov. 25, 2003 At the beginning of the class No late submission will be accepted as I will discuss the solutions and answer any questions regarding Homework #5 There will be a quiz on Nov. 25, 2003 It will cover memory management Recitation class on Nov. 26, 2003? Lets decide what we want to do now I have the graded Homework #3 and you can pick it up after class 01/29/20

COP4610 2 Virtual Memory Question Given the memory mapping schemes we have covered so far, can we run a program that is larger than the physical memory? Why or why not? 01/29/20 COP4610 3 Time and space multiplexing The processor is a time resource It can only be time multiplexed Memory is a space resource We have looked at space multiplexing of memory

We divide the memory into pages and segments We have several processes in the memory at the same time sharing the memory Now we will look at time multiplexing of memory 01/29/20 COP4610 4 Time and space multiplexing of hotel rooms 01/29/20 COP4610 5 Time multiplexing memory Swapping move part/whole programs in and out of memory (to disk or tape)

allowed time-sharing in early OSs Overlays move parts of program in and out of memory (to disk or tape) allowed the running of programs that were larger than the physical memory available widely used in early PC systems 01/29/20 COP4610 6 Overlays Keep in memory only those instructions and data that are needed at any given time. Needed when process is larger than amount of memory allocated to it. Implemented by user, no special support needed from operating system, programming design of overlay structure is complex

01/29/20 COP4610 7 Overlays cont. 01/29/20 COP4610 8 Swapping A process can be swapped temporarily out of memory to a backing store, and then brought back into memory for continued execution. Backing store fast disk large enough to accommodate copies of all memory images for all users; must provide direct access to these memory images. Major part of swap time is transfer time; total transfer time is directly proportional to the amount of memory swapped. Modified versions of swapping are found on many systems,

i.e., UNIX and Microsoft Windows. 01/29/20 COP4610 9 Schematic View of Swapping 01/29/20 COP4610 10 Swapping 01/29/20 COP4610 11

Virtual memory 01/29/20 COP4610 12 Implementation of virtual memory Virtual memory allows time multiplexing of memory users to see a larger (virtual) address space than the physical address space the operating system to split up a process into physical memory and secondary memory Implementation requires extensive hardware assistance and a lot of OS code and time but it is worth it 01/29/20 COP4610 13

Implementation of virtual memory cont. Separation of user logical memory from physical memory. Only part of the program needs to be in memory for execution. Logical address space can therefore be much larger than physical address space. Need to allow pages to be swapped in and out. Virtual memory can be implemented via: Demand paging Demand segmentation 01/29/20 COP4610 14 Demand Paging Bring a page into memory only when it is needed.

Less I/O needed Less memory needed Faster response More users Page is needed reference to it invalid reference abort not-in-memory bring to memory 01/29/20 COP4610 15 Valid-Invalid Bit With each page table entry a validinvalid bit is associated (1 in-memory, 0 not-in-memory) Initially validinvalid but is set to 0 on all entries. Example of a page table snapshot. Frame #

valid-invalid bit 1 1 1 1 0 During address translation, if validinvalid bit in page table entry is 0 page fault. page table 01/29/20 0 0 COP4610 16 Page Fault

If there is ever a reference to a page, first reference will trap to OS page fault OS looks at another table to decide: Invalid reference abort. Just not in memory. Get empty frame. Page replacement find some page frame in memory, but not really in use, swap it out Swap page into the frame. Reset tables, validation bit = 1. 01/29/20 COP4610 17 Modified bit Most paging hardware also has a modified bit in the page table entry which is set when the page is written to This is also called the dirty bit

pages that have been changed are referred to as dirty these pages must be written out to disk because the disk version is out of date 01/29/20 COP4610 18 Performance of Demand Paging Page Fault Rate 0 p 1.0 if p = 0 no page faults if p = 1, every reference is a fault Effective Access Time (EAT) EAT = (1 p) x memory access + p (page fault overhead + [swap page out ] + swap page in + restart overhead) 01/29/20

COP4610 19 Demand Paging Performance Example Memory access time = 1 microsecond 50% of the time the page that is being replaced has been modified and therefore needs to be swapped out. Swap Page Time = 10 msec = 10,000 msec EAT = (1 p) x 1 + p (15000) = 1 + 15000 p (in msec) 01/29/20 COP4610 20 Locality Programs do not access their address space uniformly they access the same location over and over

Spatial locality: processes tend to access location near to location they just accessed because of sequential program execution because data for a function is grouped together Temporal locality: processes tend to access data over and over again because of program loops because data is processed over and over again 01/29/20 COP4610 21 Practicality of paging Paging only works because of locality at any one point in time programs dont need most of their pages Page fault rates must be very, very low for paging to be practical like one page fault per 100,000 or more memory references

01/29/20 COP4610 22 Demand paging Summary Demand paging Bring a page into memory only when it is needed Page fault First reference to a page not in memory generates a page fault Page fault is handled by the O.S Needs an empty page frame 01/29/20 COP4610 23 Page replacement Page replacement

When there is no empty frame in memory, we need to find a page to replace Write it out to the swap area if it has been changed since it was read in from the swap area Dirty bit or modified bit which page to remove from memory to make room for a new page We need a page replacement algorithm Two categories of replacement algorithms Static paging algorithms always replace a page from the process that is bringing in a new page Dynamic paging algorithm can replace any page 01/29/20 COP4610 24 Page references Processes continually reference memory and so generate a sequence of page references

The page reference sequence tells us everything about how a process uses memory For a given size, we only need to consider the page number If we have a reference to a page, then immediately following references to the page will never generate a page fault 0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103 0104, 0101, 0610, 0103, 0104, 0101, 0609, 0102, 0105 Suppose the page size is 100 bytes, what is the page reference sequence? We use page reference sequences to evaluate paging algorithms 01/29/20 COP4610 25 Page replacement algorithms The goal of a page replacement algorithm is to produce the fewest page faults We can compare two algorithms on a range of page reference sequences Or we can compare an algorithm to the best

possible algorithm We will start by considering static page replacement algorithms 01/29/20 COP4610 26 Optimal replacement algorithm The one that produces the fewest possible page faults on all page reference sequences Algorithm: replace the page that will not be used for the longest time in the future Problem: it requires knowledge of the future Not realizable in practice but it is used to measure the effectiveness of realizable algorithms 01/29/20 COP4610 27

Beladys Optimal Algorithm Replace page that will not be used for longest period of time. Replace page with maximal forward distance: yt = max xeS t-1(m)FWDt(x) Let page reference stream,R = 2031203120316457 Frame 2 0 3 1 2 0 3 1 2 0 3 1 6 4 5 7 0 2 2 2 1 0 0 2 3 01/29/20 COP4610 28 Beladys Optimal Algorithm Replace page with maximal forward distance: yt = max xeS t-1(m)FWDt(x) Let page reference stream,R = 2031203120316457 Frame 2 0 3 1 2 0 3 1 2 0 3 1 6 4 5 7

0 2 2 2 1 0 0 2 3 01/29/20 FWD4(2) = 1 FWD4(0) = 2 FWD4(3) = 3 COP4610 29 Beladys Optimal Algorithm Replace page with maximal forward distance: yt = max xeS t-1(m)FWDt(x) Let page reference stream,R = 2031203120316457 Frame 2 0 3 1 2 0 3 1 2 0 3 1 6 4 5 7 0 2 2 2 2

1 0 0 0 2 3 1 01/29/20 FWD4(2) = 1 FWD4(0) = 2 FWD4(3) = 3 COP4610 30 Beladys Optimal Algorithm Replace page with maximal forward distance: yt = max xeS t-1(m)FWDt(x) Let page reference stream,R = 2031203120316457 Frame 2 0 3 1 0 2 2 2 2 1 0 0 0

2 3 1 01/29/20 2 2 0 1 0 3 1 2 0 3 1 6 4 5 7 2 0 1 COP4610 31 Beladys Optimal Algorithm Replace page with maximal forward distance: yt = max xeS t-1(m)FWDt(x) Let page reference stream,R = 2031203120316457 Frame 2 0 3 1

0 2 2 2 2 1 0 0 0 2 3 1 01/29/20 2 2 0 1 0 2 0 1 3 1 2 0 3 1 6 4 5 7 2 3 1

FWD7(2) = 2 FWD7(0) = 3 FWD7(1) = 1 COP4610 32 Beladys Optimal Algorithm Replace page with maximal forward distance: yt = max xeS t-1(m)FWDt(x) Let page reference stream,R = 2031203120316457 Frame 2 0 3 1 0 2 2 2 2 1 0 0 0 2 3 1 01/29/20 2 2

0 1 0 2 0 1 3 2 3 1 1 2 3 1 FWD10(2) = FWD10(3) = 2 FWD10(1) = 3 2 2

3 1 COP4610 0 3 1 6 4 5 7 0 3 1 33 Beladys Optimal Algorithm Replace page with maximal forward distance: yt = max xeS t-1(m)FWDt(x) Let page reference stream,R = 2031203120316457 Frame 2 0 3 1 0 2 2 2 2 1 0 0 0 2 3 1

01/29/20 2 2 0 1 0 2 0 1 3 2 3 1 1 2 3 1 FWD13(0) = FWD13(3) =

FWD13(1) = 2 2 3 1 COP4610 0 0 3 1 3 0 3 1 1 6 4 5 7 0 3 1

34 Beladys Optimal Algorithm Replace page with maximal forward distance: yt = max xeS t-1(m)FWDt(x) Let page reference stream,R = 2031203120316457 Frame 2 0 3 1 0 2 2 2 2 1 0 0 0 2 3 1 2 2 0 1 0 2 0 1

3 2 3 1 1 2 3 1 2 2 3 1 0 0 3 1 3 0 3 1

1 0 3 1 6 4 5 7 0 4 4 4 6 6 6 7 1 1 5 5 10 page faults Perfect knowledge of R optimal performance Impossible to implement 01/29/20 COP4610 35 Theories of program behavior All replacement algorithms try to predict the

future and act like the optimal algorithm All replacement algorithms have a theory of how program behave they use it to predict the future, that is, when pages will be referenced then the replace the page that they think wont be referenced for the longest time. 01/29/20 COP4610 36 Random page replacement Algorithm: replace a page randomly Theory: we cannot predict the future at all Implementation: easy Performance: poor

but it is easy to implement but the best case, worse case and average case are all the same 01/29/20 COP4610 37 Random page replacement 01/29/20 COP4610 38 Random Replacement Replaced page, y, is chosen from the m loaded page frames with probability 1/m Let page reference stream,R = 2031203120316457 Frame 2 0 3 1 0

2 2 2 2 1 0 0 1 2 3 3 2 2 1 3 0 3 1 2 0 2 3 3 3 0 1 1 1 1 1 0 0 0 2 2 13 page faults 3 0 3 2 1 0

3 2 6 0 6 2 4 4 6 2 No knowledge of R not perform well Easy to implement 01/29/20 COP4610 5 4 5 2

7 7 5 2 39 FIFO page replacement Algorithm: replace the oldest page Theory: pages are used for a while and then stop being used Implementation: easy Performance: poor because old pages are often accessed, that is, the theory if FIFO is not correct 01/29/20 COP4610 40 FIFO page replacement

01/29/20 COP4610 41 First In First Out (FIFO) Replace page that has been in memory the longest: yt = max xeS t-1(m)AGE(x) Let page reference stream,R = 2031203120316457 Frame 2 0 3 1 2 0 3 1 2 0 3 1 6 4 5 7 0 2 2 2 1 1 0 0 0 2 3 3 01/29/20 COP4610 42

First In First Out (FIFO) Replace page that has been in memory the longest: yt = max xeS t-1(m)AGE(x) Let page reference stream,R = 2031203120316457 Frame 2 0 3 1 2 0 3 1 2 0 3 1 6 4 5 7 0 2 2 2 1 0 0 2 3 01/29/20 AGE4(2) = 3 AGE4(0) = 2 AGE4(3) = 1 COP4610 43 First In First Out (FIFO) Replace page that has been in memory the

longest: yt = max xeS t-1(m)AGE(x) Let page reference stream,R = 2031203120316457 Frame 2 0 3 1 2 0 3 1 2 0 3 1 6 4 5 7 0 2 2 2 1 1 0 0 0 2 3 3 01/29/20 AGE4(2) = 3 AGE4(0) = 2 AGE4(3) = 1 COP4610 44 First In First Out (FIFO) Replace page that has been in memory the longest: yt = max xeS t-1(m)AGE(x) Let page reference stream,R = 2031203120316457

Frame 2 0 3 1 2 0 3 1 2 0 3 1 6 4 5 7 0 2 2 2 1 1 0 0 0 2 3 3 01/29/20 AGE5(1) = ? AGE5(0) = ? AGE5(3) = ? COP4610 45 Beladys Anomaly Let page reference stream,R = 012301401234 Frame 0 1 2 3 0 0 0 0 3 1

1 1 1 2 2 2 0 3 0 2 1 3 0 1 4 4 0 1 0 4 0 1

1 4 0 1 2 4 2 1 3 4 2 3 4 4 2 3 Frame 0 1 2 3 0 0 0 0 0 0 0 1

1 1 1 1 2 2 2 2 3 3 3 1 0 1 2 3 4 4 1 2 3 0 4 0 2 3

1 4 0 1 3 2 4 0 1 2 3 3 0 1 2 4 3 4 1 2

FIFO with m = 3 has 9 faults FIFO with m = 4 has 10 faults 01/29/20 COP4610 46 Least Frequently Used (LFU) Replace page with minimum use: yt = min xeS t-1(m)FREQ(x) Let page reference stream,R = 2031203120316457 Frame 2 0 3 1 2 0 3 1 2 0 3 1 6 4 5 7 0 2 2 2 1 0 0 2 3 01/29/20 FREQ4(2) = 1 FREQ4(0) = 1

FREQ4(3) = 1 COP4610 47 Least Frequently Used (LFU) Replace page with minimum use: yt = min xeS t-1(m)FREQ(x) Let page reference stream,R = 2031203120316457 Frame 2 0 3 1 2 0 3 1 2 0 3 1 6 4 5 7 0 2 2 2 2 1 0 0 1 2 3 3 01/29/20 FREQ4(2) = 1 FREQ4(0) = 1 FREQ4(3) = 1

COP4610 48 Least Frequently Used (LFU) Replace page with minimum use: yt = min xeS t-1(m)FREQ(x) Let page reference stream,R = 2031203120316457 Frame 2 0 3 1 0 2 2 2 2 1 0 0 1 2 3 3 01/29/20 2 2 1 3 0 3 1 2 0 3 1 6 4 5 7

2 1 0 FREQ6(2) = 2 FREQ6(1) = 1 FREQ6(3) = 1 COP4610 49 Least Frequently Used (LFU) Replace page with minimum use: yt = min xeS t-1(m)FREQ(x) Let page reference stream,R = 2031203120316457 Frame 2 0 3 1 0 2 2 2 2 1 0 0 1 2 3 3

01/29/20 2 2 1 3 0 3 1 2 0 3 1 6 4 5 7 2 1 0 FREQ7(2) = ? FREQ7(1) = ? FREQ7(0) = ? COP4610 50 LRU page replacement Least-recently used (LRU) Algorithm: remove the page that hasnt been referenced for the longest time

Theory: the future will be like the past, page accesses tend to be clustered in time Implementation: hard, requires hardware assistance (and then still not easy) Performance: very good, within 30%-40% of optimal 01/29/20 COP4610 51 LRU model of the future 01/29/20 COP4610 52 LRU page replacement 01/29/20

COP4610 53 Least Recently Used (LRU) Replace page with maximal backward distance: yt = max xeS t-1(m)BKWDt(x) Let page reference stream,R = 2031203120316457 Frame 2 0 3 1 2 0 3 1 2 0 3 1 6 4 5 7 0 2 2 2 1 0 0 2 3 01/29/20 BKWD4(2) = 3 BKWD4(0) = 2 BKWD4(3) = 1 COP4610

54 Least Recently Used (LRU) Replace page with maximal backward distance: yt = max xeS t-1(m)BKWDt(x) Let page reference stream,R = 2031203120316457 Frame 2 0 3 1 2 0 3 1 2 0 3 1 6 4 5 7 0 2 2 2 1 1 0 0 0 2 3 3 01/29/20 BKWD4(2) = 3 BKWD4(0) = 2 BKWD4(3) = 1 COP4610 55

Least Recently Used (LRU) Replace page with maximal backward distance: yt = max xeS t-1(m)BKWDt(x) Let page reference stream,R = 2031203120316457 Frame 2 0 3 1 0 2 2 2 1 1 0 0 0 2 3 3 01/29/20 2 0 3 1 2 0 3 1 6 4 5 7 1 2 3 BKWD5(1) = 1 BKWD5(0) = 3 BKWD5(3) = 2 COP4610

56 Least Recently Used (LRU) Replace page with maximal backward distance: yt = max xeS t-1(m)BKWDt(x) Let page reference stream,R = 2031203120316457 Frame 2 0 3 1 0 2 2 2 1 1 0 0 0 2 3 3 01/29/20 2 1 2 3 0 3 1 2 0 3 1 6 4 5 7 1

2 0 BKWD6(1) = 2 BKWD6(2) = 1 BKWD6(3) = 3 COP4610 57 Least Recently Used (LRU) Replace page with maximal backward distance: yt = max xeS t-1(m)BKWDt(x) Let page reference stream,R = 2031203120316457 Frame 2 0 3 1 0 2 2 2 1 1 0 0 0 2 3 3 01/29/20

2 1 2 3 0 1 2 0 3 3 2 0 1 2 0 3 1 6 4 5 7 3 3 0 0 0 6 6 6 7 1 1 1 3 3 3 4 4 4 0 2 2 2 1 1 1 5 5 COP4610

58 Least Recently Used (LRU) Replace page with maximal backward distance: yt = max xeS t-1(m)BKWDt(x) Let page reference stream,R = 2031203120316457 Frame 2 0 3 1 2 0 2 2 2 2 2 1 0 0 0 0 2 3 3 3 3 1 1 0 2 0 3 1 3 2

0 3 1 1 3 0 3 1 2 2 0 3 1 0 2 0 3 1 3 2

0 3 1 1 2 0 3 1 6 6 0 3 1 4 6 4 3 1 5 6

4 5 1 7 6 4 5 7 Backward distance is a good predictor of forward distance -locality 01/29/20 COP4610 59 Approximating LRU LRU is difficult to implement usually it is approximated in software with some hardware assistance

We need a referenced bit in the page table entry turned on when the page is accessed can be turned off by the OS 01/29/20 COP4610 60 First LRU approximation When you get a page fault replace any page whose referenced bit is off then turn off all the referenced bits Two classes of pages Pages referenced since the last page fault Pages not referenced since the last page fault the least recently used page is in this class but you dont know which one it is A crude approximation of LRU 01/29/20

COP4610 61 Second LRU approximation Algorithm: Keep a counter for each page Have a daemon wake up every 500 ms and add one to the counter of each page that has not been referenced zero the counter of pages that have been referenced turn off all referenced bits When you get a page fault replace the page whose counter is largest Divides pages into 256 classes 01/29/20 COP4610 62 LRU and its approximations

01/29/20 COP4610 63 A clock algorithm 01/29/20 COP4610 64 Clock algorithms Clock algorithms try to approximate LRU but without extensive hardware and software support The page frames are (conceptually) arranged in a big circle (the clock face) A pointer moves from page frame to page frame trying to find a page to replace and manipulating the referenced bits We will look at three variations

FIFO is actually the simplest clock algorithm 01/29/20 COP4610 65 Basic clock algorithm When you need to replace a page look at the page frame at the clock hand if the referenced bit = 0 then replace the page else set the referenced bit to 0 and move the clock hand to the next page Pages get one clock hand revolution to get referenced 01/29/20 COP4610 66 Second chance algorithm

When you need to replace a page look at the page frame at the clock hand if (referencedBit=0 && modifiedBit=0) then replace the page else if(referencedBit=0 && modifiedBit=1) then set modifiedBit to 0 and start writing the page to disk and move on else set referencedBit to 0 and move on Dirty pages get a second chance because they are more expensive to replace 01/29/20 COP4610 67 Clock algorithm flow chart 01/29/20 COP4610 68

Stack Algorithms Some algorithms are well-behaved Inclusion Property: Pages loaded at time t with m is also loaded at time t with m+1 LRU 01/29/20 Frame 0 1 2 3 0 1 4 0 1 2 3 4 0 0 0 0 3 1 1 1 1 2 2 2 Frame 0 1 2 3 0 1 4 0 1 2 3 4 0 0 0 0 0 1 1 1 1 2 2 2 3

3 COP4610 69 Stack Algorithms Some algorithms are well-behaved Inclusion Property: Pages loaded at time t with m is also loaded at time t with m+1 LRU 01/29/20 Frame 0 1 2 3 0 0 0 0 3 1 1 1 1 2 2 2 0 1 4 0 1 2 3 4 3 1 0

Frame 0 1 2 3 0 1 4 0 1 2 3 4 0 0 0 0 0 0 1 1 1 1 1 2 2 2 2 3 3 COP4610 3 70 Stack Algorithms Some algorithms are well-behaved Inclusion Property: Pages loaded at time t with m is also loaded at time t with m+1 LRU 01/29/20 Frame 0 1 2 3 0

0 0 0 3 1 1 1 1 2 2 2 0 3 0 2 1 4 0 1 2 3 4 3 0 1 Frame 0 1 2 3 0 1 4 0 1 2 3 4 0 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 3

3 COP4610 3 3 71 Stack Algorithms Some algorithms are well-behaved Inclusion Property: Pages loaded at time t with m is also loaded at time t with m+1 LRU 01/29/20 Frame 0 1 2 3 0 0 0 0 3 1 1 1 1 2 2 2 0 3 0

2 1 3 0 1 4 0 1 2 3 4 4 0 1 Frame 0 1 2 3 0 1 0 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 3 3 COP4610 3 3 4 0 1 2 3 4

0 1 4 3 72 Stack Algorithms Some algorithms are well-behaved Inclusion Property: Pages loaded at time t with m is also loaded at time t with m+1 LRU 01/29/20 Frame 0 1 2 3 0 0 0 0 3 1 1 1 1 2 2 2 0

3 0 2 1 3 0 1 4 4 0 1 0 4 0 1 1 4 0 1

2 2 0 1 3 2 3 1 4 2 3 4 Frame 0 1 2 3 0 0 0 0 0 0 0 1 1 1 1 1 2 2 2 2 3 3 3

1 0 1 2 3 4 0 1 4 3 0 0 1 4 3 1 0 1 4 3

2 0 1 4 2 3 0 1 3 2 4 4 1 3 2 COP4610 73 Stack Algorithms

Some algorithms are well-behaved Inclusion Property: Pages loaded at time t with m is also loaded at time t with m+1 FIFO 01/29/20 Frame 0 1 2 3 0 0 0 0 3 1 1 1 1 2 2 2 0 3 0 2 1 3 0 1

4 4 0 1 0 4 0 1 1 4 0 1 2 4 2 1 3 4 2

3 4 4 2 3 Frame 0 1 2 3 0 0 0 0 0 0 0 1 1 1 1 1 2 2 2 2 3 3 3 1 0 1 2 3 4

4 1 2 3 0 4 0 2 3 1 4 0 1 3 2 4 0 1 2 3

3 0 1 2 4 3 4 1 2 COP4610 74 Dynamic Paging Algorithms The amount of physical memory -- the number of page frames -- varies as the process executes How much memory should be allocated? Fault rate must be tolerable Will change according to the phase of process Need to define a placement & replacement

policy Contemporary models based on working set 01/29/20 COP4610 75 Working Set Principle Process pi should only be loaded and active if it can be allocated enough page frames to hold its entire working set The size of the working set is estimated using w Unfortunately, a good value of w depends on the size of the locality Empirically this works with a fixed w 01/29/20 COP4610 76 Working set

A page in memory is said to be resident The working set of a process is the set of pages it needs to be resident in order to have an acceptable low paging rate. Operationally: Each page reference is a unit of time The page reference sequence is: r1, r2, , rT where T is the current time W(T,) = {p | p = rt where T- < t <= T } is the working set, where is the window size 01/29/20 COP4610 77 The Working Set Window ri R=03121103012 W=3 The Window At virtual time i-1: working set = {0, 1}

At virtual time i: working set = {0, 1, 3} 01/29/20 COP4610 78 Program phases Processes tend to have stable working sets for a period of time called a phase Then they change phases to a different working set Between phases the working set is unstable and we get lots of page faults 01/29/20 COP4610 79 Working set phases

01/29/20 COP4610 80 Working set algorithm Algorithm Keep track of the working set of each running process Only run a process if its entire working set fits in memory called working set principle 01/29/20 COP4610 81 Working set algorithm example w=3 w=4 01/29/20

COP4610 82 Working set algorithm example cont. w=9 01/29/20 COP4610 83 Working set algorithm example cont. w=4 01/29/20 COP4610 84 Implementing Working Set Algorithm

Too hard to implement so this algorithm is only approximated WSClock algorithm A clock algorithm that approximates the working set algorithm It needs to keep the last reference time of each page frame When the reference bit is set, the last reference time was set to the current time When a page fault occurs Inspect each frame as in the clock algorithm When a frames reference bit is set, then determine whether it is in the working set by comparing the last reference time 01/29/20 COP4610 85 Evaluating paging algorithms Mathematical modeling powerful where it works but most real algorithms cannot be analyzed

Measurement implement it on a real system and measure it extremely expensive Simulation Test on page reference traces reasonably efficient effective 01/29/20 COP4610 86 Performance of paging algorithms 01/29/20 COP4610 87 Thrashing VM allows more processes in memory, so

one is more likely to be ready to run If CPU usage is low, it is logical to bring more processes into memory But, low CPU use may to due to too many pages faults because there are too many processes competing for memory Bringing in processes makes it worse, and leads to thrashing 01/29/20 COP4610 88 Thrashing Diagram There are too many processes in memory and no process has enough memory to run. As a result, the page fault is very high and the system spends all of its time handling page fault interrupts. 01/29/20 COP4610

89 Load control Load control: deciding how many processes should be competing for page frames too many leads to thrashing too few means that memory is underused Load control determines which processes are running at a point in time the others have no page frames and cannot run CPU load is a bad load control measure Page fault rate is a good load control measure 01/29/20 COP4610 90 Load control and page replacement 01/29/20

COP4610 91 Two levels of scheduling 01/29/20 COP4610 92 Load control algorithms A load control algorithm measures memory load and swaps processes in and out depending on the current load Load control measures rotational speed of the clock hand average time spent in the standby list page fault rate 01/29/20 COP4610

93 Page fault frequency load control L = mean time between page faults S = mean time to service a page fault Try to keep L = S if L < S, then swap a process out if L > S, then swap a process in If L = S, then the paging system can just keep up with the page faults 01/29/20 COP4610 94 Windows NT Paging System 1. Reference to Address k in Page i (User space)

Virtual Address Space 2. Lookup (Page i, Addr k) 4. Reference (Page Frame j, Addr k) Primary Memory Paging Disk (Secondary Memory) 3. 01/29/20 Supv space User space Translate (Page i, Addr k)

to (Page Frame j, Addr k) COP4610 95 Windows Address Translation Virtual page number Page Directory Line number Page Table Byte Index a A b Page Directory B c

Page Tables C Target Page Target Byte 01/29/20 COP4610 96 Linux Virtual Address Translation Virtual Address j.pgd j.pgd j.pmd j.pmd j.pte j.pte j.offset j.offset Page Directory

Base Page Page Directory Page Middle Directory 01/29/20 COP4610 Page Table 97 NT Memory-mapped Files Ordinary file Open the file Create a section object (that maps file) Identify point in address space to place the file

Secondary memory Executable memory Memory Memory mapped mapped files files Section object 01/29/20 COP4610 98 NT Memory-mapped Files cont. 01/29/20

COP4610 99 Summary Virtual memory Time multiplexing of primary memory Can run a program larger than the primary memory Separates logical and physical memory address spaces through memory hierarchy 01/29/20 COP4610 100 Summary cont. Demand paging Bring a page into primary memory only when it is needed When the referenced page is valid but not in

memory Get an empty frame If no empty frame, use page replacement algorithm to find a frame and swap it out if needed Swap the reference page in Update the page table 01/29/20 COP4610 101

Recently Viewed Presentations

  • IN MEMORIAM THE NORTH CAROLINA FEDERATION OF THE

    IN MEMORIAM THE NORTH CAROLINA FEDERATION OF THE

    IN MEMORIAM THE NORTH CAROLINA FEDERATION OF THE NATIONAL ACTIVE AND RETIRED FEDERAL EMPLOYEES ASSOCIATION Celebrates with honor those who have gone before us
  • FRACTURES - Weebly

    FRACTURES - Weebly

    This is commonly seen in arm fractures in children and is sometimes known as a buckle fracture. Other types of fractures are pathologic fracture, caused by a disease that weakens the bones, and stress fracture, a hairline crack. Examples Xray...
  • Welcome to Years 1 and 2 Miss Reed

    Welcome to Years 1 and 2 Miss Reed

    They will initially complete English and Mathematics work in a small group working with an adult. Summer Project- Animal Habitat Box Your child will need Pencil case - pencil, rubber, glue stick, sharpener, and whiteboard pens. PE kit - white...
  • Electric Charge and Static Electricity

    Electric Charge and Static Electricity

    All the materials listed in the electrostatic series is a non-metal and an insulator. Insulators do not conduct charges very well because their electrons cannot flow freely. The insulating material in a lamp cord stops charges from leaving the wire...
  • CURTAINS PLEASE! - Richmond Public Schools

    CURTAINS PLEASE! - Richmond Public Schools

    CURTAINS PLEASE! EXAMPLE 2: This is the perfect present! It is functional, pretty and desperately needed.While I can't say that I always (A) picked the greatest gifts, I must say that this one (B) was ideal! I (C) knew that...
  • Blood Vessels (Vascular System) transport blood to tissues ...

    Blood Vessels (Vascular System) transport blood to tissues ...

    Heart gets blood into Vessels, then. Vessels take over getting blood to cells. BLOOD VESSEL FUNCTIONS. Systemic Blood Pressure (Overall) must be maintained to keep blood moving to all the tissues as a whole ... Myogenic: INTRINSIC. To protect against...
  • Phonemic Awareness, Phonics, and Fluency The Fear Factor

    Phonemic Awareness, Phonics, and Fluency The Fear Factor

    The Fear Factor Joann Doyle, MS CCC-SLP SLP Literacy Academies National Reading Panel National Reading Panel and other research has clearly documented the importance of incorporating phonemic awareness, phonics, and fluency in reading instruction.
  • Office of Aviation Safety Bali Hai Helicopter Tours

    Office of Aviation Safety Bali Hai Helicopter Tours

    Accident Flight SFAR 71 - Special Operating Rules for Air Tour Operators in the State of Hawaii Eighth tour, departed at 1600 Radar Ground Track 1634 1639 1645 Accident Flight Images SFAR 71 SFAR 71 Deviations Deviations approved case-by-case Required...