讲解CSSE7610、辅导Java程序、辅导Java编程、FIFO C语言

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 understand

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 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 algorithm

above to have a second consumer process r which consumes

items from the same end that they are enqueued. Your modified program

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 synchronisation

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 Question

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 synchronized,

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 program

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 welldocumented

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 submitted

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)