Method For Determining Earliest Deadline First Schedulability of Non-preemptive Uni-Processor System

The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventor(s), to the extent the work is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.

       In a real-time task scheduling systems, a typical goal is to schedule the system's tasks on a processor, or processors, so that each task completes execution before a specified deadline. The concept of a task that is invoked repeatedly is central to both the design and analysis of real-time systems. In particular, formal studies of real-time systems frequently represent the time-constrained processing requirements of the system as a set of periodic or sporadic tasks with deadlines.

       An important class of scheduling algorithms is the class of dynamic priority algorithms. In such systems, the priority of a task can change during its execution and in the most important dynamic priority algorithms, the priority of a job (instance of a task) is inversely proportional to its absolute deadline. Non-preemptive scheduling has become a mature technique and is being implemented atop of many commercial operating systems. However, the computation cost associated with respective feasibility condition is very high. Things become more complex for the non-preemptive version of the system as compared to the corresponding preemptive version. As compared to preemptive scheduling, non-preemptive systems have received very little attention from the research community and many efforts are taking place currently to contribute towards establishing new results for the non-preemptive counterpart.

       Specifically, all the existing feasibility analysis techniques exhibit high computational complexity and are thus impractical for online systems. For instance, these problems are NP-Hard in the strong sense and as a consequence, a decent share of the processor time is devoted to determine feasibility of the set of tasks, instead of the actual execution of tasks. For example, referring to the work of Chakraborty et al. in “Schedulability analysis of non-preemptive recurring real-time tasks”, in parallel and distributed processing symposium, and incorporated herein by reference in its entirety, it is shown that there exist polynomial time approximation algorithms for both preemptive and non-preemptive scheduling of recurring task model. However, the focus of the above work was to reduce the power consumption of the system. Accordingly, with respect to the feasibility determination problem, the work of Chakraborty et al. is still um-deterministic (i.e., NP Hard). Accordingly, there is a requirement for a method to determine, in a polynomial amount of time, the feasibility of scheduling a particular task set on a uni-processor system.