Transcript holes

Operating Systems
Memory management
Memory Management
List of Topics
1. Memory Management
2. Memory In Systems Design
3. Binding Times
4. Introduction to Memory Management
5. Raw Memory Model
6. Single User Contiguous Memory
7. Relocation - Why and How
8. Overlay Management
Topics (continued)
9. Protection
10. Fixed Partitions
11. Nonuniform Sized Fixed Partitions
12. Uniformly Sized Fixed Partitions
13. Simple Paging
14. Benefits of Simple Paging
15. Page Tables
16. Translation Lookaside Buffers
17. Hierarchical Address Caching
Topics (continued)
18. Dynamic Partitions
19. Fragmentation
20. Internal Fragmentation
21. External Fragmentation
22. Coalescing Holes
23. Compaction
24. Dynamic Partition Placement
25. Simple Segmentation
26. Memory Layout of A C Program
Topics (continued)
27. malloc
28. sbrk
29. Memory Hierarchy
Memory In Systems design
CPU
memory
I/O
System
Figure 1: memory Connects
CPU and Peripherals
Binding Times
source
program
compiler or
assembler
object
model
compile
time
Other
object
modules
linkage
editor
load
module
system
library
loader
load
time
dynamically
loaded system
library
in-memory
binary
memory
image
execution
time
(run time)
Introduction to Memory Management
Memory management issues:
1. Relocation
2. Protection
3. Sharing
4. Logical Organization
5. Physical Organization
Consider a series of solutions starting
with the most primitive first
Raw Memory Model
The raw memory provides no services
and gives the programmer complete
control.
0
Figure 3:
Raw Machine
Model
1 MB
Single User Contiguous Memory
Primitive operating systems (such as MSDOS and CP/M) provide some interfaces
to the hardware but not much else in the
way of services.
Single User Contiguous Memory
(continued)
0
Monitor
fence register
User
Figure 4: Single User
Contiguous Memory
32K
Relocation - Why and How
Relocation refers to the ability to store a
program at an arbitrary base memory
address.
Actual memory locations have physical
or absolute addresses, user program's
access these locations using logical
addresses.
Relocation - Why and How
(continued)
Base
register
CPU
Logical
address
346
14000
+
Figure 5:
Address Translation
Physical
address
14346
memory
Overlay Management
Overlays have gone out of fashion with
cheaper memory, users (and compilers)
determine which code to swap in and out.
Figure 6:
Overlay
Management
Example [2]
70K pass 1
symbol
table
20K
common
routines
30K
overlay
driver
10K
pass 2 80K
Protection
It is undesirable to permit user programs
(accidentally or intentionally) to accesses
memory outside of their partition.
Protection (continued)
0
Monitor
fence register
Figure 7:
Protection
in Resident
Monitor
Model
User
32K
Fixed Partitions
Fixed partitioning refers to memory being
split into contiguous non overlapping
regions of precomputed sizes.
Fixed sized partitions make the selection
of a partition for a job easy.
Nonuniform Sized Fixed Partitions
Fixed Partitions may have differing sizes.
Figure 8:
Nonuniform
fixed
Partitions [3]
New
Process
Operating
system
Uniformly Sized Fixed Partitions
Memory is frequently partitioned into
uniformly sized regions.
Figure 9:
Uniform
Fixed Partition
Allocation [3]
Operating
system
512 K
512 K
512 K
512 K
512 K
512 K
512 K
512 K
Simple Paging
Paging provides relocation, and splits
memory into fixed length partitions
called frames.
0
Page frame 0
p-1
p
Page frame 1
2p-1
2p
Page frame 2
3p-1
3p
Page frame 3
4p-1
Figure 10:
Simple
Paging
[1]
4p
5p-1
5p
6p-1
6p
Page frame 4
Page frame 5
Figure 10:
Simple
Paging
Page frame 6
(continued)
[1]
7p-1
7p
Page frame 7
8p-1
Page
frame
number
Page
frame
size
0
1
2
3
4
5
6
7
p
p
p
p
p
p
p
p
Range of real
storage
addresses
0
p
2p
3p
4p
5p
6p
7p
p-1
2p-1
3p-1
4p-1
5p-1
6p-1
7p-1
8p-1
Benefits of Simple Paging
Simple paging allows discontiguous
storage for memory objects exceeding
the page frame size.
..
.
Contiguous
virtual
storage
locations
..
.
Virtual
memory
Address
mapping
mechanism
Real
storage
Page Tables
One simple mechanism is to allocate
some real memory space for a table, and
hash page addresses using the high
order address bits as pointers into the
page table. There are 2 real memory
accesses per virtual memory access.
Page Tables (continued)
b
b
Page # Displacement
p
b+p
b
p
d
address
} Virtual
v=(p,d)
Page
Map Table
p
p1
p1
Real
d
}address
Translation Lookaside Buffers
Translation lookaside buffers (TLB)
eliminate one physical memory reference
using special associative memory, which
addressed by its contents in O(1) parallel
search time.
Associative Memory Lookup
Page #
Displacement
d
p
Virtual
} address
V=(p,d)
Associative map
p
p1
p1
Frame #
d
Real
} Address r
Displacement
Hierarchical Address Caching
Rather than placing all addresses in the
TLB recently/frequently used addresses
are stored in associative memory, with
misses being serviced by the page table.
Hierarchical Address Caching (continued)
Page table
origin register
Virtual address v=(p,d)
Displacement
Page #
p
Address of
Page table b
+
Try
this
first
p
p1
Performed
only if no
match in
associative
map b+p
Only if no
match in
associative
map
d
Partial associative
Map (most
active pages
p p1 only
Only if match
in associative
map
Frame
Displacement
# p1
d
Real address
Direct map (all pages)
Dynamic Partitions
Dynamically partitioned memory allows
placement of relocatable code in variable
size contigous memory regions.
Dynamic Partitions (continued)
user needs
I
H
G
F
E
D
C
B
A
9K.
18K.
11K.
32K.
14K.
25K.
10K.
20K.
15K.
Operating Operating Operating Operating
system
system
system
system
User
A 15K
User
A 15K
User
B 20K
User
A 15K
User
B 20K
User
C 10K
User
A 15K
User
B 20K
User
C 10K
User
D 25K
Free
Free
Free
Free
Fragmentation
Fragmentation makes available memory
useless by breaking it into discontiguous
pieces too small to use.
Fragmentation (continued)
There are two categories of memory
fragmentation:
1. Internal Fragmentation --- A fixed partition
contains more memory than required by the
user, and some is wasted.
2. External Fragmentation --- Results from the
holes left by dynamic partitions.
Internal Fragmentation
Internal fragmentation occurs when fixed
size partitions are too large.
478
000001 01110111110
Internal
fragmentation
Page 0
Page 1
Page 2
Logical Address
Page#=1,Offset=478
Figure 16:
Internal
Fragmentation
[3]
External Fragmentation
External fragmentation happens when
dynamic partitions are released. The
fragments are frequently called holes.
operating
system
User A
User B
User C
operating
system
User A
User B
finishes
and frees Hole
its
User C
storage.
User D
User D
User E
User E
Hole
Hole
operating
system
User A
Hole
User D
finishes
and
frees its
storage.
User C
Hole
User E
Hole
Coalescing Holes
Adjacent holes in dynamic partitions
should be coalesced into a single larger
hole.
operating
system
operating
system
operating
system
other
users
other
users
other
users
2K Hole User A
finishes
and
5K user A
frees its
storage
other
users
Operating
system
combines
2K Hole adjacent
7K Hole
5K Hole
other
users
holes to
form a
single
larger
hole.
other
users
Compaction
If the amount of memory available in the
holes is large enough to service a
request, the holes may made contiguous
by compacting storage.
operating
systems
operating
systems
In use
In use
Free
In use
In use
In use
Free
In use
Free
Free
Operating
system places
all “in use”
blocks together
leaving free
storage as a
single, large
hole.
Dynamic Partition Placement
(a) First-Fit Strategy
Place job in first storage hole on free
storage place list in which it will fit
0
(kept in storage address order,
or something in random order.)
a
Operating
systems
16K hole
b
c
Free Storage List
Start
Length
Address
Request
for 13K
14K hole
d
e
a
c
16K
14K
f
e
5K
g
g
30K
In use
In use
5K hole
In use
..
.
30K hole
h
(b) Best-Fit Strategy
Place job in the smallest possible hole
in which it will fit.
0
(Kept in ascending order by
hole size.)
a
16K hole
b
c
Free Storage List
Start
Address
Request
for 13K
Length
d
e
5K
14K
f
a
16K
g
30K
In use
14K hole
e
c
g
Operating
systems
In use
5K hole
In use
..
.
30K hole
h
(c) Worst-Fit Strategy
Place job in the largest possible hole in
which it will fit.
0
(Kept in descending order by
hole size.)
a
16K hole
b
c
Free Storage List
Start
Address
Request
for 13K
Length
d
e
30K
16K
f
c
14K
g
5K
In use
14K hole
g
a
e
Operating
systems
In use
5K hole
In use
..
.
30K hole
h
Simple Segmentation
Segmentation provides relocation, and
supports contiguous variable length
partitions.
Segmentation often provides
protection (counterexample Intel 8086).
limit
CPU
Logical
address
<
base
yes
no
Trap; address error
+
memory
Memory Layout of A C Programs
Traditional Unix/C memory images of
programs use segments.
high
address
stack
Command-line
arguments and
environment
variables
heap
low
address
uninitialized data
(bss)
initialized to
zero by exec
Initialized data
read from
program file
by exec
text
malloc
Programmers often want to allocate data
objects which persist beyond the
function call creating them (e.g.
constructors in OOP).
In C and C++ the malloc operator
maintains a linked list of data objects, in
the user program's Data segment (on the
Heap).
user data
In Use List
user data
user data
Free List
user data
Key
user data
Memory
management
Information
user data
sbrk
A user program can exhaust its default
heap space allocation.
The Unix sbrk system call increases data
segment allocation at run time.
application
code
user
process
Memory allocation
function malloc
sbrk
system call
kernel
Memory Hierarchy
Users want to:
1. Increase their address
space, using slow cheaper memory to
extend their more expensive faster
memory.
2. Increase the speed at which they can
the extended memory by using small
amounts of expensive fast memory.
Memory Hierarchy
Registers
Cache
Main Memory
Magnetic Disk (Cache)
Backups
Optical Juke Box
Remote Access