学位论文 > 优秀研究生学位论文题录展示

实时系统动态优先级任务调度算法的研究

作　者: 巴巍
导　师: 王伟；张大波
学　校: 大连理工大学
专　业: 控制理论与控制工程
关键词: 实时系统调度算法动态优先级可调度性分析
分类号: TP316.2
类　型: 博士论文
年　份: 2010年
下　载: 496次
引　用: 1次
阅　读: 论文下载

内容摘要

实时系统计算结果的准确性及输出结果的及时性使得其在工业、国防、一医疗和通信等诸多领域得到越来越广泛的应用。随着对实时系统性能要求的不断提高,传统任务调度算法的调度性能越来越难以满足应用的要求。论文围绕实时系统单处理器任务调度和多处理器任务调度两个方面展开研究,特别针对动态优先级任务调度算法中存在的若干问题,进行了深入研究。本文主要研究工作归纳如下：针对单处理器最小空闲时间优先调度算法作业切换常出现颠簸的现状,提出一种改进的动态模糊阈值最小空闲时间优先软实时调度算法。给出“模糊阈值系数”的概念,选取当前作业的剩余空闲时间和周期为模糊输入,运用模糊理论生成模糊阈值系数,用动态模糊阂值作为当前作业的虚拟剩余空闲时间参予优先级比较以尽量避免抢占。仿真结果表明,与最小空闲时间优先调度算法相比,该算法在不降低调度成功率的同时有效地减少了作业的切换次数。针对最早截止期优先调度算法作业切换多、超载时错失率高的现状,提出两种改进的最早截止期优先软实时动态调度算法。两种算法选取当前作业的剩余空闲时间和关键性系数为模糊输入以生成动态模糊阈值系数,分别通过缩短和延长当前作业的绝对截止期至动态模糊阈值的方法减少抢占、避免作业错失。阈值的大小由作业的多种参数共同决定,大大提高了重要作业被成功调度的几率。仿真结果表明,与最早截止期优先调度算法比较,两种算法有效地提高了重要作业的完成率,当截止期被延长时,错失率明显降低,当截止期被缩短时,作业间的切换次数大大减少。针对优先级个数受限系统中调度算法难以确保分组准确性问题,提出一种改进的组优先级最早截止期优先调度算法。给出作业分组可调度性能测试,将满足分组可调度测试公式的作业作为一个作业组,以作业组内最早绝对截止期为作业组优先级,作业组与其他作业按照最早截止期优先调度,在作业组得到系统资源后,作业组内按照最短作业优先的原则执行作业。仿真结果表明,与最早截止期优先调度算法、尽力服务调度算法及其他组优先级调度算法相比,新算法不仅能有效降低算法所需优先级个数,还能提高调度的成功率,缩短平均响应时间,减少作业切换次数。针对同构多处理器动态优先级局部调度中密度算法和DBF*算法的判据存在可能将可调度任务误判为不可调度的情况,提出一种新的高效需求界限函数局部调度算法。算法采用更为精准的可调度性判据,分别在最小数目处理器以及固定数目处理器两种情况下,通过多阶跟踪需求界限函数轨迹确保了对任务可调度性判断的准确性。仿真结果表明,新算法与密度算法和DBF*算法相比,可调度任务的数量大大提升。针对异构多处理器局部调度算法复杂度高且难以实现最优分配的问题,提出一种新的整数线性规划局部调度算法。在准确表达处理器之间的差异以及任务参数后,设定总处理器利用率为目标函数,通过建立约束条件求取目标函数的最小值,将异构多处理器调度问题描述为整数线性规划问题,利用Lingo快速求解整数线性规划问题,进而求得异构多处理器任务的优化分配。仿真结果表明了新算法的有效性。

全文目录

摘要  4-6
Abstract  6-11
1 绪论  11-26
  1.1 研究背景、目的及意义  11-12
    1.1.1 实时系统产生、发展与定义  11-12
    1.1.2 研究目的与意义  12
  1.2 实时系统特征与分类  12-14
    1.2.1 实时系统特征  12-13
    1.2.2 实时系统分类  13-14
  1.3 实时任务调度理论概述  14-18
    1.3.1 实时任务及其分类  14-15
    1.3.2 实时任务调度分类  15-16
    1.3.3 实时任务调度策略  16-17
    1.3.4 实时任务调度算法评价标准  17-18
  1.4 实时系统动态优先级任务调度理论综述  18-23
    1.4.1 单处理器动态优先级任务调度算法  18-21
    1.4.2 多处理器动态优先级任务调度算法  21-23
  1.5 论文的主要研究内容  23-24
  1.6 论文组织结构  24-26
2 单处理器最小空闲时间优先调度算法的研究  26-38
  2.1 引言  26-27
  2.2 任务模型  27-28
  2.3 模糊阈值最小空闲时间优先调度算法  28-31
    2.3.1 动态模糊阈值  28-30
    2.3.2 动态模糊阈值最小空闲时间调度策略  30-31
  2.4 性能分析  31-37
    2.4.1 模糊阈值系数等级  31-33
    2.4.2 调度方案  33
    2.4.3 性能测量指标  33-34
    2.4.4 典型任务调度  34-35
    2.4.5 随机任务调度  35-37
  2.5 本章小结  37-38
3 单处理器最早截止期优先调度算法的研究  38-53
  3.1 引言  38-39
  3.2 任务模型  39
  3.3 模糊阈值EDF调度算法  39-44
    3.3.1 动态模糊阈值  39-41
    3.3.2 调度策略  41-44
  3.4 LTEDF和STEDF算法调度性能和复杂度分析  44-46
  3.5 性能分析  46-52
    3.5.1 阈值系数等级  46-48
    3.5.2 调度方案与性能测量指标  48
    3.5.3 仿真实验  48-52
  3.6 本章小结  52-53
4 单处理器有限优先级动态调度算法的研究  53-69
  4.1 引言  53-54
  4.2 任务模型  54-55
  4.3 组优先级最早截止期优先调度算法  55-60
    4.3.1 可调度性能测试  55-57
    4.3.2 GPEDF调度策略  57-60
  4.4 性能分析  60-68
    4.4.1 调度方案  60-61
    4.4.2 性能测量指标  61
    4.4.3 仿真实验  61-68
  4.5 本章小结  68-69
5 同构多处理器局部调度算法的研究  69-89
  5.1 引言  69-70
  5.2 调度模型  70-71
  5.3 需求界限函数问题描述  71-74
  5.4 高效需求界限函数多处理器局部调度算法  74-81
    5.4.1 eDBF任务分配判据  74-77
    5.4.2 最小数目多处理器eDBF调度算法  77-80
    5.4.3 固定数目多处理器eDBF调度算法  80-81
  5.5 eDBF算法特性分析  81-83
  5.6 性能分析  83-88
    5.6.1 受限截止期偶发任务可调度任务数比较  84-86
    5.6.2 任意截止期偶发任务可调度任务数比较  86-88
  5.7 本章小结  88-89
6 异构多处理器局部调度算法的研究  89-98
  6.1 引言  89-90
  6.2 调度模型  90-91
  6.3 整数线性规划问题描述  91-92
  6.4 整数线性规划多处理器局部调度算法  92-95
    6.4.1 ILP求解多处理器局部调度问题可能性分析  92-93
    6.4.2 ILP多处理器局部调度算法  93-95
  6.5 性能分析  95-96
  6.6 本章小结  96-98
结论  98-101
参考文献  101-110
攻读博士学位期间发表学术论文情况  110-112
创新点摘要  112-113
致谢  113-114
作者简介  114-116

相似论文

车载CAN网络的网关设计方法研究,TP273
Linux内核进程调度算法的分析、研究与改进,TP316.81
基于ARM的嵌入式实时操作系统的设计与开发,TP316.2
保证无线局域网服务质量的媒体访问控制机制的研究,TN925.93
基于域信任的自适应网格工作流调度算法,TP311.52
无线传感器网络休眠调度算法研究,TN929.5
基于IP区分服务调度算法的研究,TN915.09
基于无线网络控制系统的动态优先级调度仿真研究,TP273
CAN总线在气动管道传输系统中的应用,TP273
基于区分服务的无线多媒体传感器网络MAC协议研究,TP212.9
基于MQX的工控平台设计,TP273
HSUPA系统级仿真及关键技术的研究,TN929.5
面向方面的实时系统建模及实现方法研究,TP316.2
柔性生产线平台调度算法研究,O242.1
操作系统调度器结构及算法研究,TP316.81
具有资源约束的网络控制系统调度与控制的协同设计,TP13
超高速网络中基于终端限制的大数据传输问题的研究,TN919.3
基于CAN总线的簇绒地毯机控制系统集成技术研究,TP273
自适应音频感知的虚拟机调度的研究,TP302
基于IEEE Wireless MAN QoS框架算法的研究与仿真,TP393.09
一个MPEG2视频解码器的黑场解析模块设计与实现,TP391.41