2023年11月25日

Java代写 | Assignment 2: Synchronisation CSSE7610

本次Java代写是用多线程模拟呼叫中心

Assignment 2: Synchronisation CSSE7610

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