Mutual Exclusion Algorithm by Raymond Recall that the lines are Not FIFO but the

Question

Mutual Exclusion Algorithm by Raymond

Recall that the lines are Not FIFO but the input ports are FIFO. Will the new algorithm work(YESor NO)? If Yes give an explanation, If No give an example

Assume there are exactly two processes in the system P1 and P2. initially, the value of HOLDER at P1 is P2.

In the end, tell us what went wrong and what correctness property (safety, liveness, or fairness) is violated.

Q1. Make the following change: the third rule (R3) in the code is removed. this is the rule that says"the node recieves a PRIVILEGE message"

Q2. Make the following change in the rule R3 (which is related to receiving a PRIVILEDGE message). MAKE_REQUEST is deleted from this rule.

Explanation / Answer

Lamport's Mutual Exclusion Algorithm

* Are these the single-integer valued clocks, or the vector clocks?

The Algorithm

Correctness

Suppose Si and Sj are executing the CS concurrently.

L1 and L2 must hold at both sites concurrently.

Si and Sj both have requests at top of their queues and L1 holds, at some instant t.

WLOG suppose Si's request has earlier timestamp than Sj's.
(Remember the tie-breaking rule!)

Assuming communication channels are FIFO, at instant t Si's request is queued at Sj, when Sj is in the CS and Sj's own request is at the top of the queue, ahead of a smaller timestamp request.

This is a contradiction.

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.