A Dynamic Scheduling Algorithm to Maximize the Total Value of Real-time Tasks running on a Single Processor
In‐Su Kim, Yun-Yeol Lee, Chun‐Hui Lee, Gi-Hyeon Jeong, Gyeong-Hui Choe · The Transactions of the Korea Information Processing Society · 1999
In most of the existing real-time schedulers producing the total value as large as possible, the service times for all schedulable tasks are computed at each time a new task arrives. If all scheduled tasks would be executed completely before a new task arrives, the schedule may produce the greatest total value. But this is not always true in real situations. In many cases, (a) new tasks arrive(s) before all the scheduled tasks are executed completely. In this paper, we propose a unique scheduling algorithm for real-time tasks. The proposed algorithm determines the service times only for some tasks with earlier deadlines while the existing algorithms determine the service times for all tasks. This partial computation decreases the average scheduling complexity ramatically, even though, in the worst case, the complexity of the proposed algorithm becomes O(N2), which is equal to that of a previous algorithm that has been known as a less complicated one.