VIRTUALIZATION: CPU TO MEMORY
Andrea Arpaci-Dusseau CS 537, Fall 2019
ADMINISTRIVIA
– Project 1 Due Last Night
– Project 2 Available: Due Monday
– Discussion section: xv6 code walk through! – Homeworks:
– Process(DueThursday)
– SchedulingandMLFQ(DueTuesday)
AGENDA / LEARNING OUTCOMES
CPU virtualization Process Creation MLFQ scheduler
Memory virtualization
Why do we need memory virtualization?
How to virtualize memory? Static, dynamic, base+bounds
CPU VIRTUALIZATION
New Topic: Process Creation
Two ways to create a process
– Option 1: Build a new empty process from scratch
– Option 2: Copy an existing process and change it appropriately
Option 1: New Process
• Option 1: Create new process with specified executable
• Steps
– Loadspecifiedcodeanddataintomemory; Create empty call stack
– CreateandinitializePCB(makelooklikecontext-switch)
– Putprocessonreadylist
• Advantages: No wasted work
• Disadvantages:
Difficult to setup process and to express all possible options
– Processpermissions,wheretowriteI/O,environmentvariables
– Example: WindowsNT has call with 10 arguments
Option 2: Clone and Change
Option 2: Clone existing process and change as needed
• Example: Unix fork() and exec()
– Fork(): Clones calling process
– Exec(char *file): Overlays file image on calling process
• Fork()
– Stop current process and save its state – Make copy of code, data, stack, and PCB – Add new PCB to ready list
– Any changes needed to child process?
• Exec(char *file)
– Replace current data and code segments with those in specified file
• Advantages: Flexible, clean, simple
• Disadvantages:
Wasteful to perform copy and then overwrite of memory
Unix Shells
while (1) {
char *cmd = getcmd();
int retval = fork();
if (retval == 0) {
// This is the child process
// Setup the child’s process environment here
// E.g., where is standard I/O, how to handle signals? exec(cmd);
// exec does not return if it succeeds
printf(“ERROR: Could not execute %s\n”, cmd); exit(1);
} else {
// This is the parent process; Wait for child to finish int pid = retval;
wait(pid);
} }
Stdin and stdout redirection with file descriptors
int
fd1 = open(“
fd table
0 1 2 3 4 5
stdin stdout stderr
fds
file.txt
”); // returns
3
inode
File redirection? ls > newfile.txt Close(stdout) Open(“newfile.txt”)
fprintf(stdout,
“where do I show up?”);
offset = 0 inode =
location = … size = …
Scheduling Policy: Review
Workload
A 40 B 20 C 5 10
Schedulers: FIFO
SJF
S TCF RR
Timelines
ABCABCABABAAAA
0 20 40 60 80 RR
BCB A
0 20 40 60 80 STCF
B C A
0 20 40 60 80
SJF
A BC
0 20 40 60 80 FIFO
JOB
arrival
Scheduling Policy: Review
0
0
run
MLFQ EXAMPLE
[High Priority] Q8 AB Q7
Q6
Q5
Q4 C Q3
Q2
[Low Priority] Q1 D
Rules for MLFQ
Rule 1: If priority(A) > Priority(B)
A runs
Rule 2: If priority(A) == Priority(B), A & B run in RR
Rule 3: Processes start at top priority
Rule 4: If job uses whole slice, demote process.
If not stay at level
MLFQ with starvation mechanism
Q2 B
Q2 A Q1
Q1
C A
A
A Q0
Q0
0 50 100 150 20
Canvas Quiz: MLFQ
http: //pages. cs. wisc. edu/~remzi/OS TEP/Homework/homework. html
VIRTUALIZING MEMORY
More Virtualization
1st part of course: Virtualization
Virtual CPU: illusion of private CPU registers – 2 lectures (mechanism + policy)
Virtual RAM: illusion of private memory – 5 lectures
0KB
64KB
Motivation for virtualizing memory
First systems did not virtualize
Uniprogramming: One process runs at a time
Disadvantages?
Only one process ready at a time Process can destroy OS
Operating System (code, data, etc.)
Current Program (code, data, etc.)
max
MULTIPROGRAMMING GOALS
Transparency:
Process is unaware of sharing
Work regardless of number of processes
Protection:
Cannot corrupt or read OS or other process memory
Efficiency:
Do not waste memory (no fragmentation) or slow down processes
Sharing:
Enable sharing between cooperating processes
0KB 1KB 2KB
ABSTRACTION: ADDRESS SPACE
0KB 64KB 128KB 192KB 256KB 320KB 384KB 448KB 512KB
Program Code
Heap
(free)
Stack
Operating System (code, data, etc.)
(free)
Process C (code, data, etc.)
Process B (code, data, etc.)
(free)
Process A (code, data, etc.)
(free)
(free)
15KB
16KB
How can OS provide illusion of private address space to each process?
(it grows upward) the stack segment: contains local variables
arguments to routines, return values, etc.
the code segment: where instructions live
Address space:
the heap segment:
contains malloc’d data
Each process has own set
dynamic data structures
(it grows downward)
of addresses
0KB 1KB 2KB
WHAT IS IN ADDRESS SPACE?
the code segment: where instructions live
the heap segment: contains malloc’d data dynamic data structures (it grows downward)
Program Code
Heap
(free)
Stack
Static: Code and some global variables Dynamic: Stack and Heap
15KB
16KB
(it grows upward) the stack segment: contains local variables
arguments to routines, return values, etc.
Motivation for Dynamic Memory
Why do processes need dynamic allocation of memory?
– Do not know amount of memory needed at compile time
– Must be pessimistic when allocate memory statically
• Allocate enough for worst possible case; Storage is used inefficiently
Recursive procedures
– Do not know how many times procedure will be nested
Complex data structures: lists and trees
– struct my_t *p = (struct my_t *)malloc(sizeof(struct my_t)); Two types of dynamic allocation
– Stack – Heap
alloc(A);
alloc(B);
alloc(C);
free(C);
alloc(D);
free(D);
free(B);
free(A);
allocation
0KB 1KB 2KB
STACK ORGANIZATION
15KB
16KB
containsNlocoal vfariabglems entation! arguments to routines,
Program Code
the code segment: where instructions live
Heap
the heap segment:
contains malloc’d data
(free)
Pointer between allocated and free space Allocate: Increment pointer
Free: Decrement pointer
Memory must be freed in opposite order from
dynamic data structures
(it grows downward)
Stack
(it grows upward) the stack segment:
return values, etc.
main () {
int A = 0;
foo(A);
WHAT GOES ON STACK?
printf(“A: %d\n”, A);
}
void foo (int Z) {
int A = 2;
Z = 5;
printf(“A: %d Z: %d\n”, A, Z);
}
OS uses stack for procedure call frames (local variables and parameters)
HEAP ORGANIZATION
Allocate from any random location: malloc(), new() etc.
• Heap memory consists of allocated and free areas (holes)
• Order of allocation and free is unpredictable
Advantage
– Works for all data structures
16 bytes
24 bytes
12bytes 16 bytes
Free
Alloc
Free
Alloc
Disadvantages
– Allocation can be slow
– Hassmallchunksoffreespace-fragmentation
– Where to allocate 12 bytes? 16 bytes? 24 bytes??
A B
What is OS’s role in managing heap?
– OSgivesbigchunkoffreememorytoprocess;librarymanagesindividualallocations
One-Minute Neighbor Chat
int x;
int main(int argc, char *argv[]) {
Possible segments: static data, code, stack, heap
}
int y;
int *z = malloc(sizeof(int)););
Address
x
main
y
z
Location
Static data
code
stack
stack
*z
heap
#include
int main(int argc, char *argv[]) { int x;
x = x + 3; }
otool -tv demo1.o
(or objdump on Linux)
0x10:
0x13:
0x19:
%rbp is the base pointer:
points to base of current stack frame
MEMORY ACCESS
movl
addl
movl
0x8(%
$0x3, %
%
rbp
), %
edi
edi
edi
, 0x8(%
rbp
)
Two-minute Chat: MEMORY ACCESS
Initial %rip = 0x10 %rbp = 0x200
0x10: movl 0x8(%rbp), %edi 0x13: addl $0x3, %edi 0x19: movl %edi, 0x8(%rbp)
%rbp is the base pointer:
points to base of current stack frame
%rip is instruction pointer (or program counter)
Memory Accesses to what addresses?
How many?
Initial %rip = 0x10 %rbp = 0x200
0x10: movl 0x8(%rbp), %edi 0x13: addl $0x3, %edi 0x19: movl %edi, 0x8(%rbp)
%rbp is the base pointer:
points to base of current stack frame
%rip is instruction pointer (or program counter)
Exec:
Exec:
Exec:
MEMORY ACCESS
Fetch instruction at addr 0x10
load from addr 0x208
Fetch instruction at addr 0x13
no memory access
Fetch instruction at addr 0x19
store to addr 0x208
HOW TO VIRTUALIZE MEMORY
Problem: How to run multiple processes simultaneously? Addresses are “hardcoded” into process binaries
How to avoid collisions?
Possible Solutions for Mechanisms (covered today):
1. Time Sharing
2. Static Relocation
3. Base
4. Base+Bounds
Memory
code data
Program
TIME SHARE MEMORY: EXAMPLE
code data
Program
create
Memory
code data heap
stack
Process 1
Memory
code data
Program
code data heap
stack
Process 1
code data
Program
code data heap
stack
Process 1
create
Memory
code data2 heap2
stack2
Process 2
Memory
code data
Program
code data2 heap2
stack2
Process 2
code data heap
stack
Process 1
Memory
code data
Program
code data2 heap2
stack2
Process 2
code data heap
stack
Process 1
PROBLEMS WITH TIME SHARING?
Ridiculously poor performance
Better Alternative: space sharing!
At same time, space of memory is divided across processes Remainder of solutions all use space sharing
2) Static Relocation
Idea: OS rewrites each program before loading it as a process in memory Each rewrite for different process uses different addresses and pointers Change jumps, loads of static data
• 0x10: • 0x13: • 0x19:
movl
addl
movl
rewrite
0x8(%rbp), %edi $0x3, %edi %edi, 0x8(%rbp)
rewrite
0x1010: movl 0x8(%rbp), %edi 0x1013: addl $0x3, %edi 0x1019: movl %edi, 0x8(%rbp)
0x3010:movl 0x8(%rbp), %edi 0x3013:addl $0x3, %edi 0x3019:movl %edi, 0x8(%rbp)
Static: Layout in Memory
process 1
4 KB
8 KB
12 KB
16 KB
(free)
Program Code Heap
stack
0x1010:movl 0x8(%rbp), %edi 0x1013:addl $0x3, %edi 0x1019:movl %edi, 0x8(%rbp)
(free)
(free)
process 2
Program Code Heap
stack
0x3010:movl 0x8(%rbp), %edi 0x3013:addl $0x3, %edi 0x3019:movl %edi, 0x8(%rbp)
why didn’t OS rewrite stack addr?
(free)
(free)
Static Relocation: Disadvantages
No protection
– Process can destroy OS or other processes – No privacy
Cannot move address space after it has been placed – May not be able to allocate new process
4 KB process 1
8 KB
12 KB process 2
16 KB
(free)
Program Code
stack
Heap
(free)
(free)
Program Code
stack
Heap
(free)
(free)
3) Dynamic Relocation
Goal: Protect processes from one another Requires hardware support
– MemoryManagementUnit(MMU)
MMU dynamically changes process address at every memory reference
– Processgenerateslogicalorvirtualaddresses(intheiraddressspace) – Memoryhardwareusesphysicalorrealaddresses
Process runs here
Logical address
OS can control MMU
MMU
Physical address
CPU
Memory
Hardware Support for Dynamic Relocation
Two operating modes
Privileged (protected, kernel) mode: OS runs
• When enter OS (trap, system calls, interrupts, exceptions)
• Allows privileged instructions to be executed
– Can manipulate contents of MMU
• Allows OS to access all of physical memory
User mode: User processes run
• Performtranslationoflogicaladdresstophysicaladdress
Implementation of Dynamic Relocation: BASE REG
Translation on every memory access of user process
MMU adds base register to logical address to form physical address
MMU
registers
mode no =
user? yes
32 bits
1 bit
base
mode
+ base
logical address
physical address
Dynamic Relocation with Base Register
Translate virtual addresses to physical by adding a fixed offset each time. Store offset in base register
Each process has different value in base register Dynamic relocation by changing value of base register!
Physical memory
0 KB 1 KB 2 KB 3 KB 4 KB 5 KB 6 KB
same code
Virtual
P1: load 100, R1 P2: load 100, R1 P2: load 1000, R1 P1: load 100, R1
P1
P2
VISUAL Example of DYNAMIC RELOCATION: BASE REGISTER
Physical memory
0 KB 1 KB 2 KB 3 KB 4 KB 5 KB 6 KB
base register
Virtual
P1: load 100, R1
P2: load 100, R1 P2: load 1000, R1
P1: load 100, R1
P1
P2
VISUAL Example of DYNAMIC RELOCATION: BASE REGISTER
Quiz: Who Controls the Base Register?
What entity performs translation of addresses with base register? (1) process, (2) OS, or (3) HW
What entity should determine contents and modify the base register? (1) process, (2) OS, or (3) HW
0 KB 1 KB 2 KB 3 KB 4 KB 5 KB 6 KB
Can P2 hurt P1? Can P1 hurt P2?
Virtual
P1: load 100, R1
P2: load 100, R1 P2: load 1000, R1
P1: load 100, R1
P1
P2
How well does dynamic relocation do with base register for protection?
0KB 1 KB 2KB 3 KB 4 KB 5 KB 6 KB
Virtual
P1: load 100, R1
P2: load 100, R1 P2: load 1000, R1 P1: load 100, R1 P1: store 3072, R1
Can P2 hurt P1? Can P1 hurt P2?
Physical
load 1124, R1 load 4196, R1 load 5196, R1 load 2024, R1 store 4096, R1
(3072 + 1024)
P1
P2
How well does dynamic relocation do with base register for protection?
4) Dynamic with Base+Bounds
Idea: limit the address space with a bounds register
Base register: smallest physical addr (or starting location) Bounds register: size of this process’s virtual address space
– Sometimesdefinedaslargestphysicaladdress(base+size) OS kills process if process loads/stores beyond bounds
Implementation of BASE+BOUNDS
Translation on every memory access of user process
• MMU compares logical address to bounds register
if logical address is greater, then generate error
• MMU adds base register to logical address to form physical address
logical address
error
physical address
registers
mode no =
user? yes
32 bits
32 bits
1 bit
base
bounds
mode
yes bounds?
<
no
+ base
0 KB 1 KB
P1
P2
base register 2KB bounds register
3 KB 4 KB 5 KB 6 KB
P1 is running
0 KB 1 KB 2 KB 3 KB 4 KB 5 KB 6 KB
P2 is running
P1
P2
base register bounds register
0 KB 1 KB 2 KB 3 KB 4 KB 5 KB 6 KB
Virtual
P1: load 100, R1
P2: load 100, R1 P2: load 1000, R1 P1: load 100, R1 P1: store 3072, R1
Can P1 hurt P2?
Physical
load 1124, R1 load 4196, R1 load 5196, R1 load 2024, R1
Interrupt OS!
P1
P2
Managing Processes with Base and Bounds
Context-switch: Add base and bounds registers to PCB (process-control-block) Steps
– Changetoprivilegedmode
– Savebaseandboundsregistersofoldprocess – Loadbaseandboundsregistersofnewprocess – Changetousermodeandjumptonewprocess
What if don’t change base and bounds registers when switch?
Protection requirement
• User process cannot change base and bounds registers
• User process cannot change to privileged mode
Threads!
Base and Bounds Advantages
Provides protection (both read and write) across address spaces Supports dynamic relocation
Can place process at different locations initially and also move address spaces
Simple, inexpensive implementation: Few registers, little logic in MMU Fast: Add and compare in parallel
logical phy address add
error
registers
mode no =
user? yes
32 bits
32 bits
1 bit mode
yes bounds?
<
no
base
bounds
+ base
sic res
a s
Base and Bounds DISADVANTAGES
Disadvantages
– Each process must be allocated contiguously in physical memory – Must reserve memory that may not be used by process
– No partial sharing between processes: Cannot share limited parts of address space
0
Code
Heap
Stack
2n-1
Next VM Topics
• Remove those disadvantages, add new ones, fix those... – Segmentation
– Paging
– Segmentation + Paging
– Multi-level Page Tables – TLBs
To Do
- Project 1 Due Last Night
- Project 2 Available: Due Monday
- Discussion section: xv6 code walk through! - Homeworks:
- Process(DueThursday)
- SchedulingandMLFQ(DueTuesday)