You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format. However, this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the Department of Computer Science of the University of Maryland at College Park under terms that include this permission. All other rights are reserved by the author(s).
The periodic polytope and its applications to a scheduling problem - A. K. Subramani. A. Agrawala. May 2000.
Parameter variability and the existence of complex constraints between tasks are assured features of real-time scheduling. {\em Periodicity} of task sets is an additional feature that needs to be accomodated. Traditional scheduling models ignore the complexities involved in real-time scheduling by making simplistic assumptions about task interactions. In this paper, we present a model that captures the issues that we deem central to real-time scheduling in periodic task sets and demonstrate the existence of efficient and easily implementable algorithms for addressing schedulability queries in this model. Our model is very general and applicable to diverse areas ranging from real-time process scheduling in operating systems and avionics to manufacturing and traffic control. (Also cross-referenced as UMIACS-TR-2000-25) University of Maryland Institute for Advanced Computer Studies, Department of Computer Science, University of Maryland\,
The Parametric Polytope and its applications to a Scheduling Problem. K. Subrmani. A. Agrawala. March 2000.
An important feature in Real-time systems is {\em parameter impreciseness} i.e. the inability to accurately determine certain parameter values. The most common such parameter is {\em task execution time}. A second feature is the presence of complex relationships between tasks that constrain their execution. Traditional models do not accomodate either feature completely: (a) Variable execution times are modeled through a fixed value ( {\em worst-case} ), and (b) Relationships are limited to those that can be represented by precedence graphs. We present a task model that effectively captures {\em variable task execution time}, while simultaneously permitting arbitrary linear relationships between tasks. Our model finds applications in diverse areas such as real-time task scheduling, compiler scheduling, real-time database scheduling and machine control. This paper focuses primarily on the computational complexity of answering queries posed in our model; in particular we demonstrate the existence of constraint classes that make the scheduling problem {\em hard.} (Also cross-referenced as UMIACS-TR-2000-16) University of Maryland Institute for Advanced Computer Studies, Department of Computer Science, University of Maryland,
The Static Polytope and its applications to a scheduling problem. K. Subramani. A. Agrawala. March 2000.
In the design of real-time systems, it is often the case that certain process parameters ( such as {\em execution time} ) are not known precisely. The challenge in real-time system design is to develop techniques that efficiently meet the requirements of impreciseness. Traditional models tend to simplify the issue of impreciseness by assuming {\em worst-case} times. This assumption is unrealistic and at the same time, may cause certain constraints to be violated at run-time. In this paper, we shall study the problem of scheduling a set of ordered, non-preemptive processes under non-constant execution times. Typical applications for variable execution time scheduling include process scheduling in Real-time Operating Systems such as Maruti, compiler scheduling, database transaction scheduling and automated machine control. An important feature of application areas such as robotics is the interaction between execution times of various processes. We explicitly model this interaction through the representation of execution time vectors as points in convex sets. We present both sequential and parallel algorithms for determining the existence of a static schedule. (Also cross-referenced as UMIACS-TR-2000-14) University of Maryland Institute for Advanced Computer Studies, Department of Computer Science, University of Maryland,
A Dual intepretation of Standard Constraints in Parametric Scheduling. K. Subramani. A. Agrawala. March 2000.
The problem of parametric scheduling in hard real-time systems, ( in the presence of linear relative constraints between the start and execution times of tasks ) was posed in the litreature. In an earlier paper, a polynomial time algorithm is presented for the case when the constraints are restricted to be standard ( defined in paper ) and the execution time vectors belong to an axis-parallel hyper-rectangle. In this paper, we extend their results in two directions. We first present a polynomial time algorithm for the case when the execution time vectors belong to arbitrary convex domains. We then show that the set of standard constraints can be extended to include arbitrary network constraints. Our insights into the problem occur primarily as a result of studying the dual polytope of the constraint system. (Also cross-refernced as UMIACS-TR-2000-11) University of Maryland Institute for Advanced Computer Studies, Department of Computer Science, University of Maryland,
Last Generated Fri Aug 11 04:01:01 EDT 2000