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

可重构系统中实时任务调度算法研究

作　者: 殷进勇
导　师: 顾国昌
学　校: 哈尔滨工程大学
专　业: 计算机应用技术
关键词: 实时调度算法多处理器可重构系统 DS服务器优先约束任务软/硬件混合任务
分类号: TN791
类　型: 博士论文
年　份: 2010年
下　载: 235次
引　用: 1次
阅　读: 论文下载

内容摘要

可重构计算兼有软件的灵活性和硬件的高效性,在嵌入式系统、高性能计算和实时系统等领域有广阔的应用前景,已成为计算机领域中的一个研究热点。典型的可重构系统由一个(或多个)处理器和一片(或多片)FPGA组成,为发挥可重构计算的灵活性和高性能,一个实时任务可把计算密集部分划分成硬件任务(逻辑电路)在FPGA上加速执行,而其余部分以软件任务(指令集)方式在处理器上执行。这样在可重构系统上执行的实时任务就包括仅在处理器上执行独立软件任务、优先约束软件任务和在处理器-FPGA上执行的软/硬件混合任务,本文针对这3类实时任务的调度问题进行了深入研究,主要研究内容如下:1.在实时系统中,周期任务和非周期任务并存,而现有的独立周期/非周期混合实时任务调度算法是针对单处理器系统提出的,适用范围窄,故此提出了适用于多处理器系统的独立周期/非周期混合实时任务调度算法。该算法在DS服务器上调度非周期任务,混合调度DS服务器和周期任务,能够满足所有周期任务和系统接收的非周期任务的截止期限。2.在多处理器系统中,有些实时任务包含多个具有优先约束关系的子任务,而现有的优先约束实时任务调度算法多为静态调度算法,计算复杂度高且不能调度非周期任务,故此提出了优先约束周期/非周期混合实时任务的动态调度算法。该算法在系统运行前判定周期任务的可调度性,降低了系统的在线调度开销,在多个DS服务器上调度随机到达的非周期任务。3.在可重构系统中,有些实时任务不仅包含在处理器上执行的软件子任务,还包含在FPGA上执行的硬件子任务,而现有的实时调度算法只能调度软件任务或硬件任务,故此提出了软/硬件混合实时任务调度算法。该算法把每个实时任务的硬件子任务分成若干组,每组子任务配置到同一个空闲槽内,提高了可重构资源利用率。该算法分析了实时任务的可调度性,能够保证所有实时任务满足截止期限。4.在可重构系统中,硬件电路的配置信息存储在静态RAM中,容易受到周围环境的干扰,使硬件电路出现故障,故此提出了一种实时任务容错调度算法,以提高系统的可靠性。该算法把每个软件子任务调度到两个处理器上同时执行,如果处理器出现故障则回卷到上一个检测点处执行,保证了软件子任务的正确性;把每个硬件子任务划分到3个组中,调度到3个空闲槽内执行,屏蔽了错误结果。在硬件资源开销不大的情况下,该算法能够容忍多个硬件故障,保证实时任务的截止期限。

全文目录

摘要  5-7
Abstract  7-12
第1章绪论  12-31
  1.1 课题研究背景  12-13
  1.2 可重构计算概述  13-15
    1.2.1 FPGA 可重构模式  13-14
    1.2.2 可重构系统结构  14-15
  1.3 实时系统概述  15-18
    1.3.1 实时任务属性及分类  15-17
    1.3.2 实时系统特点  17-18
  1.4 实时调度技术的研究现状  18-26
    1.4.1 软件任务调度  20-25
    1.4.2 硬件任务调度  25-26
  1.5 论文研究内容  26-28
  1.6 论文组织结构  28-31
第2章独立软件实时任务调度  31-57
  2.1 引言  31-32
  2.2 任务模型  32
  2.3 非周期任务调度  32-39
    2.3.1 DS 算法  32-34
    2.3.2 RB 算法  34-35
    2.3.3 SU 算法  35
    2.3.4 DS-EDF 算法  35-39
  2.4 混合任务调度  39-50
    2.4.1 GSHT 调度算法  39-48
    2.4.2 PSHT 调度算法  48-50
  2.5 实验结果及分析  50-56
    2.5.1 相关算法比较  50-52
    2.5.2 算法性能测试  52-56
  2.6 本章小结  56-57
第3章优先约束的软件实时任务调度  57-76
  3.1 引言  57-58
  3.2 任务模型  58-59
  3.3 周期任务可调度性分析  59-63
  3.4 非周期任务可调度性分析  63-65
  3.5 GSHTPC 调度算法  65-68
    3.5.1 混合可调度性分析  65-66
    3.5.2 算法描述  66-68
  3.6 实验结果及分析  68-74
    3.6.1 相关算法比较  68-70
    3.6.2 周期任务调度结果  70-73
    3.6.3 非周期任务和混合任务调度结果  73-74
  3.7 本章小结  74-76
第4章软/硬件混合实时任务调度  76-100
  4.1 引言  76
  4.2 任务和资源模型  76-79
    4.2.1 任务模型  76-78
    4.2.2 可重构资源模型  78-79
  4.3 硬件子任务分组  79-83
    4.3.1 分组算法描述  79-82
    4.3.2 分组算法实验结果  82-83
  4.4 SSHTNB 调度算法  83-89
    4.4.1 可调度性分析  83-84
    4.4.2 算法描述  84-86
    4.4.3 实验结果与分析  86-89
  4.5 SSHTWB 调度算法  89-98
    4.5.1 可调度性分析  89-92
    4.5.2 算法描述  92-94
    4.5.3 实验结果与分析  94-98
  4.6 相关算法比较  98
  4.7 本章小结  98-100
第5章软/硬件混合实时任务容错调度  100-116
  5.1 引言  100-101
  5.2 容错技术  101-104
    5.2.1 硬件冗余容错  101-102
    5.2.2 软件冗余容错  102-103
    5.2.3 时间冗余容错  103-104
  5.3 FT-SSHTNB 调度算法  104-112
    5.3.1 处理器和软件子任务故障检测  105-109
    5.3.2 硬件子任务容错  109-110
    5.3.3 实时任务容错可调度性判定  110-111
    5.3.4 算法描述  111-112
  5.4 实时性分析  112-113
  5.5 实验结果与分析  113-115
  5.6 本章小结  115-116
结论  116-118
参考文献  118-129
攻读博士学位期间发表的论文  129-130
致谢  130

可重构系统中实时任务调度算法研究

内容摘要

全文目录

相似论文