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?
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?