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

Tutorial 2: Mutual Exclusion

CSSE7610

The exercises below are from Chapter 3 of M. Ben-Ari Principles of Concurrent and Distributed Programming (second edition), 2006.

The questions refer to the algorithms from Week 2’s lectures.

1. Construct the state diagram for the abbreviated version of the second attempt algorithm.

2. Construct the state diagram for (an abbreviated version of) the third at-tempt algorithm. Use it to show mutual exclusion holds for the algorithm.

3. For the fourth attempt algorithm:

(a) Construct a scenario in which both processes are starved.

(b) Explain why this scenario is considered to be starvation and not deadlock as in the third attempt.

(c) Construct a scenario in which one process is starved while the other enters its critical section infinitely often.

4. Prove whether or not the algorithm for the critical section using test-and-set is correct.

test-and-set(common, local) is

local ← common

common ← 1

5. Write an algorithm for the critical section problem using compare-and-swap (CAS).

compare-and-swap(common,old,new) is

integer temp

temp ← common

if common = old

common ← new

return temp