DocumentCode :
2601498
Title :
MOCA: A multiprocessor on-line competitive algorithm for real-time system scheduling
Author :
Koren, Gilad ; Shasha, Dennis ; Huang, Shih-Chen
Author_Institution :
Courant Inst., New York Univ., New York, NY, USA
fYear :
1993
fDate :
1-3 Dec 1993
Firstpage :
172
Lastpage :
181
Abstract :
We study competitive on-line scheduling in multiprocessor real-time environments. In our model, every task has a deadline and a value that it obtains only if it completes by its deadline. A task can be assigned to any processor, all of which are equally powerful. The problem is to design an on-line scheduling algorithm (i.e., one in which the scheduler has no knowledge of a task until it is released) with worst case guarantees as to the total value obtained by the system. We study systems with two or more processors. We present an inherent limit on the best competitive guarantee that any on-line parallel real-time scheduler can give. Then we present a competitive algorithm that achieves a worst case guarantee which is within a small factor from the best possible guarantee in many cases. The models are a distributed system having a centralized scheduler as well as a shared memory multiprocessor
Keywords :
online operation; parallel algorithms; performance evaluation; processor scheduling; real-time systems; scheduling; synchronisation; MOCA; best possible guarantee; centralized scheduler; competitive algorithm; competitive guarantee; deadline; distributed system; multiprocessor on-line competitive algorithm; on-line parallel real-time scheduler; on-line scheduling; online scheduling; real-time system scheduling; shared memory multiprocessor; worst case guarantees; Algorithm design and analysis; Circuits; Distributed computing; Kernel; Multiprocessing systems; Power system modeling; Processor scheduling; Real time systems; Scheduling algorithm; Yarn;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Real-Time Systems Symposium, 1993., Proceedings.
Conference_Location :
Raleigh Durham, NC
Print_ISBN :
0-8186-4480-X
Type :
conf
DOI :
10.1109/REAL.1993.393503
Filename :
393503
Link To Document :
بازگشت