Operating-System Support for Efficient Fine-Grained Concurrency in Applications

Betriebssystemunterstützung für effiziente feingranulare Nebenläufigkeit in Anwendungen

Please always quote using this URN: urn:nbn:de:bvb:29-opus4-133376
  • The steadily advancing trend towards multi- and manycore computing architectures bears enormous challenges for developers of application software. To be able to make efficient use of the raw parallelism provided by the hardware, programs must explicitly cater for that fact. The classic programming model of a multithreaded application process, which consists of a number of control flows (threads) managed and scheduled by the operating-system kernel within a shared address space, is being increasingly stretched to its limits: on the one hand, creating threads and switching between them is not sufficiently lightweight; on the other hand, structuring a parallel application around threads isThe steadily advancing trend towards multi- and manycore computing architectures bears enormous challenges for developers of application software. To be able to make efficient use of the raw parallelism provided by the hardware, programs must explicitly cater for that fact. The classic programming model of a multithreaded application process, which consists of a number of control flows (threads) managed and scheduled by the operating-system kernel within a shared address space, is being increasingly stretched to its limits: on the one hand, creating threads and switching between them is not sufficiently lightweight; on the other hand, structuring a parallel application around threads is often cumbersome and puts needless obstacles in the programmer’s way. A suitable alternative to multithreaded programming is the use of a so-called concurrency platform that supports developers in articulating applications as a conglomeration of fine-grained concurrent activities. Concurrency platforms come with a runtime system that is responsible for dispatching the lightweight work packages to the available computing resources. Such runtime systems generally build upon the abstractions provided by an underlying commodity operating system such as Linux – that is, upon threads as abstractions of processor cores. This construction results in a number of disadvantages: for instance, the operating system’s scheduler acts without consulting the runtime system, thus making decisions that are potentially unfavourable from the application’s point of view; the coexistence of multiple parallel application processes causes problematic reciprocal interference; blocking system calls cause a temporary loss of parallelism. This thesis presents AtroPOS, the design of an atrophied parallel operating system that is specially geared towards supporting concurrency platforms on manycore systems. AtroPOS is a derivative of the OctoPOS operating system and has undergone comprehensive further development; it rests on the paradigm of invasive computing and adopts its fundamental concepts: resource-aware programming, exclusive allocation of processor cores to applications, tailoring and dynamic reconfigurability. The operating-system kernel provides a boiled-down set of essential low-level abstractions on top of which arbitrary runtime libraries can be placed. InvRT, the invasive runtime system that supports executing applications of invasive computing, was developed as a reference runtime library. By default, AtroPOS makes the existing physical processor cores directly available to the application; their virtualisation is strictly optional and there is no notion of threads. The scheduling of user control flows is carried out purely on the user level by the runtime system without involving the operating-system kernel; this allows for the efficient handling even of very fine-grained concurrency within the application. System calls that may block within the kernel have asynchronous invocation semantics and return immediately upon blocking so that loss of parallelism during the waiting time is ruled out by design. Notification of completed system operations is carried out by means of a generic mechanism that passes user-defined data structures upward to the application and can be used by the runtime system to construct arbitrary synchronisation data structures such as futures. The same versatile mechanism is harnessed on tiled computing systems to allow parts of a distributed application to communicate with one another. In addition, AtroPOS offers configurable vertical isolation: the strict separation of the operating-system kernel from the application can be enabled and disabled in a coarse- and fine-grained manner, and both statically and dynamically. With this, type-safe applications can issue system calls as ordinary function calls and thus lower their direct and indirect costs. The aforementioned concepts were implemented in the AtroPOS kernel and the InvRT runtime system in the context of this thesis; they were evaluated with the aid of micro-benchmarks and various application suites. Moreover, the runtime library of the parallel programming language Cilk Plus – an extension of C/C++ – was ported to the AtroPOS interface in order to showcase the versatility of the approach.show moreshow less
  • Der stetig voranschreitende Trend hin zu Mehr- und Vielkernrechnerarchitekturen bringt enorme Herausforderungen für die Entwickler von Anwendungssoftware mit sich. Programme müssen speziell dafür ausgelegt sein, die von der Hardware bereitgestellte Parallelität effizient auszunutzen. Das klassische Programmiermodell eines mehrfädigen Anwendungsprozesses, bestehend aus mehreren vom Betriebssystemkern verwalteten und eingeplanten Aktivitätsträgern (Fäden) innerhalb eines gemeinsamen Adressraums, stößt hierbei zunehmend an seine Grenzen: Fäden sind einerseits in ihrer Erzeugung und Umschaltung zu schwergewichtig und legen andererseits Programmierern beim Strukturieren skalierbarer parallelerDer stetig voranschreitende Trend hin zu Mehr- und Vielkernrechnerarchitekturen bringt enorme Herausforderungen für die Entwickler von Anwendungssoftware mit sich. Programme müssen speziell dafür ausgelegt sein, die von der Hardware bereitgestellte Parallelität effizient auszunutzen. Das klassische Programmiermodell eines mehrfädigen Anwendungsprozesses, bestehend aus mehreren vom Betriebssystemkern verwalteten und eingeplanten Aktivitätsträgern (Fäden) innerhalb eines gemeinsamen Adressraums, stößt hierbei zunehmend an seine Grenzen: Fäden sind einerseits in ihrer Erzeugung und Umschaltung zu schwergewichtig und legen andererseits Programmierern beim Strukturieren skalierbarer paralleler Anwendungen oftmals unnötig Steine in den Weg. Eine geeignete Alternative zu mehrfädiger Programmierung ist die Benutzung einer sogenannten Nebenläufigkeitsplattform, die Entwickler darin unterstützt, Anwendungen als eine Menge von feingranularen nebenläufigen Aktivitäten auszudrücken. Nebenläufigkeitsplattformen beinhalten ein Laufzeitsystem, dessen Aufgabe es ist die leichtgewichtigen Arbeitspakete auf den verfügbaren Rechenressourcen zur Ausführung zu bringen. Das Laufzeitsystem baut hierbei üblicherweise auf den Abstraktionen auf, die ein darunterliegendes Standardbetriebssystem wie etwa Linux zur Verfügung stellt – also auf Fäden als Abstraktion von Rechenkernen. Diese Strukturierung bringt eine Reihe von Nachteilen mit sich: So agiert beispielsweise die Einplanung des Betriebssystems ohne Rücksprache mit dem Laufzeitsystem und trifft so potenziell für die Anwendung ungünstige Entscheidungen; die Koexistenz mehrerer paralleler Anwendungsprozesse verursacht problematische gegenseitige Beeinflussung; blockierende Systemaufrufe sorgen für den vorübergehenden Verlust von Parallelität. In dieser Arbeit wird AtroPOS vorgestellt, der Entwurf eines atrophierten parallelen Betriebssystems, das speziell für die Unterstützung von Nebenläufigkeitsplattformen auf Vielkernrechnern ausgelegt ist. AtroPOS ist eine umfassende Weiterentwicklung des Betriebssystems OctoPOS; es fußt auf dem Paradigma des invasiven Rechnens und übernimmt dessen Grundkonzepte: ressourcengewahre Programmierung, exklusive Vergabe der Rechenkerne an Anwendungen, Maßschneiderung und dynamische Rekonfigurierbarkeit. Der Betriebssystemkern stellt einen eingedampften Satz von essenziellen Abstraktionen auf niedriger Ebene bereit, auf denen beliebige Laufzeitbibliotheken aufsetzen können. Als Referenz hierfür wurde das invasive Laufzeitsystem InvRT entwickelt, das die Ausführung von Anwendungen des invasiven Rechnens ermöglicht. AtroPOS stellt der Anwendung standardmäßig die existierenden physikalischen Rechenkerne unmittelbar zur Verfügung; ihre Virtualisierung ist strikt optional und auf das Fadenkonzept wird konsequent verzichtet. Die Einplanung von Nutzerkontrollflüssen erfolgt rein auf Ebene des Laufzeitsystems und ohne Mitwirkung des Betriebssystemkerns; dies ermöglicht den effizienten Umgang selbst mit äußerst feingranular strukturierter Nebenläufigkeit auf Anwendungsebene. Systemaufrufe, die im Kern blockieren können, haben asynchrone Aufrufsemantik und kehren im Blockadefall sofort zurück, so dass während der Wartezeit prinzipbedingt keine Parallelitätseinbußen für das Nutzerprogramm auftreten können. Die Benachrichtigung über abgeschlossene Systemoperationen erfolgt mittels eines generischen Mechanismus, der nutzerdefinierte Datenstrukturen nach oben an die Anwendung reicht; hiermit lassen sich auf Ebene des Laufzeitsystems beliebige Synchronisationsdatenstrukturen wie etwa Ergebniszusagen konstruieren. Derselbe vielseitige Mechanismus wird zudem auf gekachelten Rechensystemen dafür genutzt, verteilten Anwendungsteilen die Kommunikation untereinander zu ermöglichen. Zusätzlich bietet AtroPOS konfigurierbare vertikale Isolation: Die strikte Trennung des Betriebssystemkerns von der Anwendung lässt sich auf grob- und feingranularer Ebene sowohl statisch als auch dynamisch ein- und ausschalten. Typsichere Anwendungen können so Systemaufrufe als gewöhnliche Funktionsaufrufe absetzen und damit ihre direkten und indirekten Kosten senken. Die genannten Konzepte des AtroPOS-Kerns und des InvRT-Laufzeitsystems wurden im Rahmen dieser Arbeit implementiert und anhand von Mikro-Benchmarks und diversen Anwendungssuiten ausgewertet. Ferner wurde die Laufzeitbibliothek der parallelen Programmiersprache Cilk Plus – einer Erweiterung von C/C ++ – auf die AtroPOS-Schnittstelle portiert, um die Vielseitigkeit des Ansatzes zu demonstrieren.show moreshow less

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics
Metadaten
Author:Christoph Erhardt
URN:urn:nbn:de:bvb:29-opus4-133376
Referee:Wolfgang Schröder-Preikschat, Jörg Nolte
Advisor:Wolfgang Schröder-Preikschat
Document Type:Doctoral Thesis
Language:English
Year of Completion:2020
Embargo Date:2020/03/08
Publishing Institution:Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU)
Granting Institution:Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Technische Fakultät
Date of final exam:2020/03/03
Release Date:2020/03/16
Tag:concurrency platform; invasive computing; manycore; multicore; operating system; parallelism
Pagenumber:1 – 234
Institutes:Technische Fakultät
Technische Fakultät / Department Informatik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 005 Computerprogrammierung, Programme, Daten
open_access (DINI-Set):open_access
Licence (German):Creative Commons - CC BY-NC-ND - Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International