中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 中科院软件所  > 中科院软件所
题名:
实时异构系统的集成动态调度算法研究
作者: 乔颖
答辩日期: 2001
专业: 计算机应用技术
授予单位: 中国科学院软件研究所
授予地点: 中国科学院软件研究所
学位: 博士
关键词: 实时异构系统 ; 动态调度 ; 任务分配 ; 服务质量 ; 调度成功率 ; 调度所获系统效益 ; 截止期错过率
摘要: 随着异构计算的兴起,实时异构系统已被广泛应用在航空航天、工业控制、电讯行业、图像处理以及Internet应用等诸多领域。本文对实时异构系统的集成动态调度算法进行了深入的研究,提出了一种新的实时异构系统的智能动态调度框架——FIDSH框架,并在此基础上,提出了一种新的实时异构系统的可适应性集成动态调度算法——IADSH算法。在FIDSH框架中,我们提出了一种新的实时异构系统的统一任务模型(简称统一任务模型)。该模型利用了非精确计算模型,引入了任务重要性和价值这两个参数,并充分体现了实时构系统的异构性,从而不仅可以采用统一形式描述实时异构系统中的硬、软实时任务,而且还为提高调度成功率和优化调度所获系统效益创造了条件。同时,FIDSH框架还通过智能调度器首次将智能控制的思想引入了实时异构系统的动态调度中。在FIDSH框架的基础上,我们提出了一种新的实时异构系统的可适应性集成动态调度算法——IADSH算法。该算法算法包括了基本高度和智能控制两大部分。基本调 度部分的核心是一种新的实时异构系统的硬、软实时任务集成动态调度方法——IDS算法。该算法以启发式搜索为基础,采用统一形式完成了实时异构系统的集成动态调度。同时,IDS算法一方面通过引入新的任务分配策略和软实时任务服务质量(Quality of Service, Qos)降级策略提高了调度成功率;另一方面通过引入新的指标——任务α指标,综合考虑了任务截止期和任务重要性对调度决策的影响,从而在保证调度成功率的前提下,优化了调度所获系统效益。为了使实时构系统的集成动态调度获得稳定的调度性能,我们又在基本调度部分——IDS算法的基础上引入了智能控制部分,从而形成了完整的IADSH算法。在智能控制部分中,我们以反馈控制原理为基础,将反馈控制与实时异构系统的动态调度进行了映射,并提出了相应的智能控制策略以及任务流调节策略和参数调节策略,从而使IADSH算法具有了可适应性和稳定的调度性能。为了验证IADSH算法的有效性及评估其调度性能,我们从调度成功率、调度所获系统效益和调度稳定性三个方面对IADSH算法进行了大量的模拟研究。结果表明,IADSH算法不仅成功地解决了实时异构系统中硬、软实时任务的集成动态调度问题,而且还极大地提高了调度成功率,在与其它相关算法,如传统近视算法的比较中具有明显优势;同时,IADSH算法还在保证调度成功率的前提下,优化了调度所获系统效益,通过在调度中考虑任务重要性对调度决策的影响,将系统效益提高了2-3倍;此外,IADSH算法的截止期错过率不会随着系统负载的变化而出现大的波动,其调度性能具有较好的稳定性。
英文摘要: Real-time heterogeneous systems are used widely in the field of flight control and avionics, processing control, telecommunication, imagine processing and internet applications. In this paper, a new intelligent framework for integrated dynamic scheduling of real-time heterogeneous systems, called FIDSH, is presented, Basing on FIDSH, a new adaptive integrated dynamic scheduling algorithm for real-time heterogeneous systems, called IADSH, is proposed. In FIDSH, an integrated task model for real-time heterogeneous systems is presented. This task model reveals the heterogeneity of systems and uniformly characterizes hard and soft real-time tasks in real-time heterogeneous systems by using imprecise computing model and introducing the factor of task importance and value. The new task provides an efficient way to improve the scheduling success ratio and system benefit obtained by schedule. Moreover, FIDSH firstly introduces the intelligent control mechanism in the integrated dynamic scheduling for real-time heterogeneous systems by embedding an intelligent controller in it. Basing on FIDSH, a new adaptive integrated dynamic scheduling algorithm for real-time heterogeneous systems, called IADSH, is proposed. This algorithm includes two parts that are called basic schedule and intelligent control respectively. In the part of basic schedule, a new method for integrated dynamic scheduling of hard and soft real-time tasks in real-time heterogeneous systems, called IDS, is presented. IDS is based on heuristic searching and implements the integrated schedule in real-time heterogeneous systems with uniform form successfully. IDS improves the scheduling success ratio by introducing a new task assignment policy and a Qos (Quality of Service) degradation policy for soft real-time tasks, Moreover, a new metric called α metric is proposed to trade off the effect of task's deadline and importance on the schedule decision, whereas optimizing system benefit obtained by the schedule without decreasing the scheduling success ratio. To make the integrated dynamic scheduling obtain stable scheduling performance, we introduce intelligent control to IADSH. In this part, feedback control theory is mapped to integrated dynamic schedule for real-time heterogeneous systems. Furthermore, the new intelligent control policy, task flow adjustment policy and parameter adjustment policy are presented to make IADSH achieve the stable scheduling performance. To evaluate its performance, we have conducted extensive simulation studies for IADSH. Simulation results demonstrate: 1) IADSH highly improve the scheduling success ratio. Its scheduling success ratio is averagely 30% higher than that of other related algorithms, such as myopic algorithm. 2) IADSH dramatically improve the system benefit successfully without decreasing the scheduling success ratio. 3) IADSH shows fairly stable schedule performance when workflow changes in the system.
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/6984
Appears in Collections:中科院软件所

Files in This Item:
File Name/ File Size Content Type Version Access License
LW004416.pdf(1351KB)----限制开放-- 联系获取全文

Recommended Citation:
乔颖. 实时异构系统的集成动态调度算法研究[D]. 中国科学院软件研究所. 中国科学院软件研究所. 2001-01-01.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[乔颖]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[乔颖]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace