程序代写代做 data structure compiler kernel algorithm Sharing Main Memory, Segmentation, Simple Paging

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