The specification of the sporadic server real-time scheduling policy in the IEEE POSIX standard is defective, and needs to be corrected. Via experiments using a POSIX sporadic server implementation under Linux, as well as simulations, we have shown and confirmed previously unreported defects. We propose and demonstrate a corrected sporadic server formulation that eliminates these defects without changes to the syntax of the API or any significant increase in implementation complexity.

A scheduling policy or a schedulability test is defined to be sustainable with respect to a particular workload model if any task system represented in that model that is determined to be schedulable remains so if it behaves "better" than mandated by its specifications. We investigate the sustainability properties of global scheduling algorithms when applied to systems represented using the sporadic task model. We show that Fixed-Priority (FP) scheduling of sporadic task sets is sustainable under a variety of scheduling parameter relaxations, including decreased execution requirements, later arrivals, and deadline relaxations. It follows that all sufficient tests of global FP schedulability are sustainable for sporadic task systems. We show that the Earliest Deadline First (EDF) and Earliest-Deadline with Zero Laxity scheduling policies are sustainable with respect to decreased execution requirements and later arrivals. We also introduce a notion of self-sustainability, and show that many widely-used EDF schedulability tests are not self-sustainable but one is.

Recent results on the global multiprocessor EDF scheduling of sporadic task systems are, for the most part, applicable only to task systems in which each taskpsilas relative deadline parameter is constrained to be no larger than its period. This paper introduces new analysis techniques that allow for similar results to be derived for task systems in which individual tasks are not constrained in this manner.

Many contemporary disk drives have built-in queues and schedulers. These features can improve I/O performance, by offloading work from the system's main processor, avoiding disk idle time, and taking advantage of vendor-specific disk characteristics. At the same time, they pose challenges for scheduling requests that have real-time requirements, since the operating system has less visibility and control over service times. While it may be possible for an operating system to obtain more predictable real-time performance by bypassing the on-disk queue and scheduler, the diversity and continuing evolution of disk drives make it difficult to extract the necessary detailed timing characteristics of a specific disk, and to generalize that approach to all hard drives. This paper demonstrates three techniques we developed in the Linux operating system to bound real-time request response times for disks with internal queues and schedulers. The first technique is to use the disk's built-in starvation prevention scheme. The second is to prevent requests from being sent to the disk when real-time requests are waiting to be served. The third is to limit the length of the on-disk queue in addition to the second technique. Our results show the ability to guarantee a wide range of desired response times while still allowing the disk to perform scheduling optimizations. These techniques can be generalized to disks from different vendors.

A schedulability test is derived for the global earliest deadline zero laxity (EDZL) scheduling algorithm on a platform with multiple identical processors. The test is sufficient, but not necessary, to guarantee that a system of independent sporadic tasks with arbitrary deadlines will be successfully scheduled, with no missed deadlines, by the multiprocessor EDZL algorithm. Global EDZL is known to be at least as effective as global earliest-deadline-first (EDF) in scheduling task sets to meet deadlines. It is shown, by testing on large numbers of pseudo-randomly generated task sets, that the combination of EDZL and the new schedulability test is able to guarantee that far more task sets meet deadlines than the combination of EDF and known EDF schedulability tests.

Device drivers are integral components of operating systems. The computational workloads imposed by device drivers tend to be aperiodic and unpredictable because they are triggered in response to events that occur in the device, and may arbitrarily block or preempt other time-critical tasks. This characteristic poses significant challenges in real-time systems, where schedulability analysis is essential to guarantee system-wide timing constraints. At the same time, device driver workloads cannot be ignored. Demand-based schedulability analysis is a technique that has been successful in validating the timing constraints in both single and multiprocessor systems. In this paper we present two approaches to demand-based schedulability analysis of systems that include device drivers. First, we derive load-bound functions using empirical measurement techniques. Second, we modify the scheduling of network device driver tasks in Linux to implement an algorithm for which a load-bound function can be derived analytically. We demonstrate the practicality of our approach through detailed experiments with a network device under Linux. Our results show that, even though the network device driver does not conform to conventional periodic or sporadic task models, it can be successfully modeled using hyperbolic load-bound functions that are fitted to empirical performance measurements

A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks among the processors of an identical multiprocessor platform with static-priority scheduling on each individual processor. Since the partitioning problem is easily seen to be NP-hard in the strong sense, this algorithm is not optimal. A quantitative characterization of its worst-case performance is provided in terms of sufficient conditions and resource augmentation approximation bounds. The partitioning algorithm is also evaluated over randomly generated task systems

The load parameter of a sporadic task system is defined to be the largest possible cumulative execution requirement that can be generated by jobs of the task system over any time interval, normalized by the length of the interval. This parameter is known to play a very important role in the uniprocessor feasibility analysis of sporadic task systems. In this paper, it is shown that the load of a sporadic task system may be used as an accurate indicator of its feasibility upon preemptive multiprocessors as well. Exact algorithms, and approximate ones that can be guaranteed to be accurate to within an arbitrary additive error > 0, for computing a task system's load are presented and proven correct. The performance of these algorithms is evaluated by simulation over randomly generated task systems

This paper describes a necessary condition for feasibility of scheduling a set of sporadic hard-deadline tasks on identical multiprocessor platforms, which is also a sufficient condition if there is only a single processor. The key contribution is the characterization of the maximum, over all time intervals of a given length, of the amount of computation that must be completed to meet all deadlines, and a method of computing this function efficiently to any desired degree of accuracy. Empirical data are provided to verify that the new infeasibility test can be computed efficiently and is an improvement over previously known checks for infeasibility

A new schedulability test is derived for preemptive deadline scheduling of periodic or sporadic real-time tasks on a single-queue m-server system. The new test allows the task deadline to be more or less than the task period, and is based on a new analysis concept, called a /spl mu/-busy interval. This generalizes a result of Goossens et al. [2003] that a system of periodic tasks with maximum individual task utilization u/sub max/ is EDF-schedulable on m processors if the total utilization does not exceed m(1 /sup max/)+u/sub max/. The new test allows the analysis of hybrid EDF-US [x] scheduling, and the conclusion that EDF-US[1/2] is optimal, with a guaranteed worst-case schedulable utilization of (m +1)/2.

Schedulability tests are presented for preemptive earlier-deadline-first and deadline-monotonic scheduling of periodic or sporadic real-time tasks on a single-queue m-server system, in which the deadline of a task may be less than or equal to the task period. These results subsume and generalize several known utilization-based multiprocessor schedulability tests, and are derived via an independent proof.

A hidden but critical part of any real-time application is its runtime environment. If the application is coded in a high level language, the runtime environment includes a runtime system to support the programming language. That is likely to be layered over a real-time kernel, or even a full operating system. Over the past twenty years, there have been increasing governmental and market pressures for these layers to use off-the-shelf components and standard interfaces. The goal has been to enable the more rapid development of real-time applications, with a higher degree of platform independence. These pressures achieved visible results in the Ada language, the POSIX real-time operating system interfaces, and most recently the proposals for a real-time Java standard. In the roles of standards writers, implementors and users, the members of the POSIX Ada Real-Time project at the Florida State University have explored the problem of making these standard application program interfaces work for real-time systems. This has included implementation of the POSIX real-time extensions, and implementations of Ada runtime systems over both the POSIX and Java virtual machine interfaces. We have found that the degree to which the promises of these standards are kept depends very much on the ability of the real-time application developer to design within the paradigms supported by the standards, and on the quality of the implementations of the standards.

MiThOS (Micro-kernel Threads Operating System) is an experimental operating system for embedded systems. The system kernel is a first implementation of the POSIX Minimal Real-Time System Profile. It is based on prior work of a library implementation of Pthreads (POSIX threads). The system is fully preemptive. It supports multi-threading within a single process environment with shared kernel and user space, i.e. real-time tasks are mapped onto POSIX threads. It exhibits remarkable timing predictability intended for hard real-time requirements. This is achieved by a careful design of only few device drivers. The system has been implemented and tested on the SPARC VME architecture. The system includes a fast context switching algorithm for the SPARC which outperforms the context switch under SunOS and matches the performance under Solaris. It supports selective enabling and disabling of hardware components (MMU, caches, etc.) since its sources are available. Furthermore, an implementation-defined extension of POSIX threads for deadline scheduling is presented. Overall, the system exhibits slightly faster performance than SunOS 4.x and is considerably more predictable in its timing behavior. Applications of the kernel range from evaluating the overhead of new language features in Ada 95 and its runtime system, verifying static timing predictions on a bare machine, to providing the operating system for small embedded system that require a high timing predictability.

The paradigm of computing defined by real-time applications places significant requirements on programming languages, among them (1) interfacing to hardware devices, (2) maintainability, portability, reliability, and safely, (3) fault tolerance, and nonstop operation; (4) concurrency, and (5) achieving correct timing predictably (and the consequent paramount schedulability analyzability requirement). We trace how these requirements affect various mechanisms of a typical programming language. Ada9X/spl minus/a new emerging standard for Ada/spl minus/is then illustrated as an example of a serious attempt to address these requirements in a programming language standard. While Ada9X is far from perfect, it is a significant step, and we are hopeful for the trend of schedulability analyzable languages to gain momentum and continue.>

A novel technique for predicting point-to-point execution times on contemporary microprocessors is presented. It uses machine-description rules, similar to those that have proven useful for code generation and peephole optimization, to translate compiled object code into a sequence of very low-level instructions. The stream of micro-instructions is then analyzed for tuning, via a three-level pattern matching scheme. The timing tool is currently predicting execution time of code segments targeted for the Motorola 68020 and Intel 80386 processor. The timing tool has been integrated with a version of the vpo C compiler and the ease environment. A prototype has been built and preliminary tests are very promising.>

Ada 9X is a revision of the Ada programming language standard. This revision includes some changes that are intended to improve Ada's usefulness for real-time applications. The changes under consideration include multiple clocks, new forms of delay statements, a new low-level data synchronization scheme based on a limited form of priority inheritance, and a mechanism for asynchronously controlling the execution of a task. These proposals deserve critical evaluation and refinement before they become part of a new standard. The authors deal with time measurement and with a mechanism for synchronizing shared data. They address changes to the Ada priority scheduling model and discuss a mechanism for improving responsiveness to asynchronous events.>

The stack resource policy (SRP) is a resource allocation policy which permits processes with different priorities to share a single runtime stack. It is a refinement of the priority ceiling protocol (PCP), which strictly bounds priority inversion and permits simple schedulability tests. With or without stack sharing, the SRP offers the following improvements over the PCP: (1) it unifies the treatment of stack, reader-writer, multiunit resources, and binary semaphores; (2) it applies directly to some dynamic scheduling policies, including earliest deadline first (EDF), as well as to static priority policies; (3) with EDF scheduling, it supports a stronger schedulability test; and (4) it reduces the maximum number of context switches for a job execution request by a factor of two. It is at least as good as the PCP in reducing maximum priority inversion.>

Addresses the problem of scheduling a restricted form of Ada tasks so as to guarantee satisfaction of timing constraints. Specifically, the use of deterministic scheduling for periodic tasks communicating through rendezvous is studied. This extends the work of A.K. Mok (1984) scheduling deterministic rendezvous to a class of nondeterministic rendezvous constructs. A state-space approach is used to generate schedules consistent with task systems written in an Ada subset. An algorithm for searching for valid deterministic schedules among the possible schedules is presented, along with a description of an experimental implementation. The results of scheduling some simple task systems with this implementation are included.>

Periodic processes are major parts of many real-time embedded computer applications. The programming language Ada permits programming of simple periodic processes, but it has some serious limitations: producing Ada programs with real-time performance comparable to that of programs produced to date using traditional cyclic executives requires techniques that are specific to one machine or compiler. The authors present and evaluate the cyclic executive model for controlling periodic processes. The features and limitations of Ada for programming cyclic executive software are discussed and demonstrated, and some practical techniques for circumventing Ada problems are described.>

OverloadA simple method is presented for detecting ambiguities and finding the correct interpretations of expressions in the programming language Ada.Unlike previously reported solutions to this problem, which require multiple passes over a tree structure, the method described here operates in one bottom-up pass, during which a directed acyclic graph is produced.The correctness of this approach is demonstrated by a brief formal argument.

Several representations of P, the class of deterministic polynomial time acceptable languages, are compared with respect to succinctness. It is shown that requirements such as polynomial running time, verifiability of running time, and verifiability of accepting a set in P can be causes for differences in succinctness that are not recursively bounded. Relating succinctness to nondeterminism, it is shown that P ≠ NP if and only if the relative succinctness of representing languages in P by deterministic and nondeterministic clocked polynomial time machines is not recursively bounded. questions are posed, concerning the implications of P = NP, with respect to translatability and succinctness between other pairs of deterministic and nondeterministic representations for P.

A class of algorithms is presented for very rapid on-line detection of occurrences of a fixed set of pattern arrays as embedded subarrays in an input array. By reducing the array problem to a string matching problem in a natural way, it is shown that efficient string matching algorithms may be applied to arrays. This is illustrated by use of the string-matching algorithm of Knuth, Morris and Pratt [7]. Depending on the data structure used for the preprocessed pattern graph, this algorithm may be made to run “real-time” or merely in linear time. Extensions can be made to nonrectangular arrays, multiple arrays of dissimilar sizes, and arrays of more than two dimensions. Possible applications are foreseen to problems such as detection of edges in digital pictures and detection of local conditions in board games.

Some of the questions posed by Baker, Gill, and Solovay [1] are here answered. The principal result is that there exists a recursive oracle for which the relativized polynomial hierarchy exists through the second level; that is, there is a recursive set B such that Σ2P,B ≠ π2P,B. It follows that Σ2P,B ⊂≠ Σ3P,B.

We investigate relativized versions of the open question of whether every language accepted nondeterministically in polynomial time can be recognized deterministically in polynomial time. For any set X, let $\mathcal{P}^X (\text{resp. }\mathcal{NP}^X )$ be the class of languages accepted in polynomial time by deterministic (resp. nondeterministic) query machines with oracle X. We construct a recursive set A such that $\mathcal{P}^A = \mathcal{NP}^A $. On the other hand, we construct a recursive set B such that $\mathcal{P}^B \ne \mathcal{NP}^B $. Oracles X are constructed to realize all consistent set inclusion relations between the relativized classes $\mathcal{P}^X $, $\mathcal{NP}^X $, and co $\mathcal{NP}^X $, the family of complements of languages in $\mathcal{NP}^X $. Several related open problems are described.

In this paper we consider classes of Goedel numberings, viewed as simple models for programming languages, into which all other Goedel numberings can be translated by computationally simple mappings. Several such classes of Goedel numberings are defined and their properties are investigated. For example, one such class studied is the class of Goedel numberings into which all other Goedel numberings can be translated by finite automata mappings. We also compare these classes of Goedel numberings to the class of optimal Goedel numberings and show that translation into optimal Goedel numberings can be computationally arbitrarily complex, thus indicating that from a computer science point of view, optimal Goedel numberings have undesirable properties.