On a real-time scheduling problem
SK Dhall, CL Liu - Operations research, 1978 - pubsonline.informs.org
SK Dhall, CL Liu
Operations research, 1978•pubsonline.informs.orgWe study the problem of scheduling periodic-time-critical tasks on multiprocessor computing
systems. A periodic-time-critical task consists of an infinite number of requests, each of
which has a prescribed deadline. The scheduling problem is to specify an order in which the
requests of a set of tasks are to be executed and the processor to be used, with the goal of
meeting all the deadlines with a minimum number of processors. Since the problem of
determining the minimum number of processors is difficult, we consider two heuristic …
systems. A periodic-time-critical task consists of an infinite number of requests, each of
which has a prescribed deadline. The scheduling problem is to specify an order in which the
requests of a set of tasks are to be executed and the processor to be used, with the goal of
meeting all the deadlines with a minimum number of processors. Since the problem of
determining the minimum number of processors is difficult, we consider two heuristic …
We study the problem of scheduling periodic-time-critical tasks on multiprocessor computing systems. A periodic-time-critical task consists of an infinite number of requests, each of which has a prescribed deadline. The scheduling problem is to specify an order in which the requests of a set of tasks are to be executed and the processor to be used, with the goal of meeting all the deadlines with a minimum number of processors. Since the problem of determining the minimum number of processors is difficult, we consider two heuristic algorithms. These are easy to implement and yield a number of processors that is reasonably close to the minimum number. We also analyze the worst-case behavior of these heuristics.