Un programme multi-threadé peut-il jamais être déterministe?

Connaître l'algorithme ne vous permettra pas de prédire ce qui va arriver quand. Toutes sortes de retards qui se produisent dans l'exécution d'un programme ou d'un fil dépendent des conditions environnementales telles que: mémoire disponible, échange, interruptions entrantes, autres tâches occupées, etc.

Si vous deviez cartographier votre programme multi-threads sur une exécution séquentielle et que vos threads se comportent de manière déterministe, votre vaste programme pourrait être déterministe et que les problèmes de «concurrence» pourraient être reproductibles. Bien sûr, à ce stade, ils ne seraient plus problèmes de concurrence.

Si vous souhaitez en savoir plus, http://fr.wikipedia.org/wiki/process_calculus est une lecture très intéressante.

Il existe des outils (dans le développement) qui essaieront de créer des conditions de raccourci de manière un peu prévisible, mais il s'agit d'un essai prospectif, et non de reconstruire un «bogue à l'état sauvage».

échecs est un exemple.

Normalement, il est dit que les programmes multi-filetés sont non déterministes, ce qui signifie que s'il se bloque, il sera presque impossible de recréer l'erreur qui a provoqué la condition.

Je suis en désaccord avec cela entièrement, certains programmes multi-filetés sont non déterministes, mais sont donc de même que les options à filetage unique, en tenant compte de l'entrée utilisateur, des pompes à des messages, de la manipulation de la souris / du clavier et de nombreux autres facteurs. Un programme multi-threadé rend généralement plus difficile la reproduction de l'erreur, mais certainement pas impossible. Pour toutes raisons, l'exécution du programme n'est pas complètement aléatoire, il existe une sorte de répétabilité (mais pas de prévisibilité), je peux généralement reproduire des bugs multi-filetés plutôt rapidement dans mes applications, mais j'ai ensuite beaucoup de journalisation de Verbose dans mes applications, car les actions des utilisateurs finaux.

En tant que mis à part, si vous avez des crashs, vous ne pouvez pas également obtenir de bûches de crash, avec des informations sur la pile d'appels? Cela aidera grandement au processus de débogage.

Il serait possible d'exécuter un programme sur une machine virtuelle multi-threadé où l'attribution de cycles virtuels à chaque thread a été effectuée via un processus entièrement déterministe, éventuellement à l'aide d'un générateur pseudo-aléatoire (qui pourrait être ensemencé avec une constante avant chaque programme). Une autre possibilité, éventuellement plus intéressante, serait d'avoir une machine virtuelle qui alternerait entre les filets d'exécution en mode "éclaboussures" (où presque toute variable qu'ils touchent auraient que sa valeur deviendrait "inconnue" à d'autres threads) et le mode "nettoyage" ( où les résultats d'opérations avec des opérandes connus seraient visibles et connus d'autres threads). Je m'attendrais à ce que la situation soit probablement quelque peu analogue à la simulation matérielle: si la production de chaque porte est considérée comme "inconnue" entre ses temps de propagation minimale et maximale, mais la simulation fonctionne de toute façon, c'est une bonne indication que la conception est robuste, mais Il existe de nombreuses conceptions utiles qui n'ont pas pu être construites pour travailler dans de telles simulations (les États seraient essentiellement garantis pour évoluer dans une combinaison valide, bien que l'on ne pouvait pas garantir lequel). Néanmoins, cela pourrait être une avenue d'exploration intéressante, car de grandes parties de nombreux programmes pourraient être écrits pour fonctionner correctement, même dans un «mode éclaboussant» VM.

Je ne pense pas que ce soit praticable. Pour faire respecter une entrelacement de thread spécifique, nous avons besoin de placer des verrous sur des variables partagées, forçant les threads pour y accéder dans un ordre spécifique. Cela provoquerait une grave dégradation de performances.

Rejouer les bugs de concurrence est généralement géré par des systèmes Record & Replay. Étant donné que l'enregistrement de telles quantités importantes d'informations dégrade également les performances, les systèmes les plus récents effectuent une journalisation partielle et complètent ultérieurement les entrelacements de fil à l'aide de la résolution de SMT. Je crois que l'avancée la plus récente de ce type de systèmes est la symbiose (publiée dans la conférence PLDI de cette année). TOU peut trouver des implémentations open source dans cette URL:

http://www.gsd.inesc-id.pt /~nmachado/software/symbiosis_Tutorial.html

Il s'agit en fait d'une exigence valide dans de nombreux systèmes aujourd'hui qui souhaitent exécuter des tâches parallèlement, mais souhaitent également du déterminisme de temps à autre.

Par exemple, une entreprise mobile voudrait traiter des événements d'abonnement de plusieurs utilisateurs parallèlement, mais voudrait exécuter des événements d'un seul utilisateur à la fois.

Une solution consiste bien sûr à écrire tout pour être exécuté sur un seul fil. Une autre solution est une filetage déterministe. J'ai écrit une bibliothèque simple en Java qui peut être utilisée pour atteindre le comportement que j'ai décrit dans l'exemple ci-dessus. Jetez un coup d'œil à ceci- https://github.com/mukulbansal93/deterministique-Trireading .

Maintenant, après avoir dit cela, l'allocation réelle de la CPU à un thread ou à un processus est entre les mains du système d'exploitation. Donc, il est possible que les threads obtiennent les cycles de la CPU dans un ordre différent à chaque fois que vous exécutez le même programme. Donc, vous ne pouvez pas atteindre le déterminisme dans l'ordre des threads attribués des cycles de processeur alloués. Toutefois, en déléguant efficacement les tâches entre les threads, de telles tâches séquentielles sont attribuées à un seul thread, vous pouvez obtenir du déterminisme dans l'exécution globale des tâches.

Aussi, pour répondre à votre question sur la simulation d'un crash. Tous les algorithmes de planification modernes de la CPU sont libres de la famine. Donc, chaque fil est tenu d'obtenir des cycles de processeur garantis. Maintenant, il est possible que votre accident soit le résultat de l'exécution d'une certaine séquence de threads sur un seul processeur. Il n'existe aucun moyen de remédier à la même commande d'exécution ou à la même commande d'allocation de cycle de la CPU. Cependant, la combinaison d'algorithmes de planification modernes de la CPU étant la loi sans faim et la loi de Murphy vous aidera à simuler l'erreur si vous exécutez suffisamment votre code.

PS, la définition de suffisamment de fois est assez vague et dépend de nombreux facteurs tels que les cycles d'exécution ont besoin de la totalité du programme, du nombre de threads, etc. mathématiquement parler, une façon de calcul brut de calculer La probabilité de simuler la même erreur causée par la même séquence d'exécution est sur un seul processeur est -

1 / Nombre de façons d'exécuter toutes les opérations atomiques de tous les threads définis

Par exemple, un programme avec 2 threads avec 2 instructions atomiques peut chacune des cycles de processeur alloués de 4 manières différentes sur un seul processeur. La probabilité serait donc 1/4.