周期性任务调度的装箱算法  

Bin-packing algorithms for periodic task scheduling

作　　者：朱智林[1] 时晨 韩俊刚[3] 陈平[1] 

机构地区：[1]山东工商学院计算机系 [2]骊山微电子研究所第1研究室,陕西西安710080 [3]西安邮电学院计算机系,陕西西安710061

出　　处：《计算机应用》2006年第3期679-681,691,共4页journal of Computer Applications

基　　金：国家自然科学基金资助项目(90207015)

摘　　要：针对基于时间触发的CAN控制系统,给出了确定周期性任务表中的基本周期的两种策略,提出了构造周期性任务调度表的下次适应、降序下次适应、最佳适应和降序最佳适应四种算法,分析了这四种不同算法的时间复杂度和最坏渐近性能比,最后对不同规模下的四种算法进行了仿真比较,结果表明文中给出的四种算法效果均优于经典的一维装箱算法。As the extension of off-line bin-packing problem, periodic task scheduling has many important applications in real-time distributed systems. For time triggered CAN control systems, two strategies to determine basic cycle（BC） of TTCAN were presented. Next-fit algorithm, next-fit deereaming algorithm, best-fit algorithm and best-fit decreaming algorithm were proposed to construct periodic task scheduling tables. Time complexity and worst-case asymptotic performance ratio of these algorithms were analyzed. Experiment results show that the four algorithms have the advantage over the typical one-dimensional bin-packing algorithm.

关 键 词：TFCAN 装箱问题 周期性任务调度 渐近性能比 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP273[自动化与计算机技术—控制科学与工程]