98 lines
5.9 KiB
Plaintext
98 lines
5.9 KiB
Plaintext
Concurrent programming for gem-graph
|
|
|
|
Le thread maître, dans l'ordre:
|
|
(1) - cherche, en un temps fini, un espace local dans l'espace global de préemption et, s'il le trouve:
|
|
+ tente, en un temps fini, de le préempter et, si la préemption a été possible,
|
|
+ tente, en un temps fini, de réserver une place dans la liste des threads
|
|
+ en cas de succès, crée un thread de calcul en lui communiquant les adresses
|
|
|
|
(2) - cherche, en un temps fini, dans la liste des threads s'il y a qui ont fini leur calcul et, s'il y en a:
|
|
+ lève la préemption de leur espace local et
|
|
+ les retire de la liste des threads.
|
|
|
|
(3) - affiche les résultats.
|
|
|
|
Chaque thread de calcul, dans l'ordre:
|
|
(1) - lit son espace local graphique et les règles écrites dans l'arbre des transitions et les compare.
|
|
(pour faire ce calcul, il n'écrit que dans des variables locales)
|
|
si échec, il se termine, sinon:
|
|
|
|
(2) - si une règle peut être appliquée, écrit le résultat de son calcul dans l'espace global.
|
|
|
|
(3) - dans tous les cas, écrit qu'il est terminé dans une liste où le thread maître peut lire et écrire.
|
|
cette écriture est sa dernière instruction. (après, il est terminé)
|
|
|
|
---
|
|
|
|
> engine (top-level ?) > thread maître en boucle infinie:
|
|
|
|
opération type ressource thread maître thread de calcul
|
|
--------- ---- ---------- ------------- ----------------
|
|
recherche espace local boucle finie liste des flèches lecture
|
|
espace global de préemption lecture
|
|
|
|
préemption espace local section critique espace global de préemption fermeture verrou
|
|
vérification boucle finie espace global de préemption lecture
|
|
si confirmation: boucle finie espace global de préemption écriture
|
|
fin section c. espace global de préemption ouverture verrou
|
|
si succès préemption:
|
|
recherche d'une place thread section critique liste des threads fermeture verrou
|
|
boucle finie liste des threads lecture
|
|
si succès, assignment liste des threads écriture
|
|
fin section c. liste des threads ouverture verrou
|
|
si succès, création d'un thread assignment mémoire / CPU système écriture
|
|
|
|
recherche règle de transition parcours d'arbre arbre des transitions lecture
|
|
espace global graphique lecture
|
|
|
|
si succès, transition locale boucle finie espace global graphique écriture
|
|
|
|
terminaison d'un thread section critique liste des threads fermeture verrou
|
|
(adresse connue) assignment liste des threads écriture
|
|
fin section c. liste des threads ouverture verrou
|
|
fin du thread
|
|
|
|
recherche place espace local section critique liste des threads fermeture verrou
|
|
boucle finie liste des threads lecture
|
|
si succès, levée préemption assignment liste des threads écriture
|
|
fin section c. liste des threads ouverture verrou
|
|
|
|
thread d'affichage boucle finie recherche résultats lecture
|
|
sorties système écriture
|
|
--------- ---- ---------- ------------- ----------------
|
|
|
|
Trois ressources doivent être accessibles aux threads de calcul de l'automate:
|
|
- les transitions (c-a-d: l'arbre des règles) en lecture seulement:
|
|
- l'état local (c-a-d: une partie de l'espace global préemptée) pour:
|
|
(1) lire les contraintes nécéssaires pour le choix de la règle de transition
|
|
(2) puis écrire le résultat de son calcul en cas de succès
|
|
- la liste des threads en écriture pour indiquer au thread maître qu'ils vont se terminer
|
|
|
|
Un thread de calcul n'est crée que si la préemption a été possible.
|
|
Son calcul aboutit au choix de l'une des règles ou échoue.
|
|
Comme les threads ont seulement besoin de lire l'arbre des règles pendant leur calcul,
|
|
leurs lectures ne causent pas de risque de race condition.
|
|
|
|
La liste des threads est le seul objet où plusieurs threads doivent écrire:
|
|
- le thread maître au début du calcul (quand il a préempté et va créer un thread) et
|
|
- chaque thread quand il va se finir (pour que le thread maître sache qu'il peut lever la préemption)
|
|
|
|
Un point délicat est qu'il ne faut pas que l'espace global de préemption soit modifié entre:
|
|
- le moment où le thread maître vient de trouver un espace local convenable et
|
|
- le moment où il a fini de préempter cet espace local.
|
|
Il faut donc qu'il soit vérifié après mise en place du verrou sur l'espace global
|
|
et avant préemption (et levée du verrou)
|
|
|
|
Il ne semble pas y avoir de risque entre:
|
|
- le moment où un thread de calcul a fini de modifier son espace local, et
|
|
- le moment où le thread maître lève la préemption associée
|
|
|
|
La préemption et sa levée doivent être des opérations atomiques
|
|
|
|
David Beazley & Brian K.Jones Python Cookbook 2013 p503:
|
|
"The solution in which locks are always acquired in strict order [...]
|
|
can be mathematically proven to avoid deadlocks
|
|
[because] you can't get cyclic locking dependencies,
|
|
which are a necessary condition fordeadlock to occur."
|
|
|