关键词 > COMP3151/9154

COMP3151/9154 Homework 7

发布时间：2023-08-28

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP3151/9154

Homework 7

Due: 9:00 Monday Jul 24, 2023

1 Process algebra

1. We saw a large number of algebraic laws of CCS in the lecture on CCS. Here are some more proposed laws. Briefly discuss the merits of each proposed law, and whether you think it should be accepted. If you think it should be accepted, give an informal intution for why; if you think not, give a concrete example where it has absurd consequences. a) P | P = P

b) P / b / b = P / b

c) (a.P)|(a.Q) = a.(P|Q)

2. Consider the CCS processes P = a.b.P and Q = a.b.Q. Draw the labelled transition system for the process (P|Q) / a, and justify each transition by means of a proof using the operational semantics of CCS.

2 Ricart-Agrawala Algorithm

Pseudocode of the Ricart-Agrawala Algorithm is:

a) Suppose that we exchanged the lines p8 and p9–p11 in Main, i.e. requestCS ← false now executes after the for loop (instead of executing be- fore the for loop). Suppose furthermore that it’s possible for Receive to preempt Main at these locations. Provide an example that illustrates why the modified algorithm is no longer correct.

b) In Receive, can the statement p2: highestNum ← max(highestNum, requestNum) be replaced by p2: highestNum ← requestNum? Why? Justify your answer

and provide an example.

In both parts of this question, you can sketch diagrams in addition to textual explanations. However, if your textual explanations are clear, such diagrams might be unnecessary.

3 Token-Passing

Pseudocode of the Ricart-Agrawala Token-passing Algorithm is:

a) In node i, can the value of requested[j] be less than the value of granted[j] for j i? Why? Justify your answer.

b) In node i, can the value of requested[j] be greater than the value of granted[j] for j i? Why? Justify your answer.