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

70 Views Asked by At

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?

0

There are 0 best solutions below