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

Question

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?

Answer 1

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?

Answer 2

The "correct" solution is to have an "uninterruptible mode" flag that has the following properties:

1. Atomic read and write (you have that with the test-and-set operator);
2. Your application cannot be interrupted under any conditions (thread rescheduling, etc.) while this is set.

You have one holding thread under a mutex and n waiting threads, which are placed in a queue (any kind of list, but I prefer a queue.) On mutex lock, you go into uninterruptible mode by atomically test/setting your flag (spin or sleep while the flag is set,) and either acquire the mutex or enter the queue to do so (in the latter case, the current thread cannot reenter the scheduler's ready queue.) On unlock, you go into uninterruptible mode and relinquish the mutex to the next thread in the queue, if any.

I think libpthread and such implement mutexes in this fashion. It's not a hard thing to do, per se, but solutions are either definitively correct or incorrect.

Hope this makes sense!