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

Department of Computer Science, UMass Amherst Andrew H. Fagg

Announcements/Reminders

² HW 4 due Friday at 19:30

² Lab 3 due Wednesday, April 16

CMPSCI 377: Operating Systems Lecture 17, Page 1

Department of Computer Science, UMass Amherst Andrew H. Fagg

Memory Management

² Where is the executing process?

² How do we allow multiple processes to use main memory simultaneously?

² What is an address and how is one interpreted?

CMPSCI 377: Operating Systems Lecture 17, Page 2

Department of Computer Science, UMass Amherst Andrew H. Fagg

Background: Computer Architecture

² Program executable

starts out on disk

² The OS loads the

program into memory

² CPU fetches

instructions and

data from memory

while executing the

program

Disk

Controller

disk disk

Physical

System Bus

Memory Controller

Data

Processor

Address

Virtual Trap

CPU

Cache

Virtual

Address

TLB/MMU

Memory

Control

Address

CMPSCI 377: Operating Systems Lecture 17, Page 3

Department of Computer Science, UMass Amherst Andrew H. Fagg

Memory Management: Terminology

² Segment: A chunk of

memory assigned to a

process.

² Physical Address:

a real address in

memory

² Virtual Address: an

address relative to the

start of a process's

address space.

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 17, Page 4

Department of Computer Science, UMass Amherst Andrew H. Fagg

Where do addresses come from?

How do programs generate instruction and data addresses?

² Compile time: The compiler generates the exact physical location in

memory starting from some ¯xed starting position k. The OS does

nothing.

² Load time: Compiler generates an address, but at load time the OS

determines the process' starting position. Once the process loads, it does

not move in memory.

² Execution time: Compiler generates an address, and OS can place it any

where it wants in memory.

CMPSCI 377: Operating Systems Lecture 17, Page 5

Department of Computer Science, UMass Amherst Andrew H. Fagg

Uniprogramming

² OS gets a ¯xed part of memory (highest memory in DOS).

² One process executes at a time.

² Process is always loaded starting at address 0.

² Process executes in a contiguous section of memory.

² Compiler can generate physical addresses.

² Maximum address = Memory Size - OS Size

² OS is protected from process by checking addresses used by process.

CMPSCI 377: Operating Systems Lecture 17, Page 6

Department of Computer Science, UMass Amherst Andrew H. Fagg

Uniprogramming

Memory

0

2400 OS

Memory

0

2400 OS

Memory

0

2400 OS

A

B

C

2200 2200 2200

Processes A, B, C

)Simple, but does not allow for overlap of I/O and computation.

CMPSCI 377: Operating Systems Lecture 17, Page 7

Department of Computer Science, UMass Amherst Andrew H. Fagg

Multiple Programs Share Memory

Transparency:

² We want multiple processes to coexist in memory.

² No process should be aware that memory is shared.

² Processes should not care what physical portion of memory to which

they are assigned.

Safety:

² Processes must not be able to corrupt each other.

² Processes must not be able to corrupt the OS.

E±ciency:

² Performance of CPU and memory should not be degraded badly due to

sharing.

CMPSCI 377: Operating Systems Lecture 17, Page 8

Department of Computer Science, UMass Amherst Andrew H. Fagg

Relocation

² Put the OS in the highest

memory.

² Assume at compile/link time

that the process starts at 0

with a maximum address =

memory size - OS size.

C C

A

Memory

0

2400

2000

900

A

Memory

0

2400

2000

900

B

OS

B

OS

400 400

1200

² Load a process by allocating a contiguous segment of memory in which

the process ¯ts.

² The ¯rst (smallest) physical address of the process is the base address and

the largest physical address the process can access is the limit address.

CMPSCI 377: Operating Systems Lecture 17, Page 9

Department of Computer Science, UMass Amherst Andrew H. Fagg

Relocation

² Static Relocation:

{ At load time, the OS adjusts the addresses in a process to re°ect its

position in memory.

{ Once a process is assigned a place in memory and starts executing it,

the OS cannot move it. (Why?)

CMPSCI 377: Operating Systems Lecture 17, Page 10

Department of Computer Science, UMass Amherst Andrew H. Fagg

Relocation

² Dynamic Relocation:

{ Hardware adds relocation register (base) to virtual address to get a

physical address;

{ Hardware compares address with limit register (address must be less

than limit).

{ If test fails, the MMU generates an address trap and ignores the

physical address.

register

limit

CPU

relocation

register

+

logical address

physical address

trap: addressing error

>

CMPSCI 377: Operating Systems Lecture 17, Page 11

Department of Computer Science, UMass Amherst Andrew H. Fagg

Relocation

² Advantages:

{ OS can easily move a process during execution.

{ OS can allow a process to grow over time.

{ Simple, fast hardware: two special registers, an add, and a compare.

² Disadvantages:

{

{

{

{

{

CMPSCI 377: Operating Systems Lecture 17, Page 12

Department of Computer Science, UMass Amherst Andrew H. Fagg

Relocation

² Advantages:

{ OS can easily move a process during execution.

{ OS can allow a process to grow over time.

{ Simple, fast hardware: two special registers, an add, and a compare.

² Disadvantages:

{ Slows down hardware due to the add on every memory reference.

{ Can't share memory (such as program text) between processes.

{ Process is still limited to physical memory size.

{ Degree of multiprogramming is very limited since all memory of all

active processes must ¯t in memory.

{ Complicates memory management.

CMPSCI 377: Operating Systems Lecture 17, Page 13

Department of Computer Science, UMass Amherst Andrew H. Fagg

Relocation: Properties

² Transparency: processes are largely unaware of sharing.

² Safety: each memory reference is checked.

² E±ciency: memory checks and virtual to physical address translation are

fast as they are done in hardware, BUT if a process grows, it may have to

be moved which is very slow.

CMPSCI 377: Operating Systems Lecture 17, Page 14

Department of Computer Science, UMass Amherst Andrew H. Fagg

Memory Management: Memory Allocation

As processes enter the system, grow, and terminate, the OS must keep track

of which memory is available and utilized.

Allocate D A terminates

OS

A

B terminates

0

1500

900

400

B

C

2100

1800

OS

A

0

900

400

C

2100

1800

OS

A

0

900

400

C

2100

1800

OS

0

900

400

C

2100

1800

2400 2400 2400 2400

D

1500

D

² Holes: pieces of free memory (shaded above in ¯gure)

² Given a new process, the OS must decide which hole to use for the

process

CMPSCI 377: Operating Systems Lecture 17, Page 15

Department of Computer Science, UMass Amherst Andrew H. Fagg

Memory Allocation Policies

² First-Fit: allocate the ¯rst one in the list in which the process ¯ts. The

search can start with the ¯rst hole, or where the previous ¯rst-¯t search

ended.

² Best-Fit: Allocate the smallest hole that is big enough to hold the

process. The OS must search the entire list or store the list sorted by size

hole list.

² Worst-Fit: Allocate the largest hole to the process (so as to leave as

large a hole as possible). Again { the OS must search the entire list or

keep the list sorted.

² Simulations show ¯rst-¯t and best-¯t usually yield better storage

utilization than worst-¯t; ¯rst-¯t is generally faster than best-¯t.

CMPSCI 377: Operating Systems Lecture 17, Page 16

Department of Computer Science, UMass Amherst Andrew H. Fagg

Fragmentation

² External Fragmentation

{ Frequent loading and unloading programs causes free space to be

broken into little pieces

{ External fragmentation exists when there is enough memory to ¯t a

process in memory, but the space is not contiguous

{ 50-percent rule: Simulations show that for every 2N allocated blocks,

N blocks are lost due to fragmentation (i.e., 1/3 of memory space is

wasted)

{ We want an allocation policy that minimizes wasted space.

CMPSCI 377: Operating Systems Lecture 17, Page 17

Department of Computer Science, UMass Amherst Andrew H. Fagg

Fragmentation (cont)

² Internal Fragmentation:

{ Consider a process of size 8846 bytes and a block of size 8848 bytes

) it is more e±cient to allocate the process the entire 8848 block than it

is to keep track of 2 free bytes

{ Internal fragmentation exists when memory internal to a partition goes

unused

CMPSCI 377: Operating Systems Lecture 17, Page 18

Department of Computer Science, UMass Amherst Andrew H. Fagg

Compaction

(needs 600)

(needs 600)

Alternative 1:

Alternative 2:

OS

0

400

2400

D

1000

C

1300

E

E

OS

0

400

2400

D

1000

1800

C

1600

2100

OS

0

400

2400

D

1000

1800

C 2100

E

OS

0

900

400

C

2100

1800

2400

D

1500

OS

0

900

400

C

2100

1800

2400

D

1500

Compaction

OS

0

400

2400

D

1000

C

1300

1900

E

² How much memory is moved?

² How big a block is created?

² Any other choices?

CMPSCI 377: Operating Systems Lecture 17, Page 19

Department of Computer Science, UMass Amherst Andrew H. Fagg

Swapping

² Roll out a process to disk, releasing all the memory it holds.

² When process becomes active again, the OS must reload it in memory.

{ With static relocation, the process must be put in the same position.

{ With dynamic relocation, the OS ¯nds a new position in memory for

the process and updates the relocation and limit registers.

² If swapping is part of the system, compaction is easy to add.

² How could or should swapping interact with CPU scheduling?

CMPSCI 377: Operating Systems Lecture 17, Page 20

Department of Computer Science, UMass Amherst Andrew H. Fagg

Summary

² Processes must reside in memory in order to execute.

² Processes generally use virtual addresses which are translated into

physical addresses just before accessing memory.

² Segmentation allows multiple processes to share main memory, but makes

it expensive for processes to grow over time.

² Swapping allows the total memory being used by all processes to exceed

the amount of physical memory available, but increases context switch

time.

CMPSCI 377: Operating Systems Lecture 17, Page 21

Department of Computer Science, UMass Amherst Andrew H. Fagg

Next Time

² Monday: Paging

² Wednesday: Paging

CMPSCI 377: Operating Systems Lecture 17, Page 22