Penso che la tua domanda riguardi maggiormente le primitive utilizzate per implementarle e la risposta è - dipende. Cercherò di concentrarmi sulle implementazioni moderne.
In primo luogo, Linux utilizza futex syscall ( F ast U serspace mu TEX ). Le due operazioni più comuni sono 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.
e 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.
È molto importante che FUTEX_WAIT verifichi il valore prima di andare a dormire, poiché ciò garantisce che il thread non si dimentichi dei wake-up.
Usando futex(2) è possibile implementare il mutex che non richiede alcun syscall se il mutex non è contestato, ma è in grado di sospendere altrimenti il thread chiamante. Esempio di seguito:
struct mutex { int ftx; };
enum { UNLOCKED, LOCKED, CONTESTED };
void mutex_init(struct mutex *mtx)
{
mtx->ftx = UNLOCKED;
}
void mutex_lock(struct mutex *mtx)
{
if (atomic_cmpxchg(&mtx->ftx, UNLOCKED, LOCKED) == UNLOCKED)
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);
}
Il semaforo può essere implementato in questo modo:
struct sema { int ftx; int waiters; };
void sema_init(struct sema *sem)
{
sem->ftx = 0;
sem->waiters = 0;
}
bool sema_trywait(struct sema *sem)
{
int val = atomic_load(&sem->ftx);
do {
if (val == 0)
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 {
futex_wait(&sem->ftx, 0);
} while (!sema_trywait(sem));
atomic_sub(&sem->waiters, 1);
}
void sema_post(struct sema *sem, int n)
{
int val = atomic_load(&sem->ftx);
while ((val = atomic_cmpxchg(&sem->ftx, val, val + n)) != val)
{ }
// This accesses semaphore after unlocking. What if it was destroyed?
// You can try to think about how this can be fixed.
// I won't put correct implementation here due to higher complexity.
if (atomic_load(&sem->waiters) != 0)
futex_wake(&sem->ftx, n); // no point in waking more than 'n'
}
Le variabili di condizione sono più difficili. La complessità e le prestazioni di implementazione dipendono da quanto si vuole attenersi a un'interfaccia "classica", principalmente se si consente "notifica" per essere chiamato al di fuori della sezione critica o no.
La variabile stato di condizione potrebbe dover essere protetta da un mutex separato, quindi è normale che le implementazioni mantengano un altro mutex all'interno di una variabile di condizione. Se si consente di chiamare "notify" solo all'interno della sezione critica, non è richiesto un blocco mutex aggiuntivo, rendendo l'implementazione più semplice e veloce. Tale combinazione di mutex e una variabile di condizione che consente solo di chiamare "notify" dalla sezione critica di solito è chiamata "monitor".
Lingue come Java e C # utilizzano entrambi i monitor anziché i mutex e le variabili di condizione.
Un altro trucco futex(2) è un'operazione FUTEX_REQUEUE che può essere utilizzato per spostare i camerieri da un futex a un altro e può essere utilizzato per rendere la condizione varaible molto efficace.
C'è un buon documento "Futexes Tricky" sui futex scritti da Ulrich Drepper. Spiega come funziona futex(2) e mostra come può essere utilizzato per implementare i primitivi comuni. Puoi trovarlo qui .
Un altro articolo decente che mostra l'utilizzo di futex(2) è qui , ma questa implementazione è troppo "orientata al benchmark".
Come per altri sistemi operativi, oggi la maggior parte fornisce l'equivalente di Linux futex(2) :
-
WaitOnAddress , WakeOnAddress su Windows 8 e versioni successive.
-
_umtx_op(2) su OS X, FreeBSD (mai usato quelli, puoi leggere più qui ).
- Penso che OpenBSD implementa anche parzialmente
futex(2) .
Le versioni precedenti di Windows (7, Vista, XP) sono speciali. Forniscono API alternative non documentate denominate "Eventi con chiave". Proprio come futex(2) , gli eventi con chiave utilizzano la tabella delle code di attesa con hash per indirizzo. Ci sono due operazioni: "aspetta" e "rilascia" (scia). Questo meccanismo garantisce che i wake-up non vengano persi rendendo il blocco delle operazioni di "rilascio", ad es. chiamare i thread è bloccato fino a quando non sveglia effettivamente qualcuno. L'utilizzo di tale API richiede il contatore dei camerieri nello spazio utente. Puoi leggere più qui .
Se vuoi vedere più Eventi con chiave in azione, dovresti controllare le fonti di Wine e la loro implementazione di RTL_SRWLOCK e RTL_CONDITION_VARIABLE .
Gli eventi con chiave sono adatti per le variabili di condizione, rendendo l'implementazione estremamente semplice. La variabile di condizione è solo un contatore da 4 byte dei camerieri.
Il codice seguente è semplificato, puoi controllare l'originale qui .
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 );
}
Un altro modo è di emulare funzionalità simili a futex dallo spazio utente. ParkingLot di WebKit ne è un esempio. Puoi leggere più qui . Il meccanismo è fondamentalmente uguale a futex(2) , ma poiché è implementato in userspace, consente l'esecuzione di codice utente personalizzato dall'interno del blocco della coda. Ciò consente di memorizzare meno informazioni nell'oggetto di sincronizzazione e di essere globalmente più intelligente con la schedulazione dei thread. Sfortunatamente, le prestazioni in caso di contestazione molto probabilmente saranno più lente, poiché utilizzeranno comunque futex(2) per bloccare il thread chiamante, quindi c'è un ulteriore livello di codice e blocco che deve essere eseguito.
L'implementazione di WebKit non ha equivalenti di FUTEX_REQUEUE , sebbene sia possibile aggiungerla se necessario.