对硬实时时间槽分配问题的EDF算法实现  

EDF Algorithm for HRT-TSA

作　　者：潘娅[1] 王牛[1] 

机构地区：[1]重庆大学电气工程学院,重庆400044

出　　处：《计算机测量与控制》2003年第10期803-805,共3页Computer Measurement &Control

摘　　要：在计算机及通信网络中,实时通信变得越来越重要。为了保证通信数据的传递在指定的截止时间时限内完成,避免产生冲突,可以采用一些合适的消息调度算法。针对硬实时时间槽分配问题(HRT-TSA),简要论述了这是一个NP-问题,对可行调度的必要条件进行了讨论,并提出了用截止时间最早最优先的启发式算法(EDF),可以在多项式时间内实现HRT-TSA问题,给出了算法描述。EDF算法具有良好的调度性能,在实时系统中得到广泛应用。The real-time traffic is becoming increasingly important in computer and communication networks.A proper scheduling algorithm of the messages can be used in order to avoid collisions and traffic will be completed within a specific deadline. It shows that HRT-TSA is a NP-complete and a necessary condition for the feasible schedule. Then EDF heuristic algorithm, which has good performance than other real-time algorithms is given. 

关 键 词：消息调度算法 启发式调度算法 EDF算法 时间槽 分配问题 NP问题 通信网络 

分 类 号：O224[理学—运筹学与控制论] TN915[理学—数学]