论文部分内容阅读
实时系统通常是指可实现计算机控制的嵌入式系统。它自出现一来一直稳步发展,近几年来更有着飞速地发展,应用于几乎所有行业:从日常家电到一般工业、交通……直至航天航空等领域。对实时系统的研究涉及到实时编程语言及工具、实时通讯、实时任务调度、容错技术及可靠性评估技术等众多方面内容,而在这些研究中,实时任务调度占据核心位置。
随着硬件技术的发展和实际控制任务变得越来越复杂,实时系统已由无操作系统阶段发展到带有通用嵌入式操作系统(RTOS)阶段,出现了所谓的片上系统(SOC)。同时,嵌入式系统在应用层上的飞速发展,也促使嵌入式系统体系结构由静态向动态,由通用向可定制的特定应用转变,从而出现了基于特定应用的嵌入式操作系统(ASOS)。特定应用系统是一种片上系统,它实现了嵌入式与Internet网络的真正结合,嵌入式操作系统与应用设备的无缝结合,代表着嵌入系统发展的一种趋势。ASOS本身是一种实时操作系统但与一般意义上的RTOS存在区别:
■ASOS更强调面向应用的功能专用性,如面向某一(组)应用的高可靠性的部分功能集,而并不像RTOS的系统通用性与系统资源可配置性;
■ASOS更强调面向应用的实时高性能,而并不像RTOS强调的系统整体效率;
■ASOS更强调系统结构的可伸缩性和可裁减性,一个极典型的例子是传真机操作系统(OSforFAXMachine);
■ASOS更强调与Internet的连接,特别是无线接入接口。
■ASOS追求更高的性价比。
ASOS与RTOS间的差异反映在调度算法上主要表现为基于ASOS的调度算法应满足以下三个基本要求:(1)任务调度开销要尽量小。ASOS的实时高效性要求任务切换要尽量少。在RTOS算法研究中,往往忽略任务切换开销,而在实际任务的调度中,任务的切换时间往往是不可忽略的,尤其是在复杂的多任务系统中,任务抢占频繁,任务切换开销相对较大,而再像RTOS的调度算法中忽略任务的切换开销,将造成灾难性后果。(2)任务调度的内存需求不能太高。在经典实时调度算法研究中通常都没有考虑到内存容量的限制,即假设所需的内存都能满足要求。由于特定应用系统是一种片上系统,因此系统空间决定内存配置不能太大,此外,对系统低成本的追求也决定各种配置不能太高,这就要求调度算法应考虑到存储容量的限制。(3)算法应便于在实际开发中的应用。现在,嵌入式处理器的运行速度越来越快,系统软件及基于其上的应用软件也越来越复杂,因此在软件开发上,许多特定应用系统引进了实时系统的面向对象设计技术(ROOM)和统一建模语言(UML),这些高级技术的引进也决定了面向特定应用系统的调度算法不同于通用嵌入系统的调度算法。
虽然ASOS的概念提出已有几年了,但是针对ASOS的调度算法研究还是一个较新的领域,有着现实的需求。本文根据ASOS算法要求,提出了单处理器的专门基于片上ASOS系统的静态优先级和动态优先级调度算法。
对于处理器利用率要求不十分高的ASOS系统,本文首先给出了静态优先级下的改进可抢占阈调度算法(IPTS)。它合并了单调截止时限算法(DMS)与抢占阈算法(PTS),是基于DMS算法上的一种改进算法。当每一个任务的抢占阈与按DMS算法分配的初始优先级相等时,IPTS算法就退化成完全可抢占的DMS算法;当每个任务的抢占阈都等于最高优先级时,它就变成了不可抢占调度算法。文章还给出了IPTS算法下的有效线程、最优线程和堆栈需求最小线程的分配方法。由于线程内的任务互不可抢占,又最优线程方法是最少的线程分配方法,所以最优线程能最大限度地降低了任务间的抢占次数,有效满足了ASOS任务调度的高效实时性要求。堆栈需求最小线程分配方法给了系统对堆栈内存需要最小情况下的线程分配方法。此外,线程的引进可以使IPTS算法与ROOM等技术较容易地结合在一起,便于复杂软件的开发。
对处理器要求较高的系统,文章给出了动态优先级抢占阈调度算法(DPTS),在理论上它可以达到100%的处理器利用率。DPTS算法是建立在动态优先级调度算法一一EDF算法上的抢占阈调度算法。在DPTS算法下每个任务被赋予三个优先级:初始优先级、抢占水准和抢占阈。当抢占水准与抢占阈相等时,DPTS算法退化成可抢占的EDF算法,当抢占阈等于最高抢占水准时,DPTS算法变成完全不可抢占调度算法。文中同样给出的DPTS算法下的有效线程、最优化线程和堆栈需求最小线程分配方法。在文章最后还给出了优化的DPTS算法,它将静态不变的抢占阈按运行时的实际情况而加以改变,可以更有效地降低任务间的切换开销。
对ASOS的调度算法研究是一个开放的课题,需要研究的内容及深度都需要加宽加深,希望通过本人的一点拙见,起到抛砖引玉的作用。