3
$\begingroup$

I entered into a discussion with a friend on the following question, which asks if mutual exclusion holds:

Consider two processes:

$s_1$ and $s_2$ are two variables, set equal initially.

P1:

  1. while $s_1 = s_2$: wait.

  2. /execute critical section/

  3. $s_1$ is set such that it is not equal to $s_2$

P2:

  1. while $s_1 = s_2$: wait.

  2. /execute critical section/

  3. $s_1$ is set such that it is not equal to $s_2$

My friend argues that mutual exclusion holds. His explanation:

Mutual Exclusion holds if the following implication holds: If a process is in its critical section, then other processes should not be allowed in their critical sections.

Consider this implication as $P \to Q$. He argues that since the premise $P$ is wrong (because none of P1 and P2 are in their critical sections), the implication is true and hence mutual exclusion holds.

Whereas my thinking is that when none of the processes get to enter their critical section, talking about mutual exclusion is pointless and hence the property doesn't hold.

Is the implication way of thinking the correct approach? I feel that it's not, but I have not been able to prove my intuition.

$\endgroup$
  • $\begingroup$ What worries me here that this is wrong at more than one level. 1. the current version deadlocks right away. 2. one could be tempted in switching the $=$ in P2's step 1 for $\neq$ and vice versa in step 3. Now the deadlock is gone but it's wrong again. Maybe discuss with your friend why. $\endgroup$ – Kai Dec 6 '16 at 9:16
  • $\begingroup$ Mutual exclusion is a safety property: it simply states that bad things do not happen. A stuck system like that satisfies safety. Then there are liveness properties, requiring that good things do happen eventually. The algorithm above fails liveness. $\endgroup$ – chi Dec 6 '16 at 10:46
  • $\begingroup$ @Kai: It was just a puzzle kind of thing we were discussing. I agree that this is not a proper solution for the critical section problem. $\endgroup$ – pratz Dec 6 '16 at 11:16
6
$\begingroup$

Your friend is correct. In your context, mutual exclusion holds if at most one process is at a critical section at any given time.

You state that you feel that this interpretation is wrong, but you have not been able to prove your intuition. You cannot prove a definition! What you are really saying is that the concept of mutual exclusion is vacuous if no process is ever in a critical section. To some extent you are correct—this agrees with colloquial usage. The same colloquial usage also states that "A or B" has the connotation of "A or B, but not both". When dealing with formal concepts you have to forgo the colloquial point of view, trading it with the mathematical point of view.

$\endgroup$
  • $\begingroup$ Thanks for clarifying @Yuval. Actually, I gave the same colloquial usage of "A or B" to my friend in order to convince him. But I felt that textbook definitions meant the colloquial usage. $\endgroup$ – pratz Dec 6 '16 at 7:41
4
$\begingroup$

A mutual exclusion solution should satisfy not only the mutual exclusion property but also the deadlock property. Deadlock occurs when one or more processes are "trying to enter" their critical sections, but no process ever does. See Lamport@JACM'86; Page 6.

Although the algorithm you describe trivially satisfies the mutual exclusion property (and the implication proof of your friend is correct), it does not satisfy the deadlock property. Thus, strictly speaking, this algorithm is not a sensible mutual exclusion solution.

$\endgroup$
  • $\begingroup$ More commonly the property we care about is know an eventual entry: If a process intends to enter its CS it will eventually succeed in doing so. $\endgroup$ – Kai Dec 6 '16 at 9:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.