Qu'est-ce qui empêche une condition de concurrence critique sur une écluse?

24

Je comprends les bases de ce que sont les races de données et comment les verrous / mutex / sémaphores aident à les empêcher. Mais que se passe-t-il si vous avez une "condition de concurrence" sur la serrure elle-même? Par exemple, deux threads différents, peut-être dans la même application, mais fonctionnant sur des processeurs différents, tentent d'acquérir un verrou en même temps .

Que se passe-t-il alors? Que fait-on pour empêcher cela? Est-ce impossible ou tout simplement improbable? Ou est-ce une vraie condition de course qui attend de se produire?

Gavin Howard
la source
Cette question a été posée avant sur SO: stackoverflow.com/questions/980521/…
Doc Brown
et une question connexe ici sur P.SE: programmers.stackexchange.com/questions/228827/…
ratchet freak
Vous acquérez un verrou pour acquérir le verrou;) (en d'autres termes, si votre verrou a une condition de
concurrence critique
Vous avez manqué un point important dans le fonctionnement des verrous. Ils sont construits de telle sorte qu'il n'est pas possible d'avoir une course sur une écluse, sinon ils sont complètement inutiles.
Zane

Réponses:

36

Est-ce impossible ou tout simplement improbable?

Impossible. Il peut être implémenté de différentes manières, par exemple via la fonction de comparaison et d'échange où le matériel garantit l'exécution séquentielle. Cela peut devenir un peu compliqué en présence de plusieurs cœurs ou même de plusieurs sockets et nécessite un protocole compliqué entre les cœurs, mais tout est pris en charge.

maaartinus
la source
3
Merci ... Dieu ... c'est géré dans le matériel ... (ou au moins un niveau inférieur à ce que nous touchons.)
corsiKa
2
@gdhoward Je ne peux pas le croire ... cette réponse m'a pris moins de 5 minutes et c'est le troisième plus élevé voté sur mes quatre cents réponses (principalement SO). Et aussi probablement le plus court.
maaartinus
1
@maaartinus - Court et doux le fait parfois.
Bobson
17

Etudier le concept des opérations atomiques "Test and Set".

Essentiellement, l'opération ne peut pas être divisée - il n'est pas possible de faire deux choses exactement en même temps. Il vérifiera une valeur, la définira si elle est claire et renverra la valeur telle qu'elle était lors du test. Dans une opération de verrouillage, le résultat sera toujours "lock == TRUE" après un test et un réglage, la seule différence est qu'il a été défini ou non au début.

Au niveau du microcode dans un processeur monocœur, il s'agit d'une instruction indivisible et facile à mettre en œuvre. Avec des processeurs multiples et multicœurs, cela devient plus difficile, mais en tant que programmeurs, nous n'avons pas à nous en soucier, car il est conçu pour fonctionner par les gars vraiment intelligents qui font le silicium. Essentiellement, ils font la même chose - faire une instruction atomique qu'une version sophistiquée de test-and-set

mattnz
la source
2
Fondamentalement, si le matériel n'est pas intrinsèquement séquentiel à un certain niveau, il disposera d'un mécanisme lui permettant de rompre les liens qui pourraient autrement se produire.
Bill Michell
@BillMichell, j'aurais dû y penser. En fait, je l'ai fait; Je ne savais tout simplement pas si mon hypothèse était correcte.
Gavin Howard
2

Mettez simplement le code pour entrer dans la section critique est spécialement conçu pour qu'une condition de concurrence ne viole pas l'exclusion mutuelle.

La plupart du temps, des boucles atomiques de comparaison et de définition sont utilisées qui s'exécutent au niveau matériel

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);

En l'absence de cela, il existe des solutions logicielles bien étudiées pour permettre l'exclusion mutuelle.

monstre à cliquet
la source
1

Il n'est pas possible que deux threads (ou plus) acquièrent le verrouillage en même temps. Il existe par exemple quelques types de méthodes de synchronisation:

Attente active - verrouillage de rotation

Pseudocode:

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

XCHG est un exemple de fonctionnement atomique (existe sur l'architecture x86) qui définit d'abord la nouvelle valeur d'une variable "lock", puis renvoie l'ancienne valeur. Atomic signifie qu'il ne peut pas être interrompu - dans l'exemple ci-dessus entre la définition d'une nouvelle valeur et le retour de l'ancien. Atomique - résultat déterministe quoi qu'il arrive.

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

Lorsque le verrouillage est égal à 0, un autre thread peut entrer dans la section critique - tandis que la boucle se termine.

Suspendre le fil - par exemple compter le sémaphore

Il existe deux opération atomique .Wait()et .Signal()et nous avons variable entière permet de l' appeler 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;

La résolution d'un problème de section critique est désormais très simple:

Pseudocode:

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

Habituellement, votre API de thread de programmation devrait vous donner la possibilité de spécifier des threads simultanés maximaux dans la section critique du sémaphore. Évidemment, il existe plus de types de synchronisation dans les systèmes multithread (mutex, moniteurs, sémaphore binaire, etc.) mais ils se basent sur les idées ci-dessus. On pourrait faire valoir que les méthodes qui utilisent la suspension des threads devraient être préférées à l'attente active (donc le processeur n'est pas gaspillé) - ce n'est pas toujours la vérité. Lorsque le thread est suspendu - une opération coûteuse appelée changement de contexte a lieu. Cependant, c'est raisonnable lorsque le temps d'attente est court (nombre de threads ~ nombre de cœurs).

fex
la source