COMP3151/COMP9151 Foundations of Concurrency Final Exam

Shared-variabIe concurrency (20 Marks)

Question 1  (10 marks)

Algorithm 6 below is a close relative of peterson,s algorithm for the critical section problem. It solves the critical section problem.

(a)  Does Algorithm 6 still solve the critical section problem if we swap lines 2 and 3, that is, exchange statement p2 with statement p3 and exchange statement q2 with statement q3？

(b)  consider another variant of Algorithm 6 above where the statement await  b[1] = false is added at the end of the code of process p.  Does the modiied algorithm satisfy deadlock freedom？

(c)  consider the same variant of Algorithm 6 as in part b.   Does the modiied algorithm satisfy eventual entry？

Justify each of your answers briely.

Question 2  (10 marks)

The sauings Account PToblem. A savings account is shared by several people (processes).  Each person may deposit or withdraw funds from the account.  The current balance in the account is the sum of all deposits to date minus the sum of all withdrawals to date.   The  balance must never become negative.  A deposit never has to delay (except for mutual exclusion), but a withdrawal has to wait until there are su伍cient funds.   withdrawals have to be serviced irst-come-irst-served.

Develop  a  monitor  to  solve  this  problem. The monitor  should  have  two  procedures:   de- posit(amount) and withdraw(amount).  specify a monitor invariant.  Assume the arguments to deposit and withdraw are positive.  use the signal-and-continue discipline.  Explain how your solution implements each of the requirements.

Message-passing concurrency (30 Marks)

Question 3  (8 marks)

Two kinds of processes, A,s and B,s, enter a room.  An B process cannot leave until it meets two A processes and an A process cannot leave until it meets a B process.  Each process leaves the room—without meeting any other processes—once it has met the required number of other processes.

(a)  Develop a server process to implement this synchronisation.  show the interface of the processes modelling individual A and B processes.

(b)  Modify your answer to a so that the irst of the two A processes that meets a B process does not leave the room until after the B process meets a second A process.

use promela (with message passing primitives only) to express your solutions.

Question 4  (10 marks)

Consider the synchronous transition diagram in Fig. 1 and prove

with Levin & Gries or AFR for full marks or via semantics and Floyd for half marks.

Question 5  (12 marks)

system modeI:    The system comprises of n E ” nodes named 1）. . . ）n.  Nodes communicate by passing messages over asynchronous, reliable channels.  Every node can send messages to every other node. Nodes have unique IDs. Neither nodes nor channels crash.

Each process has a  clock  CLi  that ranges over the non-negative integers and starts at 0.  A timestamp is a pair (cv）i) consisting of a clock value and a process ID. Timestamps are ordered lexicographically, that is, we use the process IDs to break ties to have a total order on process, clock values.

Nodes execute local actions, sends, and receives.  These actions are augmented as follows to accommodate timestamping.

.  Every local action increments the clock by 1.

.  Every send of a message m of node i is replaced by (a) incrementing the clock, CLi ++, followed by (b) sending (m）(CLi）i)).

. whenever anode i receives any message timestamped with (U）k), it updates its clock CLi to max(CLi）U) + 1.

Each node i maintains an initially empty Tequest queue Tqi consisting of timestamped messages, ordered lexicographically by their timestamps.

The following protocol is proposed to solve the critical section problem with the aid of times- tamps. For simplicity, the individual actions such as R1 can be assumed to be atomic.

Requesting access.

R1 when node i wants to enter its Cs, it sends a REQUEST message to all other nodes, and places the request (REQUEST）(CLi）i)) on its own request queue Tqi. (Recall that irst the clock is incremented and that all the messages are timestamped.)

R2  when a node k receives a message REQUEST from i, it places node i,s request on its request queue Tqk  and sends a REPL、message to i.

Gaining access.   Node i enters its Cs when both

A1 i has received from every other node a message with timestamp lexicographically greater

than the timestamp of its own REQUEST, and

A2  i,s own request is at the head of Tqi.

ReIeasing the Cs.

E1  upon exiting the Cs,node i removes its request from Tqi  and sends a timestamped RELEASE message to all other nodes.

E2 when node k receives RELEASE from i, it removes i,s request from its request queue Tqk .

In the context of the model and algorithm outlined above,  answer the following questions. Justify your answers.

(a)  show that this algorithm does not guarantee mutual exclusion.