Assignment 2: Synchronisation CSSE7610
Answer questions 1 to 3 below. This assignment is worth 25% of your final
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/ite…
Due date and time: Friday 22 October, 4pm
- A bounded buffer is frequently implemented as a circular buffer, which is
an array that is indexed modulo its length:
One variable, in, contains the index of the first empty space (if any)
and another, out, the index of the first full space. If in > out , there
is data in buffer[out..in-1]; if in < out , there is data in buffer[out..N-1]
and buffer[0..in-1]; if in = out , the buffer 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 buffer:
Producer-consumer (circular buffer)
dataType array [0..N-1] buffer
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 ← buffer[out]
p3: buffer[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 buffer 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 modified pro-
gram must use a circular buffer, 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. Briefly justify each synchronisa-
tion mechanism introduced.
Deliverable: A file circular.pdf containing your answers to (a) and (b),
and your name and student number.
- Write a Promela specification for your modified 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 buffer is empty, and never appended
when the buffer 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 file deque.pml containing the Promela specification, a
comment describing the property you proved, and your name and student
number (as a comment). - 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 first.
? 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 first 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 file containing a file CallCentre1.java with your
main method for the first program, and a file CallCentre2.java with your
main method for the second program, along with all supporting source
(.java) files (apart from Event), and a file 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 files should be well-
documented and in particular the code for synchronisation should be well
explained. All files 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 files 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 efficiency. 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)
Modification of algorithm (3 marks)
Justification of synchronisation constructs (3 marks)
Question 2 (4 marks)
Promela specification of algorithm (3 marks)
Property for correctness (1 mark)
Question 3 (13 marks)
readme file (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)