Introduction and Overview
Virtualization:
The CPU
Questions answered in this lecture:
What is a process?
Why is limited direct execution a good approach for virtualizing the CPU?
What execution state must be saved for a process?
What 3 states could a process be in?
CSE 2431
Systems II
Based on slides by Andrea Arpaci-Dusseau, University of Wisconsin
What is a Process?
Process: An execution stream in the context of a process execution state
What is an execution stream?
Stream of executing instructions
Running piece of code
“thread of control”
What is process execution state?
Everything that the running code can affect or be affected by
Registers
General purpose, floating point, status, program counter, stack pointer
Address space
Heap, stack, and code
Open files
Processes vs. Programs
A process is different than a program
Program: Static code and static data
Process: Dynamic instance of code and data
Can have multiple process instances of same program
Can have multiple process instances of the same program
Example: many users can run the Linux program “ls”, with each user running the program as a separate process, at the same time
Process API
In a typical OS, the following interfaces/actions are provided for processes (sometimes different names are used in some OSes):
Create
Destroy
Wait (to wait on another process to finish
running)
Miscellaneous control
Status
Process creation
The OS needs to bring (at least a part of) the program’s code and static data from disk; for the time being, we will pretend that the OS brings all of the process’s code and static data from disk.
Allocate space for a stack segment
Allocate some space for the heap
Set up I/O facilities (In Unix/Linux, e.g., each process has three open file descriptors, by default – more on this later)
Starting the process
Once the process code, memory, stack space, heap space, and I/O have been set up, it is still not actually running
When it is time to run the process, the OS will start the process running at its entry point (the first instruction which executes when the process starts; for example, the first instruction in main() ); the entry point must be stored as part of the executable which runs as the process
We will see more details about how this occurs later
Process states
Ready: everything the process needs to run is in memory, but the process is not executing instructions on the CPU; it is waiting in line to be able to execute instructions on the CPU.
Running: the process is actually executing instructions on the CPU.
Blocked: the process is waiting in line for some event to occur (for example, for the disk drive to do an I/O transfer, or for a lock to be available)
Process Creation
code
static data
Program
CPU
Memory
Process Creation
code
static data
Program
CPU
Memory
code
static data
heap
stack
Process
Processes vs. Threads
A process is different than a thread (more on this distinction later; this is an introduction)
Thread: sometimes called a “Lightweight process” (LWP)
An execution stream that shares an address space (with other threads in the same process)
Can be multiple threads within a single process
Example:
Two (non-interacting) processes examining same memory address 0xffe84264 see different values (i.e., different contents)
Two threads (in the same process) examining memory address 0xffe84264 see same value (i.e., same contents)
Virtualizing the CPU
Goal:
Give each process impression it alone is actively using CPU; for software writers, this greatly simplifies things.
Resources can be shared in time and space
Assume single uniprocessor (i.e., one core)
Time-sharing
(Note: multi-processors with more than one core: advanced issue)
Memory?
Space-sharing (later)
Disk?
Space-sharing (later)
How to Provide Good CPU Performance?
Direct execution
Allow user process to run directly on hardware
OS creates process and transfers control to starting point (i.e., main())
Problems with direct execution?
Process could do something that should not be allowed
Could read/write other processes’ data (disk or memory)
Process could run forever (slow, buggy, or malicious)
OS needs to be able to switch between processes
Process could do something slow (like I/O)
OS wants to use resources efficiently and switch CPU to other process
Solution:
Limited direct execution – OS and hardware maintain some control
LIMITED DIRECT EXECUTION: Problem 1 –
Restricted OPS
How can we ensure user process can’t harm others?
Solution: privilege levels supported by hardware (status bit)
User processes run in user mode/restricted
OS runs in kernel mode/unrestricted mode
Instructions for interacting with devices are restricted
Could have more than two privilege levels (need more than one status bit)
This can be used to support virtual machines, for example
We will suppose just two privilege levels (one status bit)
How can user process access devices (see more details on next slide)?
System calls (call to a function implemented by OS)
Change privilege level through system call (trap)
Transition from user mode to kernel mode
Two kinds of transitions cause CPU to change mode bit from user mode to kernel mode:
Interrupts: raised by devices (such as disk drive) – more details on these later
Exceptions:
Traps: for a trap instruction, the instruction does not execute again after the trap is handled by the OS. This is used for system calls, and also for errors (division by zero, e.g.)
Faults: when an instruction causes a fault, the instruction executes again after the fault is handled by the OS. We will see examples later.
Why THE cpu changes mode from user to kernel
Consider why the CPU makes the transition from user mode to kernel mode
Another alternative: have the kernel (rather than the CPU) change the mode bit from user mode to kernel mode after kernel code starts executing.
Problem?
If the mode bit is set to user mode, and the kernel can change from user mode to kernel mode, user processes would also be able to make this change, and the purpose of the mode bit is defeated!
Transition back to user mode
When the kernel is ready to transition back to user mode, it changes the mode bit to user mode, and at the same time (in the same instruction) puts the address of the next instruction of the user process to run in the PC (program counter)
Now the user process can begin running, or continue running (if it was running before, for example, if it made a system call by executing a trap instruction)
What to limit?
User processes are not allowed to perform:
General memory access
Disk I/O
Special x86 instructions (can only be executed in privileged/unrestricted/kernel mode; for example, changing the address in the PC)
What if process tries to do something restricted?
Problem 2: How to take CPU AWAY?
OS requirements for multiprogramming (or multitasking)
Mechanism
To switch between processes
Policy
To decide which process to schedule when
Separation of policy and mechanism
Reoccuring theme in OS
Policy: Decision-maker to optimize some workload performance metric
Which process when?
Process Scheduler: Future lecture
Mechanism: Low-level code that implements the decision
How?
Process Dispatcher: Today’s lecture
Dispatch Mechanism
OS runs dispatch loop
while (1) {
run process (say, A) for some time-slice
stop process (say, A) and save its context
load context of another process (say, B)
}
Question 1: How does dispatcher gain control?
Question 2: What execution context must be saved and restored?
Context-switch
Q1: How does Dispatcher get CONTROL?
Option 1: Cooperative Multi-tasking
Trust process to relinquish CPU to OS through traps
Examples: System call, page fault (access page not in main memory-more later), or error (illegal instruction or divide by zero)
Provide special yield() system call
Cooperative Approach
P1
yield() call
Cooperative Approach
OS
yield() call
Cooperative Approach
OS
yield() return
Cooperative Approach
P2
yield() return
Cooperative Approach
P2
yield() call
q1: How Does Dispatcher Run?
Problem with cooperative approach?
Disadvantages: Processes can misbehave
By avoiding all traps (performing no I/O, and making no other system calls) can take over entire machine
Only solution: Reboot!
Not done in modern operating systems
Q1: How does Dispatcher run?
Option 2: True Multi-tasking
Guarantee OS can obtain control periodically
Enter OS by enabling periodic alarm clock
Hardware generates timer interrupt (CPU or separate chip)
Example: Every 10ms
User must not be able to mask (disable) timer interrupt
Dispatcher counts interrupts between context switches
Example: Waiting 20 timer ticks between context switches gives 20 X 10 = 200 ms time slice
Common time slices range from 10 ms to 200 ms
Q2: What Context must be Saved?
Dispatcher must preserve context of process when not running
To do context switch save context, that is, process execution state (all registers) of process that was interrupted in process control block (PCB) (or, Process Descriptor)
What information is stored in PCB?
PID
Process state (I.e., running, ready, or blocked)
Execution state (all registers, including PC, stack ptr)
Scheduling priority
Accounting information (parent and child processes)
Credentials (which resources can be accessed, owner)
Pointers to other allocated resources (e.g., open files)
Requires special hardware support
CPU saves process PC and PSR on interrupts or exceptions
Question: Why can’t kernel do this after it starts executing code?
Problem 3:
Slow Ops such as I/O?
When running process performs op that does not use CPU, OS switches to process that needs CPU (policy issues)
OS must track mode of each process:
Running:
On the CPU (only one process on a uniprocessor)
Ready:
Waiting for the CPU
Blocked
Asleep: Waiting for I/O or some other event to complete
Running
Blocked
Ready
Transitions?
Problem 3:
Slow OPS SUCH as I/O?
OS must track every process in system
Each process identified by unique Process ID (PID)
OS maintains queues of all processes
Ready queue: Contains all ready processes
Event queue: One logical queue per event
e.g., disk I/O, and locks
Contains all processes waiting for that event to complete
Next Topic: Policy for determining which ready process to run
Summary
Virtualization:
Context switching gives each process impression it has its own CPU
Direct execution makes processes fast
Limited execution at key points to ensure OS and CPU retain control
Hardware provides a lot of OS support
user vs kernel mode
timer interrupts
automatic register saving (of PC and PSR)
Process Creation
Two ways to create a process
Build a new empty process from scratch
Copy an existing process and change it appropriately
Option 1: New process from scratch
Steps
Load specified code and data into memory;
Create empty call stack
Create and initialize PCB
Put process on ready list
Advantages: No wasted work
Disadvantages: Difficult to setup process correctly and to express all possible options
Process permissions, where to write I/O, environment variables
Example: WindowsNT has call with 10 arguments
Process Creation
Option 2: Clone existing process and change
Example: Unix fork() and exec()
fork() (system call): Clones calling process
exec(char *file) (system call): 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 (there are solutions to this, one of which we will see)
Unix Process Creation
How are Unix shells implemented?
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(NULL);
}
}
/docProps/thumbnail.jpeg