Transcript Document

Operating Systems Principles
Memory Management
Lecture 7: Physical Memory
主講人：虞台文
Content


Preparing a Program for Execution
–
Program Transformations
–
Logical-to-Physical Address Binding
Memory Partitioning Schemes
–
Fixed Partitions
–
Variable Partitions

Allocation Strategies for Variable Partitions

Dealing with Insufficient Memory
Operating Systems Principles
Memory Management
Lecture 7: Physical Memory
Preparing a Program
for Execution
Preparing a Program for Execution
Modules reflecting different
functions are designed separately,
possibly by different
programmers.
Preparing a Program for Execution
Compilation will produce an object module and a
corresponding external symbol table.
Preparing a Program for Execution
. . . . .
float x;
int i;
. . . . .
void fun()
{
. . . . .
}
Compilation
External Symbol Table
Name
Type
Address
...
x
float
100
...
i
int
108
...
fun
function
1000
...
...
...
...
...
Preparing a Program for Execution
Compilation
Name
Type
Address
...
Name
Type
Address
...
Name
Type
Address
...
The linker combines several object
modules together to build a load
module (EXE) by resolving external
references through symbol tables.
Preparing a Program for Execution
Name
Type
Address
...
Name
Type
Address
...
Name
Type
Address
...
Preparing a Program for Execution
Logical-to-physical address mapping is done by
the loader to transfer the load module from
the secondary storage to the main memory.
More on Linking
00000000
Object
Module 1
Object
Module 2
Object
Module n
Linking
Object
Module 1
Object
Module 2
Object
Module n
FFFFFFF
Logical
Address Space
More on Linking
00000000
Name
Type
Address
Object
Module 1
...
Name
Type
Address
Object
Module 2
...
Name
Type
Address
...
Object
Module n
Object
Module 1
Object
Load 2
Module
Module
Linking


Logical address space is used by the
linker to resolve external references.
Binding can be static or dynamic.
Object
Module n
FFFFFFF
Logical
Address Space
Assignment of actual physical addresses
to program instruction and data.
Logical-to-Physical Address Binding
00000000
00000000
Load
Module 1
Load
Module 2
aaaaaaaa
Load
Module 3
Created by linker
(on logical address space)
Program relocation needed
(done by the loader)
Load
Module 3’
bbbbbbbb
Load
Module 1’
Load
Module 2’
cccccccc
Physical
Address Space
Assignment of actual physical addresses
to program instruction and data.
Address Binding

Static binding
–
–
–
–

Programming time
Compilation time
Linking time
Loading time
Dynamic binding
–
Execution time
Static Binding

•
•
•
•
Programming time
Compilation time
Linking time
Loading time
Programming-time Binding
–
Seldom used
–
Used in low-level environments
–
E.g., OS, real-time and embedded systems,
control special hardware component.
Static Binding
•
•
•
•
Programming time
Compilation time
Linking time
Loading time
SAMPLE PROGRAM FOR MC6802 USING CRS8
The following source file has been named MC6802.ASM
Source:
Length:
Destin:
CPU
HOF
ORG
DFB
EQU
DFS
Entry:
ORG
LDX
Loop:
Fin:
LDAB
LDAA
STAA
INX
DECB
BNE
JMP
END
6802
; 6802 processor
MOT
; Motorola Records
0100H
; Start of Data
'Hello and Welcome'
$ - Source
;Length of Source
Length
; Buffer which has same
; length as Source
0120H
; Start of Code
#Source
; Point Index Reg to
; Source string
#Length
; Number of characters to move
0,X
Length,X
Loop
Fin
Entry
Static Binding

•
•
•
•
Programming time
Compilation time
Linking time
Loading time
Compile-time Binding
–
The compiler is given the starting address for
the program to be load for execution.
–
The resulting program can execute only when
loaded into the specific preassigned memory
space.
–
Not relocatable
–
Rarely used
Static Binding

•
•
•
•
Programming time
Compilation time
Linking time
Loading time
Compile-time Binding
–
–
Named variables have their addresses hardcoded

Global variables given offset from start of global data area

Local variables given offset from top of stack

Object variables given offset from start of object data
Normal function and method calls are hardcoded

Normal functions have specific starting address in object file

Object methods have specific starting address in object file
Static Binding

•
•
•
•
Programming time
Compilation time
Linking time
Loading time
Link-time Binding
–
The load module is still not relocatable
–
The program will be loaded to memory with
starting location specified or assumed by the
linker (Linkage Editor).
–
Linking loader: combining linking and loading
–
Widely used in smaller, single user systems
(e.g., CP/M)
Static Binding
Object
program(s)
Library
Linkage editor
Load
Module
Simple Loader
Memory
•
•
•
•
Programming time
Compilation time
Linking time
Loading time
Object
program(s)
Library
Linking loader
Memory
Static Binding
Object
program(s)
Library
Linkage editor
Load
Module
Simple Loader
Memory
•
•
•
•
Programming time
Compilation time
Linking time
Loading time
Object
program(s)
Library
Linking loader
Memory
•
•
•
•
Static Binding

Programming time
Compilation time
Linking time
Loading time
What?
Load-Time Binding
–
The load module is relocatable
–
What operands are needed to
be relocated (relocatable)?


–
Indicated by compilers and
assemblers
Needed for linking and
loading
How to perform relocation?
Object
program(s)
Library
Linkage editor
relocatable
How?
Load
Module
Loader
Memory
What?
•
•
•
•
Static Binding

Programming time
Compilation time
Linking time
Loading time
What?
What operands are needed to
Object
program(s)
be relocated?
–
Register?
–
Immediate operand (constant)?
–
Offset to a base register?
–
Absolute memory address
–
Relative memory address?
Library
Linkage editor
relocatable
How?
Load
Module
Loader
Memory
What?
•
•
•
•
Static Binding

Programming time
Compilation time
Linking time
Loading time
What?
What operands are needed to
Object
program(s)
be relocated?
–
Register?
–
Immediate operand (constant)?
–
Offset to a base register?
–
Absolute memory address
–
Keep unchanged
Relative memory address?
Ralocatable
Library
Linkage editor
relocatable
How?
Load
Module
Loader
Memory
What?
•
•
•
•
Static Binding

Programming time
Compilation time
Linking time
Loading time
What?
How to relocate the relocatable
operands?
Object
program(s)
Library
x
Load
Module
y
Load
Module’
relocatable
How?
Logical
Address Space
Linkage editor
Physical
Address Space
Load
Module
Loader
Memory
What?
•
•
•
•
Static Binding

Programming time
Compilation time
Linking time
Loading time
What?
How to relocate the relocatable
operands?
Add all relocatable
operands in the load
module by the amount
of yeditor
Linkage
Library
 x.
x
Load
Module
Object
program(s)
y
Load
Module’
relocatable
How?
Logical
Address Space
Physical
Address Space
Load
Module
Loader
Memory
What?
Example
0
20
. . .
int i;
. . .
i = ???;
. . .
g();
. . .
0
store 20
compiler
function
f
i
call g
f()
{
. . .
}
200
function
g
compiler
g()
{
. . .
}
Source
Module 1
Source
Module 2
Logical
Address Space
Logical
Address Space
Example
0
20
. . .
int i;
. . .
i = ???;
. . .
g();
. . .
Source
Module 1
0
function
f
i
store 20
compiler
Relative memory address
(relocatable)
call g
f()
{
. . .
}
200
function
g
compiler
g()
{
. . .
}
External
reference
Logical
Address Space
Source
Module 2
Logical
Address Space
Example
0
20
. . .
int i;
. . .
i = ???;
. . .
g();
. . .
compiler
0
i
Object
store 201
Module
(obj1)
call g
f()
{
. . .
}
function
Object
f
200
Module 2
function
(obj2)
g
compiler
g()
{
. . .
}
Source
Module 1
Source
Module 2
Logical
Address Space
Logical
Address Space
Link obj3+obj2+obj1, myexe
Example
Obj1
0
20
Obj2
0
i
store 20
200
function
f
0
Obj3
0
Others
50
250
function
g
call g
350
370
linker
Others
function
f
function
g
i
store 370
call 250
Logical
Address Space
Link obj3+obj2+obj1, myexe
Example
Obj1
0
20
0
i
store 20
call g
Obj3
0
Others
50
Obj2
200
function
f
0
250
function
g
relocated
350
370
Others
function
f
function
g
i
store 370
call 250
External
reference
resolved
Logical
Address Space
Link obj3+obj2+obj1, myexe
Example
Obj1
0
20
Obj2
0
i
store 20
call g
200
function
f
function
g
0
Obj3
0
Others
50
250
350
370
Others
function
f
function
Load
g
Module
(myexe)
i
store 370
call 250
Logical
Address Space
Example
0
1000
1050
1250
1350
1370
Others
50
function
f
250
function
g
i
store 1370
Physical
Address
Space
loader
call 1250
350
370
Others
function
f
function
g
i
store 370
relocated
call 250
myexe
Physical address differs from logical address
usually by a constant offset.
Dynamic Binding



Dynamic Binding = Binding at Execution Time
That is, binding immediately before each memory
reference.
Hardware support needed for logical-to-physical
address mapping
Physical address differs from logical address
usually by a constant offset.
Dynamic Binding
Example
Operating Systems Principles
Memory Management
Lecture 7: Physical Memory
Memory Partitioning
Schemes
Memory Partitioning Schemes

Fixed Partitions
–

The number of partitions and the size
of each partition are determined at the
time the OS is initialized.
Variable Partitions
–
–
Memory not partitioned a priori
Partitioning on demand
Fixed Partitions

Single-program systems
–
OS
2 partitions (OS/user)
User

Multi-programmed systems
–
partitions of different sizes
OS
..
.
How to Assign Processes to Partitions?
How to Assign Processes to Partitions?

FIFO for each partition
–
–
–
Typically, best-fit is used
for queue assignment.
Problem: Some partitions
may be unused if no
processes of appropriate
sizes are available.
To resolve the problem,
more complex queue
management scheme and
process scheduling scheme
would be required.
How to Assign Processes to Partitions?

Single FIFO
–
–
–
More complex, but more
flexible.
E.g., rather than leaving a
partition empty, the
scheduler may assigned a
process to a partition not in
best-fit sense.
E.g., the actual memory
requirement of a process
may grow and shrink
dynamically.
Limitations of Fixed Partitions


Program size limited to largest partition
Internal fragmentation
OS
–
unused space within partitions
Variable Partitions



Memory not partitioned a priori
Each request is allocated portion
of free space.
Allocating and releasing memory
dynamically cause external
fragmentation.
Issues

Over time, memory will consist a sequence
of variable size blocks. Some are free, and
some are not.
How to allocate memories
of sizes
1.
All free blocks are applicable.
Allocate which one?
2.
None free block is applicable.
But, the total amount of
free memory is large enough.
Adjacent holes must be coalesced to
prevent increasing fragmentation.
Hole Coalescing
A
A
A
B
B
B
C
B’
C
C
A
A
B’
B’’
B’’
D
D
D
D
B’’’
E
E
E
E
E
F
F
F
F
F
G
G
G
G
G
Adjacent holes must be coalesced to
prevent increasing fragmentation.
Hole Coalescing
Four cases on hole coalescing:
no adjacent hole
A hole at right
A hole at left
Holes at two sides


F
free
size
E
occupied
size
D
free
size
C
occupied
size
occupied
size
B
G
Free blocks are kept sorted using a doubly linked list.
What would be done to release a block of memory?
–

A
occupied
size
free
size
Link List Implementation (I)
Check both its neighbors for possible coalescing.
Problems:
–
–
How to check the right neighbor?
How to check the left neighbor?
easy
checked by starting from
the header (inefficient)

D
size
occupied
free
size
size
occupied
occupied
size
size
occupied
occupied
size
C
need not be sorted
What would be done to release a block of memory?
–

B
Free blocks are linked using a doubly linked list
–

A
size
free
occupied
size
free
size
Link List Implementation (II)
Check both its neighbors for possible coalescing.
Problems:
–
–
How to check the right neighbor?
How to check the left neighbor?
easy
easy
E
Bitmap Implementation




Memory divided into fix-size blocks
Each block represented by a 0/1 bit in a
binary string: the “bitmap”
Can be implemented as char or int array
Operations use bit masks
–
–
–
Release: B[i] = B[i] & '11011111'
Allocate: B[i] = B[i] | '11000000'
Search: Repeatedly, Check left-most bit and
Shift mask right: TEST = B[i] & '10000000'
Bitmap Implementation
00000000
00001000
00002000
00003000
00004000
00005000
00006000
00007000
00008000
00009000
0000a000
0000b000
0000c000
0000d000
0000e000
0000f000
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
00010000
00011000
00012000
00013000
00014000
00015000
00016000
00017000
00018000
00019000
0001a000
0001b000
0001c000
0001d000
0001e000
0001f000
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
















00070000
00071000
00072000
00073000
00074000
00075000
00076000
00077000
00078000
00079000
0007a000
0007b000
0007c000
0007d000
0007e000
0007f000
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
How to allocate a block of continuous
memory of a given size?
Bitmap Implementation
00000000
00001000
00002000
00003000
00004000
00005000
00006000
00007000
00008000
00009000
0000a000
0000b000
0000c000
0000d000
0000e000
0000f000
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
00010000
00011000
00012000
00013000
00014000
00015000
00016000
00017000
00018000
00019000
0001a000
0001b000
0001c000
0001d000
0001e000
0001f000
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
















00070000
00071000
00072000
00073000
00074000
00075000
00076000
00077000
00078000
00079000
0007a000
0007b000
0007c000
0007d000
0007e000
0007f000
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
4K
2i1
Buddy Systems
2i
2i1

Compromise between fixed and variable partitions

Fixed number of possible hole sizes; typically, 2i.
–
Each hole of size 2i can be divided (equally) into 2
buddies of size 2i1.
–
Two buddies can be combined into the original hole of
size 2i.

Track holes by size on separate lists
–
List entries for holes of sizes 20, 21, …, 2m.
Buddy Systems

Compromise
between fixed and variable partitions
2m

. number of possible hole sizes; typically, 2i.
Fixed
.
.
–
22
21
–
20

Each hole of size 2i can be divided (equally) into 2
buddies of size 2i1.
Two buddies can be combined into the original hole of
size 2i.
Track holes by size on separate lists
–
List entries for holes of sizes 20, 21, …, 2m.
Buddy Systems
2m
.
.
.
22
21
20

When n bytes requested, find smallest i so that n  2i
–
–
If hole of this size available, allocate it;
otherwise, consider larger holes.




Recursively split each hole into two buddies
until smallest adequate hole is created
Allocate it and place other holes on appropriate lists
On release, recursively coalesce buddies
–
Buddy searching for coalescing can be inefficient
Example
Hole Sizes: 1, 2, 4, 8, 16
3 blocks allocated & 3 holes left
void p=malloc(1*blocksize);
free(12*blocksize);
Operating Systems Principles
Memory Management
Lecture 7: Physical Memory
Allocation Strategies for
Variable Partitions
Allocation Strategies

Problem:
Given a request for n bytes, find hole ≥ n

Goal:
–
Maximize memory utilization
(Minimize “external fragmentation”)
–
Minimize search time
Common Allocation Strategies

First-fit:
–
–
–

Next-fit:
–
–

Rotating-first-fit (Resume search)
Improves distribution of holes
Best-fit:
–
–

Always start from the beginning of free-list
Simplest
Generally the best choice
Closest fit
Avoid breaking up large holes.
Worst-fit:
–
–
Largest fit
Avoid leaving tiny hole fragments
What measurement could be used?
Measure of Memory Fragmentation
What measurement could be used?
m: #blocks occupied
n: #holes
Measure of Memory Fragmentation
n 1

m 4
n 2

m 4
n 3

m 4
n 5

m 4
What measurement could be used?
m: #blocks occupied
n: #holes
Measure of Memory Fragmentation
n
 ? at equilibrium.
m
n 1

m 4
n 2

m 4
n 3

m 4
n 5

m 4
What measurement could be used?
m: #blocks occupied
n: #holes
Measure of Memory Fragmentation
Increase one
hole on release.
#holes unchanged
on release
Decrease one
hole on release.
Four types of occupied memory blocks.
What measurement could be used?
m: #blocks occupied
n: #holes
Measure of Memory Fragmentation
Let a, b, c, d be the average number of occupied blocks of each type in
memory during equilibrium.
Fact: b = c
Increase one
hole on release.
#holes unchanged
on release
m  a bc  d
2d  b  c
n
 d b  d c
2
Decrease one
hole on release.
m  a bc  d
n  d b  d c
Measure of Memory Fragmentation
Increase one
hole on release.
#holes unchanged
on release
Decrease one
hole on release.
a
P(increase one hole)  P(release) 
m
d
P(decrease one hole)  P(release)   P(request)  (1  p)
m
m  a bc  d
n  d b  d c
Measure of Memory Fragmentation
Increase one
hole on release.
p: The probability that the
request memory size
doesn’t match any hole size.
Fact: p  1.
#holes unchanged
on release
Decrease one
hole on release.
a
P(increase one hole)  P(release) 
m
d
P(decrease one hole)  P(release)   P(request)  (1  p)
m
m  a bc  d
n  d b  d c
Measure of Memory Fragmentation
In equilibrium, P(increase one hole)  P(decrease one hole)
P(request)  P(release)
a d
  (1  p )
m m
a  d  (1  p)m
m  d  (1  p)m  b  c  d  (1  p)m  2n
a
P(increase one hole)  P(release) 
m
d
P(decrease one hole)  P(release)   P(request)  (1  p)
m
In Equilibrium, of the total number of occupied
blocks and holes, 1/3 are holes.
Measure of Memory Fragmentation
In equilibrium, P(increase one hole)  P(decrease one hole)
P(request)  P(release)
a d
  (1  p )
m m
a  d  (1  p)m
m  d  (1  p)m  b  c  d  (1  p)m  2n
n  0.5 pm  0.5m
n
 0.5 p  0.5
m
50% rule (Knuth 1968)
In Equilibrium, of the total number of occupied
blocks and holes, 1/3 are holes.
Measure of Memory Utilization
In equilibrium, P(increase one hole)  P(decrease one hole)
P(request)  P(release)
a d
  (1  p )
m m
a  d  (1  p)m
m  d  (1  p)m  b  c  d  (1  p)m  2n
n  0.5 pm  0.5m
n
 0.5 p  0.5
m
50% rule (Knuth 1968)
n  0.5 pm  0.5m
Measure of Memory Utilization
The sum of hole sizes
nh
f 

Memory size (M )
nh  mb
0.5mkb
k


0.5mkb  mb k  2
Assume b: average block size
h: average hole size
h
k
b
Measure of Memory Utilization
k
The sum of hole sizes

f 
k2
Memory size (M )
1
f  if k  1
3
50% rule (Knuth 1968)
Assume b: average block size
h: average hole size
h
k
b
Measure of Memory Utilization
k
The sum of hole sizes

f 
k2
Memory size (M )
Assume b: average block size
h: average hole size
h
k
b
How to know the value of k?
Measure of Memory Utilization
k
The sum of hole sizes

f 
k2
Memory size (M )


Simulations by Knuth (1968) provide an answer.
k depends on the ratio of b/M, e.g.,
b  M/10, k = 0.22  f  0.1
b  M/3, k = 2  f  0.5
Assume b: average block size
h: average hole size
h
k
b
Measure of Memory Utilization
k
The sum of hole sizes

f 
k2
Memory size (M )
M
b
Conclusion:
must be large relative to ,
otherwise much of main memory will remain unused.
Assume b: average block size
h: average hole size
h
k
b
Operating Systems Principles
Memory Management
Lecture 7: Physical Memory
Dealing with
Insufficient Memory
Managing Insufficient Memory

What to be done?
–
–
–
when the total size of free memory is large
enough while the memory requirement of a
process exceeds the size of the largest
partition
when new process arrives with insufficient
free memory?
When the memory requirement is larger than
the physical memory size.
Dealing with Insufficient Memory

Memory compaction
–

Swapping
–
–

How much and what to move?
Temporarily move process to disk
Requires dynamic relocation
Overlays
–
–
Allow programs larger than physical memory
Programs loaded as needed according to calling
structure.
Request for a memory block of size 10.
Memory Compaction
Initial
Complete
Compaction
Partial
Compaction
Minimal data
Movement
What are needed to be swapped out?
• Code?
Swapping

• Data?
More efficient than memory compaction.
–
–
–
–
Memory compaction may fail to create a large enough hole.
Effect only small number of processes each time, thus
requiring fewer memory accesses.
Swapping can be overlapped with process execution.
Swapping can be used with both fixed and variable size
partition, whereas memory compaction is applicable only
for variable size partition.
Overlaps


Allow programs large than physical memory
Programs loaded as needed, according to calling
structure.
A
A
k1
B
B
C
D
E
Overlaps


Allow programs large than physical memory
Programs loaded as needed, according to calling
structure.
A
A
k1
B
B
C
C
k2
D
E
D
Overlaps


Allow programs large than physical memory
Programs loaded as needed, according to calling
structure.
A
A
k1
B
B
C
C
k2
D
E
D
E
Overlaps


Allow programs large than physical memory
Programs loaded as needed, according to calling
structure.
A
A
A
A
B
C
B
C
D
E
k1
B
C
k2
D
E