Carnegie Mellon
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
1
14
–
513
18
–
613
Carnegie Mellon
Exceptional Control Flow: Exceptions and Processes
15-213/18-213/14-513/15-513/18-613: Introduction to Computer Systems 19th Lecture, November 3, 2020
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 2
Carnegie Mellon
Printers Used to Catch on Fire
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 3
Carnegie Mellon
Highly Exceptional Control Flow
https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/drivers/char/lp.c?h=v5.0-rc3
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 4
Carnegie Mellon
Today
Exceptional Control Flow Exceptions
Processes
Process Control
CSAPP 8 CSAPP 8.1 CSAPP 8.2 CSAPP 8.3-8.4
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
5
Carnegie Mellon
Control Flow
Processors do only one thing:
▪ From startup to shutdown, each CPU core 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) Physical control flow
Time
inst1
inst2
inst3
…
instn
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
6
* Externally, from an architectural viewpoint (internally, the CPU may use parallel out-of-order execution)
Carnegie Mellon
Altering the Control Flow
Up to now: two mechanisms for changing control flow: ▪ Jumps and branches
▪ Call and return
React to changes in program state
Insufficient for a useful system:
Difficult to react to changes in system state
▪ Data arrives from a disk or a network adapter ▪ Instruction divides by zero
▪ User hits Ctrl-C at the keyboard
▪ System timer expires
System needs mechanisms for “exceptional control flow”
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 7
Carnegie Mellon
Exceptional Control Flow
Exists at all levels of a computer system
Low level mechanisms ▪ 1. Exceptions
▪ Change in control flow in response to a system event (i.e., change in system state)
▪ Implemented using combination of hardware and OS software
Higher level mechanisms ▪ 2. Process context switch
▪ Implemented by OS software and hardware timer ▪ 3. Signals
▪ Implemented by OS software
▪ 4. Nonlocal jumps: setjmp() and longjmp()
▪ Implemented by C runtime library
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 8
Carnegie Mellon
Today
Exceptional Control Flow Exceptions
Processes
Process Control
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 9
Carnegie Mellon
Exceptions
An exception is a transfer of control to the OS kernel in response to some event (i.e., change in processor state)
▪ Kernel is the memory-resident part of the OS
▪ Examples of events: Divide by 0, arithmetic overflow, page fault, I/O
request completes, typing Ctrl-C
User code
Event I_current I_next
Kernel code
Exception
• Return to I_current • Return to I_next
• Abort
Exception processing by exception handler
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 10
Carnegie Mellon
Exception Tables
Exception numbers
Exception
Table
0 1
2
n-1
Each type of event has a unique exception number k
k = index into exception table (a.k.a. interrupt vector)
Handler k is called each time exception k occurs
…
…
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
11
Code for
exception handler 0
Code for
exception handler 1
Code for
exception handler 2
Code for
exception handler n-1
Carnegie Mellon
(partial) Taxonomy
ECF
Asynchronous
Synchronous
Faults
Interrupts Traps
Aborts
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
12
Carnegie Mellon
Asynchronous Exceptions (Interrupts)
Caused by events external to the processor ▪ Indicated by setting the processor’s interrupt pin ▪ Handler returns to “next” instruction
Examples:
▪ Timer interrupt
▪ Every few ms, an external timer chip triggers an interrupt
▪ Used by the kernel to take back control from user programs ▪ I/O interrupt from external device
▪ Hitting Ctrl-C at the keyboard
▪ Arrival of a packet from a network ▪ Arrival of data from a disk
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 13
Carnegie Mellon
Synchronous Exceptions
Caused by events that occur as a result of executing an instruction:
▪ Traps
▪ Intentional, set program up to “trip the trap” and do something ▪ Examples: system calls, gdb breakpoints
▪ Returns control to “next” instruction
▪ Faults
▪ Unintentional but possibly recoverable
▪ Examples: page faults (recoverable), protection faults (unrecoverable), floating point exceptions
▪ Either re-executes faulting (“current”) instruction or aborts ▪ Aborts
▪ Unintentional and unrecoverable
▪ Examples: illegal instruction, parity error, machine check ▪ Aborts current program
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 14
Carnegie Mellon
System Calls
Each x86-64 system call has a unique ID number
Examples:
Number Name Description
0 read Read file
1 write Write file
2 open Open file
3 close Close file
4 stat Get info about file
57 fork Create process
59 execve Execute a program
60 _exit Terminate process
62 kill Send signal to process
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
15
Carnegie Mellon
System Call Example: Opening File
Usercalls:open(filename,options)
Calls __open function, which invokes system call instruction syscall
00000000000e5d70 <__open>: …
e5d79:
e5d7e:
e5d80:
…
e5dfa: c3 retq
mov $0x2,%eax # open is syscall #2 syscall # Return value in %rax
cmp $0xfffffffffffff001,%rax
b8 02 00 00 00 0f 05
48 3d 01 f0 ff ff
User code
syscall cmp
Exception Returns
Kernel code
Open file
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
16
%rax contains syscall number
Other arguments in %rdi,
%rsi, %rdx, %r10, %r8, %r9
Return value in %rax
Negative value is an error corresponding to negative errno
Carnegie Mellon
System Call Example: Opening File Almost like a function call
• Transfer of control Usercalls:open(filename,options)
• On return, executes next instruction Calls __open function, which invokes system call instruction syscall
…
e5dfa: c3 retq
• Passes arguments using calling convention • Getsresultin%rax
00000000000e5d70 <__open>:
…
e5d79: b8 02 00 00 00 mov $0x2,%eax # open is syscall #2
One Important exception! e5d7e: 0f 05 syscall # Return value in %rax
e5d80: 48 3d 01 f0 ff ff cmp $0xfffffffffffff001,%rax
• Executed by Kernel
• Different set of privileges
• And other differences:
• E.g., “address” of “function” is in %rax
%rax contains syscall number
Other arguments in %rdi,
%rsi, %rdx, %r10, %r8, %r9
Return value in %rax
Negative value is an error corresponding to negative errno
User code
syscall cmp
Kernel code
Exception Returns
• Useserrno • Etc.
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
17
Open file
Carnegie Mellon
Fault Example: Page Fault
User writes to memory location
That portion (page) of user’s memory
is currently on disk
80483b7: c7 05 10 9d 04 08 0d movl
$0xd,0x8049d10
User code
movl
Kernel code
int a[1000];
main ()
{
a[500] = 13; }
Exception: page fault
Return and reexecute movl
Copy page from disk to memory
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
18
Carnegie Mellon
Fault Example: Invalid Memory Reference
int a[1000];
main ()
{
a[5000] = 13; }
80483b7: c7 05 60 e3 04 08 0d movl $0xd,0x804e360
User code Kernel code
movl
Exception: page fault
Sends SIGSEGV signal to user process
User process exits with “segmentation fault”
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
19
Detect invalid address
Signal process
Carnegie Mellon
Today
Exceptional Control Flow Exceptions
Processes
Process Control
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 20
Carnegie Mellon
Processes
Definition: 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
Memory
Stack
Heap
Data
Code
CPU
Registers
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 21
Carnegie Mellon
Multiprocessing: The Illusion
Memory
Stack
Heap
Data
Code
CPU
Registers
Memory
Stack
Heap
Data
Code
CPU
Registers
Memory
Stack
Heap
Data
Code
CPU
Registers
…
Computer runs many processes simultaneously ▪ Applications for one or more users
▪ Web browsers, email clients, editors, … ▪ Background tasks
▪ Monitoring network & I/O devices
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 22
Carnegie Mellon
Multiprocessing Example
Running program “top” on Mac
▪ System has 123 processes, 5 of which are active
▪ Identified by Process ID (PID)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 23
Carnegie Mellon
Multiprocessing: The (Traditional) Reality
Memory
…
Stack
Heap
Data
Code
Stack
Heap
Data
Code
Saved registers
Stack
Heap
Data
Code
Saved registers
CPU
Registers
Single processor executes multiple processes concurrently
▪ Process executions interleaved (multitasking)
▪ Address spaces managed by virtual memory system (like last week) ▪ Register values for nonexecuting processes saved in memory
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 24
Carnegie Mellon
Multiprocessing: The (Traditional) Reality
Memory
…
Stack
Heap
Data
Code
Saved registers
Stack
Heap
Data
Code
Saved registers
Stack
Heap
Data
Code
Saved registers
CPU
Registers
Save current registers in memory
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 25
Carnegie Mellon
Multiprocessing: The (Traditional) Reality
Memory
…
Stack
Heap
Data
Code
Saved registers
Stack
Heap
Data
Code
Stack
Heap
Data
Code
Saved registers
CPU
Registers
Schedule next process for execution
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 26
Carnegie Mellon
Multiprocessing: The (Traditional) Reality
Memory
…
Stack
Heap
Data
Code
Saved registers
Stack
Heap
Data
Code
Saved registers
Stack
Heap
Data
Code
Saved registers
CPU
Registers
Load saved registers and switch address space (context switch) Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 27
Carnegie Mellon
Multiprocessing: The (Modern) Reality
Stack
Heap
Data
Code
Stack
Heap
Data
Code
CPU
Registers
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
28
CPU
Registers
Memory
…
Stack
Heap
Data
Code
Saved registers
Multicore processors ▪Multiple CPUs on single chip
▪Share main memory (and some caches) ▪Each can execute a separate process
▪ Scheduling of processors onto cores done by kernel
Carnegie Mellon
Concurrent Processes
Each process is a logical control flow.
Two processes run concurrently (are concurrent) if their flows overlap in time
Otherwise, they are sequential
Examples (running on single core): ▪ Concurrent: A & B, A & C
▪ Sequential: B & C
Process A Process B
Time
Process C
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
29
Carnegie Mellon
User View of Concurrent Processes
Control flows for concurrent processes are physically disjoint in time
However, we can think of concurrent processes as running in parallel with each other
Process A Process B Process C
Time
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
30
Carnegie Mellon
Context Switching
Processes are managed by a shared chunk of memory- resident OS code called the kernel
▪ Important: the kernel is not a separate process, but rather runs as part of some existing process.
Control flow passes from one process to another via a context switch
Process A Process B
user code
kernel code
user code
kernel code
user code
Time
context switch
context switch
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
31
Carnegie Mellon
Today
Exceptional Control Flow Exceptions
Processes
Process Control
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 32
Carnegie Mellon
System Call Error Handling
On error, Linux system-level functions typically return -1 and
set global variable errno to indicate cause.
Hard and fast rule:
▪ You must check the return status of every system-level function ▪ Only exception is the handful of functions that return void
Example:
if ((pid = fork()) < 0) {
fprintf(stderr, "fork error: %s\n", strerror(errno)); exit(-1);
}
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 33
Carnegie Mellon
Error-reporting functions
Can simplify somewhat using an error-reporting function:
void unix_error(char *msg) /* Unix-style error */ {
fprintf(stderr, "%s: %s\n", msg, strerror(errno));
exit(-1); }
Note: csapp.c exits with 0.
But, must think about application. Not alway appropriate to exit when something goes wrong.
if ((pid = fork()) < 0) unix_error("fork error");
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 34
Carnegie Mellon
Error-handling Wrappers
We simplify the code we present to you even further by using Stevens1-style error-handling wrappers:
pid_t Fork(void)
{
pid_t pid;
if ((pid = fork()) < 0)
unix_error("Fork error");
return pid; }
pid = Fork();
NOT what you generally want to do in a real application
1e.g., in “UNIX Network Programming: The sockets networking API“ W. Richard Stevens
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 35
Carnegie Mellon
Obtaining Process IDs
pid_t getpid(void) ▪ Returns PID of current process
pid_t getppid(void) ▪ Returns PID of parent process
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 36
Carnegie Mellon
Creating and Terminating Processes
From a programmer’s perspective, we can think of a process as being in one of three states
Running
▪ Process is either executing, or waiting to be executed and will
eventually be scheduled (i.e., chosen to execute) by the kernel Stopped
▪ Process execution is suspended and will not be scheduled until further notice (next lecture when we study signals)
Terminated
▪ Process is stopped permanently
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 37
Carnegie Mellon
Terminating Processes
Process becomes terminated for one of three reasons:
▪ Receiving a signal whose default action is to terminate (next lecture)
▪ Returning from the main routine ▪ Calling the exit function
void exit(int status)
▪ Terminates with an exit status of status
▪ Convention: normal return status is 0, nonzero on error
▪ Another way to explicitly set the exit status is to return an integer value
from the main routine
exit is called once but never returns.
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 38
Carnegie Mellon
Creating Processes
Parent process creates a new running child process by
calling fork
int fork(void)
▪ Returns 0 to the child process, child’s PID to parent process ▪ Child is almost identical to parent:
▪ Child get an identical (but separate) copy of the parent’s virtual address space.
▪ Child gets identical copies of the parent’s open file descriptors ▪ Child has a different PID than the parent
fork is interesting (and often confusing) because it is called once but returns twice
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 39
Carnegie Mellon
Conceptual View of fork ➔
Memory
Stack
Heap
Data
Code
Saved registers
Stack
Heap
Data
Code
Saved registers
Stack
Heap
Data
Code
Saved registers
Make complete copy of execution state ▪ Designate one as parent and one as child
▪ Resume execution of parent or child
CPU
Registers
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 40
Memory parent child
CPU
Registers
Carnegie Mellon
The fork Function Revisited
VM and memory mapping explain how fork provides private
address space for each process.
To create virtual address for new process:
▪ Create exact copies of current mm_struct, vm_area_struct, and page tables.
▪ Flag each page in both processes as read-only
▪ Flag each vm_area_struct in both processes as private COW
On return, each process has exact copy of virtual memory.
Subsequent writes create new pages using COW mechanism.
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 41
Carnegie Mellon
fork Example
int main(int argc, char** argv)
{
pid_t pid; int x = 1;
pid = Fork(); if(pid==0){ /*Child*/
printf("child : x=%d\n", ++x); return 0;
}
/* Parent */
printf("parent: x=%d\n", --x);
return 0;
}
fork.c
linux> ./fork parent: x=0 child : x=2
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
42
linux> ./fork child : x=2 parent: x=0
Call once, return twice Concurrent execution
▪ Can’t predict execution order of parent and child
linux> ./fork parent: x=0 child : x=2
linux> ./fork parent: x=0 child : x=2
Carnegie Mellon
fork Example
Call once, return twice Concurrent execution
▪ Can’t predict execution order of parent and child
Duplicate but separate address space
▪xhas a value of 1 when fork returns in parent and child
▪ Subsequent changes to x are independent
Shared open files
▪ stdout is the same in both parent and child
int main(int argc, char** argv)
{
pid_t pid;
int x = 1;
pid = Fork(); if(pid==0){ /*Child*/
printf(“child : x=%d\n”, ++x);
return 0; }
/* Parent */
printf(“parent: x=%d\n”, –x);
return 0; }
linux> ./fork
parent: x=0
child : x=2
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
43
Carnegie Mellon
Modeling fork with Process Graphs
A process graph is a useful tool for capturing the partial ordering of statements in a concurrent program:
▪ Each vertex is the execution of a statement
▪ a -> b means a happens before b
▪ Edges can be labeled with current value of variables ▪ printf vertices can be labeled with output
▪ Each graph begins with a vertex with no inedges
Any topological sort of the graph corresponds to a feasible total ordering.
▪ Total ordering of vertices where all edges point from left to right
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 44
Carnegie Mellon
Process Graph Example
int main(int argc, char** argv)
{
pid_t pid; int x = 1;
pid = Fork(); if(pid==0){ /*Child*/
printf(“child : x=%d\n”, ++x);
return 0;
}
/* Parent */
printf(“parent: x=%d\n”, –x);
return 0;
child: x=2
printf exit x==1 parent: x=0
main fork printf exit
Child Parent
}
fork.c
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
45
Carnegie Mellon
Interpreting Process Graphs Original graph:
child: x=2
printf exit
x==1
parent: x=0
main for printf k
Relabled graph:
exit
ef abcd
Feasible total ordering:
abecfd Feasible or Infeasible?
abfced
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
46
Infeasible: not a topological sort
Carnegie Mellon
fork Example: Two consecutive forks Bye
void fork2() {
printf(“L0\n”);
fork();
printf(“L1\n”);
fork();
printf(“Bye\n”);
L0
L1
printf
L1
printf
Bye
fork printf
Bye
printf
Bye
}
forks.c
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
47
printf fork printf fork printf
Feasible output:
L0 L1 Bye Bye L1 Bye Bye
Infeasible output:
L0 Bye L1 Bye L1 Bye Bye
Carnegie Mellon
fork Example: Nested forks in parent Bye Bye
void fork4()
{
printf(“L0\n”); if (fork() != 0) {
printf(“L1\n”); if (fork() != 0) {
printf(“L2\n”);
}
}
printf(“Bye\n”);
}
printf
printf
L0 L1 L2 Bye
printf fork printf fork printf printf
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
48
forks.c
Feasible or Infeasible?
L0
Bye
L1
Bye
Bye
L2
Infeasible
Feasible or Infeasible?
L0 L1 Bye Bye L2 Bye
Feasible
Carnegie Mellon
fork Example: Nested forks in children
L2 Bye
printf printf
L1 Bye
printf fork printf
void fork5()
{
printf(“L0\n”);
if (fork() == 0) {
printf(“L1\n”); if (fork() == 0) {
printf(“L2\n”);
}
} printf(“Bye\n”);
L0 Bye
printf fork printf
Feasible or Infeasible?
L0 Bye L1 Bye Bye L2
Infeasible
Feasible or Infeasible?
L0 Bye L1 L2 Bye Bye
}
forks.c
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
49
Feasible
Carnegie Mellon
No Quiz Today
…But let’s take a short break now
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 50
Carnegie Mellon
Reaping Child Processes Idea
▪ When process terminates, it still consumes system resources ▪ Examples: Exit status, various OS tables
▪ Called a “zombie”
▪ Living corpse, half alive and half dead
Reaping
▪ Performed by parent on terminated child (using wait or waitpid) ▪ Parent is given exit status information
▪ Kernel then deletes zombie child process
What if parent doesn’t reap?
▪ If any parent terminates without reaping a child, then the orphaned
child should be reaped by init process (pid == 1) ▪ Unless ppid == 1! Then need to reboot…
▪ So, only need explicit reaping in long-running processes ▪ e.g., shells and servers
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 51
Carnegie Mellon
Zombie Example
linux> ./forks 7 &
[1] 6639
Running Parent, PID = 6639
Terminating linux> ps PID TTY
6585 ttyp9 6639 ttyp9 6640 ttyp9 6641 ttyp9
Child, PID = 6640
TIME CMD 00:00:00 tcsh
00:00:03 forks
00:00:00 forks
linux> kill 6639 [1] Terminated linux> ps
PID TTY
6585 ttyp9
6642 ttyp9
TIME CMD
00:00:00 tcsh
00:00:00 ps
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
52
void fork7() {
if (fork() == 0) {
/* Child */
printf(“Terminating Child, PID = %d\n”, getpid());
exit(0);
} else {
printf(“Running Parent, PID = %d\n”, getpid()); while (1)
}
}
forks.c
; /* Infinite loop */
ps shows child process as “defunct” (i.e., a zombie)
Killing parent allows child to be reaped by init
Carnegie Mellon
Non- terminating Child Example
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
53
Child process still active even though parent has terminated
Must kill child explicitly, or else will keep running indefinitely
void fork8()
{
if (fork() == 0) { /* Child */
printf(“Running Child, PID = %d\n”,
getpid());
while (1)
; /* Infinite loop */
} else {
printf(“Terminating Parent, PID = %d\n”,
} }
forks.c
getpid()); exit(0);
linux> ./forks 8
Terminating Parent, PID = 6675 Running Child, PID = 6676 linux> ps
PID TTY 6585 ttyp9 6676 ttyp9 6677 ttyp9
TIME CMD 00:00:00 tcsh
00:00:06 forks
00:00:00 ps linux> kill 6676
linux> ps PID TTY
6585 ttyp9
6678 ttyp9
TIME CMD
00:00:00 tcsh
00:00:00 ps
Carnegie Mellon
wait: Synchronizing with Children Parent reaps a child by calling the wait function
int wait(int *child_status)
▪ Suspends current process until one of its children terminates
▪ Implemented as syscall
Parent Process Kernel code
syscall …
Exception Returns
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 54
And, potentially other user processes, including a child of parent
Carnegie Mellon
wait: Synchronizing with Children Parent reaps a child by calling the wait function
int wait(int *child_status)
▪ Suspends current process until one of its children terminates
▪ Return value is the pid of the child process that terminated
▪ If child_status != NULL, then the integer it points to will be set to a value that indicates reason the child terminated and the exit status:
▪ Checked using macros defined in wait.h
– WIFEXITED, WEXITSTATUS, WIFSIGNALED, WTERMSIG, WIFSTOPPED, WSTOPSIG, WIFCONTINUED
– See textbook for details
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 55
Carnegie Mellon
wait: Synchronizing with Children
HC exit
printf
HP
CT Bye
void fork9() {
int child_status;
if (fork() == 0) {
printf(“HC: hello from child\n”);
exit(0); } else {
printf(“HP: hello from parent\n”); wait(&child_status);
printf(“CT: child has terminated\n”);
}
printf(“Bye\n”); }
forks.c
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
56
Feasible output:(s):
HC HP HP HC CT CT Bye Bye
Infeasible output:
HP CT Bye HC
fork printf wait printf
Carnegie Mellon
Another wait Example
If multiple children completed, will take in arbitrary order
Can use macros WIFEXITED and WEXITSTATUS to get information about exit status
void fork10() {
pid_t pid[N];
int i, child_status;
for (i = 0; i < N; i++)
if ((pid[i] = fork()) == 0) {
exit(100+i); /* Child */
}
for (i = 0; i < N; i++) { /* Parent */ pid_t wpid = wait(&child_status); if (WIFEXITED(child_status))
printf("Child %d terminated with exit status %d\n", wpid, WEXITSTATUS(child_status));
else
} }
printf("Child %d terminate abnormally\n", wpid); forks.c
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 57
Carnegie Mellon
waitpid: Waiting for a Specific Process
pid_t waitpid(pid_t pid, int *status, int options) ▪ Suspends current process until specific process terminates
▪ Various options (see textbook)
void fork11() { pid_t pid[N];
int i;
int child_status;
for (i = 0; i < N; i++)
if ((pid[i] = fork()) == 0)
exit(100+i); /* Child */
for (i = N-1; i >= 0; i–) {
pid_t wpid = waitpid(pid[i], &child_status, 0); if (WIFEXITED(child_status))
printf(“Child %d terminated with exit status %d\n”, wpid, WEXITSTATUS(child_status));
else
}
}
printf(“Child %d terminate abnormally\n”, wpid); forks.c
58
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Carnegie Mellon
execve: Loading and Running Programs
int execve(char *filename, char *argv[], char *envp[])
Loads and runs in the current process: ▪Executable filefilename
▪ Can be object file or script file beginning with #!interpreter (e.g., #!/bin/bash)
▪ …with argument list argv
▪ By convention argv[0]==filename
▪ …and environment variable list envp
▪ “name=value” strings (e.g., USER=droh) ▪ getenv, putenv, printenv
Overwrites code, data, and stack
▪ Retains PID, open files and signal context
Called once and never returns
▪ …except if there is an error
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 59
Carnegie Mellon
execve Example
Execute “/bin/ls –lt /usr/include” in child process
using current environment:
envp[n] = NULL
envp[n-1]
…
envp[0]
environ
(argc == 3)
myargv
“PWD=/usr/droh” “USER=droh”
“/usr/include” “-lt” “/bin/ls”
myargv[argc] = NULL
myargv[2]
myargv[1]
myargv[0]
if ((pid = Fork()) == 0) { /* Child runs program */ if (execve(myargv[0], myargv, environ) < 0) {
printf("%s: Command not found.\n", myargv[0]);
exit(1); }
}
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
60
Carnegie Mellon
Structure of the stack when a new program starts
Bottom of stack
environ
(global var)
envp[0]
argv[argc] = NULL
envp
(in %rdx)
argv[argc-1]
...
argv
(in %rsi)
argv[0]
argc
(in %rdi)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
61
Null-terminated environment variable strings
Null-terminated command-line arg strings
envp[n] == NULL
envp[n-1]
...
Stack frame for
libc_start_main
Top of stack
Future stack frame for
main
Carnegie Mellon
The execve Function Revisited
User stack
Memory mapped region for shared libraries
Runtime heap (via malloc)
Uninitialized data (.bss)
Initialized data (.data)
Program text (.text)
libc.so
Private, demand-zero
To load and run a new program a.out in the current process using execve:
Freevm_area_struct’s and page tables for old areas
Createvm_area_struct’s and page tables for new areas
.data
.text
Shared, file-backed
a.out
Private, demand-zero Private, demand-zero
Private, file-backed
▪ Programs and initialized data backed by object files.
▪ .bss and stack backed by anonymous files.
Set PC to entry point in
.text
▪ Linux will fault in code and data pages as needed.
.data
.text
0
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
62
Carnegie Mellon
Summary
Exceptions
▪ Events that require nonstandard control flow
▪ Generated externally (interrupts) or internally (traps and faults)
Processes
▪ At any given time, system has multiple active processes
▪ Only one can execute at a time on any single core
▪ Each process appears to have total control of
processor + private memory space
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 66
Carnegie Mellon
Summary (cont.)
Spawning processes ▪ Call fork
▪ One call, two returns
Process completion ▪ Call exit
▪ One call, no return
Reaping and waiting for processes
▪ Call wait or waitpid
Loading and running programs ▪ Call execve (or variant)
▪ One call, (normally) no return
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 67
Carnegie Mellon
Making fork More Nondeterministic
Problem
▪ Linux scheduler does not create much run-to-run variance
▪ Hides potential race conditions in nondeterministic programs
▪ E.g., does fork return to child first, or to parent? Solution
▪ Create custom version of library routine that inserts random delays along different branches
▪ E.g., for parent and child in fork
▪ Use runtime interpositioning to have program use special version of
library code
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 68
Carnegie Mellon
Variable delay fork
69
/* fork wrapper function */
pid_t fork(void) {
initialize();
int parent_delay = choose_delay();
int child_delay = choose_delay(); pid_t parent_pid = getpid();
pid_t child_pid_or_zero = real_fork(); if (child_pid_or_zero > 0) {
/* Parent */
if (verbose) {
printf(
“Fork. Child pid=%d, delay = %dms. Parent pid=%d, delay = %dms\n”,
child_pid_or_zero, child_delay,
parent_pid, parent_delay);
fflush(stdout);
}
ms_sleep(parent_delay);
} else {
/* Child */
ms_sleep(child_delay);
}
return child_pid_or_zero;
}
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
myfork.c