Direkt zum Inhalt | Direkt zur Navigation

Eingang zum Volltext

Lizenz

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:bsz:25-opus-83824
URL: http://www.freidok.uni-freiburg.de/volltexte/8382/


Bieniusa, Annette

Consistency, isolation, and irrevocability in software transactional memory

Konsistenz, Isolation und Unwiderruflichkeit in Software Transactional Memory

Dokument1.pdf (1.541 KB) (md5sum: e5b639193f8b1e35b5ef99c36005e7c3)

Kurzfassung in Englisch

Software transactional memory (STM) is a promising paradigm for the development of concurrent software. It coordinates the potentially conflicting effects of concurrent threads on shared memory by running their critical regions isolated from each other in transactions in an “all-or-nothing” manner. When encountering a conflicting access to shared memory, a conflict resolution strategy decides which transaction has to revert its changes and is restarted.
However, this automatic coordination is sometimes too restrictive: non-revertible operations such as I/O operations are disallowed in a transaction and some transactions fail for minor conflicts that could easily be resolved. In addition, most STM schemes focus on shared-memory architectures where costly memory updates impede scalability.
This thesis tackles these limitations by exploring extensions to the standard STM schemes. It discusses two novel STM algorithms which broaden the scope for applicability of STM and provide insights into the strength and limitations of transactional programming.
Twilight STM proposes to extend STM with non-revertible actions and inconsis- tency repair. It separates a transaction into a functional transactional phase, and an imperative irrevocable phase, which supports a safe embedding of I/O operations as well as a repair facility to resolve minor conflicts. In contrast to other implementations of irrevocable transactions, twilight code may run concurrently with other transactions including their twilight code without data races. Twilight STM further allows the implementation of application-specific conflict resolution strategies. To analyze their influence on the semantics of the transactions, a formal framework for investigating consistency and isolation properties is developed and applied to different repair operations.
Decent STM transfers the STM paradigm to a distributed setting. It is a fully decentralized object-based STM algorithm with versioning. It relies on mostly immutable data structures, which are well-suited for replication and migration. A randomized consensus protocol guarantees consistency of shared memory. Transactions may proceed tentatively before consensus has been reached. Object versioning ensures that transactions read from a consistent memory snapshot, and the consensus protocol determines which transactions can merge in their effects and which transactions need to restart. Hence, delayed communication, e.g. caused by retransmissions in the transport layer, can only affect performance, not consistency.
Both STM algorithms have been implemented in functional, object-oriented, and imperative languages, on multi-core and distributed architectures. This comprehensive study points out the need for an enhanced STM interface for more flexibility and higher programming convenience. Benchmarks featuring various workloads show the scalability and competitiveness with state-of-the-art systems.


Kurzfassung in Deutsch

Software transactional memory (STM) ist ein Programmiermodell zur Entwicklung nebenläufiger Programme. In diesem Modell werden potentiell konfligierende Datenzugriffe von Threads verhindert, indem kritischen Programmabschnitte voneinander isoliert in Form von Transaktionen ausgeführt werden. Tritt ein Zugriffskonflikt auf, wird er zur Laufzeit aufgelöst, indem Transaktionen ihre Änderungen rückgängig machen und die Berechnung erneut ausgeführt werden. Das Laufzeitsystem garantiert außerdem, dass die Modifikationen der transaktional verwalteten Daten konsistent und aus der Sicht der anderen Transaktionen atomar durchgeführt werden.
Eine solche transparente Konfliktstrategie ist bisweilen zu restriktiv: Transaktionen oft auf Grund von Konflikten abgebrochen, die einfach aufgelöst und kompensiert werden könnten. Sie erfordert außerdem, dass unumkehrbare Operationen, wie I/O, nicht innerhalb von Transaktionen ausgeführt werden. Außerdem ist das klassische STM-Modell auf Shared-Memory-Architekturen beschränkt, bei denen die Konsistenz der Daten in den lokalen Caches der Prozessoren durch Speicherbarrieren erzwungen werden.
Die vorliegende Dissertation beschreibt zwei neuartige Algorithmen, die zum einen das klassische STM um adaptive Konfliktstrategien und die Einbettung von I/O erweitert, zum anderen STM auch in verteilten System zur Anwendung bringt.
Twilight STM erlaubt die Einbettung unumkehrbarer Operationen sowie flexibler Konfliktbehandlungsstrategien für Transaktionen. Es teilt eine Transaktion in eine funktionale, transaktionale Phase, sowie eine imperative, irreversible Phase auf. Im Gegensatz zu anderen STM-Erweiterungen für irreversible Transaktionen können Twilight Transaktionen vollständig parallel ohne konfligierende Datenzugriffe ablaufen. Desweiteren erlaubt Twilight STM die Implementierung von anwendungsspezifischen Konfliktstrategien. Um deren Semantik zu analysieren, stellt die Dissertation ein formales System zur Verfügung und wendet es auf verschiedene Strategien an.
Decent STM transferiert STM in eine verteilte Ausführungsumgebung. Es ist ein dezentraler, objekt-orientierter STM-Algorithmus, der auf Datenversionierung aufbaut. Da Versionen nach ihrem Transfer in das dezentrale Speichersystem unveränderlich sind, können sie einfach repliziert und migriert werden. Ein randomisiertes Konsensusprotokoll garantiert die Konsistenz bei transaktionalem Datenzugriff. Darüberhinaus können Transaktionen optimistisch bereits vor Erreichen eines Konsensus ihre Berechnungen starten. Verzögerungen im Datentransfer beeinträchtigen daher lediglich die Geschwindigkeit des Programms, nicht jedoch die Konsistenz der Daten.
Die STM-Algorithmen sind in funktionalen, objekt-orientierten und imperativen Programmiersprachen, für Multi-Core-Architekturen und verteilte Systeme implementiert. Die vorliegende Dissertation bietet einen Überblick über die praktische Anwendbarkeit von STM und unterstreicht den Bedarf einer Erweiterung des Basismodells. Verschiedene Testprogramme belegen die Skalierbarkeit der Systeme und zeigen die Wettbewerbsfähigkeit in Bezug auf andere STM-Systeme.


SWD-Schlagwörter: Informatik
Freie Schlagwörter (deutsch): Nebenläufige Programmierung , Transaktionen , Konsistenz , Konsensus
Freie Schlagwörter (englisch): Concurrent Programming , Software Transactional Memory , Consistency , Snapshot Isolation , Consensus
CCS Klassifikation D.1.3 Conc
Institut: Institut für Informatik
Fakultät: Technische Fakultät (bisher: Fak. f. Angew. Wiss.)
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Erstgutachter: Thiemann, Peter (Prof. Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 28.09.2011
Erstellungsjahr: 2011
Publikationsdatum: 12.12.2011
Indexliste