Wie testen Sie am besten eine Mutex-Implementierung?

Question

Was ist der beste Weg, eine Implementierung eines Mutex zu testen, ist in der Tat richtig? (Es ist notwendig, einen Mutex zu implementieren, Wiederverwendung ist keine praktikable Option)

Das Beste, was ich habe, ist, viele (N) gleichzeitige Threads zu haben, die iterativ versuchen, auf die geschützte Region (I) zuzugreifen, die hat ein Nebeneffekt (zB update auf ein globales), so dass die Anzahl der Zugriffe + Schreibvorgänge gezählt werden kann, um sicherzustellen, dass die Anzahl der Aktualisierungen des globalen genau (N) * (I) ist.

Haben Sie noch weitere Vorschläge?

Answer 1

Das erinnert mich an diese Frage über FIFO semaphore test. Auf den Punkt gebracht, meine Antwort war:

• Auch wenn Sie eine Spezifikation haben, vielleicht ist es nicht vermitteln Ihre Absicht genau
• Sie nachweisen können, dass der Algorithmus die Spezifikation erfüllt, aber nicht den Code (D.Knuth)
• -Test zeigt nur das Vorhandensein von Fehlern, nicht ihrer Abwesenheit (Dijkstra)

Also Ihr Vorschlag scheint ziemlich das Beste zu tun. Wenn Sie Ihr Vertrauen erhöhen möchten, verwenden Sie fuzzing, um die Planung und Eingabe zufällig zu gestalten.

Answer 2

Formaler Beweis ist besser als das Testen für diese Art von Sache.

Testen wird Ihnen zeigen, dass - solange Sie nicht Pech haben - alles funktioniert hat. Aber ein Test ist ein stumpfes Instrument; Es kann nicht genau die richtige Sequenz ausführen, um einen Fehler zu verursachen.

Es ist zu schwer, jede mögliche Abfolge von Vorgängen in der Hardware zu testen, um sicherzustellen, dass Ihr Mutex unter allen Umständen funktioniert.

Testen ist nicht ohne Wert; Es zeigt, dass Sie keine offensichtlichen Codierungsfehler gemacht haben.

Aber Sie brauchen wirklich eine formellere Code-Überprüfung, um zu demonstrieren, dass es die richtigen Dinge zur richtigen Zeit tut, so dass ein Client die Sperr-Ressource für richtige Mutex atomar beschlagnahmt. In vielen Plattformen gibt es spezielle Anweisungen, dies zu implementieren, und wenn Sie eine davon verwenden, haben Sie eine Chance, es richtig zu machen.

In ähnlicher Weise müssen Sie zeigen, dass die Freisetzung atomar ist.

Answer 3

Mit etwas wie einem Mutex kommen wir zurück zu der alten Regel, dass das Testen nur das Vorhandensein von Bugs, nicht die Abwesenheit, zeigen kann. Ein Testjahr wird Ihnen wahrscheinlich weniger sagen als einfach nur den Code zur Überprüfung zu stellen und zu fragen, ob jemand ein Problem damit sieht.

Answer 4

Wenn das Proof-Zeug für Sie nicht funktioniert, dann gehen Sie mit dem Test. Testen Sie alle möglichen Anwendungsfälle. Finde heraus, wie genau dieses Ding benutzt wird, wer es benutzt und wie es benutzt wird. Wenn Sie die Teststrecke gehen, sollten Sie jeden Test für jedes Szenario (Millionen, Milliarden, so viele wie möglich mit der Testzeit) durchführen.

Versuchen Sie, zufällig zu sein, weil Zufälligkeit Ihnen die beste Chance gibt, alle Szenarien in einer begrenzten Anzahl von Tests abzudecken. Stellen Sie sicher, dass Sie Daten verwenden, die nicht verwendet werden, aber verwendet werden können, und stellen Sie sicher, dass die Daten die Sperren nicht durcheinander bringen.

BTW, außer Sie wissen eine Tonne über Mathematik und formale Methoden Sie haben keine Chance, tatsächlich mit einem Beweis zu kommen.

Answer 5

Ich bin mit allen anderen, dass es unglaublich schwierig ist, abschließend zu beweisen, ich habe keine Ahnung, wie es geht - nicht hilfreich, ich weiß!

Wenn Sie sagen, implementieren Sie einen Mutex und diese Wiederverwendung ist keine Option, ist das aus technischen Gründen wie gibt es keine Mutex-Implementierung auf der Plattform/OS, die Sie verwenden oder aus einem anderen Grund? Wickelt man irgendeine Form von Betriebssystemlevel 'lock' und nennt es Ihre Mutex-Implementierung eine Option, zB CriticalSection auf windoze, posix Condition Variables? Wenn Sie eine OS-Sperre niedrigerer Ebenen einbinden können, ist Ihre Chance, es richtig zu bekommen, viel höher.

Falls Sie dies noch nicht getan haben, lesen Sie Herb Sutter's Effective Concurrency Artikel. Es sollte einige Sachen in diesen etwas wert zu Ihnen geben.

einige Dinge Wie dem auch sei, in Ihren Tests zu berücksichtigen:

• Wenn Ihr Mutex rekursiv ist (dh kann der gleiche Thread sperren es mehrere mal), dann stellen Sie sicher, einige Referenzzählung Tests durchführen.
• Mit Ihrer globalen Variable, die Sie ändern, wäre es am besten, wenn dies eine Variable wäre, die nicht at atomisch geschrieben werden kann. Wenn Sie z. B. auf einer 8-Bit-Plattform verwenden, verwenden Sie eine 16- oder 32-Bit-Variable, die mehrere Montageanweisungen zum Schreiben erfordert.
• Überprüfen Sie sorgfältig die Liste der Baugruppen. Abhängig von der Hardware-Plattform übersetzt die Assembly jedoch nicht direkt, wie der Code optimiert werden könnte ...
• Holen Sie sich jemand anderen, der den Code nicht geschrieben hat, um auch einige Tests zu schreiben.
• Test auf so viele verschiedene Maschinen mit unterschiedlichen Spezifikationen wie Sie können (unter der Annahme, dass dieser ‚Allzweck‘ und nicht für eine bestimmte Hardware-Setup)

Viel Glück!