实时操作系统任务调度算法的硬件化研究

发布时间：2016-08-04 09:47

第1章 绪论 

1.1  课题研究的背景和意义 
实时操作系统在如今的嵌入式领域具有广泛的应用，比如航天科技、自动化生产、医疗器械、智能化可穿戴设备、移动通讯设备等诸多应用领域。而且实时操作系统相较于其他的操作系统具有不可替代的优势，因此实时操作系统在各大嵌入式应用领域作为信息产业和传统产业的中介，处于越来越核心的地位，值得深入的研究。 相对于其他的操作系统，在嵌入式领域中实时操作系统的优势尤为明显。一方面，实时操作系统显著的增强了实时系统的健壮程度。在传统的超循环系统中，实时性要求很高的关键操作必须依靠中断处理程序来保证，很容易出现任务无法及时回应，甚至是由于强烈干扰引起整个系统的死机，从而产生无法估量的损失。而实时操作系统不仅可以充分满足任务的实时性需求，而且可以把强烈干扰造成的破坏控制在局部，只引起少数进程被破坏，系统的监控机制还能够尽可能的修复被破坏的进程，从而减少损失[1]。另一方面，实时操作系统可以减少应用软件的开发周期和维护成本。在实时操作系统下，应用程序被分化成若干相对独立的任务模块，使得应用程序的开发变得独立化和简单化。而且通过内核的系统调用使得系统资源得到更充分的利用。在后期的维护过程中，如果想增加新功能，或者对于以前的功能进行修改，也不必要做整体性的改动，大大降低了后期维护的成本。 在实时操作系统中，任务调度机制处于系统的支配地位，其遵循设定的任务调度算法，在每一个必须进行任务调度的时间点选择出下一个要执行的任务，并且完成相应的任务上下文切换等工作，保证系统的实时性要求得到满足，以及系统资源的合理化配置。而任务调度算法在任务调度过程中又处于核心地位，是确保实时系统中任务的时间约束性的关键依据。 
.......

1.2  实时操作系统任务调度的研究现状
自从 20 世纪 80 年代开始，在国外就有一些计算机科学科研机构和科技企业从事嵌入式领域实时操作系统的研究和开发。这些组织机构开发出的经典实时操作系统主要基于软件实现，其中比较有代表性的实时操作系统包括Vx Works、Lynx OS、μC/OS-II 等[4]。 Vx Works 是由美国的 Wind River 公司在 1983 年正式推出的一款可以在目标机上运行的可剪裁的、可靠的嵌入式实时操作系统。Vxwokrs 支持丰富的计算机网络协议，可以实现远距离的程序调用和文件读写操作，是网络中主机之间的连接更为密切[5]。Vxwokrs 提供了强大的网络服务功能，使得目标机能与其他主机方便的实现交互通信。Vxwokrs 的任务调度算法是基于优先级且抢占式的，任务调度内核保证把处理器和相关系统资源优先分配给具有最高优先级的就绪任务，使得系统总能运行目前最为紧迫的任务。如果有任务的状态刚刚转换为就绪态，并且其优先级高于正在执行的任务的优先级时，任务调度内核会重新开启，保存正在执行任务的上下文于任务堆栈当中，然后将正在运行的任务从运行态转换为就绪态，插入到就绪队列中相应位置，并运行就绪队列中具有最高优先级的任务。在 Vxwokrs 中任务的优先级不是始终不变的，可以调用Task Priority()系统函数动态的修改任务的优先级。Vxwokrs 支持基于优先级的抢占调度与基于时间片的轮转调度相结合，使得处理器和相关的其他系统资源更公平的分配[6]。 
...........

第2章 实时操作系统的任务调度原理 

2.1  实时操作系统的主要特点 
实时操作系统是指具有较高实时性需求的，当外部有突发事件需要响应时，能够尽可能迅速的进行处理[27]和控制系统内的所有任务协调的并发运行[28]的，支持实时性控制工作的操作系统。对于实时操作系统来说，满足系统对于时间的限制和要求，调动一切可以利用的资源保证实时的多任务控制才是第一位的，其次才是提高计算机系统其他方面的性能。 从表现上来看，实时操作系统是在启动嵌入式系统之后运行的背景程序，应用程序是在此基础上运行的多个任务。实时操作系统依据各个任务的具体要求，进行消息处理、任务调度和资源管理等工作。在实时操作系统支持的系统中，根据各个任务的重要性和紧迫性不同，都被指定相应的优先级，以此为关键依据动态的的切换任务，以确保系统对实时性的要求。这种体系结构大大化简了编程，比以前的的循环控制结构更适用于嵌入式系统。 从性能上来看，实时操作系统与其他操作系统的根本差别体现在实时性上。在实时计算中，系统的运行结果是否正确不仅取决计算结果本身，还取决于产生结果的时刻。从这个角度来看，实时操作系统是一个能够在指定的时间内实现预期功能，并且对于各种事件作出及时响应的操作系统。这就要求系统能够保存和处理系统控制所需要的大规模数据，从而在事先设定的时间范围内识别和处理离散的事件。 实时操作系统与其他操作系统不同，，实时操作系统不仅仅要解决任务如何完成，还要解决任务在规定的时间范围内及时完成的问题。另外，实时操作系统大多应用于嵌入式领域，系统还需要根据嵌入式系统的应用需求做出一些相应的调整。 
.........

2.2  μC/OS-II 的任务调度机制
在支持多道程序的环境下，允许多个程序并发的执行，此时这些程序的封闭执行就被打破了，具有了不可重现和间断执行的特性。为此操作系统引入了进程的概念，以便于合理的描述和控制多道程序的并发运行，实现系统的资源共享性和程序并发性。引入进程是为了使多道程序并发的执行，提高系统的吞吐量和资源利用率；而引入线程是为了降低程序在并发执行时所产生的时间和空间的开销，用以提高系统并发性。在 μC/OS-II 内核中，将一个线程称之为一个任务，它是用户应用程序的一个具体运行实体，作为处理器的一个基本执行单位，被系统独立的调度和分派。每一个任务都被分配自己的处理器寄存器和任务堆栈空间，在其得到执行时独占处理器资源。 从形式上来看，任务是一个无限循环的程序段落，被写成类似函数的形式，有形式参数和返回类型，但是不可能真正的返回。任务函数的形式参数通常被定义成 void 类型指针，通过这种方式在任务被创建时用户可以被传入任意类型的数据。用户也可以创建多个任务，但是都重入一个任务函数，只是输入的初始数据不同，大大减少代码空间的占用。 
........

第 3 章  实时操作系统的任务调度算法改进 .... 19 
3.1  经典任务调度算法分析 ......... 19 
3.1.1  实时调度算法 ......... 19 
3.1.2  非实时调度算法 ..... 21 
3.2 μC/OS-II 的任务调度算法改进 ....... 22 
3.2.1  调度算法设计 ......... 22 
3.2.2  数据结构修改 ......... 25 
3.3  本章小结 ...... 26 
第 4 章  实时操作系统的任务调度算法硬件化 ......... 27 
4.1 FPGA 设计原理 ..... 27 
4.2 μC/OS-II 的硬件任务调度器设计 ............ 29 
4.2.1  调度器的整体结构 .......... 29 
4.2.2  任务组的调度 ......... 31 
4.2.3  组内同级任务的调度 ...... 32 
4.3  本章小结 ...... 34 
第 5 章  仿真及实验结果分析 .......... 35 
5.1 XUP Virtex-II Pro 开发平台 ............ 35 
5.2  集成软件环境 ISE ......... 36 
5.3  任务调度器的仿真结果及分析 ...... 37 
5.4  本章小结 ...... 41 

第5章 仿真及实验结果分析 

5.1  XUP Virtex-II Pro 开发平台

Xilinx  公司是全球最早研发出 FPGA  器件的机构，也是目前全球规模最大的可编程逻辑器件供应商。Xilinx 公司在通信行业除了研发和生产制造 FPGA 器件之外，还在行业标准的制定扮演重要的角色，积极提供各种系统集成和系统解决的设计方案等。 本课题采用 Xilinx  公司的 XUP Virtex-II Pro 作为实验平台，其具有强大的处理功能，通过扩展连接器能够与多种外部模块连接，而且该系统的设计得到包括 ISE、System Generator、EDK 在内的多种行业主流的开发工具支持。所以很多研究机构和高校都采用这一系列的产品作为研发平台。 Virtex-II  Pro 系列器件是在 Virtex-II 的基础上增强了嵌入式相关的处理功能，内置了 Power PC  405 处理器硬核，为了应对高性能系统的挑战，还引入了主动互联技术，采用 0.13μm 工艺，支持超过 20 种 I/O 接口标准，完善了时钟处理和数字信号处理功能。本课题选用的是 FPGA 芯片型号是 Virtex-II Pro 系列中的 XC2VP30。 Virtex-II Pro 系列的 XC2VP30 可编程系统芯片在芯片内部集成了 2 片 32  位的 Power PC  405  处理器内核，内置了 8 个 I/O  bank  、8  个 DCM 和 30816  个Logic Cell，从而确保较为复杂的算法实现。  Virtex-II  Pro 的可配置 I/O  管脚最多可达 644 个，可用 I/O  管脚最多可达644 个，  Block RAM 的最大容量到达 2448KB，18kb  的 Block RAM 数目为 136个。 Virtex-II  Pro 还提供了 100MHz 系统时钟和 75MHz 的 SATA 时钟，支持 “User”和“Golden”FPGA  配置比特流文件，并且配备了 USB  配置端口和 JTAG 配置端口各一路。 

........

结论 

本文在研究了国内外实时操作系统任务调度的研究成果后，结合 μC/OS-II实时操作系统内核的自身特点，为 μC/OS-II 原来的任务调度算法扩展了同级任务调度功能，并基于 FPGA 硬件逻辑设计并实现了基于改进算法的硬件任务调度器。本文主要完成了以下工作：首先介绍了实时操作系统的主要特点，然后重点分析了 μC/OS-II 的任务调度机制，包括任务控制块结构、任务状态转换，以及任务的管理、调度和切换的工作原理。首先分析和总结了一些经典任务调度算法的突出特点，并提出了要根据应用需要选择和修改现有的任务调度算法；然后为了改进 μC/OS-II 不支持同级任务调度的不足，设计了一种二级混合调度算法。第一级调度采用原来的基于优先级的调度算法选择出最高的有就绪任务的优先级；第二级调度对该优先级对应的同级任务启动同级调度策略。在同级调度中，对于实时的同级任务采用较公平的时间片轮转算法；对于非实时的同级任务采用开销较小的先来先服务算法。为了适应改进的算法，本文还修改μC/OS-II 内核的部分数据结构，主要包括任务控制块的内部参数和增加了由用户设置的优先级阈值。 
.........
参考文献(略)

本文编号：84429