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/itee-student-misconduct-including-plagiarism
Due date and time: Friday 23 October, 5pm
1. A bounded buffer is frequently implemented as a circular buffer, which is
an array that is indexed modulo its length:
TT
in out
TT
out in
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
loop forever
p1: d ← produce
p2: wait(notFull)
p3: buffer[in] ← d
p4: in ← (in+1) modulo N
p5: signal(notEmpty)
dataType d
loop forever
q1: wait(notEmpty)
q2: d ← buffer[out]
q3: out ← (out+1) modulo N
q4: signal(notFull)
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.
2. 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).
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 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
• Modification of algorithm
• Justification of synchronisation constructs
Question 2 (4 marks)
• Promela specification of algorithm
• Property for correctness Question 3 (13 marks)
• readme file
• Java program utilising your design from Question 1(b)
– program displays correct behaviour
– program correctly implements your design
– appropriate use of Java synchronisation constructs
• Java program utilising class(es) from java.util.concurrent – program displays correct behaviour
– most appropriate class(es) from java.util.concurrent used
(2 mark) (3 marks) (3 marks)
(3 marks) (1 mark)
(1 mark)
(3 marks) (3 marks) (2 marks)
(2 marks) (2 marks)
4