The problem and the main idea of the project
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.
The conventional methods to cope with this problem are based on having the kernel of the system dynamically adjust priorities to ensure bounds on the waiting times [15, 20, 21]; however, the problem of waiting due to blocking is still there [15, 20, 21], enforcing serialisation on the processes and causing concurrency bottlenecks and possibly also deadlocks.
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 (it eliminates this problem altogether), but also regarding efficiency (by allowing maximum concurrency and thus, low completion times) and fault-tolerance (no task is blocked due to a task that crashed while holding a lock). The wait-free condition guarantees progress and completion for every job (of every task) regardless of the execution speeds (and priorities) 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 (e.g. under extreme load conditions of the system) may cause a given operation to take longer time to complete. Comparing the two, lock-free methods imply less-overhead (i.e. in memory requirements), 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 dierent 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.