Suppose we have the Manna-Pnueli algorithm for mutual exclusion: Manna-Pnueli algorithm

I was trying to find a sequence that violates mutual exclusion and I came up with this:

1. q1, q3; wantq=-1
2. p1
3. q4, q5; wantq=0
4. q1
5. p2; wantp=-1
6. p4
7. q3; wantq=-1
8. q4
9. p and q in critical section

Is my reasoning correct, supposing if is not atomic?

Also, were it atomic, how would I prove it to be correct? Should I just list all the possible combinations?

  • $\begingroup$ 1. We prefer you ask only one question per question, please. 2. We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Apr 23, 2016 at 4:21
  • $\begingroup$ 3. Regarding proof, what are your thoughts? What is preventing you from answering the question on your own? What approaches have you considered, and why did you reject them? You mention the idea of listing all the possible combinations; what specifically are you unsure about that? $\endgroup$
    – D.W.
    Apr 23, 2016 at 4:23


Your Answer

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

Browse other questions tagged or ask your own question.