Possibilité de conditions de concurrence dans le pseudocode lecteur / enregistreur

J’parsing le pseudocode suivant pour les conditions de course (un peu de pratique personnelle) et cherche où sont les possibilités. Le pseudocode décrit un lecteur / graveur asynchrone vague.

Fil d’écriture

r = 0; w = 1; l = 2; //assign start slot numbers while(1) { write_slot(w); l = w; //last written slot is ww = not(r,l) //assigns next slot so that w is neither r or l }

Fil de lecture

 while(1) { r = l; //read from latest write read(r); }

Les possibilités de corruption / conditions raciales que j’ai trouvées jusqu’à présent sont possibles si les variables lecture / écriture ne sont pas atomiques et ainsi, par exemple, l’écrivain pourrait changer la valeur de l alors que le lecteur est à mi-chemin de sa lecture (pourrait entraîner une valeur insensée de r par lecture / écriture déchirée). Existe-t-il toutefois des conditions de concurrence qui pourraient éventuellement amener le lecteur et l’écrivain à tenter d’accéder au même emplacement?

Le problème fondamental est que même l’atsortingbution de variable n’est pas une opération atomique. La difficulté réside dans la manière dont votre pseudo-code serait exécuté dans le matériel. La plupart des ordinateurs utilisent une architecture de “chargement / stockage” dans laquelle les valeurs de la mémoire doivent être déplacées vers un registre avant d’être déplacées vers un autre emplacement mémoire (c’est-à-dire qu’il n’y a pas d’opération directe de mémoire à mémoire). Cela introduit un état intermédiaire (le registre) qui pourrait éventuellement mélanger les choses dans une situation multithread telle que celle-ci.

Je suppose que vous implémenteriez r , w et l tant que variables en mémoire visibles par les deux threads. Les globales et la mémoire heap sont partagés entre les threads du même processus, cette partie est donc simple. Cependant, les threads doivent avoir leur propre stack et enregistrer des états, sinon ils ne fonctionneraient tout simplement pas.

Une affectation telle que la ligne du lecteur r = l; chargerait d’abord une valeur d’un emplacement de mémoire (où que l soit stocké) dans un registre, puis stockait cette valeur en mémoire (où que r soit stocké). Donc, l’affectation r = l ressemblerait au “pseudo-assemblage”:

  load r1,addr(l) ; load l from memory into register r1 store addr(r),r1 ; store register r1 to wherever r is kept

où r1 est un registre, addr(l) est l’adresse de la mémoire où l est stocké et addr(r) est l’adresse de r .

Le problème dans votre cas est que le registre d’un thread (par exemple, le lecteur) peut conserver une valeur intermédiaire tandis qu’un autre thread (rédacteur) modifie la mémoire. Le premier thread (le lecteur) écraserait alors cette mémoire lors du stockage de registre en mémoire.

Considérez la séquence d’événements suivante. Les notations [writer] et [reader] spécifient quel thread fait quoi. L’affectation du lecteur r = l est donnée comme les opérations d’assemblage ci-dessus, pour lesquelles l’auteur effectue des opérations pénibles entre:

  [writer] r=0; w=1; l=2; // (given starting conditions) [writer] write_slot(w) // w==1 [reader] load r1,addr(l) // load l (value 2) into register r1 [writer] l = w; // l gets w, which is 1 [writer] w = not(r,l) // since r *in memory* is still 0, // and l in memory is 1, // this picks 2 for w. [reader] store addr(r),r1 // stores 2 to r *in memory* [reader] read(r) // read(2) since r==2 [writer] write_slot(w) // write(2) since w==2

Les deux dernières opérations pourraient alors se dérouler en parallèle et ils essaieraient donc d’accéder au même créneau au même moment. Donc, la réponse à votre question est oui, cela pourrait arriver.

Une façon de résoudre ce problème consiste à appliquer une exclusion mutuelle : en veillant à ce qu’un segment de code soit ininterrompu en faisant attendre d’autres threads. Il existe des instructions matérielles spéciales (telles que “comparer et échanger” CMPXCHG ) et des fonctionnalités du système d’exploitation (telles que la suspension de l’exécution d’un thread) utilisées pour implémenter l’exclusion mutuelle. En règle générale, vous utiliseriez une bibliothèque pour effectuer la synchronisation à votre place sans essayer d’écrire votre propre technique. Par exemple, voir pthread_mutex_lock () et pthread_mutex_unlock () de la bibliothèque de threads POSIX pour C.