Quelle est la meilleure façon de tester une mise en œuvre d'un mutex est en effet correcte? (Il est nécessaire de mettre en œuvre un mutex, la réutilisation n'est pas une option viable)
Le meilleur que j'ai proposé est d'avoir de nombreux (n) fils simultanés qui tentent de tenter d'accéder à la région protégée (i), qui a un effet secondaire (par exemple, la mise à jour d'un global) afin que le nombre d'accès + Les écrivies peuvent être comptées pour garantir que le nombre de mises à jour du global est exactement (n) * (i).
Toute autre suggestion?
5 Réponses :
La preuve formelle vaut mieux que tester ce genre de chose.
Les tests vous montreront cela - tant que vous n'êtes pas malchanceux - tout a fonctionné. Mais un test est un instrument émoussé; Il peut ne pas exécuter la séquence exacte exacte pour provoquer une défaillance.
Il est trop difficile de tester toutes les séquences d'opérations possibles disponibles dans le matériel pour être sûr que votre mutex fonctionne dans toutes les circonstances.
test n'est pas sans valeur; Il montre que vous n'avez pas fait d'erreurs de codage évidentes.
Mais vous avez vraiment besoin d'une inspection de code plus formelle pour démontrer que les bonnes choses aux hautes temps afin qu'un client saisisse atmériquement la ressource de verrouillage requise pour un mutex approprié. Dans de nombreuses plates-formes, il existe des instructions spéciales pour la mettre en œuvre et, si vous utilisez l'une de celles-ci, vous avez une chance de vous battre de la sorte.
De même, vous devez montrer que la libération est atomique.
Avec quelque chose comme un mutex, nous revenons à l'ancienne règle que les tests ne peuvent démontrer que la présence de bugs, pas l'absence. Une année de test vous dira probablement moins que de simplement mettre le code pour inspection et demander si quelqu'un voit un problème avec cela.
Si la preuve ne fonctionne pas pour vous, passez avec le test. Assurez-vous de tester tous les cas d'utilisation possibles. Découvrez comment exactement cette chose sera utilisée, qui l'utilisera et, encore une fois, comment elle sera utilisée. Lorsque vous allez à l'itinéraire d'essai, veillez à exécuter chaque test pour chaque scénario une tonne de fois (des millions, des milliards, autant que vous pouvez éventuellement entrer avec le temps de test que vous avez).
Essayez d'être aléatoire car le hasard vous donnera la meilleure chance de couvrir tous les scénarios dans un nombre limité de tests. Assurez-vous d'utiliser des données qui seront utilisées et des données qui peuvent ne pas être utilisées mais pourraient être utilisées et assurez-vous que les données ne gâchent pas les serrures.
BTW, sauf si vous connaissez une tonne sur les mathématiques et les méthodes formelles, vous n'aurez aucune chance d'obtenir une preuve.
Cela me rappelle cette question à propos de Test de semi-sémaphore FIFO . En bref, ma réponse était:
Votre proposition semble raisonnablement le meilleur à faire. Si vous souhaitez augmenter votre confiance, utilisez Fuzzing pour randomiser la planification et l'entrée.
Je suis avec tout le monde que cela est incroyablement difficile de prouver de manière concluante, je n'ai aucune idée de la façon de le faire - pas utile, je sais!
Lorsque vous dites implémenter un mutex et que la réutilisation n'est pas une option, c'est que, pour des raisons techniques, comme il n'y a pas de mise en œuvre mutex sur la plate-forme / OS que vous utilisez ou une autre raison? Embradonnez-vous une forme de «verrouillage» de niveau du système d'exploitation et appelez-la de votre implémentation mutex une option, par exemple une critique sur Windoze, des variables de condition POSIX? Si vous pouvez envelopper une serrure de niveau de niveau inférieur, vos chances de réussir sont beaucoup plus élevées.
Si vous ne l'auriez pas déjà fait, allez lire Concurrence efficace d'Herb Sutter Articles. Il devrait y avoir des choses que cela vaut quelque chose pour vous.
Quoi qu'il en soit, certaines choses à considérer dans vos tests:
bonne chance!
Bon point sur la taille de la valeur écrite. Mon problème principal est de vérifier que la combinaison des opérations de processeur (accessible via le compilateur intrinsique) utilisée est correcte à la fois théoriquement et logiquement (elle est algorithmique correctement) et pratiquement correcte (est la mise en œuvre comme compilée fidèle à l'algorithme logiquement correct)
Tester des mutiles (et des constructions similaires) est très très difficile. Je serais intéressé de savoir pourquoi vous ne pouvez pas utiliser une solution préexistante, testée et prouvée.