Supporting lock-free synchronization in Pfair-scheduled systems

We consider various techniques for implementing shared objects and for accounting for object-sharing overheads in Pfair-scheduled multiprocessor real-time systems. Lock-free objects are more economical than locking techniques when implementing relatively simple objects such as buffers, stacks, queues, and lists. In this paper, we explain how to bound the duration of lock-free object accesses under Pfair multiprocessor scheduling. We also show that these durations can be reduced by combining tasks into supertasks, i.e., a group of tasks that are scheduled as a single entity; this is because the use of supertasks can prevent interfering tasks from executing in parallel, thereby reducing the worst-case durations of object accesses. Indeed, we show that supertasking can even enable the use of less costly uniprocessor synchronization techniques when all tasks sharing an object reside in the same supertask. We illustrate these optimizations with a case study that focuses on shared queues. Finally, we present and experimentally evaluate a simple heuristic for assigning tasks to supertasks