基于嵌入式多处理器操作系统任务调度的研究

摘要

嵌入式系统已经越来越多地应用在各个领域中，随着硬件和软件技术的发展，操作系统在嵌入式领域发挥着越来越重要的作用。其中大多数嵌入式系统都是基于单处理器环境，而随着计算机技术的迅速发展，嵌入式系统也开始应用于多处理器环境。从单处理器到多处理器，从串行到并行。多处理器并行系统由于其高性能和可靠性，已成为新一代嵌入式系统发展的趋向。 在嵌入式多处理器系统中，任务调度问题的规模也越来越大，多线程的任务调度成为决定系统性能的关键，但是多处理器系统中任务调度的求解是一个NP完全问题。当系统中的处理器和任务数目较大时，用一般的穷举遍历方法是不现实的。在大多数的情况下，人们寻求的只是次优解。 本文首先研究多处理器并行环境下的各种任务调度计算模型和常用的各种任务调度算法，分析嵌入式系统和多处理器系统的结构特性。采用单芯片多处理器(CMPChipMultiProcessors)硬件架构和对称多处理(SMPSymmetricMultiProcessing)操作系统模式，应用集中式的调度器模型，提高处理器的总体计算能力。结合并行计算的思想，通过将任务进行先划分后组合的方式，减少任务调度中的开销。研究E.B.Fernandez提出的算法模型，改进原有的计算模型和调度模型，应用启发式算法求解最小运行时间。分析单处理器环境下基本的组合分配算法和流量算法，将图论里的深度搜索思想应用到简化任务图上。在流量算法中，应用最大流最小截集算法(MaxFlow/MinCut)求解任务调度问题，并在计算模型中融入叠加开销参数。在此基础上提出一种新的调度策略，即采用逆向有序拓扑序列，通过减少任务的通信开销使得任务的运行时间最小，以此提高任务调度的效率。 在并行程序设计环境下，通过OpenMP编程模拟实验证明，改进后的算法不仅提高了处理器的利用率和任务调度的成功率，而且最大程度地减少了任务的运行时间。

目录

文摘

英文文摘

声明

第1章绪论

1.1课题背景及意义

1.2本文研究内容及工作重点

1.3论文组织结构

第2章嵌入式系统和任务调度理论

2.1嵌入式系统概述

2.2嵌入式系统的技术特点

2.3嵌入式操作系统

2.4任务调度问题

2.5任务调度

2.5.1任务的分类

2.5.2任务调度算法的分类

2.6任务调度系统

2.6.1任务图的DAG模型

2.7 NP难解问题的描述

2.8任务调度的性能评估方法

2.9小结

第3章多处理器并行系统的研究和改进

3.1多处理器并行系统

3.2硬件和软件结构

3.2.1 CMP结构

3.2.2多处理器操作系统

3.3多处理器并行系统的通信机制

3.3.1处理器之间的通信

3.3.2任务之间的通信

3.3.3多处理器并行系统的负载分配

3.4调度器模型

3.5嵌入式系统下任务调度的设计

3.5.1任务划分

3.5.2任务通信

3.5.3任务组合

3.5.4任务映射

3.6小结

第4章调度技术的研究和调度模型的改进

4.1嵌入式多处理器系统任务最小运行时间研究

4.1.1研究进展

4.1.2 Femandez模型

4.1.3 DAG最小运行时间——改进Femandez计算模型

4.2多处理器系统任务调度算法基本模型

4.3任务调度计算模型的改进

4.3.1原有计算模型的不足之处

4.3.2多处理器系统调度模型的改进

4.4小结

第5章组合分配算法和通道流量调度算法

5.1组合分配算法

5.1.1组合算法的改进

5.1.2分配算法的改进

5.2通道流量调度算法改进和应用

5.2.1 Stone计算模型及调度算法原理

5.2.2 Max Flow/Min Cut定理

5.2.3应用Max Flow/Min Cut于多处理器系统任务调度

5.2.4融合叠加开销的Max Flow/Min Cut算法

5.3组合分配算法和流量算法的比较

5.4算法性能测试

5.4.1实验的基本参数

5.4.2仿真实验分析

5.4.3仿真实验结果

5.5 小结

第6章一种新的任务调度策略——运行时间最小化算法

6.1算法的思想

6.2相关定义

6.3处理器系统模型

6.4运行时间最小化算法

6.5算法分析

6.6模拟实验及性能评价

6.6.1并行程序设计环境

6.6.2 OpenMP编程简介

6.6.3模拟实验

6.7小结

第7章总结与展望

7.1本文工作总结

7.2未来研究方向

致谢

参考文献

个人简介