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.

^{(s)}
Consider the example of the producers and consumers in the
LN of
Lecture 16. It is possible to see that the system is deadlockfree, in fact
 Initially the buffer is empty and no threads are in the waiting state (i.e. in the
wait set associated to the buffer).
 When a producer inserts a datum in the buffer, all threads exit the wait set of the buffer.
One consumer will be able to proceed.
 When a consumer removes the datum from the buffer, all threads exit the wait set of the buffer.
One producer will be able to proceed.
For each of the following modifications, say whether we lose the property of deadlockfreedom
or not. Justify your answers.
 One producer instead of three, and still two consumers.
 Use notify() instead of notifyAll() in the get() method.
Note: the method notify() removes an arbitrary thread from the wait set of the object.
 One producer, two consumers,
and use notify() instead of notifyAll()
in the put() method.
 Invert the order of the statements is_empty = false and
notifyAll() in the put() method.
 ^{(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.

^{(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.

^{(s)}
Consider the solution
to the problem of the
dining philosophers (Assignment 6).
 Is the system deadlockfree?
 Is it possible that a philosopher never eats?
 Is it possible that a chopstick is never taken?
 What happens if notify() in Chopstick.release()
is replaced by notifyAll()?
 What happens if notify() in Ticket_box.release_ticket()
is replaced by notifyAll()?
 What happens if the while in Ticket_box.take_ticket()
is replaced by if?
 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.

^{(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.
 Change the method try_to_eat() so that, after the philosopher
has eaten,
he releases the ticket first, and then the chopsticks.
 There are n tickets
 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.

^{(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.
 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?
 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 interferencefree?
 Suppose now that all the methods Buffer1.put(),
Buffer1.get(), Buffer2.put() and
Buffer2.get() are synchronized.
Would the solution still be deadlockfree?
 ^{(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?

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 nonempty, the processing of
data from them should be alternated in a
random order.

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.

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
2^{k}3^{m}5^{n}, where k, m and n are nonnegative
integers.
The system should have the following design:
++
+> mult_2 +
 ++  1
 v 
 ++ ++ v ++ ++
 +> mult_3 > 3in_ord_merge > 4out_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 4out_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.
3in_ord_merge is the ordered merge on three input queues.
4out_copy replicates the data from its input queue into four output
queues.
print takes the data from its input queue and visualizes them.