Distributed algorithms for partially clairvoyant dispatchers
Real-time systems are increasingly appearing in complex and dynamic environments such as cruise controllers, life support systems and nuclear reactors. These systems contain components that sense, control and stabilize the environment towards achieving the mission or target. These consociate components synchronize, compute and control themselves locally or have a centralized component to achieve their mission. Distributed computing techniques improve the overall performance and reliability of large real-time systems with spread components. Partially Clairvoyant scheduling was introduced in Saksena, M., PhD thesis (1994) to determine the schedulability of hard real-time jobs with variable execution times. The problem of deciding the Partially Clairvoyant schedulability of a constrained set of jobs was well studied in Gerber, R., et al., IEEE Trans. Comput. 44(3), 471-479 (1995), Choi, S. and Agrawala, A.K., Real -Time Syst. 19(1), 5-40 (2000), Subramani, K., J. Math. Model. Algorithms 2(2), 97-119 (2003). These algorithms determine the schedulability of a job-set offline and produce a set of dispatch functions for each job in the job-set. The dispatch functions of a job depend on the start and execution times of the jobs sequenced before the job. The dispatching problem is concerned with the online computation of the start time interval of a job such that none of the constraints are violated. In certain situations, the dispatcher fails to dispatch a job as it takes longer to compute the interval within which the job has to be dispatched, this phenomenon is called Loss of Dispatchability. For a job-set of size n, sequential approaches using function lists suffer from two major drawbacks, viz., Omega (n) dispatching time and the Loss of Dispatchability phenomenon. Existing approaches to this problem have been along sequential lines, through the use of stored function lists. In this paper, we propose and evaluate three distributed dispatching algorithms for Partially Clairvoyant schedules. For a job-set of size n, the algorithms have dispatch times of O(1) per job. In the first algorithm, one processor executes all the jobs and other processors compute the dispatch functions. This scenario simplifies design and is better in situations where one processor controls all other devices. In the other algorithms, all the processors execute jobs preassigned to them and compute the dispatch functions; which is a plausible scenario in distributed controlling.
partial clairvoyance loss of dispatchability distributed dispatching real-time scheduling temporal constraints