PowerPoint Presentation
Processes
http://xkcd.com/1854/
CMPT 295
Processes
Roadmap
2
car *c = malloc(sizeof(car));
c->miles = 100;
c->gals = 17;
float mpg = get_mpg(c);
free(c);
Car c = new Car();
c.setMiles(100);
c.setGals(17);
float mpg =
c.getMPG();
Java:
C:
Assembly language:
Machine code:
0111010000011000
100011010000010000000010
1000100111000010
110000011111101000011111
Computer system:
OS:
Memory & data
Arrays & structs
Integers & floats
RISC V assembly
Procedures & stacks
Executables
Memory & caches
Processor Pipeline
Performance
Parallelism
CMPT 295
Processes
2
Leading Up to Processes
System Control Flow
Control flow
Exceptional control flow
Asynchronous exceptions (interrupts)
Synchronous exceptions (traps & faults)
3
CMPT 295
Processes
Control Flow
So far: we’ve seen how the flow of control changes as a single program executes
Reality: multiple programs running concurrently
How does control flow across the many components of the system?
In particular: More programs running than CPUs
Exceptional control flow is basic mechanism used for:
Transferring control between processes and OS
Handling I/O and virtual memory within the OS
Implementing multi-process apps like shells and web servers
Implementing concurrency
4
CMPT 295
Processes
4
Control Flow
Processors do only one thing:
From startup to shutdown, a CPU simply reads and executes (interprets) a sequence of instructions, one at a time
This sequence is the CPU’s control flow (or flow of control)
5
instr1
instr2
instr3
…
instrn
Physical control flow
time
CMPT 295
Processes
Altering the Control Flow
Up to now, two ways to change control flow:
Jumps (conditional and unconditional)
Call and return
Both react to changes in program state
Processor also needs to react to changes in system state
Unix/Linux user hits “Ctrl-C” at the keyboard
User clicks on a different application’s window on the screen
Data arrives from a disk or a network adapter
Instruction divides by zero
System timer expires
Can jumps and procedure calls achieve this?
No – the system needs mechanisms for “exceptional” control flow!
6
CMPT 295
Processes
Exceptional Control Flow
Exists at all levels of a computer system
Low level mechanisms
Exceptions
Change in processor’s control flow in response to a system event
(i.e. change in system state, user-generated interrupt)
Implemented using a combination of hardware and OS software
Higher level mechanisms
Process context switch
Implemented by OS software and hardware timer
Signals
Implemented by OS software
We won’t cover these – see CMPT 300
7
CMPT 295
Processes
Exceptions
An exception is transfer of control to the operating system (OS) kernel in response to some event (i.e. change in processor state)
Kernel is the memory-resident part of the OS
Examples: division by 0, page fault, I/O request completes, Ctrl-C
How does the system know where to jump to in the OS?
8
User Code
OS Kernel Code
exception
exception processing by exception handler, then:
return to current_instr,
return to next_instr, OR
abort
current_instr
next_instr
event
CMPT 295
Processes
Exception Table
A jump table for exceptions (also called Interrupt Vector Table)
Each type of event has a unique
exception number
= index into exception table
(a.k.a interrupt vector)
Handler is called each time
exception occurs
9
0
1
2
…
n-1
Exception
Table
code for
exception handler 0
code for
exception handler 1
code for
exception handler 2
code for
exception handler n-1
…
Exception
numbers
This is extra (non-testable) material
CMPT 295
Processes
(Jump tables for switch statements: x86 Programming III slides)
The book calls this an Exception table. I am using that at the top of the slide to be consistent with the book and with the previous slide.
Exception Table (Excerpt)
10
Exception Number Description Exception Class
0 Divide error Fault
13 General protection fault Fault
14 Page fault Fault
18 Machine check Abort
32-255 OS-defined Interrupt or trap
This is extra (non-testable) material
CMPT 295
Processes
According to the book: Ones in gray are Intel-defined, Others are OS-defined
Intel® 64 and IA-32 Architectures Software Developer’s Manual, Volume 1: Basic Architecture – Describes the architecture and programming environment of processors supporting IA-32 and Intel 64 Architectures.
“Systems often use an interrupt controller to group the device interrupts together before passing on the signal to a single interrupt pin on the CPU. This saves interrupt pins on the CPU…” http://www.tldp.org/LDP/tlk/dd/interrupts.html
This is why cat /proc/interrupts doesn’t match this slide – /proc/interrupts shows APIC’s “IRQ numbers”, not the OS’s exception numbers
10
Leading Up to Processes
System Control Flow
Control flow
Exceptional control flow
Asynchronous exceptions (interrupts)
Synchronous exceptions (traps & faults)
11
CMPT 295
Processes
Asynchronous Exceptions (Interrupts)
Caused by events external to the processor
Indicated by setting the processor’s interrupt pin(s) (wire into CPU)
After interrupt handler runs, the handler returns to “next” instruction
Examples:
I/O interrupts
Hitting Ctrl-C on the keyboard
Clicking a mouse button or tapping a touchscreen
Arrival of a packet from a network
Arrival of data from a disk
Timer interrupt
Every few milliseconds, an external timer chip triggers an interrupt
Used by the OS kernel to take back control from user programs
12
CMPT 295
Processes
Also:
Hard reset interrupt
hitting the reset button on front panel
Soft reset interrupt
hitting Ctrl-Alt-Delete on a PC
Synchronous Exceptions
Caused by events that occur as a result of executing an instruction:
Traps
Intentional: transfer control to OS to perform some function
Examples: system calls, breakpoint traps, special instructions
Returns control to “next” instruction
Faults
Unintentional but possibly recoverable
Examples: page faults, segment protection faults, integer divide-by-zero exceptions
Either re-executes faulting (“current”) instruction or aborts
Aborts
Unintentional and unrecoverable
Examples: parity error, machine check (hardware failure detected)
Aborts current program
13
CMPT 295
Processes
Summary
Exceptions
Events that require non-standard control flow
Generated externally (interrupts) or internally (traps and faults)
After an exception is handled, one of three things may happen:
Re-execute the current instruction
Resume execution with the next instruction
Abort the process that caused the exception
14
CMPT 295
Processes
Processes
Processes and context switching
Creating new processes
fork(), exec*(), and wait()
Zombies
15
CMPT 295
Processes
Process 1
What is a process?
16
CPU
Registers
%rip
Memory
Stack
Heap
Code
Data
Disk
Chrome.exe
It’s an illusion!
CMPT 295
Processes
16
What is a process?
Another abstraction in our computer system
Provided by the OS
OS uses a data structure to represent each process
Maintains the interface between the program and the underlying hardware (CPU + memory)
What do processes have to do with exceptional control flow?
Exceptional control flow is the mechanism the OS uses to enable multiple processes to run on the same system
What is the difference between:
A processor? A program? A process?
17
CMPT 295
Processes
The data structure is the process control block (PCB).
17
Processes
A process is an instance of a running program
One of the most profound ideas in computer science
Not the same as “program” or “processor”
Process provides each program with two key abstractions:
Logical control flow
Each program seems to have exclusive use of the CPU
Provided by kernel mechanism called context switching
Private address space
Each program seems to have exclusive use of main memory
Provided by kernel mechanism called virtual memory
18
CPU
Registers
Memory
Stack
Heap
Code
Data
CMPT 295
Processes
What is a process?
19
Computer
Disk
/Applications/
Chrome.exe
Slack.exe
PowerPoint.exe
CPU
Process 2
Process 3
Process 4
Process 1
“Memory”
Stack
Heap
Code
Data
“CPU”
Registers
“Memory”
Stack
Heap
Code
Data
“CPU”
Registers
“Memory”
Stack
Heap
Code
Data
“CPU”
Registers
“Memory”
Stack
Heap
Code
Data
“CPU”
Registers
It’s an illusion!
CMPT 295
Processes
19
What is a process?
20
Computer
Disk
/Applications/
Chrome.exe
Slack.exe
PowerPoint.exe
CPU
Process 1
“Memory”
Stack
Heap
Code
Data
“CPU”
Registers
Process 2
“Memory”
Stack
Heap
Code
Data
“CPU”
Registers
Process 3
“Memory”
Stack
Heap
Code
Data
“CPU”
Registers
Process 4
“Memory”
Stack
Heap
Code
Data
“CPU”
Registers
Operating
System
It’s an illusion!
CMPT 295
Processes
20
Multiprocessing: The Illusion
Computer runs many processes simultaneously
Applications for one or more users
Web browsers, email clients, editors, …
Background tasks
Monitoring network & I/O devices
21
CPU
Registers
Memory
Stack
Heap
Code
Data
CPU
Registers
Memory
Stack
Heap
Code
Data
…
CPU
Registers
Memory
Stack
Heap
Code
Data
CMPT 295
Processes
Multiprocessing: The Reality
Single processor executes multiple processes concurrently
Process executions interleaved, CPU runs one at a time
Address spaces managed by virtual memory system (later in course)
Execution context (register values, stack, …) for other processes saved in memory
22
CPU
Registers
Memory
Stack
Heap
Code
Data
Saved registers
Stack
Heap
Code
Data
Saved registers
Stack
Heap
Code
Data
Saved registers
…
CMPT 295
Processes
Multiprocessing
Context switch
Save current registers in memory
23
CPU
Registers
Memory
Stack
Heap
Code
Data
Saved registers
Stack
Heap
Code
Data
Saved registers
Stack
Heap
Code
Data
Saved registers
…
CMPT 295
Processes
Multiprocessing
Context switch
Save current registers in memory
Schedule next process for execution
24
CPU
Registers
Memory
Stack
Heap
Code
Data
Saved registers
Stack
Heap
Code
Data
Saved registers
Stack
Heap
Code
Data
Saved registers
…
CMPT 295
Processes
Multiprocessing
25
CPU
Registers
Memory
Stack
Heap
Code
Data
Saved registers
Stack
Heap
Code
Data
Saved registers
Stack
Heap
Code
Data
Saved registers
…
Context switch
Save current registers in memory
Schedule next process for execution
Load saved registers and switch address space
CMPT 295
Processes
Multiprocessing: The (Modern) Reality
Multicore processors
Multiple CPUs (“cores”) on single chip
Share main memory (and some of the caches)
Each can execute a separate process
Kernel schedules processes to cores
Still constantly swapping processes
26
CPU
Registers
Memory
Stack
Heap
Code
Data
Saved registers
Stack
Heap
Code
Data
Saved registers
Stack
Heap
Code
Data
Saved registers
…
CPU
Registers
CMPT 295
Processes
Concurrent Processes
Each process is a logical control flow
Two processes run concurrently (are concurrent) if their instruction executions (flows) overlap in time
Otherwise, they are sequential
Example: (running on single core)
Concurrent: A & B, A & C
Sequential: B & C
27
Process A
Process B
Process C
time
Assume only one CPU
CMPT 295
Processes
User’s View of Concurrency
Control flows for concurrent processes are physically disjoint in time
CPU only executes instructions for one process at a time
However, the user can think of concurrent processes as executing at the same time, in parallel
28
Assume only one CPU
Process A
Process B
Process C
time
Process A
Process B
Process C
User View
CMPT 295
Processes
Context Switching
Processes are managed by a shared chunk of OS code
called the kernel
The kernel is not a separate process, but rather runs as part of a user process
In x86-64 Linux:
Same address in each process
refers to same shared
memory location
29
Assume only one CPU
CMPT 295
Processes
Context Switching
Processes are managed by a shared chunk of OS code
called the kernel
The kernel is not a separate process, but rather runs as part of a user process
Context switch passes control flow from one process to another and is performed using kernel code
30
Process A
Process B
user code
kernel code
user code
kernel code
user code
context switch
context switch
time
Exception
Assume only one CPU
CMPT 295
Processes
Processes
Processes and context switching
Creating new processes
fork() , exec*(), and wait()
Zombies
31
CMPT 295
Processes
Process 2
“Memory”
Stack
Heap
Code
Data
“CPU”
Registers
Creating New Processes & Programs
32
Chrome.exe
Process 1
“Memory”
Stack
Heap
Code
Data
“CPU”
Registers
fork()
exec*()
CMPT 295
Processes
Creating New Processes & Programs
fork-exec model (Linux):
fork() creates a copy of the current process
exec*() replaces the current process’ code and address space with the code for a different program
Family: execv, execl, execve, execle, execvp, execlp
fork() and execve() are system calls
Other system calls for process management:
getpid()
exit()
wait(), waitpid()
33
CMPT 295
Processes
Review: system calls are traps (intentional exception).
http://en.wikipedia.org/wiki/Fork-exec: “Microsoft Windows does not support the fork-exec model, as it does not have a system call analogous to fork(). The spawn() family of functions declared in process.h can replace it in cases where the call to fork() is followed directly by exec().”
33
fork: Creating New Processes
pid_t fork(void)
Creates a new “child” process that is identical to the calling “parent” process, including all state (memory, registers, etc.)
Returns 0 to the child process
Returns child’s process ID (PID) to the parent process
Child is almost identical to parent:
Child gets an identical
(but separate) copy of the
parent’s virtual address
space
Child has a different PID
than the parent
fork is unique (and often confusing) because it is called once but returns “twice”
34
pid_t pid = fork();
if (pid == 0) {
printf(“hello from child\n”);
} else {
printf(“hello from parent\n”);
}
CMPT 295
Processes
Understanding fork()
35
Process X (parent; PID X)
pid_t fork_ret = fork();
if (fork_ret == 0) {
printf(“hello from child\n”);
} else {
printf(“hello from parent\n”);
}
Process Y (child; PID Y)
pid_t fork_ret = fork();
if (fork_ret == 0) {
printf(“hello from child\n”);
} else {
printf(“hello from parent\n”);
}
CMPT 295
Processes
35
Understanding fork()
36
pid_t fork_ret = fork();
if (fork_ret == 0) {
printf(“hello from child\n”);
} else {
printf(“hello from parent\n”);
}
pid_t fork_ret = fork();
if (fork_ret == 0) {
printf(“hello from child\n”);
} else {
printf(“hello from parent\n”);
}
fork_ret = Y
Process X (parent; PID X)
pid_t fork_ret = fork();
if (fork_ret == 0) {
printf(“hello from child\n”);
} else {
printf(“hello from parent\n”);
}
Process Y (child; PID Y)
pid_t fork_ret = fork();
if (fork_ret == 0) {
printf(“hello from child\n”);
} else {
printf(“hello from parent\n”);
}
fork_ret = 0
CMPT 295
Processes
36
Understanding fork()
37
pid_t fork_ret = fork();
if (fork_ret == 0) {
printf(“hello from child\n”);
} else {
printf(“hello from parent\n”);
}
pid_t fork_ret = fork();
if (fork_ret == 0) {
printf(“hello from child\n”);
} else {
printf(“hello from parent\n”);
}
Process X (parent; PID X)
pid_t fork_ret = fork();
if (fork_ret == 0) {
printf(“hello from child\n”);
} else {
printf(“hello from parent\n”);
}
Process Y (child; PID Y)
pid_t fork_ret = fork();
if (fork_ret == 0) {
printf(“hello from child\n”);
} else {
printf(“hello from parent\n”);
}
hello from parent
hello from child
Which one appears first?
fork_ret = Y
fork_ret = 0
CMPT 295
Processes
37
Summary
Processes
At any given time, system has multiple active processes
On a one-CPU system, only one can execute at a time, but each process appears to have total control of the processor
OS periodically “context switches” between active processes
Implemented using exceptional control flow
Process management
fork: one call, two returns
execve: one call, usually no return
wait or waitpid: synchronization
exit: one call, no return
38
CMPT 295
Processes