Efficient Synchronized-by-Default Concurrency
Martin Bättig · Repository for Publications and Research Data (ETH Zurich) · 2019
Das Nebenläufigkeitsmodell "Synchronized-By-Default" (SBD) synchronisiert alle Zugriffe auf gemeinsamen genutzten Speicher standardmässig.Diese Synchronisierung wird erreicht, indem jede Instruktion eines Programmes ohne Ausnahme innerhalb einer Atomic-Section ausgeführt wird.Dies auch, falls der Code externe Nebeneffekte beinhaltet.Jeder Thread wird standardmässig in einer Atomic-Section ausgeführt.Ein Programmierer muss diese Atomizität explizit mittels einer Anweisung aufbrechen um Nebenläufigkeit zu erreichen.Das SBD-Nebenläufigkeits-Modell unterscheidet sich daher vom Modell der expliziten Synchronisation, in welchem der Programmierer Atomizität von Hand einfügen muss.Bei der expliziten Synchronisation resultiert fehlende Atomizität in Data-Races und Wettlaufssituationen, während beim SBD-Nebenläufigkeitsmodell fehlende Brüche in der Atomizität lediglich in Serialisierung resultiert.Eine naive Implementierung dieses Modells würde einen erheblichen Mehraufwand für die CPU bedeuten.Frühere Arbeiten an ähnlichen Modellen haben sich in erster Line darauf konzentriert zu simulieren, wie dieser Mehraufwand mittels Hardware-Transactional-Memory (HTM) reduziert werden kann und wie eine formale Beschreibung eines solchen Modells aussieht.In dieser Arbeit zeigen wir, wie man diesen Mehraufwand so weit reduziert, dass das Modell für realistische Applikation auf aktuell verfügbarer Hardware in Kombination mit Software-Transactional-Memory (STM) praktikabel wird.Dazu haben wir für SBD eine explizite transaktionale Semantik und mehrere neue STM-Techniken eingeführt.Diese Techniken in Kombination mit der richtigen Programmiertechnik ermöglichen es den Mehraufwand für die CPU und den Mehrverbrauch an Speicher entscheidend zu reduzieren.Im Kern von SBD steht die explizite transaktionale Semantik des Nebenläufigkeitsmodells. Diese Semantik erlaubt einem Programmierer den Mehraufwand zu reduzieren, indem er, wo nötig, Spekulation eliminiert, welche typischerweise in Transactional-Memory auftritt.Wir zeigen, dass diese Semantik, in Kombination v mit grossen Atomic-Sections, Objekt-Orientierung, automatischer Speicherverwaltung, intraprozeduralen statischen Analysen und transaktionalem I/O in gut skalierende Programme resultiert, welche einen moderaten CPU-Mehraufwand haben.Um grosse Atomic-Sections zu realisieren müssen Programmierer möglicherweise Konflikte entfernen um eine Serialisierung zu verhindern.Der bekannte Open-Nesting-Mechanismus ermöglicht ein Entfernen der Konflikte im Falle von kommutativen Operationen wie, z.B. dem Erhöhen eines Zählers, auf strukturierte Weise.Wir führen die Technik des Encapsulated-Open-Nesting ein, welche Open-Nesting erweitert.Encapsulated Open-Nesting ermöglicht es die Atomizität nur gerade so weit wie nötig aufzubrechen, um einen Konflikt zu lösen.Sie hat daher einen geringeren Programmieraufwand als reguläres Open-Nesting.Bei der Bearbeitung von grossen Datenmengen, z.B.Bilddaten, fällt ebenfalls eine grosse Menge an Synchronisierungs-Metadaten an.Dies kann den Speicherverbrauch eines Programmes unter SBD stark erhöhen, auch im Fall, wenn Zugriffe auf diese Daten letztlich selten erfolgen.Um diese Speichermenge zu reduzieren führen wir die Technik "Dynamic One-to-One Mapping" ein.Diese Technik ordnet Synchronisierungs-Metadaten automatisch je nach Verwendung zu und gibt sie bei Nichtverwendung wieder frei.Anders als z.B. bei Verwendung von Hashing, hat nach wie vor jede Speicherstelle ihre eigenen Metadaten.Daher ist "Dynamic One-to-One Mapping" kompatibel mit der expliziten transaktionalen Semantik des SBD-Nebenläufigkeitmodells.Gewisse Speicherstellen werden ausschliesslich von einem Thread gelesen und geschrieben.Das Laufzeitsystem kann dies statisch jedoch nicht feststellen und geht davon aus, dass mehrere Threads auf diese Speicherstellen gleichzeitig zugreifen können.In einem letzten Schritt führen wir eine Technik zur Erkennung dieser Speicherstellen und zur Reduktion des Synchronisationsaufwands ein.Dazu führen wir einen Instanz-Eigentums-Lebenszyklus ein, welcher einer STM ermöglicht zur Laufzeit zu bestimmen, ob eine Speicherstelle exklusiv von einem Thread verwendet wird.Diese Technik erlaubt weiterhin Synchronisation mittels Granularität auf Stufe von Instanz-Feldern und Array-Elementen und ist kompatibel mit der expliziten Semantik des SBD-Nebenläufigkeitsmodells.