Uni ed Interference-free Parallel, Concurrent and - ETH E

Diss. ETH No. 24002
Unified Interference-free Parallel,
Concurrent and Distributed
Programming
A thesis submitted to attain the degree of
DOCTOR OF SCIENCES of ETH ZURICH
(Dr. sc. ETH Zurich)
presented by
Mischael Schill
Master of Science ETH in Computer Science
born on
July 26th, 1984
citizen of
Winterthur, Switzerland and Austria
accepted on the recommendation of
Prof. Dr. Bertrand Meyer, examiner
Prof. Dr. Friedemann Mattern, co-examiner
Prof. Dr. Richard Paige, co-examiner
Dr. Piotr Nienaltowski, co-examiner
2016
Abstract
Concurrency, the art of doing many things at the same time, is growing in importance
every year. For almost a decade, computers are no longer getting faster the same way
they have been before, but they gain the ability to do more work in parallel. Most
modern programs and their functionality rely on global distributed infrastructure:
communication between computers has become essential, distributed systems are becoming the norm, not the exception.
Although the integration of systems and programs becomes tighter and tighter,
two areas are still most often treated as separate: local concurrency and parallelization, versus distribution. While there are concurrency programming models that can
operate in both areas, they are often a compromise: they rarely take full advantage
of shared memory available in a machine and, at the same time, give the developers
inadequate tools to handle complex atomicity violations. The result is that software is
often written using an unsafe multi-threading approach coupled with simple message
passing for communication between computers.
This work improves the current state of the art in two ways. First by addressing
the problem that these models often disregard the dependencies between requests,
resulting in atomicity violations similar to data races. Second by reconciling models
for concurrency and distribution with shared memory.
For the first, this work extends the Scoop concurrency model for distributed programming. Scoop provides interference-freedom to minimize atomicity violations,
but is restricted to local computing only. With distribution, failure handling is important: we present a novel approach — compensations s— which are inspired by
transactions, to let supplier and clients both contribute to failure mitigation. The core
semantics of distributed Scoop, the result of this endeavor, is described formally using a transition semantics that can be used as a specification for implementations.
A prototype of D-Scoop shows that interference-freedom can be achieved without
sacrificing performance.
For the second, this work presents two techniques:
Slicing A technique for handling arrays
Immutable Classes A technique for handling complex immutable data
With our work on integration of shared memory computing and distribution we
combine local concurrency and parallelism with distribution to form a general model.
vii
Zusammenfassung
Nebenläufigkeit, die Kunst viele Dinge gleichzeitig zu tun, wird wichtiger von Jahr zu
Jahr. Seit fast einem Jahrzeht werden Computer nicht mehr in dem Masse schneller
wie davor, aber sie erhalten die Fähigkeit mehr Arbeit parallel erledigen zu können.
Die meisten Programme und ihre Funktionalität stützen sich auf eine global verteilte
Infrastruktur: Die Kommunikation zwischen Computern wurde essentiell, verteilte
Systeme werden zur Norm.
Obwohl die Integration von Systemen und Programm immer enger und enger
wird, werden zwei Gebiete häufig immer noch getrennt behandelt: Lokale Nebenläufigkeit und Parallelität gegenüber Verteilten System. Während zwar Programmiermodelle für Nebenläufigkeit existieren, die für beide Gebiete geeignet sind, sind diese
häufig ein Kompromiss: Sie ziehen selten das Maximum aus der Verfügbarkeit von
gemeinsamen Speicher einer Maschine, und geben gleichzeitig dem Entwickler nur
inadäquate Wekzeuge zur Vermeidung von komplexen Atomizitätsverletzungen zur
Hand. Das Resultat ist, dass Software oft noch immer mit einem unsicheren Prozessmodell in Kombination mit einfachem Nachrichtenaustausch erstellt werden.
Diese Arbeit bringt den aktuellen Stand der Technik auf zwei Arten vorwärts: Sie
nimmt sich des Problems, dass solcherlei Modelle die Abhängigkeiten zwischen Anfragen, welche zu Atomizitätsverletzungen führen, oft ignorieren sowie des Problems
der Vereinheitlichung von Nebenläufigkeit und verteilten Systemen mit gemeinsamen
Speicher, an.
Für ersteres präsentiert diese Arbeit eine Erweiterung des Scoop Modells für die
Verwendung in verteilten Systemen. Scoop verfügt über ein Konzept der Interferenzfreiheit um Atomizitätsverletzungen zu minimieren, aber es ist bis jetzt auf die Verwendung als lokales System beschränkt. In verteilten Systemen ist die Handhabung
von Fehlern prioritär, darum präsentieren wir einen neuartigen Anzatz, Kompensationen, inspiriert von Transaktionssystemen, um den Befehlsempfänger sie auch den
Befehlssender an der Fehlerbehebung teilhaben zu lassen. Die Kernsemantik von verteiltem Scoop, genannt D-Scoop, das Resultat dieses Vorhabens, wird formal beschrieben mit einer Transaktionssemantik, welche als Spezifikation für Implementationen
verwendet werden kann. Ein Prototyp von D-Scoop zeigt, dass Interferenzfreiheit ohne Einbussen von Effizienz erreicht werden kann.
Für letzteres präsentiert diese Arbeit gleich zwei Techniken: Slicing, eine Technik
um Berechnungen über Felder zu parallelisieren; und Immutable Classes, eine Technik
um komplexe Datenstrukturen auf Unveränderlichkeit zu überprüfen.
Mit unserer Arbeit an der Integration von gemeinsamen Speicher und sicherem
verteilten Rechnen können wir lokale Nebenläufigkeit und Parallelität mit verteilten
Systemen kombinieren um ein generelles Modell zu formen.
viii

Download Report