Multithread-Algorithmen sind besonders schwer zu entwerfen/debug/beweisen. Der Dekker-Algorithmus ist ein Paradebeispiel dafür, wie schwierig es sein kann, einen korrekten synchronisierten Algorithmus zu entwickeln. Tanenbaums moderne Betriebssysteme sind im IPC-Bereich mit Beispielen gefüllt. Hat jemand dafür eine gute Referenz (Bücher, Artikel)? Vielen Dank!Proving Korrektheit von Multi-Thread-Algorithmen
@Just bei: I ist. Aber nach dem, was ich gelernt habe, ist es für mich ein großer Schmerz, wenn ich dies für einen nicht trivialen Algorithmus mache. Das lasse ich für Leute mit Verstand. Ich habe gelernt, was ich weiß von Parallel Program Design: A Foundation (1988) von KM Chandy, J Misra
Es ist unmöglich, etwas zu beweisen, ohne auf Garantien aufzubauen, also das erste, was Sie tun möchten, ist sich mit vertraut zu machen das Speichermodell Ihrer Zielplattform; Java und x86 verfügen beide über solide und standardisierte Speichermodelle. Ich bin nicht so sicher über CLR, aber wenn alles andere fehlschlägt, werden Sie auf dem Speichermodell Ihrer Ziel-CPU-Architektur aufbauen. Die Ausnahme von dieser Regel ist, wenn Sie beabsichtigen, eine Sprache zu verwenden, die überhaupt keinen freigegebenen änderbaren Zustand zulässt - ich habe gehört, dass Erlang so ist.
ist das erste Problem der Gleichzeitigkeit wandelbar Staat geteilt.
, die durch befestigenden kann:
Die zweite prob lem der Nebenläufigkeit ist eine sichere Veröffentlichung. Wie stellen Sie Daten anderen Threads zur Verfügung? Wie führst du eine Übergabe durch? Sie werden die Lösung für dieses Problem im Speichermodell und (hoffentlich) in der API finden. Java bietet beispielsweise viele Möglichkeiten, den Status zu veröffentlichen, und das Paket java.util.concurrent enthält Tools, die speziell für die Kommunikation zwischen Threads entwickelt wurden.
Das dritte (und schwerer) Problem der Gleichzeitigkeit sperrt. Fehlgeschlagene Lock-Ordering ist die Quelle von Deadlocks. Sie können auf der Grundlage der Speichermodell-Garantien analytisch beweisen, ob in Ihrem Code Deadlocks möglich sind. Sie müssen Ihren Code jedoch so entwerfen und schreiben, dass die Komplexität des Codes die Durchführung einer solchen Analyse in der Praxis schnell unmöglich macht.
Dann, sobald Sie haben, oder bevor Sie, die korrekte Verwendung von Gleichzeitigkeit beweisen, werden Sie Single-Threaded Richtigkeit beweisen. Die Menge der Fehler, die in einer gleichzeitigen Codebasis auftreten kann, entspricht der Menge der Programmfehler mit Singlethreading und allen möglichen Nebenläufigkeitsfehlern.
Kurze Antwort: es ist schwer.
Es gab einige wirklich gute Arbeit im Dezember SRC Modula-3 und Lärchen Sachen aus den späten 1980er Jahren.
z.B.
Thread synchronization: A formal specification (1991) von AD Birrell, JV Guttag, JJ Horning, R Levin System Programming mit Modula-3, Kapitel 5
Extended static checking (1998) von David L. Detlefs, David L. Detlefs, K. Rustan, K. Rustan, M. Leino, M. Leino, Greg Nelson, Greg Nelson, James B. Saxe, James B. Saxe
Einige der guten Ideen von Modula - 3 machen es in die Java-Welt, z.B. JML, obwohl "JML ist derzeit auf sequentielle Spezifikation beschränkt" sagt die intro.
Der Link gatekeeper.dec.com ist beschädigt, aber der DEC SRC-Bericht zur erweiterten statischen Prüfung ist unter http://research.microsoft.com/en-us/um/people/leino/papers/src-159.pdf verfügbar . Ich stimme zu, ESC war wirklich eine gute Arbeit. –
Ich habe keine konkreten Referenzen, aber vielleicht möchten Sie sich die Owicki-Gries-Theorie (wenn Sie Theorembeweis mögen) oder die Prozesstheorie/Algebra (für die es auch verschiedene Modellprüfungswerkzeuge gibt) ansehen. .
The Pi-Calculus, A Theory of Mobile Processes ist ein guter Anfang.
"Principles of Concurrent und Distributed Programming", M. Ben-Ari
ISBN-13: 978-0-321-31283-9
Sie haben in der Safari Bücher online zum Lesen:
http://my.safaribooksonline.com/9780321312839
Das war ziemlich genau das, was ich suchte. Vielen Dank! – Leandro
@Leandro: Wenn es "ziemlich genau" war, was Sie gesucht haben, dann können Sie die Antwort "akzeptieren". –
Probieren Sie es aus. – GEOCHET