Transcript Chapter 11

Slide 11-1
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 11
Slide 11-2
Memory
Management
Copyright © 2004 Pearson Education, Inc.
11
Operating Systems: A Modern Perspective, Chapter 11
The External View of the Memory Manager
Application
Program
Memory Mgr
Process Mgr
File Mgr
UNIX
Device Mgr
VirtualAlloc()
VMQuery()
VirtualLock() VirtualFree()
ZeroMemory()
Memory Mgr
Process Mgr
Device Mgr
File Mgr
exec()
shmalloc()
sbrk()
getrlimit()
Windows
Hardware
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 11
Slide 11-3
Memory Manager
Slide 11-4
• Requirements
– Minimize executable memory access time
– Maximize executable memory size
– Executable memory must be cost-effective
• Today’s memory manager:
– Allocates primary memory to processes
– Maps process address space to primary memory
– Minimizes access time using cost-effective
memory configuration
– May use static or dynamic techniques
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 11
Storage Hierarchies
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 11
Slide 11-5
The Basic Memory Hierarchy
CPU Registers
Primary Memory
(Executable Memory)
e.g. RAM
Secondary Memory
e.g. Disk or Tape
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 11
Slide 11-6
L2 Cache Memory
“Main” Memory
Optical Memory
Operating Systems: A Modern Perspective, Chapter 11
Faster access
Primary
(Executable)
L1 Cache Memory
Sequentially Accessed Memory
Copyright © 2004 Pearson Education, Inc.
Slide 11-7
CPU Registers
Rotating Magnetic Memory
Secondary
Larger storage
Contemporary Memory Hierarchy &
Dynamic Loading
Slide 11-8
Exploiting the Hierarchy
• Upward moves are (usually) copy operations
– Require allocation in upper memory
– Image exists in both higher & lower memories
• Updates are first applied to upper memory
• Downward move is (usually) destructive
– Destroy image in upper memory
– Update image in lower memory
• Place frequently-used info high, infrequently-used
info low in the hierarchy
• Reconfigure as process changes phases
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 11
Slide 11-9
Address Space vs Primary Memory
Process Address Space
Hardware Primary Memory
Mapped to object
other than memory
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 11
Slide 11-10
Creating an Executable Program
Source
code
Library
code
Secondary
memory
C
Reloc
Object
code
Other
objects
Link
Edit
Primary
memory
•Compile time: Translate elements
•Link time: Combine elements
Loader
Process
address
•Load time:
space
•Allocate primary memory
•Adjust addresses in address space
•Copy address space from secondary to primary memory
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 11
A Sample Code Segment
...
static int gVar;
...
int proc_a(int arg){
...
gVar = 7;
put_record(gVar);
...
}
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 11
Slide 11-11
The Relocatable Object module
Slide 11-12
Code Segment
Relative
Address
Generated Code
0000
...
...
Data Segment
0008
entry
proc_a
Relative
...
Address
Generated variable space
...
0220
load
=7, R1
0036
[Space for gVar variable]
0224
store
R1, 0036
...
0228
push
0036
0049
(last location in the data segment)
0232
call
‘put_record’
...
0400
External reference table
...
0404
‘put_record’
0232
...
0500
External definition table
...
0540
‘proc_a’ 0008
...
0600
(symbol table)
...
0799
(last location in the code segment)
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 11
The Absolute Program
Slide 11-13
Code Segment
Relative
Address
Generated Code
0000
(Other modules)
...
1008
entry
proc_a
Data Segment
...
Relative
1220
load
=7, R1
Address
Generated variable space
1224
store
R1, 0136
...
1228
push
1036
0136
[Space for gVar variable]
1232
call
2334
...
...
1000
(last location in the data segment)
1399
(End of proc_a)
...
(Other modules)
2334
entry
put_record
...
2670
(optional symbol table)
...
2999
(last location in the code segment)
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 11
The Program Loaded at Location 4000
Relative
Address
0000
4000
...
5008
...
5036
...
5220
5224
5228
5232
...
5399
...
6334
...
6670
...
6999
7000
...
7136
...
8000
Copyright © 2004 Pearson Education, Inc.
Generated Code
(Other process’s programs)
(Other modules)
entry
proc_a
[Space for gVar variable]
load
store
push
call
=7, R1
R1, 7136
5036
6334
(End of proc_a)
(Other modules)
entry
put_record
(optional symbol table)
(last location in the code segment)
(first location in the data segment)
[Space for gVar variable]
(Other process’s programs)
Operating Systems: A Modern Perspective, Chapter 11
Slide 11-14
Static Memory Allocation
Operating
System
Unused
In Use
Process 3
Process 0
pi
Issue: Need a
mechanism/policy for
loading pi’s address space
into primary memory
Copyright © 2004 Pearson Education, Inc.
Process 2
Process 1
Operating Systems: A Modern Perspective, Chapter 11
Slide 11-15
Slide 11-16
Fixed-Partition Memory Mechanism
Operating
System
pi needs ni units
ni
Region 0
N0
Region 1
N1
Region 2
N2
Region 3
N3
pi
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 11
Fixed-Partition Memory
Best-Fit
Slide 11-17
Operating
System
Internal
Fragmentation
Copyright © 2004 Pearson Education, Inc.
Region 0
N0
Region 1
N1
pi 2
Region
N2
Region 3
N3
•Loader must
adjust every
address in the
absolute module
when placed in
memory
Operating Systems: A Modern Perspective, Chapter 11
Fixed-Partition Memory
Worst-Fit
Operating
System
Copyright © 2004 Pearson Education, Inc.
pi
Region 0
N0
Region 1
N1
Region 2
N2
Region 3
N3
Operating Systems: A Modern Perspective, Chapter 11
Slide 11-18
Fixed-Partition Memory
First-Fit
Operating
System
Copyright © 2004 Pearson Education, Inc.
pi
Region 0
N0
Region 1
N1
Region 2
N2
Region 3
N3
Operating Systems: A Modern Perspective, Chapter 11
Slide 11-19
Fixed-Partition Memory
Next-Fit
Operating
System
Copyright © 2004 Pearson Education, Inc.
Region 0
N0
pi 1
Region
N1
Pi+1
Region 2
N2
Region 3
N3
Operating Systems: A Modern Perspective, Chapter 11
Slide 11-20
Variable Partition Memory
Operating
System
Slide 11-21
Operating
System
Operating
System
Operating
System
Process 0
Process 0
Process 0
Process 1
Process 6
Process 6
Process 2
Process 2
Process 2
Process 3
Process 4
Process 5
Process 5
Process 4
Process 4
•External fragmentation
•Compaction moves program in memory
Loader adjusts every address in
every absolute module when
placed
memory
Operating Systems: A Modern Perspective, Chapter 11
Copyright
© 2004 in
Pearson
Education, Inc.
Cost of Moving Programs
load
R1, 0x02010
3F013010
Program loaded at 0x01000
3F016010
Program loaded at 0x04000
•Must run loader over program again!
Consider dynamic techniques
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 11
Slide 11-22
C-Style Memory Layout
Text Segment
Initialized Part
Data Segment
Uninitialized Part
Data Segment
Heap Storage
Stack Segment
Environment
Variables, …
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 11
Slide 11-23
Program and Process Address Spaces
Process
Address
Space
Absolute
Program
Address
Space
Primary
Memory
0
User
Process
Address
Space
3GB
Supervisor
Process
Address
Space
4GB
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 11
Slide 11-24
Multiprogramming Memory Support
0
Unused
In Use
A
B
Operating
System
R0
Process 1
R1
Process 3
R2
Process 0
R3
Process 1
R4
C
D
E
F
G
H
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 11
Slide 11-25
Dynamic Memory Allocation
• Could use dynamically allocated memory
• Process wants to change the size of its
address space
– Smaller  Creates an external fragment
– Larger  May have to move/relocate the
program
• Allocate “holes” in memory according to
– Best- /Worst- / First- /Next-fit
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 11
Slide 11-26
Slide 11-27
Memory Mgmt Strategies
• Fixed-Partition used only in batch systems
• Variable-Partition used everywhere (except
in virtual memory)
• Swapping systems
– Popularized in timesharing
– Relies on dynamic address relocation
– Now dated
• Dynamic Loading (Virtual Memory)
– Exploit the memory hierarchy
– Paging -- mainstream in contemporary systems
– Segmentation -- the future
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 11
Moving an Executable Image
02000
Executable
Program
Executable
Image
Loader
06000
Loader
Copyright © 2004 Pearson Education, Inc.
Executable
Image
Operating Systems: A Modern Perspective, Chapter 11
Slide 11-28
Dynamic Address Relocation
Slide 11-29
CPU
Relative Address
0x02010
Relocation Register
0x10000
load
R1, 0x02010
+
0x12010
MAR
•Program loaded at 0x10000  Relocation Register = 0x10000
•Program loaded at 0x04000  Relocation Register = 0x04000
We never have to change the load module addresses!
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 11
Multiple Segment
Relocation Registers
Slide 11-30
CPU
Relative Address
+
0x12010
Code Register
Stack Register
Data Register
Copyright © 2004 Pearson Education, Inc.
MAR
Operating Systems: A Modern Perspective, Chapter 11
Slide 11-31
Runtime Bound Checking
CPU
Relative Address
+
Relocation Register
Limit Register
•Bound checking is
inexpensive to add
•Provides excellent memory
protection
Copyright © 2004 Pearson Education, Inc.

<
MAR
Interrupt
Operating Systems: A Modern Perspective, Chapter 11
Slide 11-32
Special Case: Swapping
• Special case of dynamic memory allocation
• Suppose there is high demand for
executable memory
• Equitable policy might be to time-multiplex
processes into the memory (also space-mux)
• Means that process can have its address
space unloaded when it still needs memory
– Usually only happens when it is blocked
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 11
Slide 11-33
Swapping
Image for pi
Swap pi out
Swap pj in
Image for pj
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 11
Sharing a Portion of the Address Space
Slide 11-34
Address Space for Process 1
Process 1
Process 2
Primary Memory
Address Space for Process 2
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 11
Slide 11-35
Figure 11-26: Multiple Segments
Limit
Relocation
Limit
Relocation
Private to
Process 1
CPU Executing
Process 1
Shared
Limit
Relocation
Limit
Relocation
Private to
Process 2
CPU Executing
Process 2
Primary Memory
Copyright © 2004 Pearson Education, Inc.
Operating Systems: A Modern Perspective, Chapter 11