CODEWITHSUNDEEP
multithreadingmutual-exclusiontest-and-set
Dima Chubarov
Dima Chubarov

Reputation: 17159

How to analyze a mutual exclusion algorithm with two atomic test-and-set calls

Someone has posted on this site a simple mutual exclusion algorithm for two threads.

bool locks[2];

thread_function() {
   bool id = get_id();
   while(1) {
     if (!tset(&locks[id])) {
       if (!tset(&locks[!id])) {
         x++; // critical section
         break;
       }
       else locks[id] = false;
     }
   }
   locks[id] = false;
   locks[!id] = false;
}

For Thread0 get_id() returns false and for Thread1 it returns true. Here tset() is an atomic test-and-set function that sets its argument's value to true and returns the previous value.

Before the post was deleted by the author, different users gave different answers to the questions of whether this algorithm is free from race conditions or deadlocks.

How to analyze this algorithm?

Upvotes: 2

Views: 61

Answers (0)

Related Questions