Abstract: In dynamic real-time task systems, tasks that are subject to deadlines are allowed to join and leave the system. In previous work, Stoica et al. and Baruah et al. presented conditions under which such joins and leaves may occur in fair-scheduled uniprocessor systems without causing missed deadlines. In this paper, we extend their work by considering fair-scheduled multiprocessors. We show that their conditions are sufficient on M processors, under all known (dynamic-priority) Pfair scheduling algorithms, if the utilization of every subset of M-1 tasks is at most one. Further, for the general case in which task utilizations are not restricted in this way, we derive sufficient join/leave conditions for the PD2 Pfair algorithm. We also show that, in general, these conditions cannot be improved upon without causing missed deadlines.

Abstract: Partitioning and global scheduling are two approaches for scheduling real-time tasks on multiprocessors. Though partitioning is sub-optimal, it has traditionally been preferred; this is mainly due to the fact that well-understood uniprocessor scheduling algorithms can be used on each processor. In recent years, global-scheduling algorithms based on the concept of proportionate fairness (Pfairness) have received considerable attention. Pfair algorithms are of interest because they are currently the only known method for optimally scheduling periodic, sporadic, and rate-based task systems on multiprocessors. In addition, there has been growing practical interest in scheduling with fairness guarantees. However, the frequency of context switching and migration in Pfair-scheduled systems has led to some questions concerning the practicality of Pfair scheduling.

In this paper, we investigate this issue by comparing the PD2 Pfair algorithm to the EDF-FF partitioning scheme, which uses first fit (FF) as a partitioning heuristic and the earliest-deadline-first (EDF) algorithm for per-processor scheduling. We present experimental results that show that PD2 is competitive with, and in some cases outperforms, EDF-FF. These results suggest that Pfair scheduling is a viable alternative to partitioning. Furthermore, as discussed herein, Pfair scheduling provides many additional benefits, such as simple and efficient synchronization, temporal isolation, fault tolerance, and support for dynamic tasks.

Abstract: Two important trends are expected to guide the design of next-generation networks. First, with the commercialization of the Internet, providers will use value-added services to differentiate their service offerings from other providers; such services require the use of sophisticated resource scheduling mechanisms in routers. Second, to enable extensibility and the deployment of new services in a rapid and cost-effective manner, routers will be instantiated using programmable network processors. In this research, our goal is to develop sophisticated multiprocessor scheduling mechanisms that would enable networks that deploy such router platforms to provide service guarantees to applications. Existing multiprocessor scheduling techniques are either not applicable to router platforms due to their complexity or simplistic assumptions, or are not based on rigorous formalism, which is necessary to enable strong assertions about service guarantees. In this work, we propose to address these limitations. This paper presents our current ideas and planned future directions.

Abstract: We consider the problem of scheduling periodic task systems on multiprocessors and present a deadline-based scheduling algorithm for solving this problem. We show that our algorithm successfully schedules on m processors any periodic task system with utilization at most m^2/(2m-1).

Abstract: We propose two server implementations for multiplexing aperiodic and recurrent (i.e., periodic, sporadic, or rate-based) real-time tasks in fair-scheduled multiprocessor systems. This is the first paper to consider the problem of integrating support for aperiodic tasks within fair multiprocessor scheduling algorithms. We also provide admission-control tests for the scheduling of hard aperiodic tasks (which have deadlines). Further, we point out some of the additional complexities involved in server-based implementations on multiprocessors and present some ways to handle them. Most of these complexities arise because of the parallelism that exists in such systems. Finally, we provide experimental results that demonstrate the effectiveness of our implementations.

Abstract: The PD2 Pfair/ERfair scheduling algorithm is the most efficient known algorithm for optimally scheduling periodic tasks on multiprocessors. In this paper, we prove that PD2 is also optimal for scheduling "rate-based" tasks whose processing steps may be highly jittered. The rate-based task model we consider generalizes the widely-studied sporadic task model.

Abstract: There has been much recent interest in multiprocessor Pfair and ERfair scheduling algorithms. Under Pfair scheduling, each task is broken into quantum-length subtasks, each of which must execute within a "window" of time slots. These windows divide each period of a task into potentially overlapping subintervals of approximately equal length. "Early-release" fair (ERfair) scheduling was recently proposed as a work-conserving variant of Pfair scheduling. Under ERfair scheduling, subtasks within the same job are allowed to execute before their Pfair windows.

In this paper, we prove that a simplified variant of the PD Pfair algorithm, called PD2, is optimal for scheduling any mix of early-release and non-early-release asynchronous tasks on a multiprocessor. This result breaks new ground in two ways. First, we are the first to consider the problem of scheduling both early-release and non-early-release tasks under a common framework. Second, all prior work on optimal multiprocessor Pfair or ERfair scheduling algorithms has been limited to synchronous periodic task systems.

Abstract: In this paper, we consider variants of Pfair and ERfair scheduling in which subtasks may be released late, i.e., there may be separation between consecutive windows of the same task. We call such tasks intra-sporadic tasks. There are two main contributions of this paper. First, we show the existence of a Pfair (and hence ERfair) schedule for any intra-sporadic task system whose utilization is at most the number of available processors. Second, we give a polynomial-time algorithm that is optimal for scheduling intra-sporadic tasks in a Pfair or ERfair manner on systems of one or two processors.

Abstract: We present a variant of Pfair scheduling, which we call early-release fair (ERfair) scheduling. Like conventional Pfair scheduling, ERfair scheduling algorithms can be applied to optimally schedule periodic tasks on a multiprocessor system in polynomial time. However, ERfair scheduling differs from Pfair scheduling in that it is work conserving. As a result, average job response times may be much lower under ERfair scheduling than under Pfair scheduling, particularly in lightly-loaded systems. In addition, runtime costs are lower under ERfair scheduling. This is because, in Pfair-scheduled systems, significant bookkeeping information is required to determine when a job of a task is and is not eligible for execution. In an ERfair system, this bookkeeping information is not required because, once released, a job continues to be eligible until it completes. To the best of our knowledge, ERfair scheduling is the first truly work-conserving scheduling discipline for periodic task systems that is optimal for multiprocessors.