Efficient scheduling algorithms for real-time multiprocessor systems

Ramamritham, K. ; Stankovic, J. A. ; Shiah, P. F. (1990) Efficient scheduling algorithms for real-time multiprocessor systems IEEE Parallel and Distributed Technology: Systems and Applications, 1 (2). pp. 184-194. ISSN 1063-6552

Full text not available from this repository.

Official URL: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arn...

Related URL: http://dx.doi.org/10.1109/71.80146


Efficient scheduling algorithms based on heuristic functions are developed for scheduling a set of tasks on a multiprocessor system. The tasks are characterized by worst-case computation times, deadlines, and resources requirements. Starting with an empty partial schedule, each step of the search extends the current partial schedule by including one of the tasks yet to be scheduled. The heuristic functions used in the algorithm actively direct the search for a feasible schedule, i.e. they help choose the task that extends the current partial schedule. Two scheduling algorithms are evaluated by simulation. To extend the current partial schedule, one of the algorithms considers, at each step of the search, all the tasks that are yet to be scheduled as candidates. The second focuses its attention on a small subset of tasks with the shortest deadlines. The second algorithm is shown to be very effective when the maximum allowable scheduling overhead is fixed. This algorithm is hence appropriate for dynamic scheduling in real-time systems.

Item Type:Article
Source:Copyright of this article belongs to IEEE.
ID Code:62893
Deposited On:24 Sep 2011 05:10
Last Modified:24 Sep 2011 05:10

Repository Staff Only: item control page