A Real-Time Scheduling Algorithm Based on Priority Table and Its Implementation
Yongyan Wang, Qiang Wang, Hongan Wang, Jin Hong, Guozhong Dai · 2004
Abstract: This paper proposes a new scheduling scheme based on priority table design by integrating two characteristic parameters (i.e. deadline and value) of a task. Two real-time scheduling algorithms from the scheme are presented: earliest deadline value (EDV) and value earliest deadline (VED). Furthermore, how to implement the two algorithms using multi-linked lists is given, including task acceptance policy and task completion/abortion policy. This scheme can also be applied to integrate two other characteristic parameters or even three characteristic parameters of a task. Based on hit value ratio, weighted guarantee ratio and differentiated guarantee ratio, the performance of the VED and EDV algorithms are analyzed, the experimental results show that the VED and EDV algorithms can improve the performance compared to the classical EDF (earliest deadline first) and HVF (highest value first) algorithms under all workload conditions. Key words: real-time scheduling; task; priority; hit value ratio; deadline guarantee ratio 摘 要: 讨论了综合考虑任务的截止期和价值两个特征参数的优先级表设计方法,提出 了 EDV(earliest