List the four necessary conditions for deadlock, and give a one-sentence definition of each.
There are only four correct answers for the conditions, but many equally good ways of wording the definitions. For example:
- mutual exclusion - While one process is holding a resource other processes cannot use it. (Could also be stated in terms of threads.)
Answer both parts.
- Give an example of a single-unit reusable resource graph that shows
a deadlock.
The critical things here are that the graph be a single-unit reusable resource graph, and that it have a deadlock. Common errors include:
- reversing the direction of the "held-by" and/or "waiting for" arrows
- giving a process wait-for graph (in which processes wait directly for processes, with no resources)
- graph with no deadlock
- giving a 2D "trajectory" graph
- giving a picture of Dining Philosphers table
- Give an example of a multi-unit reusable resource graph that contains
a cycle but does not contain a deadlock.
The critical things here are that the graph be a multi-unit reusable resource graph, that it have a (directed) cycle, and that it have no deadlock. To achieve all these things, you need at least one resource with two or more units, and you need at least one unit to be held by a process that is not in the cycle. Common errors include:
- reversing the direction of the "held-by" and/or "waiting for" arrows
- giving a process wait-for graph (in which processes wait directly for processes, with no resources)
- graph with no deadlock
- giving a 2D "trajectory" graph
- originating the held-by arcs from the circle, rather than one or more of the resource-discs within the circle
- making a wait-for arc from a process to a reource where there are free units available
Suppose there is a (non-virtual memory) system that has only 200 Mb of main memory and there are two processes that make the following sequence of requests:
| P1 | P2 | |
|---|---|---|
| ... | ... | |
| Request 80Mb; | Request 70Mb; | |
| ... | ... | |
| Request 60Mb; | Request 80Mb; |
Can there be a deadlock? If not, argue why not. Otherwise, explain how the deadlock can happen, and then also explain how it could be avoided.
There can be a deadlock. One way it can occur is if the execution of P1 and P2 is interleaved so that: (1) P1 requests 80Mb and it is granted; (2) P2 requests 70Mb and it is granted; (3) P1 requests 60Mb and it is granted; (4) P2 requests 80Mb and it is granted. At that point (and only then) there is a deadlock. Note that the deadlock does not occur until both processes are fatally blocked. Several people only carried the example up to step (2), and claimed there was a deadlock at that point. That is not so. After step (2) the system is in an unsafe state, and future deadlock is unavoidable, but it is not yet deadlocked.
To avoid the deadlock, one can apply the Banker's Algorithm, which would cause P2 to block at step (2) above, until P1 releases its 80Mb allocation. Note that the Banker's algorithm does not make P2 wait to start until P1 has completed. It only blocks P2 at the request for 70Mb. Note also that several other techniques suggested by students, such as giving P1 all the memory, and making process request all their memory at once, are prevention techniques, not avoidance techniques.
What is the output for one of the legal thread scheduling orders of the following program? Assume the correct #include's are provided and the program compiles and runs without error.
pthread_mutex_t M;
pthread_cond_t C;
volatile int X = 0;
void * body (void * arg) {
pthread_mutex_lock (&M);
fprintf (stderr, " 1/%d ", (int) arg);
X++;
pthread_cond_signal (&C);
while (X <= (int) arg) {
pthread_cond_wait (&C, &M);
fprintf (stderr, " 2/%d ", (int) arg);
}
fprintf (stderr, " 3/%d ", (int) arg);
X++;
pthread_mutex_unlock (&M);
pthread_cond_signal (&C);
}
int main() {
pthread_t t1, t2;
pthread_mutex_init (&M, NULL);
pthread_cond_init (&C, NULL);
pthread_create (&t1, NULL, body, 1);
pthread_create (&t2, NULL, body, 2);
pthread_join (t1, NULL);
pthread_join (t2, NULL);
return 0;
}
The main point of this question was to see if you understand how condition variables work. It is fairly easy to see that one thread will output a sequence of the form 1/1 ( 2/1 )* 3/1, and the other will output a sequence of the form 1/2 ( 2/2 )* 3/2, where the notation ( ... )* is intended as a regular expression, indicating zero or more repetitions of the text inside. The critical issue is that the way the condition variables are used imposes some constraints on the interleavings of these two sequences, namely:
- Thread 1 cannot leave its while-loop until both thread have incremented X (making the value 2), so "2/1" must follow "1/2".
- Thread 2 cannot leave its while-loop until thread 1 has incremented X the second time (making the value 3), so "2/2" must follow "3/1".
Thus, for example, one possible output sequence is " 1/1 1/2 2/1 3/1 2/2 3/2".
(I apologize for the typos in this question, which caused some distance students confusion. Therefore, those few students who did not see the corrections, and who wrote as their answer that the program will not compile, and so will not run, received credit. However, in the future, please be aware that if the point of a question with code is for you to find errors in it I will (as in question 6) make that clear. Otherwise, you should assume that the code is part of a compilable and then executable program. In this case I did compile and execute the code, as I always do for exam questions containing oce. I guess that I must have used "gcc q4.c" without the "-ansi -Wall -pedantic", and so the compiler did not catch the typos.)
What is the output of the following program? Assume the correct #include's are provided. (Hint: The read (a, b, c) reads c bytes from the file designated by file descriptor a into the buffer designated by pointer b, and write (a, b, c) writes c bytes to the file designated by file descriptor a into the buffer designated by pointer b. These operations read and write raw bits, without respect to datatype.) Assume the program load module exists in a file called "q4" in the current working directory. Assume the program is initially called as "q4" with no command-line arguments, i.e., argc = 1. Of course, if the execve() call in the program is executed, the argc value after that will be determined by the relevant parameter to execve().
int n = 0;
int main(int argc, char *argv[]) {
pid_t child;
int status;
int fd[2];
char *myargv[] = {"q4", "stop", NULL};
char buf[10];
n++;
if (argc > 1) {
read (0, &n, sizeof (n));
printf ("n = %d\n", n);
exit (3);
}
pipe (fd);
child = fork();
if (child != 0) {
write (fd[1], &n, sizeof (n));
waitpid (child, &status, 0);
n = WEXITSTATUS (status);
} else {
n++;
dup2 (fd[0], 0);
execve ("q4", myargv, NULL);
}
printf ("n = %d\n", n);
return 0;
}
n = 1 n = 3
Assuming the first execution of "q4" has argc = 1, the original process will increment n from 0 to 1 and continue on to the fork() call without producing any output. It will write its current value of n (which is 1) to the pipe, and wait for the child to terminate. The child will increment its copy of n (to 2), redirect stdin to the pipe, and exec itself with the argument "stop". After the exec, the child process will start the program over from the beginning, with argc = 2. It will read into n the value (1) put into the pipe by the parent process, print "n = 1\n", and exit with value 3. The parent will wake up, and store into its copy of n the exit status value (3) provided by the child, print "n = 3\n", and exit.
Suppose the following code is taken from the consumer side of a producer-consumer pair. Suppose the compilation context of the code is correct, so there are #includes for all necessary headers, and all variables are declared and initialized correctly. In particular, assume "char *shared_buf[NITEMS};" is declared and NITEMS is an integer > 1, as in the examples covered in class.
char *local_buf = (char *) malloc (N);; ... pthread_mutex_lock (&M);ifwhile (next_out == next_in) {pthread_mutex_unlock (&M);pthread_cond_wait (&CV, &M);pthread_mutex_lock (&M);} strncpy (local_buf, shared_buf[next_out], N); next_out = (next_out + 1) % NITEMS; pthread_cond_signal (&CV, &M); pthread_mutex_unlock (&M);
What is wrong with the code? List at least three distinct major defects in design and/or coding, and explain or show how to correct each defect. If possible, show corrections by crossing out and/or writing in bits of code above.If it would take more than just a simple change to correct a problem, use a sentence to explain what needs to be done. (Don't waste time trying to write out a complete correct solution!)
There are more than three errors. The green text inserted above is an approximate attempt to correct these errors, which we describe below:
- The pointer variable local_buf is never initialized.
- The call to pthread_cond_wait() has no loop to test for the secondary condition.
- The calls to pthread_mutex_unlock() and pthread_mutex_lock() around the call to pthread_cond_wait() are wrong, since waiting on a condition variable requires the mutex be held (already locked) by the calling thread, and on return from the wait operation the mutex is again held (locked) by the thread.
- There is danger of buffer overflow with strcpy. It should be replaced by a use of strncpy(). (Note that the proposed solution shown above is not complete, since it does not check to see whether the entire string was copied.)
- A call to pthread_cond_signal() is needed to wake up the producer, after next_out is incrementd. (Note that it would be wrong to say that the consumer needs to be awakened by this call, or to place the call inside the while loop or if statement.