Mini-test de l’unité · Station Minuit

1. Dans un modèle lecture–calcul–écriture, A et B incrémentent une fois un compteur initialement nul. A lit 0, B lit 0, A écrit 1, B écrit 1. Quel résultat et quel diagnostic?

Application · version 1

Hypothèses et règle de réponse

Chaque lecture et écriture du modèle est indivisible; chaque thread calcule ancienne valeur + 1.
Modèle pédagogique seulement; aucune borne du langage C pour des accès ordinaires en course.

Les hypothèses fixent le modèle. Les traces sont possibles, sans FIFO ou vitesse supposée. Une reformulation équivalente est admise dans la rubrique des réponses rédigées, qui restent autoévaluées. Les modèles ne bornent pas une data race C.

Corrigé — question 1

Les deux calculs utilisent la même ancienne valeur 0; la seconde écriture de 1 remplace la première. Le compteur vaut 1 dans cette trace. Une exécution sérielle du modèle donnerait 2. Ces résultats illustratifs ne bornent pas une data race C, dont le comportement peut être indéfini.

Variantes : Les hypothèses fixent le modèle. Les traces sont possibles, sans FIFO ou vitesse supposée. Une reformulation équivalente est admise dans la rubrique des réponses rédigées, qui restent autoévaluées. Les modèles ne bornent pas une data race C.

Revoir la matière — 2.2 Définition d’une condition de concurrence Revoir la matière — 2.3 Exemple du spouleur d’impression

2. Le verrou est initialement 0. Chaque thread teste while(lock==1), puis écrit lock=1 avant sa section critique. Construis une trace qui viole l’exclusion et identifie la correction nécessaire.

Application · version 1

Hypothèses et règle de réponse

Modèle abstrait à lectures/écritures indivisibles, test séparé de l’affectation; deux participants.
Le raisonnement ne présente pas ce fragment comme une implantation C concurrente correcte.

Les hypothèses fixent le modèle. Les traces sont possibles, sans FIFO ou vitesse supposée. Une reformulation équivalente est admise dans la rubrique des réponses rédigées, qui restent autoévaluées. Les modèles ne bornent pas une data race C.

Corrigé — question 2

La trace test A → test B → prise B → entrée B → prise A → entrée A laisse deux participants en section critique. Chacun a correctement observé un ancien état libre; le problème est la séparation du test et de la prise. La réponse rédigée reste autoévaluée, sans score automatique de correction.

A lit 0 et franchit le test, puis est interrompu avant son affectation.
B lit 0, écrit 1 et entre sans encore sortir.
A reprend, écrit 1 et entre alors que B est encore en section critique.
Le test et la prise doivent former une primitive atomique, ou employer un protocole prouvé; volatile ou sleep ne ferme pas cette fenêtre.

Variantes : Les hypothèses fixent le modèle. Les traces sont possibles, sans FIFO ou vitesse supposée. Une reformulation équivalente est admise dans la rubrique des réponses rédigées, qui restent autoévaluées. Les modèles ne bornent pas une data race C.

Revoir la matière — 3.2 Verrou logiciel naïf

3. Peterson : critical[0]=critical[1]=1 et la dernière écriture de waiting vaut 1. Qui peut franchir sa boucle à cet instant?

Application · version 1

Hypothèses et règle de réponse

Deux participants seulement; lectures/écritures atomiques et cohérence séquentielle du modèle.
Boucle exacte : waiting == p && critical[1-p] == 1; aucun participant ne retire encore son indicateur.

Les hypothèses fixent le modèle. Les traces sont possibles, sans FIFO ou vitesse supposée. Une reformulation équivalente est admise dans la rubrique des réponses rédigées, qui restent autoévaluées. Les modèles ne bornent pas une data race C.

Corrigé — question 3

Pour p=0, waiting==0 est faux, donc P0 franchit la boucle. Pour p=1, les deux termes sont vrais et P1 attend. Lorsque P0 sort et met critical[0]=0, P1 peut avancer. Ce modèle n’autorise pas une transcription C avec des objets ordinaires en course; atomiques et ordre mémoire doivent être corrects.

Variantes : Les hypothèses fixent le modèle. Les traces sont possibles, sans FIFO ou vitesse supposée. Une reformulation équivalente est admise dans la rubrique des réponses rédigées, qui restent autoévaluées. Les modèles ne bornent pas une data race C.

Revoir la matière — 4.1 Solution de Peterson

4. Le consommateur constate count=0 mais ne dort pas encore. Le producteur ajoute un élément et appelle wakeup. Déroule le réveil perdu et explique deux mécanismes qui ferment cette fenêtre.

Application · version 1

Hypothèses et règle de réponse

sleep/wakeup naïfs : un wakeup sans dormeur n’est pas mémorisé.
Aucune autre production ni réveil ultérieur dans la trace; modèles sans erreur ni annulation.

Les hypothèses fixent le modèle. Les traces sont possibles, sans FIFO ou vitesse supposée. Une reformulation équivalente est admise dans la rubrique des réponses rédigées, qui restent autoévaluées. Les modèles ne bornent pas une data race C.

Corrigé — question 4

La faute est la fenêtre entre test et sommeil. Un sémaphore garde la permission si le post précède le wait. Une condition s’appuie sur un prédicat persistant sous mutex et une libération/blocage atomique; son signal isolé ne garde pas de jeton. Les deux solutions ne rendent pas les garanties des primitives identiques.

C constate 0 puis est interrompu avant sleep; P produit, count devient 1, et le réveil sans dormeur est perdu.
C reprend et dort malgré un élément présent; aucun délai fixe ne garantit la correction.
Un sémaphore full initialisé à 0 mémorise le post; le wait ultérieur consomme la permission.
Une condition avec prédicat protégé par le même mutex utilise wait atomique et reteste dans while; la condition seule ne mémorise pas les signaux.

Variantes : Les hypothèses fixent le modèle. Les traces sont possibles, sans FIFO ou vitesse supposée. Une reformulation équivalente est admise dans la rubrique des réponses rédigées, qui restent autoévaluées. Les modèles ne bornent pas une data race C.

Revoir la matière — 5.2 Pourquoi `sleep`/`wakeup` ne suffit pas

5. Quelle différence entre sémaphore de comptage, usage binaire et mutex est correcte?

Compréhension · version 1

Hypothèses et règle de réponse

Modèle et API décrits par le maître S05; aucune VM, compilation ni manipulation personnelle attestée.

Les hypothèses fixent le modèle. Les traces sont possibles, sans FIFO ou vitesse supposée. Une reformulation équivalente est admise dans la rubrique des réponses rédigées, qui restent autoévaluées. Les modèles ne bornent pas une data race C.

Corrigé — question 5

Un sémaphore n’attribue pas la propriété d’un mutex : un autre thread peut effectuer post. POSIX sem_t reste un compteur; initialiser à 1 ne le borne pas magiquement à 1. L’usage binaire dépend du protocole qui évite les post excédentaires. Un mutex acquis doit être libéré par son propriétaire selon son contrat.

Variantes : Les hypothèses fixent le modèle. Les traces sont possibles, sans FIFO ou vitesse supposée. Une reformulation équivalente est admise dans la rubrique des réponses rédigées, qui restent autoévaluées. Les modèles ne bornent pas une data race C.

Revoir la matière — 6.2 Comptage, binaire et ordre Revoir la matière — 6.1 Modèle Revoir la matière — 7. Mutex Pthreads

6. C revient avec succès de pthread_cond_wait(&cv,&m). Peut-il utiliser l’élément sans retester le prédicat?

Application · version 1

Hypothèses et règle de réponse

Modèle et API décrits par le maître S05; aucune VM, compilation ni manipulation personnelle attestée.

Les hypothèses fixent le modèle. Les traces sont possibles, sans FIFO ou vitesse supposée. Une reformulation équivalente est admise dans la rubrique des réponses rédigées, qui restent autoévaluées. Les modèles ne bornent pas une data race C.

Corrigé — question 6

Wait libère atomiquement le mutex et attend, puis le réacquiert avant de retourner. Le retour n’affirme pas la vérité du prédicat. Un signal ne réserve pas la ressource et n’est pas mémorisé sans attenteur. Le prédicat se lit et se modifie sous le même mutex; la boucle le vérifie à nouveau.

Variantes : Les hypothèses fixent le modèle. Les traces sont possibles, sans FIFO ou vitesse supposée. Une reformulation équivalente est admise dans la rubrique des réponses rédigées, qui restent autoévaluées. Les modèles ne bornent pas une data race C.

Revoir la matière — 8. Variables de condition

7. Trois travailleurs écrivent chacun leur case A[i], atteignent une barrière de compte 3, puis lisent toutes les cases. Que garantit le rendez-vous?

Application · version 1

Hypothèses et règle de réponse

Même génération de barrière; chaque travailleur arrive exactement une fois; API réussie, cases distinctes pendant A.
Aucune écriture suivante non synchronisée sur ces cases pendant leur lecture.

Les hypothèses fixent le modèle. Les traces sont possibles, sans FIFO ou vitesse supposée. Une reformulation équivalente est admise dans la rubrique des réponses rédigées, qui restent autoévaluées. Les modèles ne bornent pas une data race C.

Corrigé — question 7

La barrière attend les trois arrivées et sépare les phases avec synchronisation mémoire. PTHREAD_BARRIER_SERIAL_THREAD est retourné à un participant non spécifié; les autres reçoivent zéro. Elle ne sérialise pas les opérations de la phase B. Un mauvais compte ou un participant absent peut empêcher le rendez-vous.

Variantes : Les hypothèses fixent le modèle. Les traces sont possibles, sans FIFO ou vitesse supposée. Une reformulation équivalente est admise dans la rubrique des réponses rédigées, qui restent autoévaluées. Les modèles ne bornent pas une data race C.

Revoir la matière — 9. Barrières

8. Tampon vide : C prend mutex puis attend full=0 sans libérer mutex. P doit prendre ce même mutex avant d’insérer. Quel diagnostic et quel ordre correct?

Application · version 1

Hypothèses et règle de réponse

Modèle des sémaphores sans erreur : full=0, empty=N>0, mutex=1; un producteur et un consommateur, aucun autre post.

Les hypothèses fixent le modèle. Les traces sont possibles, sans FIFO ou vitesse supposée. Une reformulation équivalente est admise dans la rubrique des réponses rédigées, qui restent autoévaluées. Les modèles ne bornent pas une data race C.

Corrigé — question 8

C conserve la structure verrouillée pendant qu’il attend l’élément que P ne peut pas insérer : les deux attendent. Le bon ordre est permission de ressource puis mutex; après modification, libérer mutex et poster la ressource opposée. Pour N=2 : empty=2, full=0, mutex=1 initialement. À repos après une insertion : empty=1, full=1, mutex=1; après retrait : 2/0/1.

Variantes : Les hypothèses fixent le modèle. Les traces sont possibles, sans FIFO ou vitesse supposée. Une reformulation équivalente est admise dans la rubrique des réponses rédigées, qui restent autoévaluées. Les modèles ne bornent pas une data race C.

Revoir la matière — 6.3 Producteur-consommateur corrigé

Mini-test — Concurrence

1. Dans un modèle lecture–calcul–écriture, A et B incrémentent une fois un compteur initialement nul. A lit 0, B lit 0, A écrit 1, B écrit 1. Quel résultat et quel diagnostic?

2. Le verrou est initialement 0. Chaque thread teste while(lock==1), puis écrit lock=1 avant sa section critique. Construis une trace qui viole l’exclusion et identifie la correction nécessaire.

3. Peterson : critical[0]=critical[1]=1 et la dernière écriture de waiting vaut 1. Qui peut franchir sa boucle à cet instant?

4. Le consommateur constate count=0 mais ne dort pas encore. Le producteur ajoute un élément et appelle wakeup. Déroule le réveil perdu et explique deux mécanismes qui ferment cette fenêtre.

5. Quelle différence entre sémaphore de comptage, usage binaire et mutex est correcte?

6. C revient avec succès de pthread_cond_wait(&cv,&m). Peut-il utiliser l’élément sans retester le prédicat?

7. Trois travailleurs écrivent chacun leur case A[i], atteignent une barrière de compte 3, puis lisent toutes les cases. Que garantit le rendez-vous?

8. Tampon vide : C prend mutex puis attend full=0 sans libérer mutex. P doit prendre ce même mutex avant d’insérer. Quel diagnostic et quel ordre correct?