Cosa impedisce una condizione di gara su un lucchetto?

Is it impossible, or just plain unlikely?

Impossibile. Può essere implementato in diversi modi, ad esempio tramite Compare-and-swap dove l'hardware garantisce sequenziale esecuzione. Può diventare un po 'complicato in presenza di più core o anche più socket e richiede un complicato protocollo tra i core, ma questo è tutto a posto.

Studiare il concetto di operazioni atomiche "Test e Set".

Essenzialmente l'operazione non può essere divisa - non è possibile che due cose lo facciano esattamente nello stesso momento. Controllerà un valore, lo imposterà se è chiaro e restituirà il valore com'era durante il test. In un'operazione di blocco, il risultato sarà sempre "lock == TRUE" dopo un test-and-set, l'unica differenza è che è stata impostata o meno all'inizio.

A livello di codice micro in un processore single core, questa è un'istruzione indivisibile ed è facile da implementare. Con processori multipli e multicore, diventa più difficile, ma come programmatori non abbiamo bisogno di preoccuparci di questo, dato che è progettato per funzionare da persone davvero intelligenti che fanno il silicio. Fondamentalmente fanno la stessa cosa - fai un'istruzione atomica che una versione di fantasia di test-and-set

Inserisci semplicemente il codice per entrare nella sezione critica appositamente progettato in modo che le condizioni di gara non violino l'esclusione reciproca.

La maggior parte delle volte vengono utilizzati i confronti atomici e i loop impostati che vengono eseguiti a livello hardware

while(!CompareAndSet(&lock, false, true));//busy loop won't continue until THIS thread has set the lock to true
//critical section
CompareAndSet(&lock, true, false);

In assenza di ciò ci sono soluzioni software ben studiate per consentire l'esclusione reciproca.

Non è possibile che due (o più) thread acquisiscano lock allo stesso tempo. Esistono alcuni tipi di metodi di sincronizzazione, ad esempio:

Attesa in attesa - spin lock

Pseudocodice:

1. while ( xchg(lock, 1) == 1); - entry protocole

XCHG è un esempio di operazione atomica (esiste sull'architettura x86) che prima imposta un nuovo valore per una variabile "lock" e quindi restituisce il vecchio valore. Atomico significa che non può essere interrotto - nell'esempio sopra tra l'impostazione di un nuovo valore e il ritorno vecchio. Atomico - risultato deterministico indipendentemente da cosa.

2. Your code
3. lock = 0; - exit protocol

Quando il blocco è uguale a 0, un altro thread può entrare nella sezione critica - mentre il loop termina.

Sospensione del thread, ad esempio conteggio del semaforo

Esistono due operazioni atomiche .Wait() e .Signal() e abbiamo una variabile intera che consente di chiamarlo int currentValue .

Wait():
if (currentValue > 0) currentValue -= 1;
else suspend current thread;

Signal():
If there exists thread suspended by semaphore wake up one of them
Else currentValue += 1;

Ora risolvere il problema della sezione critica è davvero semplice:

Pseudocodice:

mySemaphore.Wait();
do some operations - critical section
mySemaphore.Signal();

Di solito l'API del thread di programmazione dovrebbe darti la possibilità di specificare i thread simultanei massimali nella sezione critica del semaforo. Ovviamente ci sono più tipi di sincronizzazione in sistemi multithread (mutex, monitor, semaforo binario ecc.) Ma si basano su idee sopra. Si potrebbe obiettare che i metodi che usano la sospensione del filo dovrebbero essere preferiti all'attesa attiva (quindi la cpu non viene sprecata) - non è sempre la verità. Quando il thread viene sospeso, un'operazione costosa chiamata context switch prende il suo posto. Tuttavia è ragionevole quando il tempo di attesa è breve (numero di thread ~ numero di core).