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

Department of Computer Science, UMass Amherst Andrew H. Fagg

Announcements/Reminders

² HW 5: due Tuesday.

² Lab 4: due in 2 weeks. Don't wait!

CMPSCI 377: Operating Systems Lecture 21, Page 1

Department of Computer Science, UMass Amherst Andrew H. Fagg

The Next Step: Demand Paged Virtual Memory

² Up to now, the virtual address space of a process ¯ts into memory, and

we assumed it was all in memory.

² OS illusions:

1. Treat disk (or other backing store) as a much larger, but much slower

main memory.

2. Analogous to the way in which main memory is a much larger, but

much slower, cache or set of registers.

² The illusion of an in¯nite virtual memory enables:

1. A process to be larger than physical memory.

2. A process to execute even if all of the process is not in memory.

3. More processes than ¯t in memory to run concurrently.

CMPSCI 377: Operating Systems Lecture 21, Page 2

Department of Computer Science, UMass Amherst Andrew H. Fagg

Demand Paged Virtual Memory

² Demand Paging uses memory as a cache for the disk

² The page table (memory map) indicates if the page is on disk or memory

using a valid bit

² Once a page is brought from disk into memory, the OS updates the page

table and the valid bit

² For e±ciency reasons, it only makes sense that memory accesses reference

pages that are in memory the vast majority of the time

{ Otherwise... the e®ective memory access time will approach that of the

disk

² Key Idea: Locality|the working set size of a process must ¯t in

memory, and must stay there. (90/10 rule.)

CMPSCI 377: Operating Systems Lecture 21, Page 3

Department of Computer Science, UMass Amherst Andrew H. Fagg

Demand Paged Virtual Memory: Example

page

table

.

page

page

page

page

.

.

virtual

memory

memory Disk

CMPSCI 377: Operating Systems Lecture 21, Page 4

Department of Computer Science, UMass Amherst Andrew H. Fagg

When to load a page?

² At process start time: the virtual address space must be no larger than

the physical memory.

² Overlays: application programmer indicates when to load and remove

pages.

{ Allows virtual address space to be larger than physical address space

{ Di±cult to do and is error-prone

² Request paging: process tells an OS before it needs a page and when it

is done with a page.

CMPSCI 377: Operating Systems Lecture 21, Page 5

Department of Computer Science, UMass Amherst Andrew H. Fagg

When to load a page?

² Demand paging: OS loads a page the ¯rst time it is referenced.

{ May remove a page from memory to make room for the new page

{ Process must give up the CPU while the page is being loaded

{ Page-fault: interrupt that occurs when an instruction references a page

that is not in memory.

² Pre-paging: OS guesses in advance which pages the process will need

and pre-loads them into memory

{ Allows more overlap of CPU and I/O if the OS guesses correctly.

{ If the OS is wrong )page fault

{ Errors may result in removing useful pages.

{ Di±cult to get right due to branches in code.

CMPSCI 377: Operating Systems Lecture 21, Page 6

Department of Computer Science, UMass Amherst Andrew H. Fagg

Implementation of Demand Paging

² A copy of the entire program must be stored on disk. (Why?)

² Valid bit in page table indicates if page is in memory.

1: in memory; 0: not in memory (either on disk or bogus address)

² If the page is not in memory, trap to the OS on ¯rst the reference

² The OS checks that the address is valid. If so, it:

1. Selects a page to replace (page replacement algorithm)

2. Invalidates the old page in the page table

3. Starts loading new page into memory from disk

4. Context switches to another process while I/O is being done

5. Receives an interrupt when page is loaded in memory

6. Updates the page table entry

7. Continues faulting process (why not continue current process?)

CMPSCI 377: Operating Systems Lecture 21, Page 7

Department of Computer Science, UMass Amherst Andrew H. Fagg

Swap Space

² What happens when a page is removed from memory?

{ If the page contained code, we could simply remove it. Why?

{ If the page contained data, we need to save the data so that it can be

reloaded if the process it belongs to refers to it again.

{ Swap space: A portion of the disk is reserved for storing pages that are

evicted from memory

² At any given time, a page of virtual memory might exist in one or more of:

{ The ¯le system

{ Physical memory

{ Swap space

² Page table must be more sophisticated so that it knows where to ¯nd a

page

CMPSCI 377: Operating Systems Lecture 21, Page 8

Department of Computer Science, UMass Amherst Andrew H. Fagg

Performance of Demand Paging

² Theoretically, a process could access a new page with each instruction.

² Fortunately, processes typically exhibit locality of reference

{ Temporal locality: if a process accesses an item in memory, it will

tend to reference the same item again soon.

{ Spatial locality: if a process accesses an item in memory, it will tend

to reference an adjacent item soon.

² Let p be the probability of a page fault (0 · p · 1).

² E®ective access time = (1 ¡ p) £ ma + p£ page fault time

{ If memory access time is 200 ns and a page fault takes 25 ms

{ E®ective access time = (1 ¡ p) £ 200 + p£ 25,000,000

{ If we want the e®ective access time to be only 10% slower than

memory access time, what value must p have?

CMPSCI 377: Operating Systems Lecture 21, Page 9

Department of Computer Science, UMass Amherst Andrew H. Fagg

Performance of Demand Paging

² If memory access time is 200 ns and a page fault takes 25 ms

² E®ective access time = (1 ¡ p) £ 200 + p£ 25,000,000

² If we want the e®ective access time to be only 10% slower than memory

access time, what value must p have?

220 = (1 ¡ p) ¤ 200 + p ¤ 25; 000; 000

220 = 200 ¡ 200p + 25; 000; 000p

220 = 200 + 24; 999; 800p

20 = 24; 999; 800p

:0000008 = p

page fault is acceptable 1 time in 1,250,000 addresses

CMPSCI 377: Operating Systems Lecture 21, Page 10

Department of Computer Science, UMass Amherst Andrew H. Fagg

Updating the TLB

² In some implementations, the hardware loads the TLB on a TLB miss.

² If the TLB hit rate is very high, use software to load the TLB

1. Valid bit in the TLB indicates if page is in memory.

2. on a TLB hit, use the frame number to access memory

3. trap on a TLB miss, the OS then

(a) checks if the page is in memory

(b) if page is in memory, OS picks a TLB entry to replace and then ¯lls

it in the new entry

(c) if page is not in memory, OS picks a TLB entry to replace and ¯lls it

in as follows:

i. invalidates TLB entry

ii. perform page fault operations as described earlier

iii. updates TLB entry

iv. restarts faulting process

CMPSCI 377: Operating Systems Lecture 21, Page 11

Department of Computer Science, UMass Amherst Andrew H. Fagg

Updating the TLB

... All of this is still functionally transparent to the user.

CMPSCI 377: Operating Systems Lecture 21, Page 12

Department of Computer Science, UMass Amherst Andrew H. Fagg

Making Page Faults Transparent

How does the OS transparently restart a faulting instruction?

² Need hardware support to save

1. the faulting instruction,

2. the CPU state.

² What about instructions with side-e®ects? (CISC)

{ mov a, (r10)+ : moves a into the address contained in register 10

and increments register 10.

² Solution: unwind side e®ects

CMPSCI 377: Operating Systems Lecture 21, Page 13

Department of Computer Science, UMass Amherst Andrew H. Fagg

Transparent Page Faults

² Block transfer instructions where the source and destination overlap can't

be undone.

source begin

source end

destination begin

destination end

² Solution: check that all pages between the starting and ending addresses

of the source and destination are in memory before starting the block

transfer

CMPSCI 377: Operating Systems Lecture 21, Page 14

Department of Computer Science, UMass Amherst Andrew H. Fagg

Page Replacement Algorithms

On a page fault, we need to choose a page to evict

Random: amazingly, this algorithm works pretty well.

FIFO: First-In, First-Out. Throw out the oldest page.

Simple to implement, but the OS can easily throw out a page that is

being accessed frequently.

MIN: (a.k.a. OPT) Look into the future and throw out the page that will be

accessed farthest in the future (provably optimal [Belady'66]). Problem?

LRU: Least Recently Used. Approximation of MIN that works well if the

recent past is a good predictor of the future. Throw out the page that

has not been used in the longest time.

CMPSCI 377: Operating Systems Lecture 21, Page 15

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example: FIFO

3 page Frames

4 virtual Pages: A B C D

Reference stream: A B C A B D A D B C B

FIFO: First-In-First-Out

A B C A B D A D B C B

frame 1

frame 2

frame 3

Number of page faults?

CMPSCI 377: Operating Systems Lecture 21, Page 16

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example: FIFO

FIFO: First-In-First-Out

A B C A B D A D B C B

frame 1 A A A D D D C

frame 2 B B B A A A

frame 3 C C C B B

Number of page faults? 7

CMPSCI 377: Operating Systems Lecture 21, Page 17

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example: MIN

MIN: Look into the future and throw out the page that will be accessed

farthest in the future.

A B C A B D A D B C B

frame 1

frame 2

frame 3

Number of page faults?

CMPSCI 377: Operating Systems Lecture 21, Page 18

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example: MIN

MIN: Look into the future and throw out the page that will be accessed

farthest in the future.

A B C A B D A D B C B

frame 1 A A A A C

frame 2 B B B B

frame 3 C D D

Number of page faults? 5

CMPSCI 377: Operating Systems Lecture 21, Page 19

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example: LRU

LRU: Least Recently Used. Throw out the page that has not been used in

the longest time.

A B C A B D A D B C B

frame 1

frame 2

frame 3

Number of page faults?

CMPSCI 377: Operating Systems Lecture 21, Page 20

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example: LRU

LRU: Least Recently Used. Throw out the page that has not been used in

the longest time.

A B C A B D A D B C B

frame 1 A A A A C

frame 2 B B B B

frame 3 C D D

Number of page faults? 5

CMPSCI 377: Operating Systems Lecture 21, Page 21

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example: LRU

When will LRU perform badly?

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

frame 1

frame 2

frame 3

CMPSCI 377: Operating Systems Lecture 21, Page 22

Department of Computer Science, UMass Amherst Andrew H. Fagg

Example: LRU

When will LRU perform badly?

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

frame 1 A A A D D D C C C B B B

frame 2 B B B A A A D D D C C

frame 3 C C C B B B A A A D

CMPSCI 377: Operating Systems Lecture 21, Page 23

Department of Computer Science, UMass Amherst Andrew H. Fagg

Summary

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 21, Page 24

Department of Computer Science, UMass Amherst Andrew H. Fagg

Next Time

² More on page replacement algorithms ...

CMPSCI 377: Operating Systems Lecture 21, Page 25