|
|||||
|
|
| 周期性任务调度的装箱算法 | |
| 引用本文： | 朱智林,时晨,韩俊刚,陈平.周期性任务调度的装箱算法[J].计算机应用,2006,26(3):679-0681. |
| 作者姓名： | 朱智林 时晨 韩俊刚 陈平 |
| 作者单位： | 1. 山东工商学院,计算机系,山东,烟台,264005;西安电子科技大学,软件研究所,陕西,西安,710071 2. 骊山微电子研究所,第1研究室,陕西,西安,710080 3. 西安邮电学院,计算机系,陕西,西安,710061 4. 山东工商学院,计算机系,山东,烟台,264005 |
| 摘 要： | 针对基于时间触发的CAN控制系统，给出了确定周期性任务表中的基本周期的两种策略，提出了构造周期性任务调度表的下次适应、降序下次适应、最佳适应和降序最佳适应四种算法，分析了这四种不同算法的时间复杂度和最坏渐近性能比，最后对不同规模下的四种算法进行了仿真比较，结果表明文中给出的四种算法效果均优于经典的一维装箱算法。 |
| 关 键 词： | 装箱问题 周期性任务调度 渐近性能比 |
| 文章编号： | 1001-9081（2006）03-0679-03 |
| 收稿时间： | 2005-09-05 |
| 修稿时间： | 2005-09-052005-11-21 |
Bin-packing algorithms for periodic task scheduling |
|
| ZHU Zhi-lin,SHI Chen,HAN Jun-gang,CHEN Ping.Bin-packing algorithms for periodic task scheduling[J].journal of Computer Applications,2006,26(3):679-0681. | |
| Authors: | ZHU Zhi-lin SHI Chen HAN Jun-gang CHEN Ping |
| Abstract: | 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 decreaming 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. |
| Keywords: | TTCAN |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |
| 点击此处可从《计算机应用》浏览原始摘要信息 | |
| 点击此处可从《计算机应用》下载全文 | |
