CS 537: Introduction to Operating Systems

Problem set 1

Due: June 29, at the beginning of class.

“...but which one do I use for dessert?”

The questions in this section refer to the following program, called forko.

#include <stdlib.h>
#include <stdio.h>

#define FOO 2

int main(int c, char *v[]) {
	int i = FOO;
	while (i-- >= 0) {
		fork();
	}
	exit(0);
}

1. Draw a graph of the parent-child relation created by executing forko.
2. How many processes will forko create if FOO is set to 3? to 5? to 7?

“Time synch”

1. Answer problem 6.3 from the textbook.
2. Answer problem 6.5 from the textbook.
3. Implement a solution to the sleeping-barber problem. (This is described in the textbook's problem 6.11.) You may use Java or C (with pthreads). If you use Java, do not use any of the new Java 1.5 java.util.concurrent features in your solution.
4. Using Java or C, design a correct solution to the producer-consumer problem that allows greater concurrency than the solution we discussed in class. Your solution must only support one producer and one consumer, but it should allow put() and take() operations to execute concurrently if it is safe to do so.

“Lock and load”

1. Of special concern if you have a car in Madison: answer problem 7.1 from the textbook.
2. Using only monitors for synchronization, write a short Java program that is susceptible to deadlock. Argue why your program is susceptible to deadlock.