CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Simple Wait-Free Snapshots for Real-Time Systems with Sporadic Tasks

Håkan Sundell (Institutionen för datavetenskap, Datakommunikation och Distribuerade System) ; Philippas Tsigas (Institutionen för datavetenskap, Datakommunikation och Distribuerade System)
10th International Conference on Real-Time and Embedded Computing Systems and Applications p. 325-340. (2004)
[Konferensbidrag, refereegranskat]

We present a simple and wait-free implementation of a snapshot shared data structure suitable for real-time systems with sporadic tasks. Snapshot mechanisms give the means to a real-time task to read a globally consistent set of variable values while other concurrent tasks are updating them. Such a mechanism can be used to solve a variety of communication and synchronization problems, including system monitoring and control of real-time applications. Typical snapshot implementations are based on mutual exclusion, which causes blocking. Besides from causing reduced overall system performance, blocking also complicates the scheduling analysis and can cause serious problems as priority inversion or dead-locks. To address those problems researchers have introduced non-blocking synchronization methods. The strongest form of non-blocking algorithms is wait-free, and is suitable for hard real-time systems as it gives guarantees in the form of worst-case execution times. In this paper we consider real-time systems with scheduling of periodic or sporadic tasks. Previous suitable wait-free snapshot algorithms are based on strong atomic primitives. By exploiting the timing information that is available and necessary to the real-time scheduler, we have designed a simpler wait-free snapshot algorithm that only relies on atomic read and writes. Experiments on a Sun Enterprise 10000 multiprocessor system show that the new algorithm, because of its simplicity, outperforms considerably the respective wait-free snapshot algorithm that is not using the timing information.

Nyckelord: wait-free, snapshot, real-time, non-blocking, shared memory, shared data structure, sporadic task



Denna post skapades 2006-08-25.
CPL Pubid: 1539

 

Institutioner (Chalmers)

Institutionen för datavetenskap, Datakommunikation och Distribuerade System (2002-2004)

Ämnesområden

Information Technology

Chalmers infrastruktur