Non-blocking shared data structures for shared memory multiprocessor systems
Yi Zhang · 2001
The goal of this work is to implement non-blocking shared data objects for shared memory multiprocessor systems: real-time systems and high performance systems. Non-blocking synchronization has significant advantages over lock-based one: it is deadlock-free; it has better fault-tolerance behaviour; it eliminates the interference between synchronisation and the scheduler for real-time systems; it has better performance under high contention situations. In this thesis, we present non-blocking constructions for two fundamental shared data objects, read/write bu er and queue, which are widely used in real-time systems and high performance systems. Our constructions outperform the respective lock-based ones. The construction of real-time bu er extends previous results and is optimal with respect to space requirements. Both the schedulability analysis and the schedulability experiments show that the algorithm is applicable and efficient for real-time systems. Our