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
Node(T item) { this.item = item; }
}
private AtomicReference
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