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 欢迎咨询51作业君