基于优先级表的实时调度算法及其实现  

A Real-Time Scheduling Algorithm Based on Priority Table and Its Implementation

作　　者：王永炎[1] 王强[1] 王宏安[1] 金宏[1] 戴国忠[1] 

机构地区：[1]中国科学院软件研究所人机交互技术与智能信息处理实验室,北京100080

出　　处：《软件学报》2004年第3期360-370,共11页Journal of Software

基　　金：国家自然科学基金~~

摘　　要：讨论了综合考虑任务的截止期和价值两个特征参数的优先级表设计方法,提出了EDV(earliestdeadlinevalue)与VED(valueearliestdeadline)两种不同的基于优先级表的实时任务调度算法,并且利用多重链表给出了这两种算法的实现,包括任务接收策略与任务完成/夭折策略的算法实现.这种优先级表设计方法及其基于多重链表的实现方法也适用于对任务的其他两种甚至3种不同特征参数之间的综合.基于累积实现价值率、加权截止期保证率与差分截止期保证率3个方面,分析了VED算法与EDV算法的性能,实验结果表明,在所有负载条件下VED算法与EDV算法相对于EDF(earliestdeadlinefirst)算法与HVF(highestvaluefirst)算法都有很大的性能改进.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.

关 键 词：实时调度算法 任务 优先级表 实现价值率 截止期保证率 

分 类 号：TP316[自动化与计算机技术—计算机软件与理论]