一种实时系统进程调度方法探究

陈 艺，徐宝磊

（四川文理学院 教务处，四川 达州635000）

0 引言

在嵌入式实时系统中，最核心的部分是进程调度，它起着至关重要的作用，保障了整个系统的实时性.进程调度效率的高低直接关系到实时系统的效率和性能，优秀的进程调度方法既可以保证关键进程得到实时运行，又不至于让普通进程盲等.［1］实时操作系统主要通过中断和任务方式来响应处理外部事件.任务的优先级反映了外部事件的重要程度，在μC／OS-Ⅱ进程调度模型中，主要基于静态优先级的调度策略，使得系统缺乏实时性和灵活性.使用可抢占方式的调度策略，可以保证高优先级的外部事件能得到及时响应，高性能实时系统需要在外部事件复杂频发的环境中，及时响应并有效处理重要的高优先级的突发事件，保证系统具有稳定的、高效的大吞吐量处理事件能力.［2］进程调度的时机与引起进程调度的原因尤为重要，它是进程调度设计的前提和基础.

多数开源的、基于优先级可抢占式多进程实时系统，通过任务控制块（TCB）和任务栈实现对任务的管理、调度和切换，多用于家电等小型系统中.在μC／OS-Ⅱ实时系统中，其本身的调度策略无法满足，由于每个优先级只容纳一个进程，所有任务的优先级各不相同，即使就绪栈队中有多个任务等待处理，也只能是优先级最高的进程才能得到执行，这样使得进程调度存在一定的局限性，当最高优先级的进程需要次优先级进程的运行结果时就需要有多个进程交替运行.［3］

1 实现原理及方法

模型所述进程调度的方法包括进程调度前系统环境的准备和进程调度的策略：

1.1 进程调度前的准备工作包括：

（1）设置进程的类型、状态；进程分为关键实时进程（sched＿RTkey）、普通实时进程（sched＿RTcom）、普通进程（sched＿common）三种类型，分别有就绪、阻塞、执行三种状态，采用就绪队列嵌套、局部分时调度的方式；［4］就绪进程按照优先级高低排列成一个队列，相同优先级进程（sched＿RTcom类型进程）按照时间片大小排列成一个子队列；

（2）建立就绪队列，该发明假定系统中共64个优先级数，其中0-7保留为系统优先级，8-31为sched＿RTkey实时进程优先级，32-39为sched＿RTcom采用时间片轮转实时进程优先级，其余为普通进程优先级（sched＿common）；［5］

（3）初始化一个空链表，建立挂起队列；

（4）为每一个临界资源建立一个阻塞队列，并且初始化为先进先出的空链表；

（5）建立时间片等待队列，根据进程被延迟的时间进行排序的有序链表，用于类型为sched＿RTcom的进程；

（6）建立包含标识进程状态的进程控制块结构；

1.2 当进程运行的环境初始化以后，按照以下步骤执行进程调度

（1）创建进程，指定进程的类型、优先级；

（2）进程进入挂起队列；

（3）当进程被激活，根据进程的类型、优先级，将其挂到相应的就绪栈队；

（4）查找就绪栈队，获取当前就绪的具备最高优先级条件的进程，如果是sched＿RTcom类型的进程，还要查找所在子队列中时间片最大的进程；［6］

（5）根据所获得的最高优先级的进程（或者时间片最大的进程）控制模块内容确定进程类型，并将其挂到相应的栈队.

2 本方法的模型构建及详细实施方案

2.1 确定进程的状态模型

系统进程状态及其转换简单描述如图1.将进程的类型分为关键实时进程（sched＿RTkey）、普通实时进程（sched＿RTcom）、普通进程（sched＿common）三种类型：

关键实时进程（sched＿RTkey）适用于运行所需时间比较短、对响应时间要求比较高的实时任务，在该策略中，各实时任务按其先来先服务的原则依次获得CPU使用权.在进程运行过程中，除了因等待某个事件主动放弃CPU优先使用权或者出现更高优先级的进程而剥夺其CPU优先使用权之外，将优先满足该类型进程的CPU的使用量，直至其完成.

普通实时进程（sched＿RTcom）适用于运行时间较长且对响应时间要求较高的实时任务.采用该策略时，该栈队中的进程按时间片轮流合理使用CPU.当栈队中一个进程的时间片应用结束后，进程调度程序将停止其运行并自动将其放置于可运行栈队的末尾进行等待下一次时间片的使用.

sched＿common是面向普通非实时进程的时间片轮转类型.

图1 系统进程状态转换图

此调度策略以优先级优先调度为主、按照时间片轮转为辅助，并根据每个进程的运行状态进行一定的优化使得进程调度可以公平有效而又不损失响应时间，有效降低系统的时间复杂度.［7］

在实时系统进程调度中，主要存在下面四种进程调度时机：

（1）在进程状态转换时刻，进程终止或睡眠时；

（2）可运行栈队中增加一个新进程时；

（3）内核处理完中断后，由中断返回时；

（4）预定设置的时间片到时.

2.2 初始化方法

（1）取出8个优先级为普通实时进程（sched＿RTcom）专用，如图2所示，设立时间片，在各自优先级进程组中采用时间片轮转方式；

图2 整个系统的就绪队列

（2）在TCB控制块中增加一项counter作为其任务进程调度的权值（时间片）；

（3）在进程调度函数和初始化函数中取得当前最高优先级；

（4）在时钟中断处理函数中，将当前运行任务的counter减1（如果该任务属于实时时间片轮转进程专用的任务）.

2.3 进程调度的步骤

进程创建后，在栈队中显示为处于挂起状态，该进程的类型、优先级也就随之确定，进程进入挂起栈队.［8］如果进程被激活，则进入就绪状态，如图3所示，进程依据其优先级挂入就绪栈队的相应位置.

判断当前就绪栈队中优先级最高的进程，如果不属于sched＿RTcom类型，则直接将其取出，并与当前运行的进程进行优先级对比，若高于当前进程的优先级，则执行运行环境切换，直接运行；否则转入第3步；

如果属于sched＿RTcom进程中的8个进程级别之一，则顺序完成所有就绪的sched＿RTcom专用进程组，挂到相同优先级下的时间片轮转组.［9］并且比较当前进程的优先级，如果相同则按照时间片轮转调度，并且转入第4步；否则按优先级调度，转入第5步；

计算时间片counter的值，取出时间片量最大的进程运行，遇到时间片大小相同的进程，则取出优先级大的进程运行.如果在遍历中发现所有的sched＿RTcom进程组时间片都已经用完，则再将他们赋予一定的初值，并取出优先级最大的进程投入到CPU运行；

按优先级调度，高优先级进程直接抢占低优先级进程，如果属于sched＿RTcom类型进程，则按照步骤3按时间片轮转调度，否则转入步骤2；［10］

图3 系统的调度函数示意图

3 结束语

本方法主要通过增加进程的类型，在就绪队列中使用嵌套子队列，与现有进程调度方法相比有着很好的灵活性，适用于各种复杂的环境，在保证实时性的前提下，采用局部时间片轮转，兼顾公平.

［1］张晓芳，刘云生.一种支持时态数据的实时数据模型［J］.计算机科学，2006（2）：118-120.

［2］夏家莉.嵌入式实时数据库系统中无冲突并发控制协议CCCP［J］.计算机研究与发展，2004（11）：1936-1940.

［3］Raghu Ramakrishnan，Johannes Gehrke.数据库管理系统原理与设计［M］.北京：清华大学出版社，2007：389-420.

［4］谢西庭.嵌入式主动实时数据库ARTs-EDB事务处理的设计［D］.武汉：华中科技大学硕士学位论文，2004：28-45.

［5］Kam-Yiu Lam.Evaluationofconcurrencycontrolstrategiesformixedsoftreal-timedatabasesystems［C］.UMBC，Maryland：Information Systems，2005.

［6］张 涛.嵌入式实时数据库关键技术研究与实现［D］.成都：电子科技大学硕士学位论文，2005：67-80.

［7］明日科技.SQL Server 2005开发技术大全［M］.北京：人民邮电出版社，2007：239-276.

［8］刘云生.实时数据库系统［J］.计算机科学，1994（3）：42-46.

［9］刘云生，夏家莉.基于功能替代的实时事务调度［J］.计算机学报，2003（2）：250-256.

［10］周东球，杜殿林，左 信.先进控制软件系统实时数据库的设计［J］.微计算机信息，2003（10）：23-24.