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

Space Efficient Wait-Free Buffer Sharing in Multiprocessor Real-Time Systems Based on Timing Information

Håkan Sundell (Institutionen för datavetenskap, Datakommunikation och Distribuerade System) ; Philippas Tsigas (Institutionen för datavetenskap, Datakommunikation och Distribuerade System)
Proceedings of the 7th IEEE International Conference on Real-Time Computing Systems and Applicatons (RTCSA 2000) p. 433-440. (2000)
[Konferensbidrag, refereegranskat]

A space efficient wait-free algorithm for implementing a shared buffer for real-time multiprocessor systems is presented in this paper. The commonly used method to implement shared buffers in real-time systems is based on mutual exclusion. Mutual exclusion is penalised by blocking that typically leads to difficulties in guaranteeing deadlines in real-time systems. Researchers have introduced non-blocking algorithms and data structures that address the above problems. Many of the non-blocking algorithms that appeared in the literature have very high space demands though, some even unbounded, which makes them not suitable for real-time systems. In this paper we look at a simple, elegant and easy to implement algorithm that implements a shared buffer but uses unbounded time-stamps and we show how to bound the time-stamps by using the timing information that is available in many real-time systems. Our analysis and calculations show that the algorithm resulting from our approach is space efficient. The protocol presented here can support an arbitrary number of concurrent read and write operations.

Nyckelord: Concurrent, wait-free, shared register, real-time, time-stamp

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


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

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


Information Technology

Chalmers infrastruktur