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
Northern Real Time Applications
Project: Wait-free snapshots in real-time systems: algoritms and performance
Project: Wait-free snapshots in real-time systems: algoritms and performance


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.


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.


  1. 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.
  2. 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.
  3. H Sundell, P Tsigas, And Y. Zhang. Bounding Wait-Free Snapshot Algorithm Buffers Using Timing Information. (To be submitted)
  4. 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.
  5. 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).
  6. 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.
  7. 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.
  8. 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.
  Strategic Research