Predictable Synchronisation Algorithms for Asynchronous Critical Sections

Please always quote using this URN: urn:nbn:de:bvb:29-opus4-93953
  • Multi-core processors are ubiquitous. Even embedded systems nowadays use processors with multiple cores. Such use cases often impose latency requirements because they interact with physical objects. One consequence is a need for synchronisation algorithms that provide predictable latency, in addition to high throughput. A promising approach are asynchronous critical sections that avoid waiting even when a resource is occupied. This paper introduces two algorithms that allow for both synchronous and asynchronous critical sections. Both algorithms base on a novel wait-free queue. The evaluation shows that both algorithms outperform pre-existing synchronisation algorithms for asynchronousMulti-core processors are ubiquitous. Even embedded systems nowadays use processors with multiple cores. Such use cases often impose latency requirements because they interact with physical objects. One consequence is a need for synchronisation algorithms that provide predictable latency, in addition to high throughput. A promising approach are asynchronous critical sections that avoid waiting even when a resource is occupied. This paper introduces two algorithms that allow for both synchronous and asynchronous critical sections. Both algorithms base on a novel wait-free queue. The evaluation shows that both algorithms outperform pre-existing synchronisation algorithms for asynchronous requests, and perform similarly to traditional lock-based algorithms for synchronous requests. In summary, our synchronisation algorithms can improve throughput and predictability of parallel applications.show moreshow less

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics
Metadaten
Author:Stefan Reif, Wolfgang Schröder-Preikschat
URN:urn:nbn:de:bvb:29-opus4-93953
DOI:https://doi.org/10.25593/issn.2191-5008/CS-2018-03
ISSN:2191-5008
Series (Volume number):Technical reports / Department Informatik (CS-2018-03)
Document Type:Report
Language:English
Year of Completion:2018
Embargo Date:2018/02/22
Publishing Institution:Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU)
Release Date:2018/03/01
SWD-Keyword:Datenstruktur; Mehrkernprozessor; Nebenläufigkeit; Paralleler Algorithmus; Synchronisierung
Pagenumber:15
Institutes:Technische Fakultät / Department Informatik
CCS-Classification:C. Computer Systems Organization
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 005 Computerprogrammierung, Programme, Daten
open_access (DINI-Set):open_access
Licence (German):Keine Creative Commons Lizenz - es gilt der Veröffentlichungsvertrag und das deutsche Urheberrecht