A Dynamic Scheduling Algorithm to Maximize the Total Value of Real-time Tasks running on a Single Processor


KIPS Transactions on Software and Data Engineering, Vol. 6, No. 6, pp. 1678-1685, Jun. 1999
10.3745/KIPSTE.1999.6.6.1678, Full Text:

Abstract

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 dramatically, even though, in the worst case, the complexity of the proposed algorithm becomes O(N^2), which is equal to that of a previous algorithm that has been known as a less complicated one.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
K. I. Soo, L. Y. Yeol, L. C. Hee, J. G. Hyun and C. K. Hee, "A Dynamic Scheduling Algorithm to Maximize the Total Value of Real-time Tasks running on a Single Processor," KIPS Journal (1994 ~ 2000), vol. 6, no. 6, pp. 1678-1685, 1999. DOI: 10.3745/KIPSTE.1999.6.6.1678.

[ACM Style]
Kim In Soo, Lee Yun Yeol, Lee Chun Hee, Jung Gi Hyun, and Choi Kyung Hee. 1999. A Dynamic Scheduling Algorithm to Maximize the Total Value of Real-time Tasks running on a Single Processor. KIPS Journal (1994 ~ 2000), 6, 6, (1999), 1678-1685. DOI: 10.3745/KIPSTE.1999.6.6.1678.