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?

`test-and-set` can certainly be used to implement mutual exclusion for more than 2 threads. It looks like the point they make is that with a higher thread number, it can no no longer be done 'wait-free' (i.e. in a finite number of steps) — curiousguy12, Jun 23 '19 at 16:20
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, Jun 24 '19 at 11:28

Dinei · Accepted Answer · 2019-06-25T23:11:49.940

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?

I think you meant to write "it can provide _consensus_ for more than two threads, but not in a wait-free manner. Mutual exclusion can definitely be solved using TAS for more than 2 threads in a wait-free manner because solving the mutual exclusion problem is equivalent to solving consensus for 2 threads (do I get to enter the critical section or not?) — Eric, Jun 24 '19 at 10:56
You're right @Eric. I made a mistake trying to oversimplify things. I removed this part of the answer to keep it simple, and copied your comment in the question. A more detailed explanation on the subject can be found in the [Herlihy's article](http://cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf) referred in the answer. — Dinei, Jun 25 '19 at 23:14

score 1 · Answer 2 · answered Jun 25 '19 at 23:15

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

Atomic read and write (you have that with the test-and-set operator);
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!

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

2 Answers2