Browsing by Author "Subramani, K."

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    A Dual intepretation of Standard Constraints in Parametric Scheduling
    (2000-03-07) Subramani, K.; Agrawala, A.
    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)
  • Thumbnail Image
    Item
    The periodic polytope and its applications to a scheduling problem - A Static Perspective
    (2000-05-09) Subramani, K.; Agrawala, A.
    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)
  • Thumbnail Image
    Item
    The Static Polytope and its applications to a scheduling problem
    (2000-03-14) Subramani, K.; Agrawala, A.
    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)