摘要:论述了OS 中调度的概念、类型、调度队列模型,并着重对VxWorks 实时内核进行了分析。
关键词:嵌入式实时操作系统(RTOS) ;VxWorks ;调度
0 引 言
VxWorks 是美国Wind River 公司推出的一种嵌入式强实时操作系统,自20 世纪80 年代问世以来,以其高性能、高可靠性、高实时性等特点成为实时操作系统中最具特色的系统。尤其以成功应用于火星探测车和爱国者导弹等高科技产品而声名鹊起。自1996 年登陆中国,短短几年就已成为国防、工业自动化、网络通信、航空航天、医疗仪器、状态监控以及消费电子产品等嵌入式实时领域的首选操作系统。嵌入式实时操作系统在内核方面具有自身的特点。本文着重对实时内核中任务调度进行了分析。
1 调度的概念
构成应用软件系统的程序集合中,独立的、相互作用的程序单元,在其执行时称之为任务。单个CPU 中,多任务机制制造了一个多个任务同时执行的假象。其实系统只是根据一个多任务调度算法,将内核插入到这些任务中执行。任务由系统内核调度运行一段固定长度的时间,称为时间片。
调度是指为任务分配资源和时间,使系统满足特定的性能要求。调度算法的目的是在正常情况下,尽可能满足所有任务的时限;在峰值负载条件下,保证强实时任务满足时限。因为时限是区分实时系统和非实时系统的关键因素,因此调度算法是实时系统的基本问题。实时操作系统所具有的运行性能,如吞吐量的大小、周转时间的长短、相应的及时性和可预测性等在很大程度上都取决于实时调度。
2 调度的类型
虽然调度的主要目的都是为了分配处理机,但在不同的OS 中所采用的调度方式是完全不同的。在执行调度时所采用的调度算法也可能不同。因此,常按照调度的层次把调度分成高级、中级和低级调度。
高级调度又称长程调度或作业调度,用于决定把外存上处于后备队列中的哪些作业调入内存,并为它们创建进程、分配必要的资源,然后再将新创建的进程排在就绪队列上,准备执行。然而在实时系统中,为了能及时响应,用户通过键盘输入的数据都是直接送入内存,因而实时系统通常不需要作业调度。中级调度又称中程调度,引入它的主要目的是为了提高内存利用率和系统吞吐量。它使那些暂时不能运行的进程不再占用宝贵的内存空间,而将它们调到外存上去等待,此时的状态称为挂起状态。当这些进程重新具备运行条件,且内存又有空闲,由中级调度决定,将外存上的那些重新具备运行条件的就绪进程重新调入内存,并使它为就绪状态,挂在就绪队列上等待进程调度。低级调度又称进程调度。它决定就绪队列中的哪个进程将获得处理机,然后由分派程序执行把处理机分配给该进程的操作。进程调度是最基本的一种调度,各种OS 中都必须配置这级调度。
进程调度可采用下述两种方式。
1) 非抢占方式。采用这种调度方式,一旦把处理机分配给某进程后,便让该进程一直执行,直到该进程完成或发生某事件而被阻塞,才再把处理机分配给其他进程,决不允许某进程抢占已经分配出去的处理机。显然它难于满足紧急任务的要求,实时系统中不宜采用这种调度方式。
2) 抢占方式。允许调度程序根据某种原则,去停止某个正在执行的进程,将已分配给该进程的处理机,重新分配给另一进程。抢占的原则有:
①时间片原则。各进程按时间片运行,当一个时间片用完后,便停止该进程的执行而重新进行调度。
②优先权原则。当一个进程到来时,如果其优先级比正在执行的进程的优先级高,便停止正在执行的进程,将处理机分配给优先级高的进程,使之执行。实时系统中一般采用基于优先级的抢占式调度和轮转调度的进程调度和中程调度相结合的调度策略。因此既可具有较大的灵活性,又能获得极小的调度延迟。
3 调度队列模型
3. 1 仅有进程调度的调度队列模型就绪态的进程排在就绪队列中,按时间片轮转调度运行,每个进程执行时,都可能出现以下3种情况。
1) 任务在时间片内完成,则该任务释放处理机,该进程完成。
2) 任务在时间片内未完成,则OS 将该进程放在就绪队列的末尾,等待下一轮调度。
3) 任务在执行期间,进程被阻塞后,OS 将该进程放入阻塞队列。如图1 所示。
图1 仅具有进程调度的调度队列模型
3. 2 引入中级调度的调度队列模型较完善的OS 中,除设置了进程调度外,还引入中级调度来改善内存的利用率。当在OS 引入中级调度后,可把进程的就绪状态分为内存就绪态(进程在内存中就绪) 、外存就绪态(进程在外存中就绪) ;把阻塞状态分为内存阻塞和外存阻塞。在调出操作的作用下,可使内存就绪转变为外存就绪、内存阻塞转变为外存阻塞;在中级调度的作用下,可使外存就绪转变为内存就绪。如图2 所示。
图2 引入中级调度的进程调度的调度队列模型
4 VxWorks 实时内核Wind 调度分析Wind 内核缺省调度机制为基于优先级的抢占式调度。采用这种机制时,系统把处理机分配给优先级最高的进程,使之执行。一旦出现了另一个优先级更高的进程时,进程调度程序剥夺当前任务的执行,将处理机分配给高优先级任务。而在相同优先级的多个任务之间,采用时间片轮转调度机制。采用这种机制时,当一个任务到达时,它被排在轮转队列的后面,等待分配给自己的间片的到来,如果在时间片内没有结束,则再等待属于自己的时间片的到来,直到任务完成。
4. 1 基于优先级的抢占式调度
采用基于优先级的抢占式调度,系统中每个任务都有一个介于最高0 到最低255 之间的优先级。任一时刻,系统内核一旦发现一个优先级更高的任务转变为就绪态,内核就保存当前任务的上下文并把当前任务状态转换为阻塞态,同时切换到这个高优先级任务的上下文执行。如图3 ,低优先级的task1 被中优先级的task2 抢占,task2又被高优先级的task3 抢占。
图3 基于优先级的抢占式调度
4. 2 轮转调度算法
采用轮转调度算法,系统让处于就绪态的优先级相同的一组任务依次轮流执行预先确定长度的时间片。这是一种处理机平均分配的方法。如果不使用轮转调度算法,优先级相同的一组任务中第一个获得处理机的任务将不会被阻塞而独占处理机,如果没有阻塞或其他情况发生,它不会放弃处理机的使用权。如图4 , 相同优先级的task1 、task2 和task3 平均分配预先确定的处理机时间片。
图4 优先级相同轮转调度
4. 3 基于优先级的抢占式调度与轮转调度相结合有时,基于优先级的抢占式调度可与轮转调度相结合。当优先级相同的一组任务依次轮流平均分配处理机时,若有高优先级的任务转变为就绪态则可抢占该组任务。直到再一次符合执行条件时,该组任务才可再次共享处理机。如图5 ,相同优先级的task1 、task2 和task3 轮流占有处理机时,高于该组优先级的task4 抢占处理机,等task4执行结束,该组任务再次共享处理机。
图5 基于优先级的抢占式调度与轮转调度相结合调度
为了任务控制的灵活性,Wind 内核还提供了动态优先级机制,任务的优先级在运行期间可动态地变化。同时,为了防止优先级反转,还具有优先级继承机制,通过使用互斥信号量可以防止高优先级的任务被迫等待一段不确定时间,直到一个低优先级任务完成。
5 结论
内核调度是一个实时系统的核心,它的好坏直接影响整个系统的好坏,通过对这种内核调度分析,可以更深入的理解实时操作系统设计的独到之处。
参考文献：
[1 ] 孔祥营. 嵌入式实时操作系统VxWorks 及其开发环境Tornado[M] . 北京:中国电力出版社,2001.
[2 ] 拉伯罗斯.μC/ OS 2 Ⅱ- 源代码公开的实时嵌入式操作系统[M] . 北京:中国电力出版社,2001.
[3 ] 郭凤仪,王其平,孙鹤旭. 开关电弧材料侵蚀研究[J ] . 辽宁工程技术大学学报,1997 ,16 (3) : 374 -379.
[4 ] 张吉军. 模糊层次分析法[J ] . 模糊系统与数学,2000 ,14 (2) :15 - 18.
[5 ] 王 琦. 实用模糊数学[M] . 北京:科学技术文献出版社,1991.