Consider the following mutual exclusion algorithm for n processors (Algorithm 4.7), suggested by Lamport.

(In PDF.)

# Question 1

Prove that the algorithm provides __mutual exclusion__.

__Hint.__** Suppose in contradiction that there is a configuration when two processors, p _{i} and p_{j}, are in the critical section simultaneously. Observe all the possible cases, e.g.: p_{i} enters through the fast path whereas p_{j} enters through the slow path, etc.**

# Question 2

Prove the no deadlock property of the algorithm.

**Hint.** Assume that there is a

*deadlock*, i.e., some processors are trying to enter the critical section, and none of them succeeds (although the execution is infinite).

**Show that there is no processor that continually executes**goto*in Line 6 or Line 13.**Show that all the processors cannot be forever stuck waiting in Line 5/Line 10/Line 12.*

# Question 3

Does the algorithm satisfy the __no lockout__ property?