Search

In this paper, we discuss certifying algorithms for zero-clairvoyant scheduling (ZCS) problems. ZCS problems are a class of real-time scheduling problems defined in the E-T-C scheduling framework [Subramani, K. (2005) A comprehensive framework for specifying clairvoyance, constraints and periodicity in real-time scheduling. Comput. J., 48, 259–272]. In ZCS, the dispatcher has no knowledge of the execution time of a given job, even after the job has finished executing. A polynomial-time algorithm for ZCS was proposed in previous work of the first author [Subramani, K. (2007) A polynomial time algorithm for zero-clairvoyant scheduling. J. Appl. Logic, 5, 667–680]. However, the algorithm proposed therein is not certifying. The algorithm that we propose in this paper is certifying, in that it provides a structure that certifies the ‘yes’-instances and another structure that certifies the ‘no’-instances of ZCS problems. These structures make the discovery of implementation errors straightforward and greatly simplify the software development cycle. Moreover, the certifying algorithm has the same running time (asymptotically) as its non-certifying counterpart. We also show that the proposed certifying technique can be used to certify a class of mathematical programs called E-Quantified Polyhedral programs (E-QPPs). However, for E-QPPs, the proposed certifying algorithm has a higher asymptotic running time than its non-certifying counterpart. [ABSTRACT FROM AUTHOR]

Abstract: In the design of real-time systems, it is often the case that certain process parameters, such as the execution time of a job are not known precisely. The challenge in real-time system design then, is to develop techniques that efficiently meet the requirements of impreciseness, while simultaneously guaranteeing safety. In a traditional scheduling model, such as the one discussed in [M. Pinedo, Scheduling: Theory, Algorithms, and Systems, Prentice-Hall, Englewood Cliffs, 1995. ]; [P. Brucker, Scheduling Algorithms, second ed., Springer, 1998. ], the tendency is to either overlook the effects of impreciseness or to simplify the issue of impreciseness by assuming worst-case values. This assumption is unrealistic and at the same time, may cause certain timing constraints to be violated at run-time. Further, depending on the nature of the constraints involved, it is not immediately apparent, what the worst-case value for a given parameter is. Whereas, in traditional scheduling, constraints among jobs are no more complex than those that can be represented by a precedence graph, in case of real-time scheduling, complicated constraints such as relative timing constraints are commonplace. Additionally, the purpose of scheduling is to achieve a schedule that optimizes some performance metric, whereas in real-time scheduling the goal is to ensure that the imposed constraints are met at run-time. In this paper, we study the problem of scheduling a set of ordered, non-preemptive jobs 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. This modeling vastly extends previous models of execution times as either single points or range-bound intervals. Our algorithms do not assume any knowledge of the distributions of execution times, i.e. they are Zero-Clairvoyant. We present both sequential and parallel algorithms for determining the existence of a Zero-Clairvoyant schedule. To the best of our knowledge, our techniques are the first of their kind. [Copyright &y& Elsevier]