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

单芯片系统（SoC）中的实时任务调度算法研究

作　者: 贺小川
导　师: 贾焰
学　校: 国防科学技术大学
专　业: 计算机科学与技术
关键词: 实时控制系统单芯片系统(SoC) 实时调度抢占阈值调度节能调度栈资源协议异步任务任务抢占阈值延迟调度
分类号: TN47
类　型: 博士论文
年　份: 2009年
下　载: 130次
引　用: 0次
阅　读: 论文下载

内容摘要

随着大规模集成电路设计技术和半导体技术的迅速发展,尤其是器件关键尺寸到达纳米级的深亚微米技术的出现使得单一芯片上可以集成上亿个晶体管。微控制器芯片,作为各种嵌入式实时控制系统(如飞行控制系统、对空防御系统等)的关键器件,已经全面采用SoC(System-On-a-Chip)技术,以控制成本,降低功耗,提高产品设计的可重用性,减少市场反应时间。与此同时,为了解决系统高性能指标和低成本之间、逐渐攀升的系统复杂性与日渐缩短的更新换代周期之间、设计技术落后与半导体集成电路芯片技术飞速发展之间等等诸多矛盾,越来越多的微控制器开始使用软/硬件协同设计方法来设计制造。使用软硬件协同设计的方法,系统级芯片内必然包括各种硬件设备和与之协同工作的软件。面向SoC的嵌入式实时操作系统(SoCRTOS)不仅能有效改善系统级芯片的性能和可靠性,而且能降低产品开发难度,提高产品设计的可重用性,正逐渐成为单芯片系统(SoC)中非常重要的基础部件之一与经典实时控制系统相比,SoC实时控制系统的硬件资源相对有限,同时需要遵循事件驱动的反应式运行模式,而且目标应用平台也复杂多样。这些基本特征使得SoC实时控制系统中的实时任务调度策略,作为SoC实时操作系统中最重要的部分,其任务切换开销要尽量低,其系统功耗要尽量少,其内存需求要尽量小。但是,SoC实时控制系统中资源严重受限的现状,与当前RTOS中普遍使用抢占式调度策略所带来的任务切换频繁、资源消耗过大等特征,形成了应用环境需求与技术实现途径之间的结构性矛盾。在SoC实时控制系统这种典型的嵌入式实时计算环境下,如何在不降低任务可调度性的前提下尽可能减少不必要的任务切换、降低系统资源需求,逐渐成为具有重要理论意义和应用价值的新的研究热点。本文旨在研究基于软/硬件协同设计方法构建的、嵌入式SoC实时控制系统中的任务实时调度问题。在分析当前已有研究工作和解决方案的基础上,提出多个节能(energy-efficient)、内存节省(memory-efficient)任务调度算法,理论上分析和证明了算法的可行性和正确性的同时,通过实例研究和仿真实验说明了算法的实用性和有效性。其主要工作和研究成果如下：1.基于SoC实时控制系统的事件驱动特征,提出一种异步实时任务集合的抢占阈值调度算法FPPT-AST。该算法首先推导出抢占阀值调度模型中异步任务最长响应时间的计算方法,而后在此基础上给出任务抢占阀值的分配算法。仿真实验表明,与普通抢占阈值调度算法相比较,FPPT-AST调度算法能够进一步提高任务集合的可调度性。2.基于SoC实时控制系统的资源受限特征,提出一种在抢占阈值调度模型任务松弛因子的离线计算方法ES-FPPT。该方法首先给出带有松弛因子的任务集合可调度性得到满足的充分条件,而后将各个任务的松弛因子的计算问题转换为线性最优化问题。仿真试验表明,与现有节能技术相比,ES-FPPT易于实现并且平均可降低17%-35%的能耗。3.基于SoC实时控制系统的资源受限特征,提出一种任务执行时间可变时的电压/频率调度算法SVS-FPPT。该算法基于使用最优化方法得到抢占阈值调度模型下每个任务最长可能执行时间,而后根据任务执行时间的分布来计算任务内的电压/频率调度,以达到系统平均能耗最小化的目的。仿真试验表明,任务执行时间变化愈剧烈,算法的节能效果愈高。4.针对在嵌入式实时系统中运用DVS技术所带来的副作用之一,即DVS技术的应用使得任务切换次数迅速增加的问题,提出一种节能的抢占阈值调度算法EE-FPPT。该算法借鉴抢占阈值调度模型,提出一种基于响应时间分析、面向低功耗系统、针对静态优先级任务的可调度性判定方法,而后证明应用DVS技术的静态优先级系统,在使用抢占阈值调度策略时,在获得最大阈值分配的情况下,系统功耗最低,最后给出低功耗系统获取最低能耗的算法,该算法同时使得系统的任务切换次数最低。5.针对在嵌入式实时系统中运用DVS技术所带来的副作用之一,即DVS技术的应用使得任务执行时间延长进而使得处理器的静态功耗(由CMOS电路的泄露电流引起)迅速增加的问题,提出一种两阶段节能调度算法LAEES-FPPT。该算法将节能调度和延迟调度结合起来,先使用离线算法来计算每个任务的最优处理器执行速度,而后使用在线模拟调度算法来计算每个的任务的延迟时间,从而动态判定处理器开启/关闭时刻。实例研究和仿真实验表明,我们的方法能够进一步降低抢占阈值任务调度算法的功耗。6.为了高效使用片上系统中的有限内存,提出一种内存受限平台上的高效抢占阈值调度算法FPTS。该算法将SRP协议和PTS调度算法结合起来,将任务的抢占阈值分配和各个共享资源的冲顶值分配统一起来,在防止高优先级任务的过多抢占的同时,保持共享资源的串行访问,从而实现运行栈空间的最小化使用。仿真实验表明,与普通抢占阈值调度算法相比较,FPTS算法能够有效降低系统内存使用。

全文目录

摘要  11-13
ABSTRACT  13-16
第一章绪论  16-38
  1.1 研究背景  17-25
    1.1.1 SoC实时控制系统的基本特征  17-19
    1.1.2 SoC实时控制系统中的任务调度算法  19-20
    1.1.3 任务调度算法面临的新挑战  20-25
  1.2 研究现状分析  25-34
    1.2.1 任务调度算法  25-27
    1.2.2 资源访问控制协议  27-31
    1.2.3 实时系统的功耗优化  31-32
    1.2.4 控制额外内存消耗  32-34
  1.3 本文主要工作  34-36
  1.4 本文组织结构  36-38
第二章面向异步任务集合的抢占阀值调度算法  38-56
  2.1 相关概念与技术  38-42
    2.1.1 基本术语与假定  38-39
    2.1.2 level-i忙周期分析方法  39-41
    2.1.3 抢占阈值调度算法  41-42
  2.2 可调度性判定方法  42-48
    2.2.1 关键时刻  43
    2.2.2 可行性区间  43-44
    2.2.3 任务最长响应时间分析  44-48
  2.3 抢占阀值分配方法  48-51
    2.3.1 抢占阀值分配算法  48
    2.3.2 算法分析  48-50
    2.3.3 确性证明  50-51
  2.4 实验验证  51-54
    2.4.1 实验设置  51
    2.4.2 评价指标  51
    2.4.3 测试数据集  51-52
    2.4.4 实验结果分析  52-54
  2.5 本章小结  54-56
第三章可变电压处理器上的抢占阈值节能调度算法  56-96
  3.1 实时系统的节能调度理论  56-63
    3.1.1 CMOS电路功耗模型  56-58
    3.1.2 实时系统的低功耗设计  58-59
    3.1.3 DVS技术  59-60
    3.1.4 基于DVS技术的实时节能调度算法  60-63
  3.2 抢占阈值调度策略下的离线节能调度算法  63-67
    3.2.1 可调度性分析方法  63-64
    3.2.2 功耗最小化的离线算法ES-FPPT  64-65
    3.2.3 实验验证  65-67
  3.3 任务时间动态变化时任务内电压/频率调度算法  67-71
    3.3.1 最大可能系统负载的计算方法  67-68
    3.3.2 任务内电压/频率调整方法  68-70
    3.3.3 实验验证  70-71
  3.4 低功耗系统的抢占阈值调度  71-81
    3.4.1 可调度性分析方法  71-75
    3.4.2 功耗最优的抢占阈值分配方法  75-78
    3.4.3 实验验证  78-81
  3.5 抢占阈值调度算法的在线功耗优化  81-92
    3.5.1 系统模型和问题定义  82-84
    3.5.2 两阶段节能调度算法  84-86
    3.5.3 算法分析  86-90
    3.5.4 实验验证  90-92
  3.6 本章小节  92-96
第四章内存受限系统中的抢占阈值调度算法  96-110
  4.1 RTOS内存使用分析  96-98
    4.1.1 独立运行堆栈的必要性  96-97
    4.1.2 使用全局运行栈  97
    4.1.3 PTS策略的非抢占组  97-98
  4.2 抢占阈值调度与SRP协议  98-99
  4.3 FPTS调度模型  99-102
    4.3.1 任务执行过程中只访问单个资源  99-100
    4.3.2 任务执行过程中访问多个共享资源  100-102
  4.4 内存消耗最少的抢占阈值分配方法  102-105
    4.4.1 MPTA的内存消耗最优性  102-103
    4.4.2 最大抢占阈值MPTA分配算法  103-105
  4.5 实验验证  105-107
    4.5.1 评价指标  105
    4.5.2 测试数据集  105-106
    4.5.3 实验结果分析  106-107
  4.6 本章小结  107-110
第五章原型系统验证  110-130
  5.1 引言  110-111
  5.2 RT-Linux平台上抢占阈值调度算法的实现  111-114
    5.2.1 RT-Linux平台上实现抢占阈值调度策略  112-114
    5.2.2 如何在RT-Linux平台上实现更加复杂的任务调度算法  114
  5.3 RT-Linux平台上实时节能调度算法的实现  114-119
  5.4 节能效果评估  119-127
    5.4.1 实验环境设置  119-120
    5.4.2 实验设计  120-122
    5.4.3 实验结果分析  122-127
  5.5 内存节省效果评估  127-129
    5.5.1 LTT测试工具  127-128
    5.5.2 实验设计  128
    5.5.3 实验结果分析  128-129
  5.6 本章小结  129-130
结束语  130-134
致谢  134-136
参考文献  136-150
作者在学期间取得的学术成果  150-152
附录A 基于RT-Linux平台的应用层调度器  152-160
  A.1 如何在RT-Linux平台上实现更加复杂的调度算法  152
  A.2 应用层调度模型  152-156
  A.3 在RT-Linux平台上实现应用层调度模型  156-160
附录B RT-Linux平台上如何实施节能调度  160-166
  B.1 Cpufreq内核子系统的设计和使用  160-162
  B.2 RT-Linux内核中用于电源管理的数据结构和函数接口  162-166
附录C PXA255处理器的节能特性  166-170
  C.1 处理器工作模式  166-168
  C.2 处理器时钟  168
  C.3 处理器能耗评估  168-170

单芯片系统（SoC）中的实时任务调度算法研究

内容摘要

全文目录

相似论文