CSE 120 Homework #2

Fall 2007

1. On /home/linux/ieng6/cs120f/hw/ we've placed a library libthread.a that has the object files of a reference implementation of the threads package. You can link to this library as follows: suppose you have a program foo.c that includes /home/linux/ieng6/cs120f/p1/thread.h. Compile your program with the following command:

      gcc -o foo foo.c -L/home/linux/ieng6/cs120f/hw -lthread

   Implement the semaphore-based readers/writers algorithm given in Lecture 6 in C using the threads package. You should implement three reader threads and three writer threads. You will find it easier to have t_start start a thread that creates the two conditions - one for the semaphore mutex and one for the semaphore r_or_w - and t_forks the three reader and three writer threads. The parameter to the thread should be a unique name for the thread (for example, you could name the reader threads R1, R2 and R3).

   1. Each reader should execute a loop so that it tries to enter the Read section three times. The Read section should be:

      printf("%s starts reading\n", name);
      t_yield();
      printf("%s stops reading\n", name);

      where name is unique name you gave to this reader thread. Similarly, each writer should execute a look so that it tries to enter the Write section three times. The Write section should be:

      printf("%s starts writing\n", name);
      t_yield();
      printf("%s stops writing\n", name);

      where name is unique name you gave to this writer thread.

      Run your program to verify that it is behaving the way it should. This is the program whose listing we'd like you to turn in along with the output it generates.

   2. Comment out the t_yield statements and re-run it. Turn in this output as well. Explain why the output pattern is so much simpler than the output you got from the first part.

2. You'll implement a solution to the Dining Philosopher's problem as a Java monitor. We'll be covering this problem in Lecture 8, but it's simple: there are five philosophers sitting around a circular table. Philosophers alternate between thinking and eating. But, a philosopher can't eat while either of his neighbors is eating (this is because there are also just five chopsticks, one between each pair of adjacent professors, and philosophers need to use both chopsticks to eat, see...) So, a philosopher can also be in a third state, waiting, which means she is hungry but at least one of her neighbors is eating.

   The monitor will be the class Table that has two methods: one called StartEating(i) which means that Philosopher i wishes to eat, and one called StopEating(i) which means that Philosopher i stops eating. The file Table.java is the file you'll need to modify to implement this monitor. In StartEating(i), Philosopher i checks to see if either of her neighbors is eating; if so, then i is hungry and waits. StopEating(i) turns the Philosopher's state back to thinking, which may allow a hungry neighbor to start eating. The class also includes a place for you to implement toString: the Philosopher class uses this to print the current states of the philosophers in a convenient manner. This string should contain five character - the first represents the state of Philosopher 0, the second the state of Philosopher 1, and so on. Use the character 'T' to indicate thinking, 'H' for hungry, and 'E' for eating. For example, "THETE" means Philosopher 0 and 3 are thinking, Philosopher 1 is hungry, and Philosophers 2 and 4 are eating. Note that this class has a constructor, in which we've already supplied some code. You'll need to do more.

   The file Philosopher.java is the class that implements a philosopher thread, and DiningPhilosophers.java is the class that implements the program: this is the class that has main. You won't have to change either of these files.

   To give you a template for a Java monitor, we've also posted BSem.java, which is a java class that implements a binary semaphore (that is, a mutex semaphore). Don't use this class in your implementation of Table; instead, look at it to show you the syntax Java uses for writing monitors.

   Turn in a listing of Table.java and the output you generate from running DiningPhilosophers.

3. [Lecture 5] Consider an alarm clock as a system.

   1. Describe the state of an alarm clock as a set of variables. It needs to be detailed enough to express the answers to the rest of this question.

   2. Give two safety properties of this system in terms of the state you've defined.

   3. Give two liveness properties of this system in terms of the state you've defined.

4. [Modified from Silberschatz 4.4] Give two advantages threads have over multiple processes.`Give one major disadvantage that they have. Suggest one application that would benefit from the use of threads instead of processes, and one that would not.

5. Suppose you were implementing a counting semaphore in a new operating system for a mobile phone. Even though in CSE 120 you were told that counting semaphores were unbounded, you know that in practice there is a maximum value which will be imposed by the exact representation you use. In your case, the maximum value is 2^32.

   In your implementation, you have three options for the case where signal(s) is done on a semaphore that has already attained its maximum value. You can (i) treat the operation as a no-op; (ii) block the operation until some other thread executes wait(s); (iii) raise an exception (that, if not caught, causes the process to terminate).

   For each of these, give a positive attribute and a negative attribute for using that solution. Which do you think is the best, and why?

6. [Modified from Silberschatz 6.15] Suppose that we replace the wait and signal with a single construct await(B), where B is a general boolean expression that causes the thread to wait until B becomes true.

   One decision to make with an await construct is defining exactly when the boolean expression is evaluated. Of course, when await(B) is initially executed, if B is true then the thread need not wait. The interesting case is when should B be re-evaluated for threads that are waiting for B to become true.

   1. One idea is the following: whenever an entry procedure modifies a variable (say, x), all expressions B that reference x are immediately re-evaluated. Give two drawbacks of this approach. Hint: for one of them, think about monitor invariants.

   2. Another approach is to re-evaluate the expressions B of the blocked threads only when a thread returns from an entry procedure. Unfortunately, this can result in a liveness problem. Explain.

   3. From this point out, we will use the approach that the boolean expressions are re-evaluated whenever a thread releases the monitor lock. Rewrite the readers/writers monitor given in Lecture 7 to use this await construct instead of wait and signal.