Condition de concurrence
Logique séquentielle asynchrone
Dans un circuit logique séquentiel asynchrone, il peut y avoir une condition selon laquelle - lorsque la valeur binaire de la variable d'entrée change, il peut y avoir plus d'une (deux ou plusieurs) variables d'état qui changent de valeur simultanément.
Cette condition est appelée condition de concurrence.
Si l’état stable final atteint par le circuit est indépendant du changement d’ordre des variables d’état, alors la concurrence est appelée une concurrence non critique.
Si le circuit atteint deux ou plusieurs états stables différents en fonction de l'ordre dans lequel les variables d'état changent, alors la concurrence est une concurrence critique.
Les conditions de concurrence critiques doivent être supprimées car elles constituent un obstacle au bon fonctionnement du circuit.
Prenons un exemple pour comprendre les conditions de concurrences, concurrence critique et concurrence non critique.
Exemple de concurrence non critique :
1. Supposons que nous ayons une table de transition comme ci-dessous:
| x | |||
| x'(0) | x(1) | ||
| y1y2 | y1'y2' (00) | 00 | 11 |
| y1'y2 (01) | 11 | ||
| y1y2 (11) | 11 | ||
| y1y2' (10) | 11 | ||
Dans le tableau de transition, l'état stable final est y1y2x = 111.
Pour atteindre l'état stable final, les transitions possibles (changements dans les valeurs des variables d'état) sont indiquées ci-dessous:
| y1 | y2 | x | Remarque | |
| 0 | 0 | 0 |
La valeur binaire de la variable d'entrée x passe de 0 à 1. Avec le changement de x, y1 et y2 changent d'état simultanément. C'est une condition de concurrence. |
|
| État stable final avec y1y2X = 111 | 1 | 1 | 1 |
|
| Transition possible de y1 y2 est 00 -> 11 pour atteindre l'état stable final y1y1x = 111 | ||||
| 0 | 0 | 0 | État initial |
|
| 0 | 1 | 1 | La valeur binaire de la variable d'entrée x passe de « 0 » à « 1 ». Avec un changement de x1y1 reste '0' mais y2 change en 1 |
|
| État stable final avec y1y2x = 111 | 1 | 1 | 1 | Maintenant y1 change en 1 |
| Transition possible de y1 y2 est 00 -> 11 pour atteindre l'état stable final y1y1x = 111 | ||||
| 0 | 0 | 0 | État initial |
|
| 1 | 0 | 1 | La valeur binaire de la variable d'entrée x passe de « 0 » à « 1 ». Avec un changement de x, y2 reste '0' mais y1 change en 1 |
|
| État stable final avec y1y2x = 111 | 1 | 1 | 1 | Maintenant y2 change en 1 |
| Transition possible de y1 y2 est 00 -> 11 pour atteindre l'état stable final y1y1x = 111 | ||||
La table de transitionci-haut est un exemple de concurrence non critique car toutes les transitions (changements) possibles de y1y2x, comme illustré dans le tableau des transitions possibles, conduisent à un état stable final y1y2x = 111.
2. Prenons une autre table de transition comme le montre la figure ci-dessous:
| x | |||
| x'(0) | x(1) | ||
| y1y2 | y1'y2' (00) | 00 | |
| y1'y2 (01) | 01 | ||
| y1y2 (11) | 01 | ||
| y1y2' (10) | 11 | ||
Dans le tableau de transition de la figure, l'état stable final est y1y2x = 011.
Pour atteindre l'état stable final, les transitions possibles (changements dans les valeurs des variables d'état) sont présentées dans le tableau transitions possibles ci-dessous:
| y1 | y2 | x | Remarque | |
| 0 | 0 | 0 |
État initial |
|
| 1 | 1 | 1 |
La valeur binaire de la variable d'entrée x passe de 0 à 1. Avec le changement de x, y1 et y2 changent d'état simultanément. C'est une condition de concurrence. |
|
| État stable final avec y1y2X = 011 | 0 | 1 | 1 |
Maintenant y1 change pour 0 |
| Transition possible de y1 y2 est 00 -> 11 -> 01 pour atteindre l'état stable final y1y1x = 111 | ||||
| 0 | 0 | 0 | État initial |
|
| État stable final avec y1y2x = 011 | 0 | 1 | 1 | La valeur binaire de la variable d'entrée x passe de « 0 » à « 1 ». Avec un changement de x, y2 reste '0' mais y1 change en 1 |
| Transition possible de y1 y2 est 00 -> 10 -> 11 -> 01 pour atteindre l'état stable final y1y1x = 111 | ||||
| 0 | 0 | 0 | État initial |
|
| 1 | 0 | 1 | La valeur binaire de la variable d'entrée x passe de « 0 » à « 1 ». Avec un changement de x, y2 reste '0' mais y1 change en 1 |
|
| 1 | 1 | 1 | Maintenant y2 change en 1 |
|
| État stable final avec y1y2x = 011 | 0 | 1 | 1 | Maintenant y1 change en 0 |
| Transition possible de y1 y2 est 00 -> 10 -> 11 -> 01 pour atteindre l'état stable final y1y1x = 111 | ||||
Exemple de course critique :
1. Supposons que nous ayons une table de transition comme le montre le tableau ci-dessous:
| x | |||
| x'(0) | x(1) | ||
| y1y2 | y1'y2' (00) | 00 | 11 |
| y1'y2 (01) | 01 | ||
| y1y2 (11) | 11 | ||
| y1y2' (10) | 10 | ||
Pour atteindre l'état stable, les transitions possibles (changements dans les valeurs des variables d'état) sont indiquées dans le tableau ci-dessous:
| y1 | y2 | x | Remarque | |
| 0 | 0 | 0 |
État initial |
|
| État stable final avec y1y2X = 111 | 1 | 1 | 1 |
La valeur binaire de la variable d'entrée x passe de 0 à 1. Avec le changement de x, y1 et y2 changent d'état simultanément. C'est une condition de concurrence. |
| Transition possible de y1 y2 est 00 -> 11 pour atteindre l'état stable final y1y1x = 111 | ||||
| 0 | 0 | 0 | État initial |
|
| État stable final avec y1y2x = 011 | 0 | 1 | 1 | La valeur binaire de la variable d'entrée x passe de « 0 » à « 1 ». Avec un changement de x, y1 reste '0' mais y2 change en 1 |
| Transition possible de y1 y2 est 00 -> 00 -> 01 pour atteindre l'état stable final y1y1x = 011 | ||||
| 0 | 0 | 0 | État initial |
|
| État stable final avec y1y2x = 101 | 1 | 0 | 1 | La valeur binaire de la variable d'entrée x passe de « 0 » à « 1 ». Avec un changement de x, y2 reste '0' mais y1 change en 1 |
| Transition possible de y1 y2 est 00 -> 10 pour atteindre l'état stable final y1y1x = 101 | ||||
La table de transition est un exemple de course critique car différentes transitions (changements) possibles de y1y2x conduisent à différents états stables.
Cela signifie que le circuit atteint deux ou plusieurs états stables différents en fonction de l'ordre dans lequel les variables d'état changent.
Prenons une autre table de transition comme indiqué dans le tableau ci-dessous:
| x | |||
| x'(0) | x(1) | ||
| y1y2 | y1'y2' (00) | 00 | 11 |
| y1'y2 (01) | 01 | ||
| y1y2 (11) | 11 | ||
| y1y2' (10) | 10 | ||
Pour atteindre l'état stable, les transitions possibles (changements dans les valeurs des variables d'état) sont indiquées dans le tableau ci-dessous:
| y1 | y2 | x | Remarque | |
| 0 | 0 | 0 |
État initial |
|
| État stable final avec y1y2X = 011 | 0 | 1 | 1 |
La valeur binaire de la variable d'entrée x passe de 0 à 1. Avec le changement de x, y1 et y2 changent d'état simultanément. C'est une condition de concurrence. |
| Transition possible de y1 y2 est 00 -> 11 pour atteindre l'état stable final y1y1x = 011 | ||||
| 0 | 0 | 0 | État initial |
|
| 0 | 1 | 1 | La valeur binaire de la variable d'entrée x passe de « 0 » à « 1 ». Avec un changement de x, y1 reste '0' mais y2 change en 1 |
|
| État stable final avec y1y2x = 111 | 1 | 1 | 1 | |
| Transition possible de y1 y2 est 00 -> 01 -> 11 pour atteindre l'état stable final y1y1x = 111 | ||||
| 0 | 0 | 0 | État initial |
|
| État stable final avec y1y2x = 101 | 1 | 0 | 1 | La valeur binaire de la variable d'entrée x passe de « 0 » à « 1 ». Avec un changement de x, y2 reste '0' mais y1 change en 1 |
| Transition possible de y1 y2 est 00 -> 10 pour atteindre l'état stable final y1y1x = 101 | ||||
Les tables de transition illustrées sont un exemple de course critique car différentes transitions (changements) possibles de y1y2x, comme illustré dans le tableau des transitions possibles, conduisent à différents états stables.
Cela signifie que le circuit atteint deux ou plusieurs états stables différents en fonction de l'ordre dans lequel les variables d'état changent.
Comment éviter les concurrences ?
Les conditions de concurrence peuvent être évitées en attribuant un nombre binaire approprié aux variables d'état.
Les variables d'état doivent se voir attribuer des nombres binaires de telle sorte qu'une seule variable d'état puisse changer à la fois lorsqu'une transition d'état se produit dans la table de flux.
Le circuit donné doit passer par des états instables intermédiaires avec un changement unique de variable d'état afin que les conditions de concurrence puissent être évitées.
Lorsqu’un circuit traverse une séquence unique d’états instables, on dit qu’il a un cycle.
Dans 1e tableau de transition ci-dessous y1y2 = 00 et le changement de l'entrée 'x' est de 0 à 1.
Le tableau de transition ci-dessous donne une séquence unique qui se termine par un état totalement stable 101.
| x | |||
| x'(0) | x(1) | ||
| y1y2 | y1'y2' (00) | 00 | 01 |
| y1'y2 (01) | 11 | ||
| y1y2 (11) | 10 | ||
| y1y2' (10) | 10 | ||
Dans le tableau ci-dessous, même si les variables d'état changent de 00 à 11, le cycle fournit une transition unique de 00 à 01 puis à 11 qui se termine par un état totalement stable 111.
| x | |||
| x'(0) | x(1) | ||
| y1y2 | y1'y2' (00) | 00 | 01 |
| y1'y2 (01) | 11 | ||
| y1y2 (11) | 11 | ||
| y1y2' (10) | 10 | ||
Si un cycle ne se termine pas par un état stable, le circuit continuera à passer d’un état instable à un autre, rendant l’ensemble du circuit instable.
Ceci est illustré dans le tableau ci-dessous:
| x | |||
| x'(0) | x(1) | ||
| y1y2 | y1'y2' (00) | 00 | 01 |
| y1'y2 (01) | 11 | ||
| y1y2 (11) | 10 | ||
| y1y2' (10) | 10 | ||
