Name
Abstract | ||
|---|---|---|
The application of static optimization techniques such as branch-and-bound to real-time task scheduling has been investigated. Few pieces of work, however, have been reported which propose and investigate on-line optimization techniques for dynamic scheduling of real-time tasks. In such task domains, the difficulty of scheduling is exacerbated by the fact that the cost of scheduling itself contributes directly to the performance of the algorithms and that it cannot be ignored. This paper proposes a class of algorithms that employ novel, on-line optimization techniques to dynamically schedule a set of sporadic real-time tasks. These algorithms explicitly account for the scheduling cost and its effect on the ability to meet deadlines. The paper addresses issues related to real-time task scheduling in the context of a general graph-theoretic framework. Issues related to where and when the task of scheduling is performed are also addressed. We compare two on-line scheduling strategies, namely an inter-leaving strategy and an overlapping strategy. In the former strategy, scheduling and execution are inter-leaving in time. Each scheduling phase performed by one processor of the system is followed by an execution phase. In the latter strategy, scheduling and execution are overlapping in time. A specified processor, in this strategy, is dedicated to perform scheduling. Results of experiments show that the proposed algorithms perform better than existing approaches, in terms of meeting deadlines and total execution costs, over a large range of workloads. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1109/HICSS.1996.495496 | HICSS (1) |
Keywords | Field | DocType |
multiprocessor architectures,inter-leaving strategy,dynamic scheduling,former strategy,real-time task scheduling,scheduling phase,real-time aperiodic tasks,scheduling cost,on-line optimization technique,latter strategy,overlapping strategy,on-line scheduling strategy,branch and bound,parallel algorithms,computer science,graph theory,resource management,computer architecture,scheduling algorithm,real time systems,real time | Fixed-priority pre-emptive scheduling,Fair-share scheduling,Computer science,Deadline-monotonic scheduling,Two-level scheduling,Rate-monotonic scheduling,Earliest deadline first scheduling,Dynamic priority scheduling,Round-robin scheduling,Distributed computing | Conference |
ISBN | Citations | PageRank |
0-8186-7324-9 | 4 | 0.47 |
References | Authors | |
6 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hamidzadeh Babak | 1 | 184 | 24.99 |
| Yacine Atif | 2 | 306 | 37.88 |