- Applications of wait/lock-free protocols to real-time systems
- Project no: A8-9805
- Philippas Tsigas, Hans Hansson and Marina Papatriantafilou
- Chalmers University of Technology, Department of Computing Science
- Application as pdf. Support letter from Enea OSE systems AB, support is also given by Northern Real Time Applications.
- Mobility application May 1999.
- New project plan 00-08-20
- Prolongation application september 2001
- Support: 2 PhD student for 2 years decided 98-10-06. Mobility support 154 kkr decided 99-06-04.
- Start 99-03-01 with Håkan Sundell at Chalmers and 99-05-01 with Björn Allvin at MDH as PhD students, Yi Zhang join the project as PhD student March 2001 at Chalmers.
- Reports: at
-
Industry contacts
- Ken Tindell ktindell@nrtg.com
- Northern Real Time Applications
- Project: Wait-free snapshots in real-time systems: algoritms and performance
-
- ENEA OSE Systems AB
- Täby
- Project: Wait-free snapshots in real-time systems: algoritms and performance
Overview
In most real-time systems, concurrency and access to shared resources are controlled by
locking. A serious disadvantage is that locking may give rise to priority inversion, i.e.
situations in which a high-priority task has to wait for a low-priority task to release a lock.
That is a serious problem, because it can make a task miss its deadline, which, in turn can
cause various types of disaster in the system.
It is possible to share data and objects, without using locks. Wait/lock-free interprocess
communication/coordination permits access to concurrent objects without the use of locking;
thus, it offers guarantees not only regarding priority inversion , but also regarding efficiency and fault-tolerance. The wait-free condition guarantees progress and completion for
every job regardless of the execution speeds of the other
tasks in the system. Lock-free implementations have a more relaxed requirement:
locking is ruled out, as in wait-free implementations, but repeated interferences may cause a given operation to take longer time to
complete. Comparing the two, lock-free methods imply less-overhead, while wait-free methods guarantee fully predictable behaviour for every
task. The so-far experience with non- locking synchronisation has shown that it can offer
significant benefits in practice and -more significantly- it is efficient alternative to
lock-based synchronisation methods for managing concurrency and access to shared
resources. However, there has been only limited (although very successful and promising)
effort to study and apply the lock/wait-free synchronisation ideas on real-time systems and
in practice in general.
This project is to continue our recently started collaboration to explore the power and
applicability of non-locking synchronisation in real-time systems and applications, by com-
bining the experience of the two research groups in theses areas and the useful feedback
from the industrial nodes in the project.
Our aim in this project is to study and apply the lock/wait-free methods (each one where
appropriately suited) to derive new protocols and algorithms for real-time systems and
show how they can improve the system behaviour, compared with lock-based methods. An
im-portant area that we plan to explore is on real-time operating system kernels, in
particular wait/lock-free implementations of shared data structures. By introducing such
mechanisms, we expect to achieve:
- elimination of priority inversion and of deadlock
- fault-tolerance (as opposed to locking, which implies that the failure of a process
- which holds a lock will prevent others from making progress)
- scalability and uniformity between uni-processor and multi-processor systems (as
- opposed to locking, for which one needs to employ di erent methods)
- better task execution times and schedulability conditions (since absence of locking
- in- creases concurrency and prevents priority inversion)
- no change of the structure of the existing operating system kernel.
Results and contributions
In our work until now we presented new efficient non-blocking shared
data structures that are widely used in modern commercial real-time operating systems.
The performance of the new implementations was tested analytically and experimentally.
The results that are described in the papers listed below are very positive.
Co-operation
Industry and other sectors of society
The project has clear industrial relevance since the goal is to show
that (and how) commercial RT-kernels can be extended with wait-free/lock-free
mechanisms, as will be evaluated by real case-studies. Industrial
relevance is also indicated by the interest from our two industrial
partners: ENEA OSE Systems and Northern Real-Time Group. On the exploitation
side we expect that (if we are successful) wait free techniques will
be introduced in commercial RT-kernels and OSs.
We have receive the source code from ENEA and Northern Real-Time Technology.
ENEA OSE has expressed formally (with a letter signed by Lars its
support of the project and a non-disclosure agreement has been signed
from our site when taking the source code; since then, a number of
informal e-mail and phone contacts with technical nature have been
taken place. We expect the frequency of the contacts to increase as
we go along with the project.
Publications
- Björn Allvin, Hans Hansson, Andreas Ermedahl, H. Sundell, P. Tsigas: Evaluating the Performance of Wait-Free Snapshots in Real-Time Systems, In Swedish National Real-Time Conference SNART'99, August 1999.
- H. Sundell, P. Tsigas. Space Efficient Wait-Free Buffer Sharing in Multiprocessor Real-Time Systems Based on Timing Information. Chalmers University of Technology. Proceedings of RTCSA 2000 in
Cheju Island (South Korea) 12-14 December 2000. p. 433-440, 2000 IEEE press.
- H Sundell, P Tsigas, And Y. Zhang. Bounding Wait-Free Snapshot Algorithm
Buffers Using Timing Information. (To be submitted)
- H. Sundell, P. Tsigas, Y. Zhang, Simple and Fast Wait-Free Snapshots for Real-Time Systems,
Chalmers University of Technology, Proceedings of OPODIS 2000 in Paris (France) 20-22 December
2000. p. 91-106, Studia Informatica Universalis.
- P. Tsigas and Y. Zhang. The Effect of Faults on the Performance of
Non-blocking Shared Data Objects in Multiprocessor Systems. 1999
Pacific Rim International Symposium On Dependable Computing (PRDC
1999) part of the federated 1999 International Computer Congress
(ICC'99).
- Philippas Tsigas, Yi Zhang. Non-blocking Data Sharing in Multiprocessor
Real-Time System. In Proceedings of the 6th International Conference
on Real-Time Computing Systems and Applications (RTCSA '99), part
of the federated 1999 International Computer Congress (ICC '99),
IEEE press, pp. 247-254.
- Tsigas, P. and Y. Zhang (2001). Evaluating The Performance of Non-Blocking Synchronisation on Modern Shared-Memory Multiprocessors. ACM Sigmetrics 2001 / Performance 2001, ACM, pages: 320-321, 2001 ACM press.
- Tsigas, P. and Y. Zhang (2001). A Simple, Fast and Scalable Non-Blocking Concurrent FIFO queue for Shared Memory Multiprocessor Systems. 13th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '01), ACM.
|
