An improved dynamic scheduling algorithm for multiprocessor real-time systems

Author

Xiangbin, Zhu ; Shiliang, TU

Author_Institution

Dept. of Comput. Sci. & Eng., Fudan Univ., Shanghai, China

fYear

2003

fDate

27-29 Aug. 2003

Firstpage

710

Lastpage

714

Abstract

In the scheduling algorithms on multiprocessor real-time systems, the heuristic algorithm is an important algorithm and a known heuristic algorithm is myopic algorithm (K.Ramamritham, et. at., 1990). The performance of the myopic algorithm is greatly based on heuristic functions. We present an improved heuristic algorithm, which has a new heuristic function. The improved algorithm considers not only the deadlines and the resource requirements of a task, but also the processing time of the task. The most important metric for real-time scheduling algorithms is scheduling success ratio. To evaluate the effectiveness of the improved algorithm, we have done extensive simulation studies. The simulation results show that the scheduling success ratio of the improved heuristic algorithm is superior to that of myopic algorithm.

Keywords

computational complexity; distributed algorithms; dynamic scheduling; multiprocessing systems; processor scheduling; real-time systems; resource allocation; dynamic scheduling algorithm; heuristic algorithm; heuristic function; multiprocessor real-time system; myopic algorithm performance; real-time scheduling algorithm; resource task requirement; scheduling success ratio; task processing time; Computational modeling; Computer science; Dynamic scheduling; Heuristic algorithms; Job shop scheduling; Multiprocessing systems; Optimal scheduling; Processor scheduling; Real time systems; Scheduling algorithm;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Computing, Applications and Technologies, 2003. PDCAT'2003. Proceedings of the Fourth International Conference on

Print_ISBN

0-7803-7840-7

Type

conf

DOI

10.1109/PDCAT.2003.1236397

Filename

1236397