Transcript PPT
Operating Systems Design (CS 423)
Elsa L Gunter
2112 SC, UIUC
http://www.cs.illinois.edu/class/cs423/
Based on slides by Roy Campbell, Sam King, and
Andrew S Tanenbaum
4/7/2016
1
Address Spaces and Memory
Process = one or more threads in an address
space
Thread: stream of execution
Unit of concurrency
Address space: memory space that threads
use
Unit of data
4/7/2016
2
Address Space Abstrac2on
Address space: all the memory data
Hardware interface (physical reality)
Program code, stack, data segment
One memory, small, shared
Application interface (illusion)
Each process has own memory, large
4/7/2016
3
Illusions Provided by Address Apace
Address independence
Protection
Same address in different processes not
conflicting with each other
Eg Same address for stack
One process cannot access the data of another
Secret data, protected code
Virtual memory
64 bit address space, memory many 4 G
4/7/2016
4
Uni‐programming
One process runs at a
time
Always load process
into the same spot
How do you switch
processes?
What abstractions
does this provide?
Problems?
4/7/2016
Operating
System
ROM
User
Memory
5
Multi‐programming
Multi‐programming: more than one process
in memory at a time
Need address translation
Need protection
Address translation
Avoid conflicting addresses
Static: before you execute
Dynamic: during execution, could change
4/7/2016
6
Dynamic translation
Translate every memory reference from
virtual address to physical address
Virtual address: an address used by the user
process to reference a location in memory
Physical address: an address used by the
physical memory
4/7/2016
7
Dynamic Address Translation
User
Translator
Physical
Process
(MMU)
Memory
Virtual Add
Physical Add
Translation enforces protection
Translation enables virtual memory
One process can’t even refer to another process’s address space
A virtual address only needs to be in physical memory when it is
being accessed
Change translations on the fly as different virtual addresses
occupy physical memory
Do you need hardware support?
4/7/2016
8
Address translation
User
Translator
Physical
Process
(MMU)
Memory
Virtual Add
Physical Add
Lots of ways to implement, remember the
big picture
Tradeoffs:
Flexibility (e.g., sharing, growth, virtual memory)
Size of translation data
Speed of translation
4/7/2016
9
Base and Limit
Load each process into
contiguous regions of
physical memory
virtual
mem
lim2
0
If(virt addr > bound){
trap to kern
} else {
phys addr =
virt addr + base
}
base2 + lim2
base2
virtual
mem
lim1
0
4/7/2016
physical
mem
base1 + lim1
base
1
0
10
Base and limit
What must change during a context switch?
Can a process change its own base and
limit?
Can you share memory with another
process?
How does the kernel handle the address
space growing
You are the OS designer, come up with an
algorithm for allowing processes to grow
4/7/2016
11
Memory Allocation in the small
virtual
mem
physical
mem
physical
mem
physical
mem
virtual
mem
virtual
mem
4/7/2016
virtual
mem
?
virtual
mem
12
Memory Management w/ Linked Lists
A
B
8
C
D
16
E
24
F
32
Info for each hole
Both ends:
Size of hole
Bit saying free or allocated
Together
Next and Previous pointers to other holes
Info for each allocated “chunk:
Size and allocation bit, together, on each end
4/7/2016
13
Memory Allocation Algorithms
A
B
C
8
D
E
16
F
24
32
Allocated 2 units:
First fit
A
G
B
C
8
D
E
16
F
24
32
Best fit
A
Worst fit
B
8
A
4/7/2016
C
E
16
B
8
D
C
F
24
D
16
G
G
32
E
24
F
32 14