Sharing Main Memory, Segmentation, Simple Paging
1
Reading assignment
Dinosaur Chapter 8
Comet Chapter 13, 15, 16
2
12
Connecting the dots
main.o math.o
linker
main.c math.c
compiler
a.out
memory management
loader
Load a.out to mem Manage mem for proc
Instruction arch execution
3
The big picture
A program needs address space for
text seg, data seg, and (hypothetical) heap, stack
A running process needs phy. memory for text seg, data seg, heap, stack
But no way of knowing where in phy mem at Programming time, compile time, linking time
Best way out?
Make agreement to divide responsibility
Assume address starts at 0 at prog/compile/link time OS needs to work hard at loading/runing time
34
Connecting the dots
main.o math.o
main.c math.c
compiler
a.out
memory management
loader
Load a.out to mem Manage mem for proc
Logical memory
linker
OS
Logical memory & Physical memory
Instruction arch execution
1. Simple uniprogramming: Single segment (code, data, stack heap) per process
Physical memory
OS
Segment 1 address 0
6
56
2. Simple multiprogramming: Single segment per process, static relocation
OS
Segment 2 Segment 1
7
Simple multiprogramming: Single segment per process, static relocation
four drawbacks
1. No protection
2. Low utilization — Cannot relocate dynamically
Binary is fixed (after loading); otherwise have to fix pointers (awful)
Cannot do anything about memory holes
3. No sharing — Single segment per process
Cannot share part of process address space (e.g. text) 4. Entire address space needs to fit in mem
Need to swap whole, very expensive!
8
78
3. Dynamic memory relocation
Instead of changing the address of a program before it’s loaded, change the address dynamically during every reference
Under dynamic relocation, each program-
generated address (called a logical address or virtual address) is translated in hardware to a physical or real address
Can this be done in software?
9
Translation overview
CPU
virtual address
physical address
Actual translation process is usually performed by hardware
Translation table is set up
by software
CPU view
what program sees, virtual addresses
Translation
Memory view
physical memory
addresses (semantics?) IO view
Physical memory
I/O device
10
9 10
3.1 Base and bound
bound
virtual address
>
error
Built in Cray-1 (1976) A program can only
access physical memory in
[base, base+bound]
On a context switch: save/restore base, bound registers
+
base
physical address
Pros:
simple, fast translation, cheap
Can relocate segment 11
3.1 Base and bound
bound
virtual address
>
The essence:
A level of (static) indirection
Phy. Addr = Vir. Addr + base
error
+
base
physical address
12
11 12
3.1 Base and bound
bound
> +
error
Cons:
Only one segment per
process
How can two processes share code while keeping private data areas (shared editors)?
Can it be done safely
with a single-segment scheme?
virtual address
base
physical address
13
What have we solved?
four drawbacks
1. No protection
2. Low utilization — Cannot relocate dynamically
Cannot do anything about holes
3. No sharing — Single segment per process
Cannot share part of process address space (e.g. text)
4. Entire address space needs to fit in mem Need to swap whole, very expensive!
14
13 14
3.2 Multiple Segments
Virtual address
+
physical address
>
error
Have a table of (seg, size)
Further protection: each entry has
(nil, read, write, exec)
On a context switch: save/restore the table (or a pointer to the table) in kernel memory
15
segment
offset
Seg base size .
How does this allow two processes to share code segment?
16
15 16
Segmentation example
text segment [0x0000, 0x04B0]
foo:
019A: LD R1, 15DC 01C2: jmp 01F4
bar procedure 0320: bar:
Data segment [0x1000, 0x16A0]
15DC: _Y:
01E0: call 01F4: X:
0320
Segment Base Bounds
0 4000 4B0
1 06A0 23000FFF 2 3 — —
Where is 01F4 in physical memory? Where is 15DC in physical memory?
A virtual address 12 bits
RW 10 11 11 00
Seg
Offset with the seg
17
Pros/cons of segmentation
Pros:
Process can be split among several segments
Allows sharing
Segments can be assigned, moved, or swapped
independently Cons:
External fragmentation: many holes in physical memory
Also happens in base and bound scheme
18
17 18
Simple multiprogramming: Single segment per process, static relocation
OS
Segment 2
Segment 3
Segment 4?
External fragmentation
19
What fundamentally causes external fragmentation?
1. Segments of many different sizes
2. Each has to be allocated contiguously
20
19 20
Dynamic memory allocation problem
Problem: external fragmentation
How much can a smart allocator help?
The allocator maintains a free list of holes
Allocation algorithms differ in how to allocate from the free list
21
Break
You’re standing on the surface of the Earth. You walk one mile south, one mile west, and one mile north. You end up exactly where you started. Where are you?
Hint: more than one correct answer. Can you get them all?
22
21 22
Dynamic allocation algorithms
Best fit: allocate the smallest chunk big enough First fit: allocate the first chunk big enough
Is best fit necessarily better than first fit?
Example: 2 free blocks of size 20 and 15
If allocation ops are 10 then 20, which one wins? If ops are 8, 12, then 12, which one wins?
20
15
23
Dynamic allocation algorithms
Analysis shows
First fit tends to leave average-size holes
Best fit tends to leave some very large holes, very small holes
Knuth claims that if storage is close to running out, it will run out regardless of which scheme is used
Pick the easiest or most efficient (e.g. first fit)
24
23 24
Segmentation: OS implementation
Keep segment table in PCB
When creating process, allocate space for segments,
fill in PCB bases/bounds
When process dies, return physical space used by segments to free pool
Context switch?
Saves old segment table / Loads new segment table What about context switch of threads?
True-or-false: CS between threads of same process cheaper than CS between processes 25
[lec2] Kernel data structure:
Process Control Block
(Process Table)
Process management info
State (ready, running, blocked)
PC & Registers, parents, etc
CPU scheduling info (priorities, etc.)
Memory management info
Segments, page table, stats, etc
I/O and file management
Communication ports, directories, file descriptors, etc. 26
25 26
Managing segments (cont)
To enlarge a segment:
See if space above segment is free. If so, just update the bound and use that space
Or, move this segment to disk and bring it back into a larger hole (or maybe just copy it to a large hole)
27
Managing segments (cont)
When there is no space to allocate a new segment: Compact memory – how?
28
27 28
Summary: Evolution of Memory Management (so far)
Scheme
Simple uniprogramming
Simple multiprogramming
Base & Bound
Multiple segments
How
1 segment loaded to starting address 0
1 segment relocated at loading time
Dynamic mem relocation at runtime
Dynamic mem relocation at runtime
Pros
Simple
Simple,
Multiple processes
Simple hardware, Multiple processes Protection
Sharing, Protection, multi segs/process
Cons
1 process
1 segment No protection
1 segment/process No protection External frag.
1 segment/process, External frag.
More hardware, External frag.
29
What fundamentally causes external fragmentation?
Segments of many different sizes
Each has to be allocated contiguously
“Million-dollar” question:
Physical memory is precious.
Can we limit the waste to a single hole of X bytes?
30
29 30
Virtual pages / physical pages
Virtual address
. . . .
Virtual pages
physical pages
Physical memory
31
Paging
Goal:
to make allocation and swapping easier (time) to reduce memory fragmentation (space)
Key idea:
Make all chunks of memory the same size, called pages
Implementation:
For each process, a page table defines the base address of each of that process’ pages along with existence and read/write bits
Translation? 32
31 32
Translation overview
CPU
virtual address
physical address
Actual translation process is usually performed by hardware
Translation table is set up
by software
CPU view
what program sees, virtual addresses
Translation
Memory view
physical memory
addresses (semantics?) IO view
Physical memory
I/O device
33
Paging
Virtual address
Page table
Physical address
> error
Context switch
similar to the segmentation scheme
Pros:
easy to allocate memory
easy to swap easy to share
page table size
VPage #
offset
PPage# … . …
. PPage# …
PPage #
offset
34
33 34
Deek thinking:
Paging implementation
Translation: table lookup and bit substitution
Why is this possible?
Why cannot we do the same in segmentation?
Virtual address
error
35
offset >
physical address
segment
Seg addr size .
+
How many PTEs do we need? (assume page size is 4096 bytes)
Worst case for 32-bit address machine? What about 64-bit address machine?
36
35 36
Paging implementation – how does it really work?
Virtual address
Page table PPage# …
. …
. PPage# …
Physical address
Where to store page table? error How to use MMU?
page table size
VPage #
offset
>
Even small page tables too large to load into MMU
Page tables kept in mem and MMU only has their base addresses
What does MMU have to do?
Page size?
Small page -> big table
32-bit with 4k pages
Large page ->small table but large internal fragmentation 37
PPage #
offset
Paging vs. segmentation
Segmentation:
– External fragmentation
– Complicated allocation, swapping + Small segmentation table
Paging
– Internal fragmentation
+ Easy allocation, swapping – Large page table
38
37 38
Deep thinking
Why does the page table we talked about so far have to be contiguous in the physical memory?
Why did a segment have to be contiguous in memory?
For a 4GB virtual address space, we just need 1M PTE (~4MB), what is the big deal?
My PC has 2GB, why do we need PTEs for the entire 4GB address space?
39
39