Pfair scheduling has usually been applied in the context of scheduling periodic tasks with coinciding periods and deadlines. This paper addresses the problem of scheduling hard real-time tasks characterized by arbitrary deadlines in a pfair manner on multiprocessor systems. We prove fundamental properties of the weight functions of such tasks and show that when such tasks are scheduled in a pfair manner every job of every task meets its deadline. We also present RRM (rational rate-monotonic), a static-priority scheme to schedule a set of such tasks, and derive demand-based sufficient conditions for determining the pfair schedulability of hard real-time tasks with arbitrary deadlines on multiprocessors under the RRM scheme. We also address the problem of accounting for interrupt-handling overheads in pfair systems and present a technique for implementing the priority ceiling protocol on pfair systems by modifying task weight functions.

This paper concerns the problem of scheduling sets of preemptable, periodic tasks on multiple resources. We consider a task model that allows arbitrary mixes of fixed and migratable tasks, and prove the existence of an optimal pfair scheduler in this model. Fixed tasks must always be scheduled on a given resource, while migratable tasks can be scheduled on different resources at different times. A pfair scheduler produces a periodic schedule in which the times each task is allocated a processor are approximately evenly spread throughout its period. This paper extends work of Baruah et al., who proved a similar result for systems in which all tasks are migratable.

SCRAMNet network cards provide a replicated shared memory via a high-speed, fiber-optic ring. Such systems combine the advantages of conventional shared-memory multiprocessors and message-passing networks by allowing a collection of different computers to access a shared memory with low latency. This paper presents several synchronization mechanisms --- both blocking and nonblocking --- for SCRAMNet systems. It is well known that, for general non-blocking synchronization, strong synchronization primitives such as compare-and-swap (CAS) or load-linked/storeconditional (LL/SC) are needed. SCRAMNet cards do not provide such primitives. However, we show that strong synchronization primitives can be implemented in software by exploiting certain features of SCRAMNet cards. In particular, we show that wait-free consensus can be solved in SCRAMNet systems, and we present a simple and efficient wait-free implementation of CAS. We also present new mutual exclusion and renaming algorithms for SCR...

Wait-free objects are often implemented through the use of a "helping scheme", whereby one process "helps" one or more other processes to complete an operation. This paper presents several new helping schemes that can be generally applied to efficiently implement a variety of different objects on priority-based uniprocessor and multiprocessor systems. Examples of such systems include lock-free multiprocessor kernels and real-time systems. Our helping schemes reduce overhead by exploiting the way in which processes are scheduled in priority-based systems. We illustrate the use of these schemes by presenting wait-free implementations of linked lists and a multi-word compare-and-swap primitive. 1 Introduction We consider the implementation of wait-free shared objects on multiprogrammed systems in which processes are scheduled for execution based on priority. We assume that processes are scheduled on a per-processor basis and do not migrate between processors during object accesses. Our ...

Several new wait-free object-sharing schemes for real-time uniprocessors and multiprocessors are presented. These schemes have characteristics in common with the priority inheritance and priority ceiling protocols, but are nonblocking and implemented at the user level. In total, six new object-sharing schemes are proposed: two for uniprocessors and four for multiprocessors. Breakdown utilization experiments are presented that show that the multiprocessor schemes entail less overhead than lock-based schemes.

This article considers the use of lock-free shared objects within hard real-time systems. As the name suggests,lock-freeshared objects are distinguished by the fact that they are accessed without locking. As such, they do not give rise to priority inversions, a key advantage over conventional, lock-based object-sharing approaches. Despite this advantage, it is not immediately apparent that lock-free shared objects can be employed if tasks must adhere to strict timing constraints. In particular, lock-free object implementations permit concurrent operations to interfere with each other, and repeated interferences can cause a given operation to take an arbitrarily long time to complete. The main contribution of this article is to show that such interferences can be bounded by judicious scheduling. This work pertains to periodic, hard real-time tasks that share lock-free objects on a uniprocessor. In the first part of the article, scheduling conditions are derived for such tasks, for both static and dynamic priority schemes. Based on these conditions, it is formally shown that lock-free shared objects often incur less overhead than object implementations based on wait-free algorithms or lock-based schemes. In the last part of the article, this conclusion is validated experimentally through work involving a real-time desktop videoconferencing system.

We present an integrated framework for developing real time systems in which lock-free algorithms are employed to implement shared objects. There are two key objectives of our work. The first is to enable functionality for object sharing in lock-free real time systems that is comparable to that in lock based systems. Our main contribution toward this objective is an efficient approach for implementing multiobject lock-free operations and transactions. A second key objective of our work is to improve upon previously proposed scheduling conditions for tasks that share lock-free objects. When developing such conditions, the key issue is to bound the cost of operation "interferences". We present a general approach for doing this, based on linear programming.

No abstract available.

This paper considers the use of lock-free shared objects within hard real-time systems. As the name suggests, lock-free shared objects are distinguished by the fact that they are not locked. As such, they do not give rise to priority inversions, a key advantage over conventional, lock-based object-sharing approaches. Despite this advantage, it is not immediately apparent that lock-free shared objects can be employed if tasks must adhere to strict timing constraints. In particular, lock-free object implementations permit concurrent operations to interfere with each other, and repeated interferences can cause a given operation to take an arbitrarily long time to complete. The main contribution of this paper is to show that such interferences can be bounded by judicious scheduling. This work pertains to periodic, hard real-time tasks that share lock-free objects on a uniprocessor. In the first part of the paper, scheduling conditions are derived for such tasks, for both static and dynamic priority schemes. Based on these conditions, it is formally shown that lock-free object-sharing approaches can be expected to incur much less overhead than approaches based on wait-free objects or lock-based schemes. In the last part of the paper, this conclusion is validated experimentally through work involving a real time desktop videoconferencing system.