CS计算机代考程序代写 data structure Java concurrency algorithm Semester Two Final Examinations, 2019 CSSE7610 Concurrency: Theory and Practice

Semester Two Final Examinations, 2019 CSSE7610 Concurrency: Theory and Practice

Page 1 of 4

This exam paper must not be removed from the venue

School of Information Technology and Electrical Engineering

EXAMINATION

Semester Two Final Examinations, 2019

CSSE7610 Concurrency: Theory and Practice

This paper is for St Lucia Campus students.

Examination Duration: 120 minutes

Reading Time: 10 minutes

Exam Conditions:

This is a Central Examination

This is a Closed Book Examination – specified materials permitted

During reading time – write only on the rough paper provided

This examination paper will be released to the Library

Materials Permitted In The Exam Venue:

(No electronic aids are permitted e.g. laptops, phones)

Calculators – No calculators permitted

One A4 sheet of handwritten or typed notes double sided is permitted

Materials To Be Supplied To Students:

1 x 14-Page Answer Booklet

Instructions To Students:

You must hand in your crib sheet when you submit your examination.

Answer all questions in the supplied answer booklet.

Additional exam materials (eg. answer booklets, rough paper) will be
provided upon request.

Total marks = 50

Venue
____________________

Seat Number ________

Student Number
|__|__|__|__|__|__|__|__|

Family Name
_____________________

First Name
_____________________

For Examiner Use Only

Question
Mark

Total ________

Semester Two Final Examinations, 2019 CSSE7610 Concurrency: Theory and Practice

Page 2 of 4

Question 1. 15 marks
Consider the following algorithm for the critical section problem. The Doran-Thomas
algorithm is a variant of Dekker’s algorithm.

Doran-Thomas algorithm

Boolean wantp  false, wantq  false
Integer turn  1

p q

Loop forever
p1: non-critical section
p2: wantp true
p3: if wantq
p4: if turn = 2
p5: wantp  false
p6: await turn = 1
p7: wantp  true
p8: await wantq = false
p9: critical section
p10: wantp  false
p11: turn  2

Loop forever
p1: non-critical section
p2: wantq true
p3: if wantp
p4: if turn = 1
p5: wantq  false
p6: await turn = 2
p7: wantq  true
p8: await wantp = false
p9: critical section
p10: wantq  false
p11: turn  1

(a) Provide a proof by induction that the algorithm ensures mutual exclusion. If you
require other invariants in your proof, they must appear as lemmas and also be
proved by induction. (5 marks)

(b) Use Linear Temporal Logic (LTL) to state that the algorithm is deadlock-free.
Argue informally whether the algorithm satisfies this property. (5 marks)

(c) Use Linear Temporal Logic (LTL) to state that the algorithm is starvation-free.
Argue informally whether the algorithm satisfies this property for two processes.
Argue informally whether the algorithm satisfies this property for n processes.
(5 marks)

Semester Two Final Examinations, 2019 CSSE7610 Concurrency: Theory and Practice

Page 3 of 4

Question 2 15 marks
A queue is a first-in-first out (FIFO) data structure with operations: enqueue, to add an
element to the tail of the queue and dequeue, to remove an element from the front of
the queue (or throw an exception if the queue is empty). Consider the following
concurrent linked-list implementation of a queue in Java.

public class ConcurrentQueue {

class Node {

T item;

AtomicReference next;

Node(T item) { this.item = item; }

}

private AtomicReference> head =

new AtomicReference>();

public void enqueue(T item) …

public T dequeue () throws EmptyQueueException …

}

(a) Provide the code for a simple implementation of the enqueue and dequeue methods
for a concurrent queue. (6 marks)

(b) A simple implementation of a concurrent queue does not scale well. Explain why this
is the case. Provide explanations of two different approaches that could be used to
improve the performance of a concurrent queue. (9 marks)

Question 3 10 marks
Let P1, P2 and P3 be three tasks. Is the earliest deadline first (EDF) scheduling algorithm
feasible for the following timing constraints? Provide a scheduling diagram which shows
the first two times P3 is scheduled.

D1 = p1 = 8, e1 = 4, r1 = 0

D2 = p2 = 10, e2 = 2, r2 = 0

D3 = p3 = 12, e3 = 3, r3 = 2

where Di is the (relative) deadline, pi is the period, ei is the execution time, and ri is the
release time of process Pi.

Semester Two Final Examinations, 2019 CSSE7610 Concurrency: Theory and Practice

Page 4 of 4

Question 4 10 marks
A disk scheduling algorithm has the head start at one end of the disk and move towards
the other end. When the head is moving up, it services requests at or above the current
position, then reverses direction and services all requests at or below the current
position. The head continuously scans back and forth across the disk.

The head can be called to a destination by calling request(i). The request moves the
head to the destination i. After it has finished servicing the request, it is released by
calling release().

The monitor will require two condition variables: upsweep when moving up and
downsweep when moving down. A request must place itself in the correct queue: if the
current position < destination, wait in upsweep or if the current position > destination,
wait in downsweep. If the current position = destination, wait in upsweep or downsweep
depending on the current direction.

Design an algorithm for a monitor that simulates the disk scheduler.

END OF EXAMINATION