主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
邱卫东,陈燕,李洁萍,彭澄廉.一种实时异构嵌入式系统的任务调度算法.软件学报,2004,15(4):504-511
一种实时异构嵌入式系统的任务调度算法
A Task Scheduling Algorithm for Real-Time Heterogeneous Embedded Systems
投稿时间:2003-03-31  修订日期:2003-11-18
DOI:
中文关键词:  异构系统  列表调度  调度长度  动态关键路径  通信资源访问  最早完成时间
英文关键词:heterogeneous system  list scheduling  scheduling length  dynamic critical path  communication resource access  earliest finish time
基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.69873010, 69873010 (国家自然科学基金)
作者单位
邱卫东 复旦大学,计算机与信息技术系,上海,200433 
陈燕 复旦大学,计算机与信息技术系,上海,200433 
李洁萍 复旦大学,计算机与信息技术系,上海,200433 
彭澄廉 复旦大学,计算机与信息技术系,上海,200433 
摘要点击次数: 2965
全文下载次数: 4216
中文摘要:
      异构分布式系统已被广泛应用在实时嵌入式系统中,而调度算法是在进行嵌入式系统综合时,确保系统实现性能目标的一个关键问题,这是一个NP-完全问题.现有的算法主要是启发式算法,性能还有待提高.提出了一个异构分布式系统的动态BLevel优先(dynamic BLevel first,简称DBLF)算法,算法选择就绪任务中动态BLevel值最大的任务进行调度,用插入法为任务分配处理器,遵循以下3个插入原则:满足任务先后顺序关系;任务的最早完成时间(earliest-finish-time,简称EFT)最小;在EFT相等时,优先分配到利用率较低的处理器上.与现有算法比较可以看出,DBLF算法可以有效降低调度长度.
英文摘要:
      Heterogeneous computing environments have been widely used in real-time embedded systems. Efficient task scheduling is essential for achieving high performance in the synthesis of embedded systems. The problem has been proved to be NP-complete and mainly heuristic algorithms which often have room for improvement exist. In this paper, an algorithm called the dynamic BLevel first (DBLF) has been presented. The DBLF algorithm selects the ready task with a maximum Blevel (ni) at each step and assigns the selected task to a processor in an insertion mode. The task is assigned to the suitable processor that satisfies the precedence sequence and has the minimum earliest-finish-time (EFT) of the task. When the EFT costs are equal, the task is firstly assigned to the processor which has the least utilization. Comparied with the related work, the result shows that the DBLF algorithm significantly surpasses the previous approaches in scheduling length.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利