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

Department of Computer Science, UMass Amherst Andrew H. Fagg

Announcements/Reminders

˛ Lab 3 due today

˛ Exam 2 is 1 week from Friday

˛ Lab 4, HW 4 solutions and HW 5 are available from the web page

CMPSCI 377: Operating Systems Lecture 19, Page 1

Department of Computer Science, UMass Amherst Andrew H. Fagg

Quiz

Who Said: \Operating Systems are Destined to be Free"?

What did he mean?

What was he arguing for?

CMPSCI 377: Operating Systems Lecture 19, Page 2

Department of Computer Science, UMass Amherst Andrew H. Fagg

Quiz

Who Said: \Operating Systems are Destined to be Free"?

Neal Stephenson in: \In the Beginning was the Command Line."

also wrote: Snow Crash and Cryptonomicon

CMPSCI 377: Operating Systems Lecture 19, Page 3

Department of Computer Science, UMass Amherst Andrew H. Fagg

So Far: Paging

˛ Process generates virtual addresses from 0 to Max.

˛ OS divides the process onto pages; manages a page table for every

process; and manages the pages in memory.

˛ Hardware maps from virtual addresses to physical addresses.

˛ Sharing of pages is possible, but not very useful as implemented. Why?

CPU p

f

p

f d d

Page Table

virtual address

Memory

physical address

CMPSCI 377: Operating Systems Lecture 19, Page 4

Department of Computer Science, UMass Amherst Andrew H. Fagg

Today: Segmentation

Segments take the user's view of the program.

˛ User views the program in logical segments, e.g., code, global variables,

stack, heap (dynamic data structures), not a single linear array of bytes.

˛ New idea: the compiler generates references that identify the segment

and the oŽset in the segment, e.g., a code segment with oŽset = 399

˛ Thus processes use virtual addresses that include both the segment and

segment oŽset.

) Segments make it easier for the call stack and heap to grow dynamically.

Why?

) Segments make both sharing and protection easier. Why?

CMPSCI 377: Operating Systems Lecture 19, Page 5

Department of Computer Science, UMass Amherst Andrew H. Fagg

Today: Segmentation

) Segments make it easier for the call stack and heap to grow dynamically.

Why?

{ Without segmentation, the stack and the heap grow toward each other.

{ With segmentation, each segment is managed separately, so if the

stack or the heap grows, the OS can increase the segment size.

) Segments make both sharing and protection easier. Why?

{ The OS manages these logical units separately (instead of managing a

¯xed-size page).

CMPSCI 377: Operating Systems Lecture 19, Page 6

Department of Computer Science, UMass Amherst Andrew H. Fagg

Implementing Segmentation

˛ Segment table: each entry contains a base address in memory, length of

segment, and protection information (can this segment be shared, read,

modi¯ed, etc.).

˛ Hardware support: multiple base/limit registers.

˛ How is this diŽerent than a TLB?

limit base

limit base

limit base

CPU > d

virtual address

yes

no

trap

physical address +

s

s

CMPSCI 377: Operating Systems Lecture 19, Page 7

Department of Computer Science, UMass Amherst Andrew H. Fagg

Implementing Segmentation

˛ Compiler needs to generate virtual addresses whose higher-order bits are a

segment number.

˛ Segmentation can be combined with a dynamic or static relocation

system,

{ Each segment is allocated a contiguous piece of physical memory.

{ External fragmentation can be a problem again

˛ Similar memory mapping algorithm as paging. We need something like

the TLB if programs can have lots of segments

Let's combine the ease of sharing we get from segments with eącient

memory utilization we get from pages.

CMPSCI 377: Operating Systems Lecture 19, Page 8

Department of Computer Science, UMass Amherst Andrew H. Fagg

Combining Segments and Paging

˛ Treat virtual address space as a collection of segments (logical units) of

arbitrary sizes.

˛ Treat physical memory as a sequence of ¯xed size page frames.

˛ Segments are typically larger than page frames,

) Map a logical segment onto multiple page frames by paging the

segments

CMPSCI 377: Operating Systems Lecture 19, Page 9

Department of Computer Science, UMass Amherst Andrew H. Fagg

Combining Segments and Paging

Shared library

Constant data

Physical Memory Virtual Address Space

Local data

Code

Heap

Stack

CMPSCI 377: Operating Systems Lecture 19, Page 10

Department of Computer Science, UMass Amherst Andrew H. Fagg

Addresses in a Segmented Paging System

base

limit base

limit base frame

frame

s

limit

p

CPU

virtual address

s p d

>? trap

+ physical address

Segment Table

Page Table

CMPSCI 377: Operating Systems Lecture 19, Page 11

Department of Computer Science, UMass Amherst Andrew H. Fagg

Addresses in a Segmented Paging System

˛ A virtual address becomes a segment number, a page within that

segment, and an oŽset within the page.

˛ The segment number indexes into the segment table which yields the

base address of the page table for that segment.

˛ Check the remainder of the address (page number and oŽset) against the

limit of the segment.

˛ Use the page number to index the page table. The entry is the frame.

(The rest of this is just like paging.)

˛ Add the frame and the oŽset to get the physical address.

CMPSCI 377: Operating Systems Lecture 19, Page 12

Department of Computer Science, UMass Amherst Andrew H. Fagg

Addresses in a Segmented Paging System: Example

˛ Given a memory size of 256 addressable words,

˛ a page table indexing 8 pages,

˛ a page size of 32 words, and

˛ 8 logical segments

1. How many bits is a physical address?

2. How many bits for the segment number, page table, and oŽset?

3. How many bits is a virtual address?

4. How many segment table entries do we need?

CMPSCI 377: Operating Systems Lecture 19, Page 13

Department of Computer Science, UMass Amherst Andrew H. Fagg

Addresses in a Segmented Paging System: Example

˛ Given a memory size of 256 addressable words,

˛ a page table indexing 8 pages,

˛ a page size of 32 words, and

˛ 8 logical segments

1. How many bits is a physical address? 8 bits

2. How many bits for the segment number, page table, and oŽset? 3 3 5

3. How many bits is a virtual address? 11 bits

4. How many segment table entries do we need? 8

CMPSCI 377: Operating Systems Lecture 19, Page 14

Department of Computer Science, UMass Amherst Andrew H. Fagg

Sharing Pages and Segments

˛ Share individual pages by copying page table entries.

˛ Share whole segments by sharing segment table entries, which is the same

as sharing the page table for that segment.

˛ Need protection bits to specify and enforce read/write permission.

{ When would segments containing code be shared?

{ When would segments containing data be shared?

CMPSCI 377: Operating Systems Lecture 19, Page 15

Department of Computer Science, UMass Amherst Andrew H. Fagg

Sharing Pages and Segments

˛ When would segments containing code be shared?

{ Read-only sharing of common applications or common libraries.

˛ When would segments containing data be shared?

{ Read-only sharing of constant data used by an application.

{ Read-write sharing of heap data used by multiple threads within a

process.

CMPSCI 377: Operating Systems Lecture 19, Page 16

Department of Computer Science, UMass Amherst Andrew H. Fagg

Sharing Pages and Segments: Implementation Issues

˛ Where are the segment table and page tables stored?

1. Store segment tables in a small number of associative registers; page

tables are in main memory with a TLB

(faster but limits the number of segments a program can have)

2. Both the segment tables and page tables can be in main memory with

the segment index and page index combined & used in the TLB lookup

(slower but no restrictions on the number of segments per program)

˛ Protection and valid bits can go either on the segment or the page table

entries

˛ Note: Just like recursion, we can do multiple levels of paging and

segmentation when the tables get too big.

CMPSCI 377: Operating Systems Lecture 19, Page 17

Department of Computer Science, UMass Amherst Andrew H. Fagg

Segmented Paging: Costs and Bene¯ts

˛ Bene¯ts: faster process start times, faster process growth, memory

sharing between processes.

˛ Costs: somewhat slower context switches, slower address translation.

˛ Pure paging system )(virtual address space)/(page size) entries in page

table. How many entries in a segmented paging system?

˛ What is the performance of address translation of segmented paging

compared to contiguous allocation with relocation? Compared to pure

paging?

˛ How does fragmentation of segmented paging compare with contiguous

allocation? With pure paging?

CMPSCI 377: Operating Systems Lecture 19, Page 18

Department of Computer Science, UMass Amherst Andrew H. Fagg

Segmented Paging: Costs and Bene¯ts

˛ How many entries in a segmented paging system?

There are as many page tables as there are segments. The total number

of page table entries for a process is <= the number required in a pure

paging scheme.

˛ What is the performance of address translation of segmented paging

compared to contiguous allocation with relocation? Compared to pure

paging?

{ Slower than contiguous allocation since need to index through segment

table AND page table. If TLB miss, much slower.

{ Slower than pure paging because index through segment table. But:

normally done in hardware, so not a big problem

CMPSCI 377: Operating Systems Lecture 19, Page 19

Department of Computer Science, UMass Amherst Andrew H. Fagg

Segmented Paging: Costs and Bene¯ts

˛ How does fragmentation of segmented paging compare with contiguous

allocation? With pure paging?

{ No external fragmentation, so no need for compaction.

{ Internal fragmentation: 1/2 page per segment on average, so worse

than pure paging.

CMPSCI 377: Operating Systems Lecture 19, Page 20

Department of Computer Science, UMass Amherst Andrew H. Fagg

Putting it All Together: A Historical View

˛ Relocation using Base and Limit registers

{ simple, but in°exible

˛ Segmentation:

{ compiler's view presented to OS

{ segment tables tend to be small

{ memory allocation is expensive and complicated (¯rst ¯t, worst ¯t,

best ¯t).

{ compaction is needed to resolve external fragmentation.

CMPSCI 377: Operating Systems Lecture 19, Page 21

Department of Computer Science, UMass Amherst Andrew H. Fagg

Putting it all together

˛ Paging:

{ simpli¯es memory allocation since any page can be allocated to any

frame

{ page tables can be very large (especially when virtual address space is

large and pages are small)

˛ Segmentation & Paging

{ only need to allocate as many page table entries as we need (large

virtual address spaces are not a problem).

{ easy memory allocation, any frame can be used

{ sharing at either the page or segment level

{ increased internal fragmentation over paging

{ two lookups per memory reference

CMPSCI 377: Operating Systems Lecture 19, Page 22

Department of Computer Science, UMass Amherst Andrew H. Fagg

Next Time

˛ Friday: Exam Review and start Virtual Memory

˛ Wednesday: Discussion (hw 3/4 and Memory Management)

˛ Next Friday: Exam 2

˛ Following Monday: Virtual Memory and Demand Paging (Chapter 10)

CMPSCI 377: Operating Systems Lecture 19, Page 23