Operating Systems – CSCI 402
Ch 7: Memory Management
http://merlot.usc.edu/william/usc/
26
321 0
Copyright ý . Systems – CSCI 402
Memory Management
Processes OS File System
kernel text
kernel stack
other stuff
kernel stack
other stuff
Stack
Stack
Challenges
what to do when you run out of space?
protection
321 0
Buffer Cache
Networking
Stack
Physical Memory
27
Copyright ý . Systems – CSCI 402
The Address-Space Concept
Protect processes from one another
Protect the OS from user processes
Provide efficient management of available storage
illusion of large memory
sharing (code, data, communication)
new abstraction (such as pipes, memory-mapped files)
28
321 0
Copyright ý . Systems – CSCI 402
32
Virtual Address
Virtual Address
Who uses virtual address?
user processes
kernel processes
pretty much every piece of software
You would use a virtual address to address any memory location in the 32-bit address space
Anything uses physical address? nothing in OS
well, the hardware uses physical address (and the processor is hardware)
the OS manages the physical address space
physical address
Copyright ý . Cheng
device
Memory
29
321 0
32
Virtual Address
Operating Systems – CSCI 402
Virtual Address
To access a memory location, you need to specify a memory address
in a user process (or even a kernel process), you would use a virtual address to address any memory location in the 32-bit address space
Why would you want to access a memory location?
e.g., to fetch a machine instruction
you need to specify a memory location to fetch from how do you know which memory location to fetch from?
EIP (on an x86 machine), which contains a virtual address
321 0
30
Copyright ý . Cheng
32
Virtual Address
Virtual Address
To access a memory location, you need to specify a memory address
in a user process (or even a kernel process), you would use a virtual address to address any memory location in the 32-bit address space
Why would you want to access a memory location?
e.g., to fetch a machine instruction e.g., to push EAX onto the stack
you need to specify a memory location to store the content of EAX
how do you know which memory location to write to?
ESP, which contains a virtual address
Operating Systems – CSCI 402
31
321 0
Copyright ý . Cheng
32
Virtual Address
Operating Systems – CSCI 402
Virtual Address
To access a memory location, you need to specify a memory address
in a user process (or even a kernel process), you would use a virtual address to address any memory location in the 32-bit address space
Why would you want to access a memory location?
e.g., to fetch a machine instruction
e.g., to push EBP onto the stack
e.g., x = 123, where x is a local variable
you need to specify a memory location to write 123 to how do you know which memory location to wrote to?
EBP, which contains a virtual address
Is there any CPU register that contains a physical address?
321 0
32
Copyright ý . Idea: Address Translation
We want the same virtual address to get “translated” to a different physical address, depending on which process is running
how?
Operating Systems – CSCI 402
low
¡Ö¡Ö
access virtual addr 100
Process A
access virtual addr 100
1200 300
9500 500
321 0
Physical Memory
Process B
Inner Core
V.A=100
P.A.
high
Processor
33
Copyright ý . Idea: Address Translation
One level of indirection with a Memory Management Unit (MMU) don¡¯t address physical memory directly
address out of CPU “inner core” is virtual use a Memory Management Unit (MMU)
virtual address is translated into physical address via MMU physical memory can be located anywhere
Operating Systems – CSCI 402
low
¡Ö¡Ö
access virtual addr 100
Process A
access virtual addr 100
1200 300
9500 500
321 0
Physical Memory
Process B
Inner Core
regs
MMU
V.A
P.A.
high
Processor
34
Copyright ý . Idea: Address Translation
One level of indirection with a Memory Management Unit (MMU) don¡¯t address physical memory directly
address out of CPU “inner core” is virtual use a Memory Management Unit (MMU)
virtual address is translated into physical address via MMU physical memory can be located anywhere
Operating Systems – CSCI 402
low
¡Ö¡Ö
access virtual addr 100
Process A
access virtual addr 100
1200 300
9500 500
321 0
Physical Memory
Process B
Copyright ý . Core
Processor
35
regs
MMU
100
1300
high
Basic Idea: Address Translation
One level of indirection with a Memory Management Unit (MMU) don¡¯t address physical memory directly
address out of CPU “inner core” is virtual use a Memory Management Unit (MMU)
virtual address is translated into physical address via MMU physical memory can be located anywhere
Operating Systems – CSCI 402
low
¡Ö¡Ö
access virtual addr 100
Process A
access virtual addr 100
1200 300
9500 500
321 0
Physical Memory
Process B
Copyright ý . Core
Processor
36
regs
MMU
100
9600
high
Address Translation
Protection/isolation
Illusion of large memory
Sharing
New abstraction (such as memory-mapped files)
low
Operating Systems – CSCI 402
Physical Memory
access virtual addr 100
Process A
access virtual addr 100
Process B
Inner Core
regs
MMU
Processor
321 0
high
37
Copyright ý . Systems – CSCI 402
Memory Fence
fault
100
100
low
Physical Memory
User Area
Inner Core
fense
MMU
OS
In the old days
if a user program tries to access OS area, hardware (very simple MMU) will generate a trap
does not protect user pocesses from each other
high
there¡¯s only one user process anyway Copyright ý . Cheng
321 0
38
Operating Systems – CSCI 402
Memory Fence and Overlays
Overlay
Resident
User Area
What if the user program won¡¯t fit in memory?
use overlays
programmers (not the OS) have to keep track of which overlay is in physical memory and deal with the complexities of managing overlays
321 0
Copyright ý . Cheng
39
Operating Systems – CSCI 402
Base and
low
Physical Memory
access virtual addr 100
Process A
base = 1200 bounds = 300
Process B
base = 9300 bounds = 500
fault
100
cmp
1200
300
9300 500
base
bounds
MMU
bounds register: address space size of the user process
base register: start of physical memory for the user process address relative to the base register
virtual memory reference >= 0 and < bounds, independent of base (this is known as "position independence")
321 0
100+1200
Multiple user processes
¡Ö¡Ö
OS maintains a pair of registers for each user process
high
Copyright ý . Core
40
Operating Systems - CSCI 402
Base and
Physical Memory
fault
100
cmp
low
Process A
base = 1200 bounds = 300
access virtual addr 100
Process B
base = 9300 bounds = 500
100+9300
1200
300
9300 500
Multiple user processes
¡Ö¡Ö
OS maintains a pair of registers for each user process
bounds register: address space size of the user process base register: start of physical memory for the user process
MMU registers are part of the context of a process
in kernel 1, a PCB has something called pagedir (MMU register for x86 CPU uses a different scheme)
321 0
high
41
Copyright ý . Core
base
bounds
MMU
One pair of base and bounds registers per segment code, data, heap, stack, and may be more
e.g., compiler compiles programs into segments
low fault
2200
1000
5800 2600
9000
200 10300
Operating Systems - CSCI 402
Generalization of Base and Bounds: Segmentation
access virtual addr 350
Process A
0 code
200
300 data
data seg 50
9000
200
10300
100
2200
1000
5800
2600
MMU
cmp 50+10300
¡Ö¡Ö
heap stack
Physical Memory
Copyright ý . Cheng
400 600
1600 2000
4600
high
Inner Core
42
321 0
Access control / protection
read-only, read/write
execute virtual addr 150
Process A
0 code
200
300 data
low fault
2200
1000
5800 2600
9000
200 10300
Operating Systems - CSCI 402
Access Control With Segmentation
code seg 150
9000
R O
200
10300
R W
100
2200
R W
1000
5800
R W
2600
MMU
cmp 150+9000
¡Ö¡Ö
heap stack
Physical Memory
Copyright ý . Cheng
400 600
1600 2000
4600
high
Inner Core
43
321 0
Access control / protection
read-only, read/write
write
virtual addr 150
Process A
0 code
200
300 data
fault
low
Operating Systems - CSCI 402
Access Control With Segmentation
code seg 150
2200
1000
5800 2600
9000
200 10300
9000
R O
200
10300
R W
100
2200
R W
1000
5800
R W
2600
MMU
cmp 150+9000
400 600
1600 2000
4600
high
¡Ö¡Ö
heap stack
Physical Memory
Inner Core
44
321 0
Copyright ý . simply setup base and bounds registers to share segments
low
Operating Systems - CSCI 402
Sharing Segments
Shared
9000
R O
200
10300
R W
100
2200
R W
1000
...
MMU
Process A
Process B
9000
R O
200
9000
R O
200
10300
R W
100
7600
R W
300
¡Ö¡Ö
high
Physical
Memory
2200
R W
1000
20500
R W
400
...
...
Copyright ý . Core
45
321 0
Can simply setup base and bounds registers to share segments
low
Operating Systems - CSCI 402
Sharing Segments
Shared
9000
R O
200
7600
R W
300
20500
R W
400
...
MMU
Process A
Process B
9000
R O
200
9000
R O
200
10300
R W
100
7600
R W
300
¡Ö¡Ö
high
Physical
Memory
2200
R W
1000
20500
R W
400
...
...
Copyright ý . Core
46
321 0
Operating Systems - CSCI 402
Segmentation Fault
Segmentation fault
virtual address not within range of any base-bounds registers
access virtual addr 450
Process A
0 code
200
300 data
data seg 150
2200
1000
5800 2600
9000
200 10300
fault
low
9000
R O
200
10300
R W
100
2200
R W
1000
5800
R W
2600
MMU
400 600
1600 2000
4600
high
cmp
¡Ö¡Ö
heap stack
Physical Memory
Inner Core
47
321 0
Copyright ý . Systems - CSCI 402
Segmentation Fault
Segmentation fault
virtual address not within range of any base-bounds registers or access is incompatible
write
virtual addr 150
Process A
0 code
200
300 data
code seg 150
2200
1000
5800 2600
9000
200 10300
fault
low
9000
R O
200
10300
R W
100
2200
R W
1000
5800
R W
2600
MMU
400 600
1600 2000
4600
high
cmp
¡Ö¡Ö
heap stack
Physical Memory
Inner Core
48
321 0
Copyright ý . Cheng
the mmap() system call
can map an entire file (or part of it) into a segment
Operating Systems - CSCI 402
Memory Mapped File
need more pairs of MMU Memory Mapped File registers in hardware
access virtual addr 8178
Process A
400
fault mm file 1 seg 178
low
Inner Core
9000
R O
200
10300
R W
100
...
400
R W
820
MMU
mm file 1
8000 8820
cmp 178+400
9000
200 10300
extra registers
high
Physical Memory
¡Ö¡Ö
321 0
OS
49
Copyright ý . Systems - CSCI 402
Copy-On-Write
Copy-on-write (COW):
set R/O bit for private, R/W memory segment
a process gets a private copy of the segment after a thread in the process performs a write for the first time
low fault
400
2000
9000
R/O
read
virtual addr 312
Process A
0 code
200
300 data
data seg 12
9000
R O
200
2000
R O
100
private
...
MMU
heap stack
this bit often not in MMU
4600
Physical Memory
400 600
1600 2000
high
Inner Core
cmp 12+2000
¡Ö¡Ö
50
321 0
Copyright ý . Systems - CSCI 402
Copy-On-Write
Copy-on-write (COW):
first time write to this segment traps into OS
a process gets a private copy of the segment after a thread in the process performs a write for the first time
R/O
write
virtual addr 312
Process A
0 code
200
300 data
data seg 12
400
2000
9000
fault
low
9000
R O
200
2000
R O
100
private
...
MMU
cmp 12+2000
heap stack
400 600
1600 2000
¡Ö¡Ö
high
Memory
this bit often not in MMU
4600
Physical
Copyright ý . Core
51
321 0
Copy-On-Write
Copy-on-write (COW):
a process gets a private copy of the segment after a thread in the process performs a write for the first time
Operating Systems - CSCI 402
copy
R/O
write
virtual addr 312
Process A
0 code
200
300 data
data seg 12
400 600
2000
9000
fault
low
9000
R O
200
600
R W
100
private
...
MMU
cmp
heap stack
this bit often not in MMU
4600
Physical Memory
400 600
1600 2000
high
¡Ö¡Ö
Copyright ý . Core
52
321 0
Operating Systems - CSCI 402
Copy-On-Write
Copy-on-write (COW):
future write to this segment will not trap into OS
a process gets a private copy of the segment after a thread in the process performs a write for the first time
R/O
write
virtual addr 312
Process A
0 code
200
300 data
data seg 12
400 600
2000
9000
heap stack
this bit often not in MMU
4600
Physical Memory
400 600
1600 2000
high
Inner Core
fault
low
9000
R O
200
600
R W
100
private
...
MMU
cmp
12+600
¡Ö¡Ö
53
321 0
Copyright ý . Cheng