准划分多核实时调度策略的研究与实现

发布时间：2020-10-01 19:53

　　 随着多核架构成为处理器发展的主要方向,多核系统上的实时调度问题已经成为了学术界与工业界的热点研究问题。在固定优先级调度中,目前已知的全局和局部固定优先级调度的最大利用率上限是50%,人们迫切地需要一种具有较高利用率上限以及较少抢占次数的多核调度算法。准划分调度算法将大部分任务固定分配到特定的处理器上,以降低运行时开销,同时为了改善可调度性,一小部分任务被切割为可以运行在多个处理器上的多个子任务。和局部策略相比,这类准划分调度算法对可调度性提供了重要的改善,而比较全局策略,它又具有较少的抢占和迁移。 软实时系统允许任务的某些作业错过截止期。在错过截止期的情况下,如果能够确知任务的执行时间延迟具有一个可计算的上限,那么处理器资源就会得到正确的分配,这对于软实时系统具有重要意义。但是目前基于该类调度算法的延迟上限的研究尚不充分,本文研究了基于固定优先级调度的准划分调度算法的延迟上限问题,并以速率单调算法(Rate Monotonic, RM)为例,给出了准划分调度算法的延迟上限的计算方法。 在允许抢占和核间迁移的情况下,准划分调度算法极大地改善了多核调度的CPU利用率。但是目前该算法在实际操作系统中的实现工作还很欠缺,本文设计实现了一个支持准划分调度策略的多核实时调度器。本文首先分析了实现该调度器的关键技术,包括任务切割、任务迁移等。在此基础上,给出了基于Linux2.6.20内核的准划分调度器的具体实现。同时,本文设计了一个用户函数库,允许将不同的准划分调度算法扩展到本系统中。通过大量实验,验证了本文准划分调度器的功能正确性。该部分工作对于开展准划分实时调度的研究,以及推进准划分调度策略在实际系统中的应用将起到重要作用。
【学位单位】：东北大学
【学位级别】：硕士
【学位年份】：2010
【中图分类】：TP332;TP301.6
【文章目录】：
摘要
Abstract
第1章 绪论
    1.1 课题背景
    1.2 研究目标和意义
    1.3 国内外研究现状
    1.4 论文的组织结构
第2章 相关理论与技术技术
    2.1 实时系统以及实时任务分类
        2.1.1 实时系统分类
        2.1.2 实时任务分类
    2.2 多核实时调度算法
    2.3 准划分固定优先级实时调度
RT'>    2.4 LITMUSRT

        2.4.1 LITMUSRT基本功能
        2.4.2 支持的实时调度策略与策略选择
        2.4.3 Trace功能
    2.5 本章小结
第3章 准划分固定优先级调度算法延迟上限的研究
    3.1 系统模型
    3.2 准划分固定优先级算法
    3.3 任务延迟上限的计算
    3.4 本章小结
第4章 准划分调度器的设计
    4.1 总体设计
    4.2 实时任务的调度过程
    4.3 实时任务的运行状态
    4.4 运行时调度的设计
        4.4.1 切割任务调度的设计
        4.4.2 队列管理的设计
    4.5 用户库的设计
    4.6 本章小结
第5章 准划分调度器的实现
    5.1 准划分调度器核心数据结构的实现
    5.2 准划分调度器关键技术实现
        5.2.1 任务抢占的实现
        5.2.2 任务切换的实现
        5.2.3 任务入队管理的实现
    5.3 准划分调度器接口部分的实现
        5.3.1 系统调用
        5.3.2 队列管理函数
    5.4 用户库的实现
        5.4.1 插件式离线划分算法模块的实现
        5.4.2 应用程序的实现
    5.5 本章小结
第6章 实验测评及分析
    6.1 任务划分与创建
        6.1.1 实验环境
        6.1.2 实验过程
    6.2 内核调试
    6.3 实时任务执行结果分析
        6.3.1 实验结果展示
        6.3.2 实验结果分析
    6.4 本章小结
第7章 结论与展望
    7.1 结论
    7.2 未来工作与展望
参考文献
致谢
科研项目和论文发表情况

【共引文献】

相关期刊论文 前1条

1 金永贤;黄经州;;开放式实时系统双层调度框架的一种改进方案[J];计算机应用;2009年06期

相关博士学位论文 前2条

1 郭秀岩;面向多核的多层次实时网络数据流调度技术研究[D];中国科学技术大学;2011年

2 吴彤;弱硬实时调度关键技术研究[D];国防科学技术大学;2008年

相关硕士学位论文 前2条

1 黄经州;开放式混合实时系统调度策略研究[D];浙江师范大学;2009年

2 袁征;基于页着色技术的多核实时系统中Cache共享策略的研究[D];东北大学;2009年

本文编号：2831932

suoshi