Site hosted by Angelfire.com: Build your free website today!

Department of Computer Science, UMass Amherst Andrew H. Fagg

Announcements/Reminders

_ HW 6 is due Friday

_ You should be well into lab 4...

CMPSCI 377: Operating Systems Lecture 22, Page 1

Department of Computer Science, UMass Amherst Andrew H. Fagg

Exam 2 is Back Today

0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

0

1

2

3

4

5

6

7

8

9

Exam 2

grade

count

median = 0.7125

mean = 0.71021

CMPSCI 377: Operating Systems Lecture 22, Page 2

Department of Computer Science, UMass Amherst Andrew H. Fagg

So Far: Demand Paged Virtual Memory

Bene_ts of demand paging:

_ Virtual address space can be larger than physical address space.

_ Processes can run without being fully loaded into memory.

{ Processes start faster because they only need to load a few pages (for

code and data) to start running.

{ Processes can share memory more e_ectively, reducing the costs when

a context switch occurs.

_ A good page replacement algorithm can reduce the number of page faults

and improve performance

CMPSCI 377: Operating Systems Lecture 22, Page 3

Department of Computer Science, UMass Amherst Andrew H. Fagg

Next Steps

_ LRU approximations:

{ Second Chance

{ Enhanced Second Chance

_ Hardware support for page replacement algorithms

_ Replacement policies for multiprogramming

CMPSCI 377: Operating Systems Lecture 22, Page 4

Department of Computer Science, UMass Amherst Andrew H. Fagg

Adding Memory

Does adding memory always reduce the number of page faults?

FIFO:

A B C D A B E A B C D E

frame 1

frame 2

frame 3

frame 1

frame 2

frame 3

frame 4

CMPSCI 377: Operating Systems Lecture 22, Page 5

Department of Computer Science, UMass Amherst Andrew H. Fagg

Adding Memory

Does adding memory always reduce the number of page faults?

Yes for LRU and MIN, and other stack based algorithms.

No for FIFO (Belady's anomaly):

A B C D A B E A B C D E

frame 1 A A A D D D E E E

frame 2 B B B A A A C C

frame 3 C C C B B B D

frame 1 A A A A E E E E D D

frame 2 B B B B A A A A E

frame 3 C C C C B B B B

frame 4 D D D D C C C

With FIFO, the contents of memory can be completely di_erent with a

di_erent number of page frames.

CMPSCI 377: Operating Systems Lecture 22, Page 6

Department of Computer Science, UMass Amherst Andrew H. Fagg

Adding Memory with LRU

LRU:

A B C D A B E A B C D E

frame 1

frame 2

frame 3

frame 1

frame 2

frame 3

frame 4

CMPSCI 377: Operating Systems Lecture 22, Page 7

Department of Computer Science, UMass Amherst Andrew H. Fagg

Adding Memory with LRU

LRU:

A B C D A B E A B C D E

frame 1 A A A D D D E C C C

frame 2 B B B A A A A D D

frame 3 C C C B B B B E

frame 1 A A A A A A A E

frame 2 B B B B B B B

frame 3 C C E E D D

frame 4 D D C C C

_ With LRU, increasing the number of frames always decreases the number

of page faults. Why?

CMPSCI 377: Operating Systems Lecture 22, Page 8

Department of Computer Science, UMass Amherst Andrew H. Fagg

Implementing LRU:

_ All implementations and approximations of LRU require hardware

assistance

_ Perfect LRU:

1. Keep a time stamp for each page with the time of the last access.

Throw out the LRU page.

{ Problems: OS must record time stamp for each memory access, and

to throw out a page the OS has to look at all pages. Expensive!

2. Keep a list of pages, where the front of the list is the most recently

used page, and the end is the least recently used.

{ On a page access, move the page to the front of the list. Doubly link

the list.

{ Problems: still too expensive, since the OS must modify 6 pointers

on each memory access (in the worst case)

CMPSCI 377: Operating Systems Lecture 22, Page 9

Department of Computer Science, UMass Amherst Andrew H. Fagg

Approximations of LRU

_ Hardware Requirements: Maintain reference bits with each page.

{ On each access to the page, the hardware sets the reference bit to '1'.

{ Set to 0 at varying times depending on the page replacement algorithm.

_ Additional-Reference-Bits: Maintain more than 1 bit, say 8 bits.

{ At regular intervals or on each memory access, shift the byte right,

placing a 0 in the high order bit.

{ On a page fault, the lowest numbered page is kicked out.

) Approximate, since it does not guarantee a total order on the pages.

) Faster, since setting a single bit on each memory access.

_ Page fault still requires a search through all the pages.

CMPSCI 377: Operating Systems Lecture 22, Page 10

Department of Computer Science, UMass Amherst Andrew H. Fagg

Second Chance Algorithm: (a.k.a. Clock)

Use a single reference bit per page.

1. OS keeps frames in a circular list.

2. On a page fault, the OS

(a) Checks the reference bit of the next frame.

(b) If the reference bit is '0', replace the page, and set its bit to `1.'

(c) If the reference bit is '1', set bit to '0', and advance the pointer to the

next frame

CMPSCI 377: Operating Systems Lecture 22, Page 11

Department of Computer Science, UMass Amherst Andrew H. Fagg

Second Chance Algorithm

_ Less accurate than additional-reference-bits, since the reference bit only

indicates if the page was used at all since the last time it was checked by

the algorithm.

_ Fast, since setting a single bit on each memory access, and no need for a

shift.

_ Page fault is faster, since we only search the pages until we _nd one with

a '0' reference bit.

_ Simple hardware requirements.

Will it always _nd a page?

What if all bits are '1'?

CMPSCI 377: Operating Systems Lecture 22, Page 12

Department of Computer Science, UMass Amherst Andrew H. Fagg

Clock Example

r

r

1

1

1

0

1 0

0

1

r

Frame 0 Frame 1 ...

) One way to view the

clock algorithm is as a

crude partitioning into two

categories: young and old

pages.

_ Why not partition pages

into more than two

categories?

CMPSCI 377: Operating Systems Lecture 22, Page 13

Department of Computer Science, UMass Amherst Andrew H. Fagg

Enhanced Second Chance

_ It is cheaper to replace a page that has not been written

{ OS need not write the page back to disk

) OS can give preference to paging out un-modi_ed pages

_ Hardware keeps a modify bit (in addition to the reference bit)

'1': page is modi_ed (di_erent from the copy on disk)

'0': page is the same as the copy on disk

CMPSCI 377: Operating Systems Lecture 22, Page 14

Department of Computer Science, UMass Amherst Andrew H. Fagg

Enhanced Second Chance

_ The reference bit and modify bit form a pair (r,m) where

1. (0,0) neither recently used nor modi_ed - replace this page!

2. (0,1) not recently used but modi_ed - not as good to replace, since the

OS must write out this page, but it might not be needed anymore.

3. (1,0) recently used and unmodi_ed - probably will be used again soon,

but OS need not write it out before replacing it

4. (1,1) recently used and modi_ed - probably will be used again soon and

the OS must write it out before replacing it

_ On a page fault, the OS searches for the _rst page in the lowest

nonempty class.

CMPSCI 377: Operating Systems Lecture 22, Page 15

Department of Computer Science, UMass Amherst Andrew H. Fagg

Page Replacement in Enhanced Second Chance

_ The OS goes around at most three times searching for the (0,0) class.

1. Page with (0,0) )replace the page.

2. Page with (0,1) )initiate an I/O to write out the page, locks the page

in memory until the I/O completes, clears the modi_ed bit, and

continue the search

3. For pages with the reference bit set, the reference bit is cleared.

4. If the hand goes completely around once, there was no (0,0) page.

{ On the second pass, a page that was originally (0,1) or (1,0) might

have been changed to (0,0) )replace this page

{ If the page is being written out, waits for the I/O to complete and

then remove the page.

{ A (0,1) page is treated as on the _rst pass.

{ By the third pass, all the pages will be at (0,0).

CMPSCI 377: Operating Systems Lecture 22, Page 16

Department of Computer Science, UMass Amherst Andrew H. Fagg

Clock Example

r

r

1

1

1

0

1

0

1

r

Frame 0 Frame 1 ...

1 1

0 0

0 0

0

0 1

CMPSCI 377: Operating Systems Lecture 22, Page 17

Department of Computer Science, UMass Amherst Andrew H. Fagg

Replacement Policies for Multiprogramming

_ Thrashing: the memory is over-committed and pages are continuously

tossed out while they are still in use

{ Memory access times approach disk access times since many memory

references cause page faults

{ Results in a serious and very noticeable loss of performance.

_ What can we do in a multiprogrammed environment to limit thrashing?

_ Proportional allocation: allocate more page frames to large processes.

_ Global replacement: put all pages from all processes in one pool so that

the physical memory associated with a process can grow

{ Advantages: Flexible, adjusts to divergent process needs

{ Disadvantages: Thrashing might become even more likely (Why?)

CMPSCI 377: Operating Systems Lecture 22, Page 18

Department of Computer Science, UMass Amherst Andrew H. Fagg

Replacement Policies for Multiprogramming

Disadvantages: Thrashing might become even more likely (Why?)

) Might replace a page that the other process needs immediately when it

gets the CPU back.

CMPSCI 377: Operating Systems Lecture 22, Page 19

Department of Computer Science, UMass Amherst Andrew H. Fagg

Replacement Policies for Multiprogramming

_ Per-process replacement: Each process has its own pool of pages.

_ Run only groups of processes that _t in memory, and kick out the rest.

_ How do we _gure out how many pages a process needs, i.e., its working

set size?

{ Informally, the working set is the set of pages the process is using right

now

{ More formally, it is the set of all pages that a process referenced in the

past T seconds

CMPSCI 377: Operating Systems Lecture 22, Page 20

Department of Computer Science, UMass Amherst Andrew H. Fagg

Replacement Policies for Multiprogramming (cont)

_ How does the OS pick T?

{ 1 page fault = 10msec

{ 10msec = 2 million instructions

) T needs to be a whole lot bigger than 2 million instructions.

_ What happens if T is too small? too big?

CMPSCI 377: Operating Systems Lecture 22, Page 21

Department of Computer Science, UMass Amherst Andrew H. Fagg

Replacement Policies for Multiprogramming

What happens if T is too small? too big?

_ Too small - remove pages still in use

_ Too big - ine_cient use of memory, unnecessarily reducing

multiprogramming level

CMPSCI 377: Operating Systems Lecture 22, Page 22

Department of Computer Science, UMass Amherst Andrew H. Fagg

Per-process Replacement

_ Working sets are expensive to compute )track page fault frequency of

each process instead

{ If the page fault frequency > some threshold, give it more page frames.

{ If the page fault frequency < a second threshold, take away some page

frames

_ Goal: the system-wide mean time between page faults should be equal to

the time it takes to handle a page fault.

{ May need to suspend a process until overall memory demands decrease.

_ Advantages: Thrashing is less likely as a process only competes with

itself. More consistent performance independent of system load.

_ Disadvantages: The OS has to _gure out how many pages to give each

process and if the working set size grows dynamically adjust its allocation.

CMPSCI 377: Operating Systems Lecture 22, Page 23

Department of Computer Science, UMass Amherst Andrew H. Fagg

Page Sizes

_ Reasons for small pages:

{ More e_ective memory use.

{ Higher degree of multiprogramming possible.

_ Reasons for large pages:

{ Smaller page tables

{ Amortizes disk overhead over a larger page

{ Fewer page faults (for processes that exhibit locality of references)

CMPSCI 377: Operating Systems Lecture 22, Page 24

Department of Computer Science, UMass Amherst Andrew H. Fagg

Page Sizes

Page sizes are growing because:

_ Physical memory is cheap. As a result, page tables could get huge with

small pages. Also, internal fragmentation is less of a concern with

abundant memory.

_ CPU speed is increasing faster than disk speed. As a result, page faults

result in a larger slow down than they used to. Reducing the number of

page faults is critical to performance.

CMPSCI 377: Operating Systems Lecture 22, Page 25

Department of Computer Science, UMass Amherst Andrew H. Fagg

Summary of Page Replacement Algorithms

_ Unix and Linux use variants of Clock, Windows NT uses FIFO.

_ Experiments show that all algorithms do poorly if processes have

insu_cient physical memory (less than half of their virtual address space).

_ All algorithms approach optimal as the physical memory allocated to a

process approaches the virtual memory size.

_ The more processes running concurrently, the less physical memory each

process can have.

_ A critical issue the OS must decide is how many processes and the frames

per process that may share memory simultaneously.

CMPSCI 377: Operating Systems Lecture 22, Page 26

Department of Computer Science, UMass Amherst Andrew H. Fagg

Next Time

_ I/O Systems (Chapter 12)

CMPSCI 377: Operating Systems Lecture 22, Page 27