Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.jss.2008.07.038 Byline: Ya-Shu Chen (a), Li-Pin Chang (b), Tei-Wei Kuo (c), Aloysius K. Mok (d) Keywords: Scheduling anomaly; Real-time task scheduling; Process synchronization; Scheduler stability Abstract: This research responds to practical requirements in the porting of embedded software over platforms and the well-known multiprocessor anomaly. In particular, we consider the task scheduling problem when the system configuration changes. With mutual-exclusive resource accessing, we show that new violations of the timing constraints of tasks might occur even when a more powerful processor or device is adopted. The concept of scheduler stability and rules are then proposed to prevent scheduling anomaly from occurring in task executions that might be involved with task synchronization or I/O access. Finally, we explore policies for bounding the duration of scheduling anomalies. Author Affiliation: (a) Department of Electronic Engineering, National Taiwan University of Science and Technology, Taipei 106, Taiwan (b) Department of Computer Science, National Chiao-Tung University, Hsin-Chu 300, Taiwan (c) Department of Computer Science and Information Engineering, National Taiwan University, Taipei 106, Taiwan (d) Department of Computer Sciences, The University of Texas at Austin, Austin, TX 78712, USA Article History: Received 8 June 2006; Revised 2 July 2008; Accepted 21 July 2008 Article Note: (footnote) [star] This paper is an extended version of the paper that appeared in .

In many emerging time-critical applications, the exact time of event occurrences may not be known. In such cases, events can be represented as a probabilistic occurrence within a time interval. Thus, monitoring of timing constraints, generally used in time-critical systems, needs to incorporate the uncertainty of event occurrences. In this paper, we propose mechanisms to monitor the satisfaction/violation of timing constraints that can be assessed probabilistically. We assume a uniform distribution of event occurrence within a time interval. Our proposed algorithm determines whether the probability that a timing constraint has been satisfied exceeds a specified threshold value. A confidence threshold is a minimum satisfaction probability of the timing constraint. A timing constraint is violated if the confidence threshold is not reached. We design an efficient monitoring algorithm for detecting timing violations of a set of timing constraints by finding the earliest expiration time (EET) for each timing constraint. Since it is critical to derive implicit constraints for early detection of violation of timing constraints, we present the derivation of the implicit constraints under uncertainty using an all-pairs shortest path algorithm. Further, we propose pruning techniques to discard unnecessary implicit constraints. We present the properties and proofs of our approach. [ABSTRACT FROM AUTHOR]

The well-known periodic task model of Liu and Layland [10] assumes a worst-case execution time bound for every task and may be too pessimistic if the worst-case execution time of a task is much longer than the average. In this paper, we give a multiframe real-time task model which allows the execution time of a task to vary from one instance to another by specifying the execution time of a task in terms of a sequence of numbers. We investigate the schedulability problem for this model for the preemptive fixed priority scheduling policy. We show that a significant improvement in the utilization bound can be established in our model. [ABSTRACT FROM AUTHOR]