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

Department of Computer Science, UMass Amherst Andrew H. Fagg

Announcements/Reminders

² Lab 3 due Wednesday

² Lab 3 demos are due no later than 1 week from Wednesday

² I am out of town next week (so this is the week to ask questions in

preparation for the exam)

CMPSCI 377: Operating Systems Lecture 18, Page 1

Department of Computer Science, UMass Amherst Andrew H. Fagg

Last Class: Memory Management

² Uniprogramming

² Static Relocation

² Dynamic Relocation

² Monolithic memory

segments

Addresses

Virtual

Addresses

OS

A

C

Physical

B

400

Memory

0

2400

2000

1400

900

400

1100

Segments

500

0

0

300

0

CMPSCI 377: Operating Systems Lecture 18, Page 2

Department of Computer Science, UMass Amherst Andrew H. Fagg

Next: Paging

Observation: Processes typically do not use their entire space in memory all

the time.

Paging:

1. Divides and assigns processes to ¯xed sized pages (logical blocks of

memory),

2. then selectively allocates pages to frames in the physical memory, and

3. manages (moves, removes, reallocates) pages in memory.

CMPSCI 377: Operating Systems Lecture 18, Page 3

Department of Computer Science, UMass Amherst Andrew H. Fagg

Paging: Motivation & Features

90/10 rule: Processes spend 90% of their time accessing 10% of their space

in memory.

) Keep only those parts of a process in memory that are actually being used

² Pages greatly simplify the hole ¯tting problem: all pages are

interchangeable

² The logical memory of the process is contiguous, but pages need not be

allocated contiguously in memory.

² By dividing memory into ¯xed size pages, we can eliminate external

fragmentation.

² Paging does not eliminate internal fragmentation (» 1=2 page per

process)

CMPSCI 377: Operating Systems Lecture 18, Page 4

Department of Computer Science, UMass Amherst Andrew H. Fagg

Paging: Example

5

A4

A3

A2

A1

A1

A5

A4

A3

A2 f11

f10

f9

f8

f7

f6

f5

f4

f3

f2

f1

f 0

A

A

in 6 pages

0

A0

2400

400

800

Memory

OS

1200

1600

2000

0

OS

Process A

Frames in

logical

memory

CMPSCI 377: Operating Systems Lecture 18, Page 5

Department of Computer Science, UMass Amherst Andrew H. Fagg

Paging Hardware

² Problem: How do we ¯nd addresses when pages are not allocated

contiguously in memory?

² Virtual Address:

{ Processes use a virtual (logical) address to name memory locations.

{ Process generates contiguous, virtual addresses from 0 to size of the

process.

{ The OS lays the process down on pages and the paging hardware

translates virtual addresses to actual physical addresses in memory.

{ In paging, the virtual address identi¯es the page and the page o®set.

{ A page table keeps track of the frame in memory in which the page is

located.

CMPSCI 377: Operating Systems Lecture 18, Page 6

Department of Computer Science, UMass Amherst Andrew H. Fagg

Paging Hardware

CPU p

f

p

f d d

Page Table

virtual address

Memory

physical address

CMPSCI 377: Operating Systems Lecture 18, Page 7

Department of Computer Science, UMass Amherst Andrew H. Fagg

Paging Hardware

² Paging is a form of dynamic relocation, where each virtual address is

bound by the paging hardware to a physical address.

² Think of the page table as a set of relocation registers, one for each

frame.

² Mapping is invisible to the process; the OS maintains the mapping and

the hardware does the translation.

² Protection is provided with the same mechanisms as used in dynamic

relocation.

CMPSCI 377: Operating Systems Lecture 18, Page 8

Department of Computer Science, UMass Amherst Andrew H. Fagg

Paging Hardware: Practical Details

² Page size (frame sizes) are typically a power of 2 between 512 bytes and

8192 bytes per page.

² Powers of 2 make the translation of virtual addresses into physical

addresses easier. Why?

CMPSCI 377: Operating Systems Lecture 18, Page 9

Department of Computer Science, UMass Amherst Andrew H. Fagg

Paging Hardware: Practical Details

² Powers of 2 make the translation of virtual addresses into physical

addresses easier. For example, given:

1. virtual address space of size 2m bytes and a page of size 2n, then

2. the high order m ¡ n bits of a virtual address select the page, and

3. the low order n bits select the o®set in the page

p d p: page number

d: page offset n m-n

CMPSCI 377: Operating Systems Lecture 18, Page 10

Department of Computer Science, UMass Amherst Andrew H. Fagg

Address Translation Example

A0

A1

A2

A3

f 0

f1

f2

f3

f5

f6

f7

f8

f9

f10

f11

0123

9

11

6

2

table

page

f4

A2

A0

A3

A1

memory

Memory

0

Frames in

ffff

12

13

14

15

32 bytes

64 bytes

96 bytes

128 bytes

160 bytes

192 bytes

224 bytes

256 bytes

memory size = 256 bytes

page size = 16 bytes

virtual

CMPSCI 377: Operating Systems Lecture 18, Page 11

Department of Computer Science, UMass Amherst Andrew H. Fagg

Address Translation Example

² How big is the page table?

² How many bits for a physical address? Assume we can address in 1-byte

increments.

² What part is p, and d?

² Given virtual address 24 (0x18), what is the virtual to physical

translation?

CMPSCI 377: Operating Systems Lecture 18, Page 12

Department of Computer Science, UMass Amherst Andrew H. Fagg

Address Translation Example

² How big is the page table?

4 entries

² How many bits for a physical address? Assume we can address in 1-byte

increments.

8 bits: 4 for page, 4 for o®set

² What part is p, and d?

p: most signi¯cant bits; d: least signi¯cant

² Given virtual address 24 (0x18), what is the virtual to physical

translation?

p = 1, d = 8 (virtual)

f = 6, d = 8 (physical)

CMPSCI 377: Operating Systems Lecture 18, Page 13

Department of Computer Science, UMass Amherst Andrew H. Fagg

Address Translation Example

² How many bits for an address? Assume we can only address in 1-word (4

byte) increments?

² What part is p, and d?

² Given virtual address 13 (0xD), what is the virtual to physical

translation?

² What needs to happen on a process context switch?

CMPSCI 377: Operating Systems Lecture 18, Page 14

Department of Computer Science, UMass Amherst Andrew H. Fagg

Address Translation Example

² How many bits for an address? Assume we can only address in 1-word (4

byte) increments?

6 bits: 4 for page, 2 for o®set

² What part is p, and d?

(again): p is most signi¯cant, d is least.

² Given virtual address 13 (0xD), what is the virtual to physical

translation?

p = 3, d = 1 (virtual)

f = 9, o®set = 1 (physical)

CMPSCI 377: Operating Systems Lecture 18, Page 15

Department of Computer Science, UMass Amherst Andrew H. Fagg

Address Translation Example (cont)

² What needs to happen on a process context switch?

Need to save page table in PCB, and then restore page table of the new

process.

CMPSCI 377: Operating Systems Lecture 18, Page 16

Department of Computer Science, UMass Amherst Andrew H. Fagg

Making Paging E±cient

How should we store the page table?

² Registers:

Advantages?

Disadvantages?

² Memory:

Advantages?

Disadvantages?

CMPSCI 377: Operating Systems Lecture 18, Page 17

Department of Computer Science, UMass Amherst Andrew H. Fagg

Making Paging E±cient

How should we store the page table?

² Registers:

Advantages? Fast.

Disadvantages? If lots of pages, need many registers. Context switch

would require saving/restoring registers which would be slow.

² Memory:

Advantages? Lots of memory. Could just save/restore a pointer to the

page table on context switch.

Disadvantages? Each memory address requires 2 memory accesses: one to

translate from virtual to physical memory, one to actually access memory.

CMPSCI 377: Operating Systems Lecture 18, Page 18

Department of Computer Science, UMass Amherst Andrew H. Fagg

Translation Look-aside Bu®ers (TLB)

A fast, fully associative memory that stores page numbers (the key) and the

frame (the value) in which they are stored.

² If memory accesses have locality, address translation has locality too.

² Typical TLB sizes range from 8 to 2048 entries.

CMPSCI 377: Operating Systems Lecture 18, Page 19

Department of Computer Science, UMass Amherst Andrew H. Fagg

TLB Implementation

v: valid bit that says

the entry is up-to-date

TLB

Miss

TLB

Miss

p

CPU p f d d

virtual address phsical address

Memory

TLB

Hit

v page frame

load

TLB

(in Memory)

TLB

p

Page Table

f

CMPSCI 377: Operating Systems Lecture 18, Page 20

Department of Computer Science, UMass Amherst Andrew H. Fagg

Costs of Using The TLB

1. What is the e®ective memory access cost if the page table is in memory?

2. What is the e®ective memory access cost with a TLB?

CMPSCI 377: Operating Systems Lecture 18, Page 21

Department of Computer Science, UMass Amherst Andrew H. Fagg

Costs of Using The TLB

1. What is the e®ective memory access cost if the page table is in memory?

ema = 2 ¤ ma

2. What is the e®ective memory access cost with a TLB?

ema = (ma + TLB) ¤ p + (1 ¡ p) ¤ (2ma + TLB)

A large TLB improves hit ratio, and thus decreases average memory cost.

CMPSCI 377: Operating Systems Lecture 18, Page 22

Department of Computer Science, UMass Amherst Andrew H. Fagg

Initializing Memory when Starting a Process

1. Process needing k pages arrives.

2. If k page frames are free, then allocate these frames to pages. Else free

frames that are no longer needed.

3. The OS puts each page in a frame and then puts the frame number in

the corresponding entry in the page table.

4. OS marks all TLB entries as invalid (°ushes the TLB).

5. OS starts process.

6. As process executes, OS loads TLB entries as each page is accessed,

replacing an existing entry if the TLB is full.

CMPSCI 377: Operating Systems Lecture 18, Page 23

Department of Computer Science, UMass Amherst Andrew H. Fagg

Saving/Restoring Memory on a Context Switch

² The Process Control Block (PCB) must be extended to contain:

{ The page table

{ Possibly a copy of the TLB

² On a context switch:

1. Copy the page table base register value to the PCB.

2. Copy the TLB to the PCB (optional).

3. Flush the TLB.

4. Restore the page table base register.

5. Restore the TLB if it was saved.

² Multilevel Paging: If the virtual address space is huge, page tables get

too big. Many systems use a multilevel paging scheme...

CMPSCI 377: Operating Systems Lecture 18, Page 24

Department of Computer Science, UMass Amherst Andrew H. Fagg

Sharing

Paging allows sharing of memory across processes, since memory used by a

process no longer needs to be contiguous.

² Shared code must be reentrant, that means the processes that are using it

cannot change it (e.g., no data in reentrant code).

² Sharing of pages is similar to the way threads share text and memory with

each other.

² A shared page may exist in di®erent parts of the virtual address space of

each process, but the virtual addresses map to the same physical address.

² The user program (e.g., emacs) marks text segment of a program as

reentrant with a system call.

CMPSCI 377: Operating Systems Lecture 18, Page 25

Department of Computer Science, UMass Amherst Andrew H. Fagg

Sharing (cont)

² The OS keeps track of available reentrant code in memory and reuses

them if a new process requests the same program.

² Can greatly reduce overall memory requirements for commonly used

applications.

CMPSCI 377: Operating Systems Lecture 18, Page 26

Department of Computer Science, UMass Amherst Andrew H. Fagg

Summary

² Paging is a big improvement over segmentation:

{ Eliminates the problem of external fragmentation and therefore the

need for compaction.

{ Allows sharing of code pages among processes, reducing overall

memory requirements.

{ Enables processes to run when they are only partially loaded in main

memory.

² However, paging has its costs:

{ Translating from a virtual address to a physical address is more

time-consuming.

{ Paging requires hardware support in the form of a TLB to be e±cient

enough.

{ Paging requires more complex OS to maintain the page table.

CMPSCI 377: Operating Systems Lecture 18, Page 27

Department of Computer Science, UMass Amherst Andrew H. Fagg

Next Time

² Segmented Paging

² Next Week:

{ Monday: Holiday

{ Wednesday: Discussion and exam review

{ Friday: Exam 2 (same place, same time)

CMPSCI 377: Operating Systems Lecture 18, Page 28