Assignment 2: Synchronisation CSSE7610
Answer questions 1 to 3 below. This assignment is worth 25% of your nal
mark. It is to be completed individually, and you are required to read and un-
derstand the School Statement on Misconduct, available on the School’s website
at: http://www.itee.uq.edu.au/itee-student-misconduct-including-plagiarism
Due date and time: Friday 12 October, 5pm
1. A bounded bu er is frequently implemented as a circular bu er, which is
an array that is indexed modulo its length:
in out
6 6
One variable, in, contains the index of the rst empty space (if any)
and another, out, the index of the rst full space. If in > out, there
is data in bu er[out..in-1]; if in < out, there is data in bu er[out..N-1]
and bu er[0..in-1]; if in = out, the bu er is either empty (when in is the
index of an empty space) or full. Consider the following algorithm for the
producer-consumer problem with a circular bu er:
Producer-consumer (circular bu er)
dataType array [0..N-1] bu er
integer in, out 0
semaphore notEmpty (0;?)
semaphore notFull (N;?)
p q
dataType d dataType d
loop forever loop forever
p1: d produce q1: wait(notEmpty)
p2: wait(notFull) q2: d bu er[out]
p3: bu er[in] d q3: out (out+1) modulo N
p4: in (in+1) modulo N q4: signal(notFull)
p5: signal(notEmpty) q5: consume(d)
1
(a) The algorithm is essentially the same as the standard semaphore
solution to the producer-consumer problem, except that appending
and taking items from the bu er is not atomic. Explain why the
algorithm is still correct, or provide a counter-example to show how
it can fail.
(b) A deque (pronounced \deck") is a double-ended queue. It allows
items to be enqueued and dequeued from either end. Modify the al-
gorithm above to have a second consumer process r which consumes
items from the same end that they are enqueued. Your modi ed pro-
gram must use a circular bu er, and must ensure that processes do
not interfere with each others’ operation. You may use semaphores
and/or monitors to achieve the latter, however no process should
ever be blocked unnecessarily. Brie y justify each synchronisa-
tion mechanism introduced.
Deliverable: A le circular.pdf containing your answers to (a) and (b),
and your name and student number.
2. Write a Promela speci cation for your modi ed algorithm from Ques-
tion 1(b), and use Spin to prove that it is correct. Correctness requires
that an item is never taken when the bu er is empty, and never appended
when the bu er is full. You may require auxiliary variables to express the
correctness property. Note that the modulo operator in Promela is % (as
in C and Java).
Deliverables: A le deque.pml containing the Promela speci cation, a
comment describing the property you proved, and your name and student
number (as a comment).
3. A call centre has 3 queues of incoming calls each serviced by a single
worker. Each queue holds a maximum of 5 calls. The operation of the call
centre is as follows:
Initially, the 3 workers should choose a queue to service. The decision
as to which queue a worker services should not be made centrally, but
by the worker themselves (based on a random choice of the queues
that are available).
Once all workers have a queue, they should answer the calls in their
queue on a FIFO basis, i.e. the earliest call should be answered rst.
A worker with an empty queue should \steal" a call from the queue of
another worker if possible. To avoid contention with the other worker,
they should steal the last call to arrive (rather than the earliest).
2
Write two Java programs to simulate the call centre. The rst program
should use your deque algorithm from Question 1(b) and Java’s synchro-
nized, wait and notify constructs. It should not use any classes from
java.util.concurrent. Recall that a semaphore can be implemented by a
monitor. The second program need not use your deque algorithm and
should use one or more classes from java.util.concurrent to make the pro-
gram as simple and elegant as possible. Any class from java.util.concurrent
can be used, not only those that have been covered in lectures.
Both programs should create (in addition to the 3 worker threads), 25
caller threads which after a random time append a call to a queue and then
terminate. When all calls have been answered, the entire program should
terminate gracefully, i.e., all threads should reach the end of their run
methods. Both programs should produce output by calling the appropriate
methods of the provided class Event.java. For testing purposes, it is a
requirement that you call the Event class every time one of the events
occurs. It is also important that you do not modify the provided class.
Deliverables: A zip le containing a le CallCentre1.java with your
main method for the rst program, and a le CallCentre2.java with your
main method for the second program, along with all supporting source
(.java) les (apart from Event), and a le readme.txt describing (in a few
paragraphs) the approach you have taken to coding each program and
providing a list of all your classes and their roles. All les should be well-
documented and in particular the code for synchronisation should be well
explained. All les should also contain your name and student number
(as a comment).
To assist with our testing of your Java code. Please do not make your sub-
mitted les dependent on being in a particular package. That is, remove
any lines:
package packageName;
Note: Care needs to be taken when using immutable classes in Java for
locks. For example,
Integer lock1 = new Integer(0);
Integer lock2 = new Integer(0);
will not result in two distinct locks, but a single lock with aliases lock1 and
lock2. This is because Java will share a single Integer object with value 0
between the variables for reasons of e ciency. Therefore, you need to use
mutable objects for locks, or immutable object with distinct values.
3
Marking criteria
Marks will be given for the correctness and readability of answers to questions 1
to 3 as follows.
Question 1 (8 marks)
Correctness of original algorithm (2 mark)
Modi cation of algorithm (3 marks)
Justi cation of synchronisation constructs (3 marks)
Question 2 (4 marks)
Promela speci cation of algorithm (3 marks)
Property for correctness (1 mark)
Question 3 (13 marks)
readme le (1 mark)
Java program utilising your design from Question 1(b)
{ program displays correct behaviour (3 marks)
{ program correctly implements your design (3 marks)
{ appropriate use of Java synchronisation constructs (2 marks)
Java program utilising class(es) from java.util.concurrent
{ program displays correct behaviour (2 marks)
{ most appropriate class(es) from java.util.concurrent used (2 marks)