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

嵌入式实时系统的任务调度与资源共享模型及算法研究

作　者: 王保进
导　师: 王志刚；李明树
学　校: 中国人民解放军信息工程大学
专　业: 通信与信息系统
关键词: 抢占阈值调度算法 SRP协议 PCP协议 levei-i忙周期伪资源 SRP-PT调度模型 TSM算法构件模型 FIFO调度
分类号: TP316
类　型: 博士论文
年　份: 2005年
下　载: 893次
引　用: 13次
阅　读: 论文下载

内容摘要

嵌入式实时系统要求任务能按时、正确地完成功能操作,这些任务还可能会互斥地访问共享资源。另外,系统的处理能力和内存容量往往是有限的。这需要将调度算法与资源访问控制协议合理地组合到一起使用,从而能恰当地排列任务执行顺序,在保证系统可调度性的同时使用更少的内存资源。实际的嵌入式实时系统提供的优先级是有限的,需要一种适当的优先级映射算法。当前采用构件技术的嵌入式实时系统在开发过程中注重从结构角度利用构件技术的优点,而往往忽视从运行角度充分利用成熟的实时调度理论。针对上述需求,本文研究了静态优先级实时调度算法和资源访问控制协议,分析了现有调度算法和资源协议结合使用时存在的不足,以及现有优先级映射算法的不足。试图找出一种合理的组合调度算法和资源协议的方案,一种能保证系统实时性的优先级映射算法,一种将构件映射成任务的方式和为底层构件化嵌入式实时操作系统选择适当的调度模型。首先,本文分析出抢占阈值调度算法与SRP资源访问控制协议更适合嵌入式实时系统,两者具有共同的特点:任务一旦执行就不会被阻塞。据此,用level-i忙周期分析方法重新推导了SRP协议下判定任务可调度性的公式,并基于新公式推导出SRP协议的特性,实现了分配任务优先级的算法。经过进一步分析,推导出抢占阈值调度是应用SRP协议的静态优先级实时系统的一个特例,表明将SRP协议和抢占阈值调度算法相结合是合理的。利用伪资源的概念在SRP协议中实现了抢占阈值调度,提出了SRP-PT调度模型。通过限制使用实资源的任务再次使用伪资源,防止了阈值过限问题。证明了SRP-PT调度模型比现有调度算法和资源协议的结合方式性能更好。通过仿真实验进行性能对比表明:与单独使用SRP协议相比,SRP-PT调度模型能提高任务集合的可调度性。其次,通过深入分析抢占阈值调度模型生成的非抢占组的特性,证明了组内任务优先级是连续递增的,组间任务优先级值不会相交,并据此提出了阈值段间映射法(TSM)和事件驱动线程框架。能充分利用抢占阈值调度模型的优点,针对没有共享资源的实时系统,在提高任务集合可调度性的同时,使用较少的系统优先级。通过仿真实验与现有优先级映射算法进行性能对比,证明了上述结论。最后,本文提出一种适合于嵌入式实时系统的软件构件模型以及将构件映射成任务的方式,同时提出一种设计方法。通过仿真实验比较了4种可用调度算法的性能,通过分析说明了抢占阈值调度算法和SRP-PT调度模型最适于构件化嵌入式实时系统。

全文目录

摘要  5-6
Abstract  6-7
第一章绪论  7-19
  1.1 嵌入式实时系统简介  7-8
  1.2 嵌入式实时系统的一般需求和特点  8-10
    1.2.1 最佳的实时性  8
    1.2.2 合适的资源访问控制协议  8-9
    1.2.3 有限的内存资源  9
    1.2.4 有限的系统优先级  9-10
  1.3 现有解决方法和存在的不足  10-15
    1.3.1 实时调度算法  10-11
    1.3.2 资源访问控制协议  11-13
    1.3.3 抢占阈值调度算法与 PCP协议结合使用时出现的问题  13-14
    1.3.4 现有优先级映射算法存在的不足  14-15
  1.4 构件化嵌入式实时系统的应用现状  15-16
  1.5 本文主要工作和贡献  16-18
  1.6 论文结构安排  18-19
第二章算法与协议的研究和分析  19-37
  2.1 基本概念和定义  19-21
  2.2 静态优先级实时调度算法  21-23
    2.2.1 抢占式调度算法-RM算法  21-22
    2.2.2 非抢占式调度算法  22
    2.2.3 抢占阈值调度算法  22-23
  2.3 资源访问控制协议  23-27
    2.3.1 优先级继承协议(PIP)  23-24
    2.3.2 优先级冲顶协议(PCP)  24-25
    2.3.3 SRP协议  25-27
  2.4 level-i忙周期分析方法  27-30
    2.4.1 在抢占式调度中应用level-i忙周期分析方法  27-28
    2.4.2 在非抢占式调度中应用level-i忙周期分析方法  28-29
    2.4.3 在抢占阈值调度中应用level-i忙周期分析方法  29-30
  2.5 阈值过限问题的分析  30-33
    2.5.1 PC-PCP协议和 PTC-PCP协议  30-33
    2.5.2 产生阈值过限问题的原因  33
  2.6 IPA和 DPA优先级映射算法  33-35
  2.7 现有构件化嵌入式操作系统采用的调度算法  35
  2.8 小结  35-37
第三章 SRP协议的新判定公式  37-51
  3.1 新判定公式的推导  37-42
    3.1.1 SRP协议的关键时刻  37-38
    3.1.2 新判定公式的推导过程和结果  38-42
  3.2 SRP协议的特性  42-46
  3.3 SRP协议下的优先级分配算法  46-50
    3.3.1 优先级分配规则  46-47
    3.3.2 优先级分配算法  47-50
  3.4 小结  50-51
第四章抢占阈值调度算法与 SRP协议的组合-SRP-PT调度模型  51-67
  4.1 抢占阈值调度算法与 SRP协议的关系  51-52
  4.2 SRP-PT调度模型  52-54
  4.3 SRP-PT调度模型的特性  54-57
  4.4 SRP-PT调度模型下的优先级分配算法  57-59
  4.5 SRP-PT调度模型与 PC-PCP协议的比较  59-61
    4.5.1 阻塞时间的比较  59-60
    4.5.2 优先级倒置的比较  60
    4.5.3 现场切换次数的比较  60-61
  4.6 SRP-PT调度模型与 SRP协议的比较  61-65
  4.7 小结  65-67
第五章抢占阈值调度下的优先级映射-TSM算法  67-83
  5.1 优先级映射问题  67-68
  5.2 IPA和 DPA优先级映射算法的特性  68-69
  5.3 抢占阈值调度下非抢占组的特性  69-71
    5.3.1 分割非抢占组的方法  69-70
    5.3.2 分割方法的特点  70-71
  5.4 TSM优先级映射算法  71-72
  5.5 事件驱动线程框架  72-73
  5.6 优先级映射算法的分析  73-76
    5.6.1 TSM算法使用过程  73-75
    5.6.2 事件驱动线程的执行过程  75-76
    5.6.3 IPA和 DPA算法的映射结果  76
  5.7 优先级映射算法的比较  76-81
    5.7.1 计算复杂度的比较  77
    5.7.2 性能比较  77-81
  5.8 小结  81-83
第六章调度模型在构件化嵌入式实时操作系统中的应用  83-92
  6.1 构件模型和映射成任务的方式  83-86
    6.1.1 构件模型和映射方式  83-85
    6.1.2 构件化嵌入式实时软件开发过程  85-86
  6.2 适合构件化嵌入式实时操作系统的调度模型  86-91
    6.2.1 针对独立任务集合几种调度算法的性能比较和结论  86-91
    6.2.2 针对有共享资源的任务集合使用 SRP-PT调度模型  91
  6.3 小结  91-92
第七章结束语  92-95
参考文献  95-101
致谢  101-102
作者在攻读博士学位期间参加的科研任务及完成情况  102-103
作者在攻读博士学位期间的论文和专利情况  103

嵌入式实时系统的任务调度与资源共享模型及算法研究

内容摘要

全文目录

相似论文