| 物联网环境下具有顺序约束关系的静态任务表调度算法 |
| |
| 引用本文： | 叶佳,周鸣争. 物联网环境下具有顺序约束关系的静态任务表调度算法[J]. 计算机应用, 2014, 34(9): 2491-2496. DOI: 10.11772/j.issn.1001-9081.2014.09.2491 |
| |
| 作者姓名： | 叶佳 周鸣争 |
| |
| 作者单位： | 安徽工程大学 计算机与信息学院，安徽 芜湖 241000 |
| |
| 基金项目： | 国家自然科学基金资助项目，安徽省自然科学基金资助项目，安徽省教育厅自然科学基金资助项目 |
| |
| 摘 要： | 针对物联网异构调度环境下并行计算的静态任务调度问题，提出了一种基于最早完成时间策略改变调度顺序的表调度算法HDPTS。该算法针对现有表调度算法在调度前不能准确地确定调度顺序的问题，在IHEFT算法的基础上添加了一个动态优先级调度策略，当节点的前驱任务都已经完成调度任务时，就改变该节点的调度优先级。任务优先级的计算在所有前驱任务到达这个任务的最晚完成时间与所有资源上最大可以使用时间之间取最大值的基础上，同时考虑到分配到各个资源上的任务对后继任务的影响和资源上的负载情况，以及上行权重的计算值和对出口任务的影响，使得优先级计算更加合理，能够根据任务分配动态合理改变任务调度顺序。通过随机生成一个算例进行测试，结果表明HDPTS比IHEFT、HEFT在调度长度方面减少14.29%；对大量随机产生的特定结构的有向无环图(DAG)进行测试，测试结果显示HDPTS算法比IHEFT、HEFT和LDCP算法更有效。
|
| 关 键 词： | 异构环境 物联网 任务调度 表调度 静态调度 |
| 收稿时间： | 2014-04-11 |
| 修稿时间： | 2014-06-20 |
List scheduling algorithm for static task with dependence in Internet of things environment |
| |
| YE Jia,ZHOU Mingzheng. List scheduling algorithm for static task with dependence in Internet of things environment[J]. Journal of Computer Applications, 2014, 34(9): 2491-2496. DOI: 10.11772/j.issn.1001-9081.2014.09.2491 |
| |
| Authors: | YE Jia ZHOU Mingzheng |
| |
| Affiliation: | College of Computer and Information Engineering, Anhui Polytechnic University, Wuhu Anhui 241000, China |
| |
| Abstract: | The static task list scheduling problems in distributed heterogeneous computing environment of Internet of things was studied, and a list scheduling algorithm named Heterogeneous Dynamic Priority Task Scheduling (HDPTS) was proposed, which can dynamically change scheduling sequence based on the strategy of the earliest completion time. Concerning that the exsiting list scheduling algorithms can not accurately determine the scheduling order before scheduling, on the basis of Improved Heterogeneous Earliest Finish Time (IHEFT) algorithm, a dynamic priority scheduling policy was added to it. When precursor tasks of a node completed scheduling, the scheduling priority of this node should be changed. Scheduling priority of task was calculated on the basis of choosing the maximum value between the latest completion time of all immediate predecessor tasks and the maximum available time of all the resources. At the same time, some other factors were also considered, including the influence to the subsequent tasks of the tasks assigned to the resource, the resource load, the calculated value of uplink weight and the influence to the exit tasks. All these considerations make the priority calculation be more reasonable, so as to dynamically change the task scheduling sequence reasonably according to the task allocation situation. By a randomly generated example test, the results show that the scheduling length of HDPTS reduced by 14.29% compared with IHEFT, HEFT (Heterogeneous Earliest Finish Time); the test results on a large number of randomly generated Directed Acyclic Graph (DAG) with specific structure prove that HDPTS is more effective than IHEFT, HEFT and LDCP (Longest Dynamic Critic Path) algorithms. |
| |
| Keywords: | heterogeneous environment Internet of Things (IoT) task scheduling list scheduling static scheduling |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《计算机应用》浏览原始摘要信息 |
|
点击此处可从《计算机应用》下载全文 |
|
