multithreadingconcurrencylanguage-agnosticatomictest-and-set

Implementing a mutex with test-and-set atomic operation: will it work for more than 2 threads?


I'm reading the Wikipedia article on the test-and-set atomic operation. It says that one way to implement mutual exclusion is by using a test-and-set based lock.

However, according to the same article, the test-and-set operation has a finite consensus number and can solve the wait-free consensus problem for at-most two concurrent processes.

So does a mutex based on the test-and-set operation work only for two threads? If so, how are "actual" mutexes implemented?


Solution

  • One thing to note is that mutual exclusion is essentially the equivalent of consensus for 2 threads. In other words, it is not necessary to have n-thread consensus to implement mutual exclusion. -- @Eric's comment

    I strongly recommend reading The Art of Multiprocessor Programming, from Maurice Herlihy and Nir Shavit. Actually, the test-and-set Wikipedia page cite an article of Herlihy to state that "test-and-set has a finite consensus number and can solve the wait-free consensus problem for at-most two concurrent processes".

    The chapter 5 of the book discusses consensus using primitive synchronization operations, but I believe chapter 7 will caught your interest: they discuss how a TAS (test-and-set) instruction can be used to implement a lock in Java. Spoiler from page 145:

    public class TASLock implements Lock {
      AtomicBoolean state = new AtomicBoolean(false);
      public void lock() {
        while (state.getAndSet(true)) {}
      }
      public void unlock() {
        state.set(false);
      }
    }
    

    So does a mutex based on the test-and-set operation work only for two threads?

    The simple answer is: no, they work for more than two threads.

    If so, how are "actual" mutexes implemented?

    The same Wikipedia page cites CAS (compare-and-swap) as a more powerful alternative to TAS, but the book present an extensive discussion on the matter. Moreover, this was already asked here in SO, so I recommend reading through the answers of How are mutexes implemented?