CSE 428: Exercises on Concurrency and Java


The superscript "(d)" stands for "difficult". Exercises similar to those marked with "(d)" might appear in candidacy exams, but not in the standard exams of CSE 428.

The superscript "(s)" stands for "solution provided". You can find the solution of these exercises here.


  1. (s) Consider the example of the producers and consumers in the LN of Lecture 16. It is possible to see that the system is deadlock-free, in fact For each of the following modifications, say whether we lose the property of deadlock-freedom or not. Justify your answers.
    1. One producer instead of three, and still two consumers.
    2. Use notify() instead of notifyAll() in the get() method. Note: the method notify() removes an arbitrary thread from the wait set of the object.
    3. One producer, two consumers, and use notify() instead of notifyAll() in the put() method.
    4. Invert the order of the statements is_empty = false and notifyAll() in the put() method.
  2. (s) Define a class Stack (LIFO buffer) in Java, as an implementation of the following interface:
       interface Stack_interface(){
          void push(int);
          int pop();
          boolean is_empty();
       }
    
    Hint: you can follow the scheme of the definition of a Queue (FIFO buffer) given in the program Eratosthenes of Lecture 17. Note that there was no method is_empty because, for that particular application, it was not required.
  3. (s) Consider the program Eratosthenes of Lecture 17. Would the program still be correct if the FIFO buffers were replaced by LIFO buffers? Motivate your answer.
  4. (s) Consider the solution to the problem of the dining philosophers (Assignment 6).
    1. Is the system deadlock-free?
    2. Is it possible that a philosopher never eats?
    3. Is it possible that a chopstick is never taken?
    4. What happens if notify() in Chopstick.release() is replaced by notifyAll()?
    5. What happens if notify() in Ticket_box.release_ticket() is replaced by notifyAll()?
    6. What happens if the while in Ticket_box.take_ticket() is replaced by if?
    7. What happens if we declare the method Philosopher.try_to_eat() as synchronized? With this modification, could we avoid declaring synchronized the methods of Ticket_box and of Chopstick?
    Motivate your answers.
  5. (s) Consider again the solution to the problem of the dining philosophers. For each of the following modifications, say whether we can have deadlock or not. Justify your answers.
    1. Change the method try_to_eat() so that, after the philosopher has eaten, he releases the ticket first, and then the chopsticks.
    2. There are n tickets
    3. There are n tickets and n+1 chopsticks (i.e. there are two neighbours philosophers such that in between them there are two chospticks instead than one, so that each of them has his own chopstick)
    Motivate your answers.
  6. (s) Consider the second solution to the definition of a buffer with two positions given in Exercise 3.2 of (CSE 428, Spring 99) MT 2.
    1. Suppose that we replace the statement
         synchronized (from) { int k = from.get();  to.put(k); }
      
      in Demon.run() with the statement
         { int k = from.get();  to.put(k); }
      
      (i.e. we eliminate the synchronization on from). Does Buffer2 still represent a buffer with two positions?
    2. Remember that the methods Buffer1.put() and Buffer1.get() are synchronized. Suppose that, instead, we make synchronized the methods Buffer2.put() and Buffer2.get(). Would the solution still be interference-free?
    3. Suppose now that all the methods Buffer1.put(), Buffer1.get(), Buffer2.put() and Buffer2.get() are synchronized. Would the solution still be deadlock-free?
    4. (d) Suppose that we replace the statement
         synchronized (from) { int k = from.get(); to.put(k); }
      
      in Demon.run() with the statement
         if (!to.is_full()) synchronized (from) { int k = from.get(); to.put(k); }
      
      What are the consequences?
  7. Define a process Merge which takes (pops) items from two input queues and inserts them into a output queue. The process should be angelic, in the sense that, if one of the queues is empty, the process should not get stuck trying to pop data from it. Rather, as long as one queue is empty, the merge should proceed processing the data from the other queue only. Furthermore the merge should be arbitrary, in the sense that, when both queues are non-empty, the processing of data from them should be alternated in a random order.
  8. Define a process Ordered_merge which takes input from two ordered queues of integers (i.e queues where the data have been inserted in increasing order), and inserts them, in order and without replications, into an output queue.
  9. Implement in Java a system of processes for the generation of the ordered sequence of the Hamming numbers. The Hamming numbers are those numbers of the form 2k3m5n, where k, m and n are non-negative integers. The system should have the following design:
            +--------+
    +------>| mult_2 |----+
    |       +--------+    |                 1
    |                     v                 |
    |       +--------+   +----------------+ v  +------------+   +-------+
    |  +--->| mult_3 |-->| 3-in_ord_merge |--->| 4-out_copy |-->| print |
    |  |    +--------+   +----------------+    +------------+   +-------+
    |  |                  ^                       |  |  |
    |  |    +--------+    |                       |  |  |
    |  |  +>| mult_5 |----+                       |  |  |       
    |  |  | +--------+                            |  |  |
    |  |  |                                       |  |  |
    |  |  +---------------------------------------+  |  |
    |  +---------------------------------------------+  |
    +---------------------------------------------------+ 
    
    where each box represents a thread, and the lines between boxes are queues. Initially, all queues are empty except the input queue of 4-out_copy, which contains the number 1. mult_n multiplies by n every number from its input queue, and inserts the result into its output queue. 3-in_ord_merge is the ordered merge on three input queues. 4-out_copy replicates the data from its input queue into four output queues. print takes the data from its input queue and visualizes them.