Nebenläufigkeit und Speichermodelle
Nebenläufigkeit und Speichermodelle definieren, wie nebenläufige Programme strukturiert sind und wie ihre interagierenden Threads den gemeinsamen Speicher beobachten, was die Grundlage für korrekte parallele Software bildet.
Definition
Nebenläufigkeitsmodelle beschreiben, wie unabhängig ausgeführte Berechnungen zusammengesetzt werden und kommunizieren, während ein Speichermodell spezifiziert, welche Werte Lesezugriffe beobachten können, wenn nebenläufige Threads auf gemeinsamen Speicher zugreifen, und definiert den Vertrag zwischen Programmierer, Sprache und Hardware.
Scope
Dieser Bereich umfasst die Sprache und Theorie der Nebenläufigkeit: Prozesskalküle und Nebenläufigkeitsmodelle für Kommunikation und Synchronisation, Speicherkonsistenzmodelle, die die erlaubten Reihenfolgen von Speicheroperationen spezifizieren, Synchronisationsmechanismen und Datenkonfliktfreiheit (data-race freedom), sowie Typsysteme für Nebenläufigkeit wie Session-Typen. Es wird behandelt, wie Sprachen Programmen, die gleichzeitig ausgeführt werden und Zustände teilen, Bedeutung verleihen.
Sub-topics
Core questions
- Wie können nebenläufige kommunizierende Prozesse modelliert und begründet werden?
- Welche Reihenfolgen von Speicheroperationen kann ein Programm beobachten?
- Wie wird die Freiheit von Datenkonflikten (data races) garantiert oder spezifiziert?
- Wie können Typen die Kommunikation disziplinieren und Nebenläufigkeitsfehler verhindern?
Key theories
- Prozesskalküle
- Hoares CSP und Milners CCS und Pi-Kalkül bieten algebraische Theorien nebenläufiger, kommunizierender Prozesse mit Operatoren für Komposition und Synchronisation sowie Begriffen der Verhaltensäquivalenz (behavioral equivalence) wie Bisimulation.
- Sequentielle Konsistenz
- Lamport definierte sequentielle Konsistenz als die Anforderung, dass eine Multiprozessor-Ausführung als eine beliebige Verschachtelung der Operationen jedes Prozessors in Programmreihenfolge erscheint, die Basis, mit der schwächere Speichermodelle verglichen werden.
- Speicherkonsistenzmodelle
- Adve und Gharachorloo systematisieren das Spektrum der Shared-Memory-Konsistenzmodelle und erklären, wie entspannte Reihenfolgen (relaxed orderings) die Leistung ermöglichen, während sie die Argumentation über nebenläufige Programme erschweren.
Clinical relevance
Speichermodelle sind heute Teil der gängigen Sprachspezifikationen (zum Beispiel in C++ und Java), da Multicore-Hardware entspannte Reihenfolgen (relaxed orderings) beobachtbar gemacht hat; ihre korrekte Implementierung ist wesentlich für korrekte, portable nebenläufige Software. Prozesskalküle und Session-Typen beeinflussen das Design von Message-Passing-Sprachen und -Protokollen.
History
Die Theorie der Nebenläufigkeit entwickelte sich aus Petrinetzen und der Arbeit von Hoare (CSP) und Milner (CCS) in den 1970er Jahren, später dem Pi-Kalkül für mobile Prozesse. Lamport definierte 1979 die sequentielle Konsistenz; mit der Verbreitung entspannter Hardware wurden Speichermodelle in den 2000er Jahren für Sprachen wie Java und C++ formalisiert, und die Semantik schwacher Speicher (weak-memory semantics) wurde zu einem aktiven Forschungsgebiet.
Debates
- Starke versus entspannte Speicherkonsistenz
- Designer tauschen die intuitive Einfachheit starker Modelle wie der sequentiellen Konsistenz gegen die Leistung entspannter Modelle, die eine Neuordnung (reordering) zulassen, was die Argumentation erschwert und sorgfältige Sprachsemantik erfordert.
Key figures
- C. A. R. Hoare
- Robin Milner
- Leslie Lamport
- Sarita Adve
Related topics
Seminal works
- hoare1978
- milner1989
- lamport1979
- adve1996
Frequently asked questions
- Was ist ein Speichermodell?
- Ein Speichermodell ist der formale Vertrag, der spezifiziert, welche Werte ein Lesezugriff zurückgeben kann, wenn mehrere Threads auf gemeinsamen Speicher zugreifen, und definiert, welche Neuordnungen der Compiler und die Hardware durchführen dürfen und worauf sich der Programmierer verlassen kann.
- Was ist sequentielle Konsistenz?
- Sequentielle Konsistenz erfordert, dass eine nebenläufige Ausführung sich wie eine einzige Verschachtelung der Operationen der Threads verhält, die die Programmreihenfolge jedes Threads respektiert, was sie zum intuitivsten (aber oft entspannten) Speichermodell macht.