کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
432949 689134 2006 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Supporting lock-free synchronization in Pfair-scheduled real-time systems
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Supporting lock-free synchronization in Pfair-scheduled real-time systems
چکیده انگلیسی

We consider the use of lock-free techniques for implementing shared objects in real-time Pfair-scheduled multiprocessor systems. Lock-free objects are more economical than locking techniques when implementing relatively simple objects such as buffers, stacks, queues, and lists. However, the use of such objects on real-time multiprocessors is generally considered impractical due to the need for analytical real-time guarantees. In this paper, we explain how the quantum-based nature of Pfair scheduling enables the effective use of such objects on real-time multiprocessors and present analysis specific to Pfair-scheduled systems. In addition, we show that analytical improvements can be obtained by using such objects in conjunction with group-based scheduling techniques. In this approach, a group of tasks is scheduled as a single entity (called a supertask in the Pfair literature). Such grouping prevents tasks from executing simultaneously, and hence from executing in parallel. Consequently, grouping tasks can improve the worst-case scenario with respect to object contention. Grouping also enables the use of less costly uniprocessor algorithms when all tasks sharing an object reside within the same group. We illustrate these optimizations with a case study that focuses on shared queues. Finally, we present and experimentally evaluate a simple heuristic for grouping tasks in order to reduce object contention. Though the analysis presented herein focuses specifically on Pfair-scheduled systems, the observations and techniques should be applicable to other quantum-scheduled systems as well.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 66, Issue 1, January 2006, Pages 47-67