A constant-approximate feasibility test for multiprocessor real-time scheduling (Q2428689)

Given a set of \(m\) machines and a set of tasks, the problem of determining whether the tasks can be assigned to the machines such that each task is completed before its deadline is the feasibility testing problem for real-time scheduling. An instance of the problem is given by a finite set \(T\) of tasks that are to be executed by the system. Each task can generate many, even an infinite sequence of jobs. In the periodic version of the problem, a task \(\tau \in T\) is characterized by a quadruple of integers \(\langle o_{\tau}, C_{\tau}, D_{\tau}, T_{\tau}\rangle\), which are defined below. {\parindent=7mm \begin{itemize}\item[1)] \(o_{\tau}\) represents the time instance when the first job generated by the task is released; \item[2)] \(C_{\tau}\) represents the execution time of a job; \item[3)] \(D_{\tau}\) represents the relative deadline of a job; \item[4)] \(T_{\tau}\) represents the period of the task. \end{itemize}} Therefore, the \(k\)-th occurrence of a task is released at time \(o_{\tau} + (k - 1) T_{\tau}\), it will require \(C_{\tau}\) processing time, and it needs to be executed before time \(o_{\tau} + (k - 1) T_{\tau} + D_{\tau}\). In the sporadic version of the problem, each task is characterized by a triple \(\langle C_{\tau}, D_{\tau}, T_{\tau}\rangle\), where \(C_{\tau}\) and \(D_{\tau}\) is as defined above, while \(T_{\tau}\) defines the minimum separation time among jobs of a task. To illustrate this, the sporadic systems are not periodic, i.e., the time between the release of two consecutive jobs of a task is not constant, it may vary. However, it is bounded from below by \(T_{\tau}\). Notice that the sporadic version of the problem is more general since a periodic task is also sporadic. The problem also depends on whether the system is a single machine system or a multiprocessor system. In the case of a single machine systems it is known that the \textsc{Earliest Deadline First} (EDF) is an optimal scheduling algorithm for scheduling a sporadic task system. However, the feasibility problem for periodic or sporadic task systems is coNP-hard even on single machine systems. In multiprocessor systems, EDF is not an optimal algorithm and there is no known optimal online algorithm for the problem. Yet, there are optimal algorithms for some special cases. However, it is known that any collection of jobs that is feasible on \(m\) unit speed machines is EDF-schedulable on \(m\) machines with speed \(2 - \frac{1}{m}\), and this result is tight. The main contribution of this paper is an efficient approximate feasibility test for arbitrary-deadline sporadic systems with an approximation guarantee of \(2 - \frac{1}{m} + \epsilon\), for any fixed \(\epsilon > 0\). In other words, the authors give a test that, given a sporadic task system \(T\) and \(\epsilon > 0\), decides either that the system can be scheduled by the EDF algorithm on \(m\) machines with speed \(2 - \frac{1}{m} + \epsilon\) or there is an instance of the task system that cannot be scheduled on \(m\) unit speed machines. In order to prove their result, the authors define a concept called forward force demand. The forward force demand of the jobs on an interval gives a lower bound on the amount of execution that needs to be performed in that interval. The main observation is that if a given job sequence cannot be scheduled then there exists an interval such that the amount of computation to be carried out in that interval exceeds the computational capabilities of the system. An FPTAS for the load estimation is provided by giving an arbitrarily good estimate for the worst-case load of the sporadic system. The paper is very well written and it is easy to follow. Technically, it is quite involved and the results are far from being trivial. The paper provides tight bounds on a problem that is of both theoretical and practical importance.