A Real-Time Scheduling Algorithm Based on Priority Table

Abstract:

Among preemptive real-time uniprocessor scheduling algorithms, many researches, such as optimal and heuristic algorithms, considers only one task attribute and neglects also the variation of attributes. To understand the relations between task attributes and scheduling success ratio, we first define the sensitivity of scheduling success ratio to task attributes. Sensitivity means the intensity of variation of scheduling success ratio as task attributes varies. The paper analyzes the sensitivities of scheduling success ratio to arrival time, execution time, deadline and laxity respectively, which have close relations with scheduling. Based on the definition of sensitivity, we also define attributes influence on scheduling success ratio, which is that the greater the influence, the higher the ratio. The essence of dynamic scheduling is a scheduling based on priority, with each dynamic algorithm matching a priority table, and vice versa. It is also much easier to infer the algorithm from the priority table, which can consider several task attributes. As priority table has various designs, it can correspond to a lot of algorithms, among which, many are inefficient. In order to deal with this kind of problem, we propose a new priority table design PTBM combining deadline and laxity based on the analysis of sensitivity and influence, which makes that a task with small deadline and large laxity has higher priority. We compare PTBM with EDF, LLF and PTD through simulation. The results verify the analysis of sensitivity and influence, and it also shows that PTBM outperforms on scheduling success ratio. It needs further exploration to design more efficient priority table by analyzing more task attributes influence on scheduling success ratio, which includes criticalness, task type and so on.

• Periodical: Advanced Materials Research (Volumes 756-759)
• Pages: 3929-3936
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.756-759.3929
• Online since: September 2013
• Authors: Er Feng Su, Kai Long Zhang, Xing She Zhou, Chen Fan
• Keywords: Dynamic Scheduling, Influence, Priority Table, Sensitivity, Task Attributes

References

[1] Liu C, Layland J. Scheduling algorithms form multiprogramming in a hard real-time environment. Journal of the ACM, 1973, 20(1): 46-61.

DOI: 10.1145/321738.321743

[2] Liu YS, He XG, Tang CJ, Li L. Special type database technology. Beijing: Science Press, 2000(in Chinese).

[3] Jensen ED, Locke CD, Toduca H. A time-driven scheduling model for real-time operating systems. Proceedings of the IEEE Real-time Systems Symposium. Washington, DC: IEEE Computer Society Press, 1985, 112-122.

[4] J. Goossens, P. Richard. Overview of real-time scheduling problems. 9th international workshop on project management and Scheduling, Nancy, France, April 26-28 2004, pp.13-22.

[5] JIN Hong, WANG Hong-An WANG Qiang, DAI Guo-zhong. An Integrated Design of Task Priority. Journal of Software, 2003, vol. 14, No. 3.

[6] Biyabani SR, Stankovic JA, Ramamritham K. The Integration of deadline and criticalness in hard real-time scheduling. Proceedings of the 9th IEEE Real-time Systems Symposium. Washington, DC: Computer Society Press, 1988, 152-160.

DOI: 10.1109/real.1988.51111

[7] Giorgio C. Buttazzo. Hard real-time computing system. Massachusetts: Kluwer Academic Publisher. (1997).