A Post-Scheduling Optimization Algorithm of Distributed Real-Time Tasks
2005
To overcome the disadvantages of existing algorithms in scheduling distributed real-time tasks, this paper proposes a post-scheduling optimization algorithm (PSO) based on a novel structure called Scheduled Clusters Tree. As the experiments shows, PSO can minimize the number of required processors without affecting the optimal scheduling length generated by duplication-based algorithms, e.g., TDS or OSA algorithm. The time complexity of PSO algorithm is O(d|V|2) when TDS is adopted, or O(d2|V|2) when OSA is adopted. Where |V| is the number of tasks and d is the maximum degree of tasks in the corresponding DAG.
Keywords:
- Real-time computing
- Distributed computing
- Lottery scheduling
- I/O scheduling
- Two-level scheduling
- Fair-share scheduling
- Algorithm
- Dynamic priority scheduling
- Fixed-priority pre-emptive scheduling
- Multiprocessor scheduling
- Computer science
- Rate-monotonic scheduling
- Earliest deadline first scheduling
- Least slack time scheduling
- Flow shop scheduling
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
7
References
0
Citations
NaN
KQI