Project plan
We plan to have two graduate students doing their doctorate research within the project, one at Mälardalen University in Västeråas and one at Chalmers University in Göteborg (additionally, we expect the Hard Real-Time Research group at Uppsala University (Andreas Ermedahl) to contribute).
Our aims include regular publications and presence at the important annual international meetings and conferences of the area, namely: the IEEE Real-Time Systems Symposium (RTSS), the Euromicro Conference on Real-Time Systems, the International Conference on Real-Time Computing Systems and Applications (RTCSA), and the Real-Time Technology and Applications Symposium (RTAS).
More precisely, the theme of the work that the two students will get involved in is to explore research advances in the area of lock-free synchronisation and non-blocking concurrent datastructures implementation and apply them for gaining in efficiency in the OS kernel level; the target is to develop an OS prototype, with a lock-free (non-blocking) kernel. Key problems that this research will involve are:
- Snapshot: i.e. taking an "instantaneous" picture of various independent components in the system, without "freezing" their execution. Snapshot objects are particularly useful and important tools for interprocess communication and coordination. Since they return to the scanner a consistent global state of the system, they provide sup- port for decision algorithms and they are also used to solve a variety of communication and synchronisation problems, e.g., consistency checking in transaction-based systems, distributed debugging, stable property detection (deadlock, stabilisation, termination, etc.), concurrent time-stamping, system monitoring and control, including many real- time applications [16, 18]. We already have some first results on this subject [8], where we build on previous work on the problem and on wait-free implementations with ap- plications in real-time systems [12, 6]; we study lock-based and lock/wait-free solutions both analytically and experimentally (using event-driven simulation) on a real-time sys- tem consisting of CAN-bus-connected nodes [1, 24] and we reveal the improvements that can be achieved by using lock-free and, even more, by a new wait-free algorithm.
- Agreement: this involves a set of tasks/jobs which are required to reach an irrevocable common decision, even if there are initial di erences of opinion about what the decision should be. It is among the most fundamental problems in distributed computing, since it lies in the heart of basic problems such as exclusion, resource allocation, symmetry breaking, synchronisation, distributed transaction commit/abort, and, hence, its solutions have direct and important applications in distributed operating systems, control systems and database systems. Moreover, it has been shown [10] that it is a key to the synchronization power of a system. Speci c paradigms of the problem that arise in practice in real-time process-control systems [25] include agreement on an estimate of an airplane's altitude based on the readings of multiple altimeters, or carrying out fault diagnosis procedures for some system component |combine individual diagnosis into a common decision about whether or not to replace some component, distributed database systems, among many others. We plan to build on several interesting protocols, derive the required concurrent data structures implementations (linked lists, stacks, queues, etc), implement our new algorithms and study their behaviour, especially from the point of view of how existing features of common architectures in real-time systems can be used to derive more efficient wait-free solutions to problems such as fault-tolerant consistent decision making [10, 17] and how these solutions can be applied and in uence the efficiency in these systems, using standard benchmarks for this type of real-time applications ([16, 18]).
The plan of the proposed work involves the following:
- Study of existing real-time operating systems and the architectures for which they are applicable on. The purpose of this is twofold: (a) to identify the data structures whose implementation is a signi cant factor for the performance of the respective real-time OS (eg run queue for Mach,...) (b) to identify the synchronization capabilities (via the wait-free agreement protocols that they support) of the architectures on top of which these OS are running. These will lead to the identi cation of the most efficient feasible ways for lock-free implementation of these basic kernel data structures for the respective architectures.
- Gradual incorporation of the new data structure implementations in the existing kernels; testing and evaluation. We believe that it is very important not to build a new OS from scratch, but only modify already existing ones; in this way we will be able rst to concentrate on the wait-free/lock-free aspects on real time OS and, second, to measure exactly the improvements; moreover, the expected bene ts of the OS may thus be immediately available to the community that is already using it.
- The study and development will throughout the project be guided by case-studies. Initially we will concentrate on using wait-free snapshots in an automotive diagnostics system.
On a more concrete level, the individual roles of the two (cooperating) graduate students will roughly be the following:
- The MdH student will focus on aspects related to the implementation of wait-free tech- niques in Real-Time kernels. This will, in addition to the actual implementation work, include evaluation and analysis of implementations and applications.
- The Chalmers student will focus on wait-free techniques and algorithms. This includes study of applications and existing kernels, development and analysis of algorithms, as well as evaluation of the use of algorithms.
<< previous: Related Research top