I think your question is more about what primitives are used to implement those, and the answer is - it depends. I will try to focus on modern implementations.
First, Linux uses futex syscall (Fast Userspace muTEX). Two most commonly used operations are FUTEX_WAIT:
This operation tests that the value at the futex word pointed to by
the address uaddr still contains the expected value val, and if so,
then sleeps waiting for a FUTEX_WAKE operation on the futex word.
and FUTEX_WAKE:
This operation wakes at most val of the waiters that are waiting
(e.g., inside FUTEX_WAIT) on the futex word at the address uaddr.
It is very important that FUTEX_WAIT verifies value before sleeping, as this ensures thread does not miss wake-ups.
Using futex(2) it is possible to implement mutex that does not require any syscall if mutex is not contested, but is able to suspend calling thread otherwise. Example below:
struct mutex { int ftx; };
enum { UNLOCKED, LOCKED, CONTESTED };
void mutex_init(struct mutex *mtx)
{
mtx->ftx = UNLOCKED;
}
bool mutex_trylock(struct mutex *mtx)
{
return atomic_cmpxchg(&mtx->ftx, UNLOCKED, LOCKED) == UNLOCKED;
}
void mutex_lock(struct mutex *mtx)
{
if (mutex_trylock(mtx))
return;
while (atomic_xchg(&mtx->ftx, CONTESTED) != UNLOCKED)
futex_wait(&mtx->ftx, CONTESTED);
}
void mutex_unlock(struct mutex *mtx)
{
if (atomic_xchg(&mtx->ftx, UNLOCKED) == CONTESTED)
futex_wake(&mtx->ftx, 1);
}
Semaphore can be implemented like this:
struct sema { int ftx; int waiters; };
enum { LOCKED = 0, CONTESTED = -1 };
void sema_init(struct sema *sem)
{
sem->ftx = LOCKED;
sem->waiters = 0;
}
bool sema_trywait(struct sema *sem)
{
int val = atomic_load(&sem->ftx);
do {
if (val <= LOCKED)
return false;
} while ((val = atomic_cmpxchg(&sem->ftx, val, val - 1)) != val);
return true;
}
void sema_wait(struct sema *sem)
{
if (sema_trywait(sem))
return;
atomic_add(&sem->waiters, 1);
do {
atomic_cmpxchg(&sem->ftx, LOCKED, CONTESTED);
futex_wait(&sem->ftx, CONTESTED);
} while (!sema_trywait(sem));
atomic_sub(&sem->waiters, 1);
}
void sema_post(struct sema *sem, int n)
{
int new, waiters, val = atomic_load(&sem->ftx);
do {
waiters = atomic_load(&sem->waiters);
new = (int) ((unsigned int) val + n + (val < LOCKED));
} while (!atomic_cmpxchg(&sem->ftx, &val, new));
/* The semaphore has been unlocked and could be deallocated,
* so it must not be touch - hence the extra CONTESTED state */
if (val < LOCKED || waiters)
futex_wake(&sem->ftx, n);
}
Condition variables are trickier. Complexity and performance of implementation depends on how much you want to stick to a "classic" interface, mainly whether you allow "notify" to be called outside of critical section or not.
State of condition variable might need to be protected by a separate mutex, so it is common for implementations to keep another mutex within a condition variable. If you allow "notify" to be only called from within critical section, additional mutex locking is not required, making implementation simpler and faster. Such combination of a mutex and a condition variable that only allows "notify" to be called from within critical section is usually called "monitor".
Languages like Java and C# both use monitors instead of mutexes and condition variables.
Another futex(2) trick is FUTEX_REQUEUE operation that can be used to move waiters from one futex to another and can be used to make condition varaible very effecient.
There is a good document "Futexes Are Tricky" about futexes written by Ulrich Drepper. It explains how futex(2) works and shows how it can be used to implemented common primitives. You can find it here.
Another decent article that shows usage of futex(2) is here, but this implementation is too "benchmark oriented".
As for other operating systems, today most provide equivalent of Linux'es futex(2):
WaitOnAddress, WakeOnAddress on Windows 8 and later._umtx_op(2) on OS X, FreeBSD (never used those, you can read more here).- I think OpenBSD partially implements
futex(2) too.
Earlier versions of Windows (7, Vista, XP) are special. They provide alternative undocumented API called "Keyed Events". Just as futex(2), keyed events use table of wait queues hashed by address. There are two operations: "wait" and "release" (wake). This mechanism ensures that wake-ups are not missed by making "release" operation blocking e.g. calling threads is blocked until it actually wakes someone. Using such API requires having waiter counter in userspace. You can read more here.
If you want to see more Keyed Events in action, you should check Wine's sources and their implementation of RTL_SRWLOCK and RTL_CONDITION_VARIABLE.
Keyed events are well suited for condition variables, making implemenation is extremely simple. Condition variable is just a 4 byte counter of waiters.
Following code is simplified, you can check the original here.
void WINAPI RtlWakeConditionVariable( RTL_CONDITION_VARIABLE *variable )
{
if (interlocked_dec_if_nonzero( (int *)&variable->Ptr ))
NtReleaseKeyedEvent( keyed_event, &variable->Ptr, FALSE, NULL);
}
void WINAPI RtlWakeAllConditionVariable( RTL_CONDITION_VARIABLE *variable )
{
int val = interlocked_xchg( (int *)&variable->Ptr, 0 );
while (val-- > 0)
NtReleaseKeyedEvent( keyed_event, &variable->Ptr, FALSE, NULL);
}
void RtlSleepConditionVariableSRW(
RTL_CONDITION_VARIABLE *variable, RTL_SRWLOCK *lock)
{
interlocked_xchg_add( (int *)&variable->Ptr, 1 );
RtlReleaseSRWLockExclusive( lock );
NtWaitForKeyedEvent( keyed_event, &variable->Ptr, FALSE, timeout );
RtlAcquireSRWLockExclusive( lock );
}
Another way is to emulate futex-like functionality in userspace. WebKit's ParkingLot is an example of this. You can read more here. Mechanism is basically the same as with futex(2), but since it is implemented in userspace it allows execution of custom user code from inside the queue lock. This makes it possible to store less information in synchronization object and be overall smarter with thread scheduling. Unfortunately, performance in contested case will most likely be slower, as it will use futex(2) underneath anyway to block the calling thread, so there is an additional layer of code and locking that needs to be executed.
WebKit implementation lacks FUTEX_REQUEUE equivalent, although it is possible to add this if needed.
