Comment puis-je vérifier les algorithmes sans verrou?

Question

En théorie, il devrait être possible à la force brute au moins une vérification d'un algorithme sans blocage (il n'y a que tant de combinaisons appels de fonction) qui se croisent. Y a-t-il des outils ou de processus de raisonnement formel disponibles pour prouver effectivement qu'un algorithme sans verrouillage est correct (idéalement, il devrait également être en mesure de vérifier les conditions de course et le problème de l'ABA ainsi)?

Remarque: Si vous connaissez un moyen de simplement prouver un point (par exemple seulement prouver qu'il est sûr du problème ABA) ou un problème que je ne l'ai pas mentionné la solution puis après de toute façon. Dans le pire des cas, chaque méthode peut être fait à son tour pour vérifier complètement.

Answer 1

Vous devez absolument essayer le modèle rel="noreferrer"> checker.

Vous écrivez un modèle comme le programme dans un simple langage C comme appelé Promela, ce qui se traduit par Spin interne dans une machine d'état. Un modèle peut contenir plusieurs processus parallèles.

Qu'est-ce que Spin fait alors est de vérifier toutes les désentrelacement possibles d'instructions de chaque processus pour quelles que soient les conditions que vous voulez tester - généralement, l'absence de conditions de course, la liberté de tout interblocage etc. la plupart de ces tests peuvent être écrits facilement en utilisant des déclarations de assert(). En cas de séquence d'exécution possible qui viole une affirmation, la séquence est imprimée, sinon vous avez la « tout clair ».

(Eh bien, en fait, il utilise un algorithme plus rapide et beaucoup plus chics pour ce faire, mais qui est l'effet. Par défaut, tous les états du programme accessibles sont vérifiés.)

Ceci est un incroyable programme, il a remporté le 2001 ACM système Software Award (autres gagnants comprennent Unix, Postscript, Apache, TeX). Je me suis commencé à l'utiliser très rapidement, et dans quelques jours a été en mesure de mettre en œuvre des modèles des fonctions MPI MPI_Isend() et MPI_Irecv() dans Promela. Spin a trouvé un couple de difficile conditions de course dans un segment de code parallèle je me suis converti à travers Promela pour les tests.

Answer 2

Spin est en effet excellent, mais pensez aussi Relacy Détecteur de course par Dmitriy V'jukov. Il est construit à cet effet pour la vérification des algorithmes concurrents, y compris les algorithmes non-blocage (attentisme / sans blocage). Il est open source et libérale sous licence.

Relacy fournit des primitives de synchronisation et Windows (POSIX mutex, variables de condition, sémaphores, CriticalSections, événements win32, Interlocked *, etc.), de sorte que votre implémentation C ++ réelle peut être amené à Relacy pour vérification. Pas besoin de développer un modèle distinct de votre algorithme comme avec Promela et Spin.

Relacy fournit C ++ 0x std::atomic (commande de mémoire explicite pour la victoire!) Afin que vous puissiez utiliser #defines pré-processeur pour choisir entre la mise en œuvre de Relacy et votre propre implémentation atomique spécifique de la plate-forme ( TBB :: atomique,

Détection de la course de données est un problème NP difficile [Netzer & Miller 1990]

J'ai entendu parler des outils Lockset et DJiT + (ils enseigner au cours CDP). Essayez de lire les diapositives et googler ce qu'ils font référence à. Il contient des informations intéressantes.

Je ne sais pas quelle plate-forme ou la langue que vous utilisez - mais sur la plate-forme .Net il y a un projet de recherche de Microsoft appelé Echecs qui est à la recherche très prometteur à aider ceux d'entre nous faire des composants multithread - y compris sans blocage

.

Je ne l'ai pas utilisé une quantité énorme, l'esprit.

Il fonctionne (explication brute) en entrelaçant explicitement dans les discussions les plus serrés les moyens possibles pour forcer réellement vos bugs dans la nature. Il analyse également le code pour trouver des erreurs communes et les mauvaises habitudes -. Similaires à l'analyse de code

Dans le passé, j'ai aussi construit des versions spéciales du code en question (par blocs de #if etc) qui ajoutent des informations de suivi de l'état supplémentaire; compte, etc versions que je peux ensuite plonger dans l'intérieur d'un test unitaire.

Le problème avec cela est que cela prend beaucoup plus de temps pour écrire votre code, et vous ne pouvez pas toujours ajouter ce genre de choses sans changer la structure sous-jacente du code qui est déjà là.

Si vous voulez vérifier vraiment le code sans verrouillage (par opposition à tester de manière exhaustive un petit exemple), vous pouvez utiliser CCV ( http://vcc.codeplex.com ), un vérificateur déductive pour le code simultané C qui a été utilisé pour vérifier certains algorithmes sans verrouillage intéressants (par exemple, des listes sans verrouillage et hashtables redimensionnables à l'aide des pointeurs de danger, transaction multiversion optimiste le traitement, la virtualisation MMU, différentes primitives de synchronisation, etc.). Il fait la vérification modulaire et a été utilisé pour vérifier les morceaux non triviaux de code industriel (jusqu'à environ 20KLOC).

Notez toutefois que CCV est un vérificateur, pas un outil de chasse aux insectes; vous devrez faire une annotation importante sur votre code pour l'obtenir pour vérifier, et la courbe d'apprentissage peut être un peu raide. Notez également que suppose la cohérence séquentielle (comme la plupart des outils).

BTW, examen par les pairs ne sont pas une bonne façon de vérifier un algorithme concurrent (ou même un séquentiel). Il y a une longue histoire de personnages célèbres édition des algorithmes concurrents dans des journaux importants, pour avoir des bugs découverts des années plus tard.

Answer 3

Answer 4

Answer 5

Answer 6

Détection de la course de données est un problème NP difficile [Netzer & Miller 1990]

Answer 7

J'ai entendu parler des outils Lockset et DJiT + (ils

Answer 8

Je ne sais pas quelle plate-forme ou la langue que vous utilisez - mais sur la plate-forme .Net il y a un projet de recherche de Microsoft appelé Echecs qui est à la recherche très prometteur à aider ceux d'entre nous faire des composants multithread - y compris sans blocage

.

Je ne l'ai pas utilisé une quantité énorme, l'esprit.

Il fonctionne (explication brute) en entrelaçant explicitement dans les discussions les plus serrés les moyens possibles pour forcer réellement vos bugs dans la nature. Il analyse également le code pour trouver des erreurs communes et les mauvaises habitudes -. Similaires à l'analyse de code

Dans le passé, j'ai aussi construit des versions spéciales du code en question (par blocs de #if etc) qui ajoutent des informations de suivi de l'état supplémentaire; compte, etc versions que je peux ensuite plonger dans l'intérieur d'un test unitaire.

Le problème avec cela est que cela prend beaucoup plus de temps pour écrire votre code, et vous ne pouvez pas toujours ajouter ce genre de choses sans changer la structure sous-jacente du code qui est déjà là.

Answer 9

Si vous voulez vérifier vraiment le code sans verrouillage (par opposition à tester de manière exhaustive un petit exemple), vous pouvez utiliser CCV ( http://vcc.codeplex.com ), un vérificateur déductive pour le code simultané C qui a été utilisé pour vérifier certains algorithmes sans verrouillage intéressants (par exemple, des listes sans verrouillage et hashtables redimensionnables à l'aide des pointeurs de danger, transaction multiversion optimiste le traitement, la virtualisation MMU, différentes primitives de synchronisation, etc.). Il fait la vérification modulaire et a été utilisé pour vérifier les morceaux non triviaux de code industriel (jusqu'à environ 20KLOC).

Notez toutefois que CCV est un vérificateur, pas un outil de chasse aux insectes; vous devrez faire une annotation importante sur votre code pour l'obtenir pour vérifier, et la courbe d'apprentissage peut être un peu raide. Notez également que suppose la cohérence séquentielle (comme la plupart des outils).

BTW, examen par les pairs ne sont pas une bonne façon de vérifier un algorithme concurrent (ou même un séquentiel). Il y a une longue histoire de personnages célèbres édition des algorithmes concurrents dans des journaux importants, pour avoir des bugs découverts des années plus tard.