嵌入式系统中操作系统调度算法讲解探讨

李秀红+古丽拉·阿东别克

摘要：嵌入式软件系统的核心就是嵌入式操作系统，学生在完成嵌入式系统设计过程中，操作系统的选择和设计至关重要，前提条件是学生对操作系统中进程的调度算法足够了解，进而进行调度算法的设计以适应嵌入式系统设计的专用性。该文旨在给出操作系统的普通调度算法和嵌入式实时操作系统的不同调度算法，对算法进行讲解和区分，以便于学生学习和掌握。

关键词：嵌入式系统；实时系统；进程调度；操作系统；优先级

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2018）01-0013-02

嵌入式系统包括硬件系统和软件系统。嵌入式软件系统是由嵌入式操作系统和嵌入式应用程序组成。嵌入式操作系统通常是实时操作系统，尽管不是所有的嵌入式系统都是实时系统，但是实时性是多数嵌入式系统最重要的特性之一。嵌入式系统当中一个很重要的思想就是嵌入式系统当中如果面对的是复杂多任务系统 ，如工业智能控制系统，银行ATM终端等，这些情况下通常需要安装嵌入式操作系统，且多数情况下是嵌入式实时操作系统。教学的难点是让学生理解什么样的系统需要安装嵌入式操作系统，不同的应用需要的操作系统差别很大，核心的思想不同的应用会需要特定类型的操作系统，而不同的操作系统会有不同的进程调度算法。实时操作系统中最重要的就是进程调度算法是实时性的，能够保证较好的响应时间。普通操作系统和实时操作系统的区别就是系统进程调度算法的差别。在课程的讲解上，为了增加学生对实时性的认知，需要讲解操作系统的调度算法。通过进程调度算法的讲解让学生在完成嵌入式系统设计的过程中，能够根据实际应用是否实时性进行有效地进行操作系统进程调度算法的选取，进而决定操作系统的类型。

1 实时系统介绍

所谓实时系统就是系统的输出在时间上至关重要的系统。这样的系统不但要求系统输出结果的正确性还要求输出结果的时间，在给定输入之后，一定要在有效的时限内产生系统输出。衡量实时系统很重要的指标是就是响应时间，是指计算机从识别一个外部时间到做出响应的时间。依据输出结果的时间的长短，实时系统分为强实时系统（响应时间在毫秒或者微秒），弱实时系统（响应时间为数十秒说着更长），一般实时系统（前两者的折中）。在航空航天，工业控制系统中多要求强实时系统，民用多媒体电子产品对实时性要求一般不高，多数是一般实时系统，比如智能手机。

2 普通系统的调度算法

普通系统和实时系统采用不同的调度算法。不同的算法决定了统实时性能的。调度算法主要是针对系统当中的进程执行的先后顺序来进行调度的算法。对于一个普通系统，进程的调度算法常用的主要有：先来先服务，短进程优先，最高响应比优先。三种这三种算法各有优劣，但是这三种算法都不利于系统当中的紧迫性高的实时任务。对于普通系统，这三种调度算法有较好的性能。

2.1 先来先服务调度算法

这是一种最简单的进程调度算法，在这种进程调度中，进程严格依照进入内存的时间先后顺序排成一个队列，处理器每次从就绪队列中选择队首的进程来占据CPU执行，这个队首的进程一定是系统当前状态下最先进入内存的进程。

FCFS调度算法属于不可抢占算法，算法简单。从表面上看，它对所有进程都是公平的，但若一個长进程先到达系统，就会使后面许多短进程等待很长时间，对长进程比较有利，但会造成短作业等待时间和占据CPU运行的时间比值过大，故而降低系统的吞吐量（系统单位时间内完成的任务总数），导致很多短作业队系统不满意。所以可以将这种算法和其他算法结合起来使用。

2.2 短进程优先调度算法

短进程优先调度算法是指对短进程优先调度的算法这是从就绪队列中选择一个估计占据CPU执行时间最短的进程，将处理机分配给它，使之立即执行。短进程算法对长进程不利，短作业多的情况下，长进程的等待使用CPU的时间会增加。严重的将导致长进程长期不被调度而出现“饿死”，即CPU依照这个算法总是调度短作业运行，长作业始终处于等待状态而得不到CPU的使用权。该算法会提高系统的吞吐量，因为系统总是调度耗时少的短进程执行，故而吞吐量一定上升，但是整体而言，这个算法对长进程很不公平。

2.3 最高响应比优先调度算法

先来先服务算法会导致系统吞吐量下降，不满意的短进程数量增加，短进程优先会提高吞吐量但是导致长作业饿死，基于上述两种算法的综合，给出了最高响应比优先调度算法。最高响应比优先是响应比高的进程优先调度运行。

该算法需要系统记录每个进程的等待时间和要求占据CPU的执行时间。进程调度时，先计算后备进程队列中每个进程的响应比，从中选出响应比最高的进程投入运行。缺点是每一次执行该调度算法时都要重新计算系统当中所有就绪队列的每一个进程的响应比，这个计算当系统任务量大时候比较消耗系统时间。

通过响应比计算公式我们可以得到以下结论：

· 进程的等待时间相同时，要求CPU执行时间短的响应比高，从而有利于短进程。

· 进程要求CPU执行时间相同，等待时间长的响应比高，此时，该算法是先来先服务。

· 长进程的响应比可以随其等待时间增长加大，从而得到CPU的使用权。因此该算法不会出现长作业饿死现象。克服了短作业优先的缺点。

3 实时系统的调度算法

实时内核必须采用基于优先级调度的算法。任务根据重要程度或者紧迫性被赋予一定的优先级，就绪队列是严格按照优先级高低排队。同一优先级的按照先来先服务的顺序排队。CPU总是调度就绪队列首位的优先级最高的进程占据CPU执行。这种调度算法一定是支持抢占的，一旦有优先级高的进程就绪，则抢夺当前进程CPU的使用权。实时系统的调度算法主要有三种：基于优先级的抢占式的调度算法，同一优先级的时间片轮转的调度算法和单调速率算法。endprint

3.1 基于优先级的抢占式的调度算法

实时系统为每一个进程分配一个优先级，优先级高低反映了进程的重要性和紧迫性，进程按优先级别高低排队。基于优先级的抢占式的调度算法，保证了高优先级的进程在得到系统资源获得CPU使用权上比低优先级的进程有更好的优先权。实时系统都是采用的基于优先级的进程调度算法，该算法依据CPU被抢夺的时间又分为以下两种：

· 非抢占式优先级调度算法。高优先级进程一旦就绪，系统会暂停低优先级别的进程，处理高优先级的请求，将其置于当前就绪队列的首位，然后接着执行低优先级别的进程，直至其结束。之后才调度就绪队列首位的进程执行，即刚才低优先级别进程执行过程中处于就绪状态的进程。

· 抢占式调度算法。高优先级进程一旦就绪，低优先级的进程立刻被剥夺CPU的使用权。系统立刻运行高优先级进程。

3.2 同一优先级的时间片轮转调度算法

在实时系统当中，如果多个任务共享同一个优先级，则统一优先级的进程在就绪队列当中按照先来先服务的顺序排队，所有进程时间片轮转的方式获取CPU的使用权。不同优先级的排成不同的就绪列，这种调度算法，系统当中有多个依据不同优先级而建成的队列，每个队列中依据到达的时间先后顺序又排队，系统总是在高优先级队列为空的情况下调度优先级别低的队列当中的进程执行。

3.3 单调速率算法

该算法是依据进程的执行频度来确定其优先级，执行频度高的优先級高，执行频度低的则优先级低，获得CPU的使用权限低。优先级高的可以优先获得CPU的使用权。

4 结论

课堂教学过程中，嵌入式系统开发的复杂度很高，务必要让学生理解操作系统选择的重要性和嵌入式系统当中的软硬件可裁剪的意义，针对性地选择合适嵌入式开发合适的环境。操作系统是否需要，需要操作系统的哪些功能，哪些功能是通用操作系统裁剪之后可以得到的，这些讲解的过程中最终要的就是操作系统的核心功能：进程调度。不同的进程调度算法决定了系统的实时响应能力。

参考文献：

[1] 马忠梅.ARM&LINUX嵌入式系统教程[M] 北京：北京航空航天大学出版社，2014.

[2] 于玉.操作系统[M] 北京：电子工业出版社，2003.

[3] 李善平.LINUX与嵌入式系统[M] 北京：清华大学出版社，2002.

[4] 何小平.选择适合ARM的嵌入式操作系统[J].BMRfech Inc.2003.

[5] 周立功. ARM嵌入式系统基础教程[M] 北京：北京航空航天人学出版社，2005.endprint