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