Tudor Dumitraş, Dec. 2006
This is the story of an exam problem from a sophomore-level course in Computer Science.
In the Fall 2006 installment of the 15-213 course (Introduction to Computer Systems) at Carnegie Mellon University, the second exam included a problem that tested the students' understanding of UNIX processes and signal handling. We wanted to introduce a nice and moderately hairy race condition related to the inherent non-determinism of process scheduling and signal delivery. The seven instructors (2 Professors and 5 Teaching Assistants, including myself) took the exam, solved this problem and suggested some changes; the program was modified, compiled and executed; finally, one professor and one TA reviewed the code once more. When we handed out the exam sheets, we thought that the 20-line program was clear and that we knew all the answers (the one and two-digit outputs described below).
Then we started noticing that students were finding three and four-digit outputs. We first disregarded these as incorrect, but, after trying to answer a few clarification questions, we realized that we had overlooked something and that the program could indeed print more than two digits. After the exam, one professor and two TAs carefully examined the problem, trying to find all the answers and working independently to cross-check their solutions. We all agreed that the problem could have 20 answers, instead of the 8 we had originally imagined. During the following recitation, after more questions from the students we realized that some of these outputs (including 2 of the original 8) cannot happen with current Linux implementations, although the specification does not preclude them. In the end, our little race condition became
What does this C program print out?
int val = 3;
void Exit(int val) {
printf("%d", val);
exit(0);
}
void usr1_handler(int sig) {
Exit(val);
}
int main() {
int pid;
signal(SIGUSR1, usr1_handler);
if ((pid = fork()) == 0) {
setpgid(0, 0);
if (fork())
Exit(val + 1);
else
Exit(val - 1);
}
kill(-pid, SIGUSR1);
}
Background
Basic program structure
One-digit output
Two-digit outputs
Three and four-digit outputs
Other cases
Summary
UNIX variants (e.g., Linux, Solaris, Aix) are multi-process operating systems; multiple processes may execute concurrently, although a CPU can only handle one process at a time. The operating-system scheduler controls the order in which processes execute and handles the context switches between them (saving and restoring all the process state). Each process has its own address space and, by default, does not share memory with any other process. The scheduler selects a process and lets it run for a certain amount of time depending on its priority, its wait time, which processes are blocked waiting for input, etc. Therefore, it is generally impossible to predict the execution order of instructions from multiple concurrent processes.
UNIX signals are a mechanism for inter-process communication (IPC) and for handling exceptional conditions that arise during execution. For example, a program will receive a SIGSEGV after an illegal memory access. Signals can also be sent explicitly to a process, using the raise() and kill() system calls. The signals are received asynchronously by a process, and they may interrupt the operation or system call in progress. A program can define a function to be invoked when it receives a particular signal; such signal handlers are installed using the system calls signal() and sigaction() (note that we used signal() only for brevity's sake; in a real program, sigaction() should always be used because signal() is not portable). In general, we cannot make any assumptions about the time instant when a signal will be delivered to a process.
Processes are created using the fork() system call, which splits the invoking process into two: a parent process and a child process, both continuing to execute the instructions that follow fork(). The parent and child process can be distinguished using the return value from fork(); however, we cannot make any assumptions about which process gets control of the CPU after the fork(). The two processes start with identical, but separate copies of all the global variables, and they have the same signal-handling vectors. The fork() system call also preserves all the open files, including stdin and stdout; moreover, if the file pointer position is updated in one of them (e.g., through a read or a write), this change will be reflected in the other process as well.
The program has a global variable called val, which is initialized with 3. It also defines a function Exit(), which prints the value of its argument val and then terminates the program with the exit code 0 (indicating success):
void Exit(int val) {
printf("%d", val); /* The argument val hides the global variable */
exit(0); /* with the same name. */
}
The main() function starts by installing a handler called usr1_handler() for the SIGUSR1 signal. The handler invokes Exit() with the current value of the global variable val:
void usr1_handler(int SIG) {
Exit(val); /* SIGUSR1 => Exit(3) (val does not change) */
}
After these initialization operations, the program creates a child process using fork(), which returns 0 in the child process and the child's process id (pid) in the parent. Since the code inside this if {} block will ultimately cause the termination of the child process, the control flow looks like this:
if ((pid = fork()) == 0) {
/* The child executes here */
...
}
/*
The parent executes here;
pid contains the process id of the child.
*/
The call setpgid(0,0) puts the child in a new process group whose group ID is identical to the child’s pid. All the processes spawned by the child will then belong to a process group with the group ID == process ID of the child (which is recorded in the pid variable in the parent). Therefore, when the parent calls kill(-pid,SIGUSR1) the signal SIGUSR1 will be delivered to the entire process group pid — that is, the child process and all its offsprings.
After resetting the group ID, the child forks another process (the grandchild):
if (fork())
Exit(val + 1);
else
Exit(val - 1);
At this point, val has the initial value 3. The grandchild will therefore invoke Exit(4) and the child will invoke Exit(2); these calls will terminate both processes.
Summarizing, the control flow of the program (including the outputs from all the processes) looks like this:
The child and the grandchild will print 2 and 4, respectively, and then they will exit. However, if one of them receives the SIGUSR1 sent by the parent, the process will print 3 and then exit.
The combined output is unpredictable because of two race conditions:
It is interesting to remark that, if the child receives the signal before executing the fork() call, the grandchild will never be created! In this case, the child prints 3 and then exits. The only possible one-digit output is:
3
(actually, if the system calls can fail then there are other posible one-digit outputs; I will explain these later, together with the other cases).
Since the child prints 4 or 3 and the grandchild prints 2 or 3, our program may print any one of the seven possible combinations of these numbers:
23
24
33
34
32
42
43
Well ... almost. 32 will be printed only if the following events happen in this sequence:
The situation is similar for the output 34 (the child and grandchild have their roles reversed). This is not likely to happen; after a kill() system call, the kernel probably updates the pending signal queues for all processes in one loop. This way, both processes will receive the signal and invoke the signal handler when they resume.
It turns out, however, that the POSIX specifications do not require signals
to be delivered to two different processes within some fixed time window. Therefore,
we must treat 32 and 34
as possible outputs, even if they are very unlikely to occur.
But what if the child and the grandchild receive the signal after executing the printf() call, but before calling exit()? In this case, the SIGUSR1 handler will be executed and the process will print another 3. Therefore, the child and the grandchild may also output 43 and 23, respectively. Since all signals are blocked while a signal handler executes, the process will terminate after usr1_handler() is invoked; nothing can interrupt the sequential execution in this case. 43 and 23 are therefore the only possible two-digit outputs from the two processes: the last digit must be a 3 and the first one must be different from 3.
void Exit(int val) {
printf("%d", val); /* SIGUSR1 may be delivered after this call executes */
exit(0);
}
void usr1_handler(int SIG) {
Exit(val); /* The handler cannot be interrupted */
}
This scenario shows that our program can have three and four-digit outputs. For example, if the child outputs two digits and the grandchild outputs one, their combination will generate a three-digit output. Before trying to list them exhaustively, it is useful to reason about how many such combined outputs are possible.
In the previous example, we are trying to create a three-digit output using two digits from the child and one digit from the grandchild. We can think of this problem as having a set of three numbers (corresponding to the positions in the three-digit output) that we can assign to the two digits of the child's output (the remaining position will be assigned to the grandchild's digit). Moreover, the positions of the two digits must be in an increasing order (i.e., we can assign positions <1,2> but not <2,1>). Note that the number of possible assignments must be the same as when trying to count the solutions for assigning three positions to one digit because this is the complementary problem of positioning the digit of the grandchild and leaving the remaining positions for the child's output. In general, if we have a set of n elements, how many subsets of k elements -- where the subsets with the same elements are not counted twice (we are only interested in the subsets with increasing positions) -- can we create? This problem is known as generating the k-subsets of a set with n elements, and the number of such subsets is the binomial coefficient:
In our case, we are generating the 2-subsets of a set with 3 elements. We are solving four of these problems, because the three-digit outputs are created by combining 43 from the child with 2 or 3 from the grandchild and 23 from the grandchild with 4 or 3 from the child. The number of possible three-digit combinations is:
However, in our case this number is only an upper bound. Since some digits are common in the outputs of the child and the grandchild, there may be some overlapping results. For example 433 will be printed when the child outputs 43 and the grandchild outputs 3, but the grandchild's digit can be assigned to either second or third position. There are algorithms for generating the k-subsets, but in this case it is easy enough to list all the possible outputs manually:
323
233
423
243
234
433
343
432
The four-digit outputs are created by combining 43 from the child with 23 from the grandchild; in this case we are generating the 2-subsets of a set with 4 elements:
Here too, six is an upper bound. There are only four possible outputs with four digits:
4323
4233
2343
2433
Some of these outputs are very unlikely. For the same reasons described in the previous section, a 3 probably cannot be followed by any digit other than 3. This affects the following outputs: 323, 234, 343, 432, 4323, and 2343. However, as any respectable Gremlin, our program has one more surprise for us: the digits are not necessarily printed in the order in which they are produced. The printf function buffers the characters and outputs them only when the invoking process exits (if stdout is connected to the console terminal, the buffer will also be flushed when a '\n' character is printed, but the messages from our program do not contain end-of-line characters). Therefore, the condition for unlikely outputs must be relaxed as followed: a 3 cannot be followed by a substring that does not contain 3. This means that the outputs 234 and 432 probably cannot happen on modern Linux implementations.
Moreover, because of the stdout buffering, it is unlikely (but still possible) that the digits printed by one process will become intertwined with the other process' output. Therefore, the following outputs are also very unlikely: 4233 and 2433.
In conclusion, we have 1 one-digit, 7 two-digit, 8 three-digit and 4 four-digit solutions. The 20-line program may produce 20 different outputs (6 of which are very unlikely), printing between one and four digits.
So are we done yet? When students complain that this problem was difficult, I tell them to look on the bright side because, under the right conditions, things can get even more interesting ;).
What if system calls fail? Any UNIX system call may fail. This is usually indicated by the return code from the call and the errno variable; however, the program above doesn't do any error checking. The program invokes six system calls (or C-library wrappers around system calls): printf, exit, signal, setpgid, fork, and kill. Let's examine what happens if each of these invocations fails.
What if SIGUSR1 comes from another source? After installing a signal handler for SIGUSR1, we must be prepared to receive it at any time and from any source (for instance, somebody can send a signal from the console using the kill command). We cannot assume that this signal is only raised from the parent process because this assumption would make the program vulnerable to a very obvious attack.
Since the signal handler for SIGUSR1 terminates the process without returning, the effect of sending SIGUSR1 multiple times to our processes will be the same as sending it only once. Above, we have examined all the possible situations when the child and grandchild receive SIGUSR1, so there is only one more possibility to consider: what happens when the parent receives SIGUSR1? The parent has the same signal handler, so it will print 3 and then exit. A 3 may therefore be inserted in any of the outputs described above.
What if we had initialized val with 0? In this case, the child will print 1, 0 or 10, and the grandchild will print -1, 0 or -10. The presence of a negative number introduces the (faint) possibility that the - gets separated from the number is negates by a digit from the other process, leading to interesting outputs such as 1-01.
The 15-213 Gremlin is a 20-line program that creates two processes. Assuming that system calls do not fail and that nobody gets the unfortunate idea of sending UNIX signals to the Gremlin, the two processes will print 4, 3, or 43 and 2, 3, or 23, respectively, leading to 20 combined outputs:
| 1-digit | 2-digit | 3-digit | 4-digit | |
|---|---|---|---|---|
| Probable outputs |
3
|
24
33 43 23 42 |
323
233 423 243 433 343 |
4323 |
| Unlikely outputs |
|
32
34 |
234
432 |
4233
2433 |
This example shows that race conditions can make even the simplest programs behave in strange and unexpected ways. The first version of the problem avoided one of the race conditions by synchronizing the processes with waitpid(); however, we considered that this would be too easy and that our students might appreciate a challenge. While the vast majority of the students who took the exam managed to find some of the three and four-digit outputs that we had initially overlooked, we never meant to make the analysis presented here a requirement for passing the exam. The complexity of this problem was, simply, a bug. Unfortunately, the change that created the Gremlin was performed on a Friday, which is (as empirical studies suggest) a bad day for programming.
Acknowledgments. I would like to thank all the heroes of this improbable odyssey, who have worked together to wrest all the secrets from our reluctant Gremlin: Professors Dave O'Hallaron and Randy Bryant who have created the fabulous 15-213 course and have trusted me enough to let me become a teaching assistant; my fellow TAs, Ashwin Bharambe, Mike Brotzman, Donnie Kim and Amit Manjhi; Nate Bauernfeind, Jiaqi Tan, Zhengheng Gho and all the 15-213 students who have discovered solutions and interactions that we had not envisioned.
If there is still something wrong with this analysis, please let me know.