Cheap and Secure Web Hosting Provider : See Now

[Solved]: Does mutual exclusion hold in this case?

, , No Comments
Problem Detail: 

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.


  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$


  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.

Asked By : pratz

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback