转自21ic网
优先级调度作为实时嵌入式系统设计方法，近年来日益受到广泛关注。
本文假定硬实时系统(hard-real-time system)具备如下特性：包含的进程具备严格时序约束且数目相对较多；这些进程具备不同的时序特性和相关性；处理器利用率并不很低，即没有太多的CPU空闲容量。
进程和调度
为了对复杂硬实时系统的性能进行预估，必须预先了解各进程的主要特性，否则不可能确保得到满足任何时序约束的优先级条件。
1.周期性进程
周期性进程由反复执行的运算组成，每个固定的时间周期执行一次运算。周期性进程的一个典型应用就是读取传感器数据并更新内部变量和输出的当前状态。
周期性进程p的四要素是rp, cp, dp, prdp：prdp表示周期；cp表示进程p在最坏情形下的运算时间；dp表示时限，即在每个周期中，从周期起始到进程p执行完毕之间的时间间隔；rp表示释放时间，即在每个周期中，从周期起始到进程p最早开始执行之间的时间间隔。此外，假定rp, cp, dp, prdp连同其他任何表示时间的参数均为整数。
周期性进程p可包含无数个周期性进程执行p0, p1, p2,...，每个周期执行一次进程。第i个进程执行对应于第i个周期的进程pi，而pi的释放时间可表示为rpi = rp prdp × (i-1)；pi的时限可表示为dpi= dp prdp × (i-1)。
2.异步进程
异步进程由响应内部或外部事件的运算组成，异步进程的典型应用是响应操作人员的请求。尽管无法预知执行异步进程a的精确请求时间，但通常能够预先得到两个连续请求间的最短时间mina。异步进程a可由三要素ca, da, mina描述：ca 表示进程a在最坏情形下的运算时间；da 表示时限，即从向进程a发出请求到进程a完成执行之间的时间间隔。异步进程a可具备无数个异步进程执行a0, a1, a2, ...,，每个进程执行对应于一个异步请求。对于对应于第i个请求的第i个异步进程执行ai，假如ai的请求时间为rai，则ai的时限为dai = rai da。
3.调度
下面引入进程执行单元和处理器时间单元的概念。假如周期性进程p或异步进程a的运算时间为cp或ca，那么假定进程执行pi或ai由cp或ca进程执行单元组成，而且每个处理器都和起始于0的进程时间轴关联并分成连续的处理器时间单元。
调度能在一个或多个处理器时间轴上，将无数个进程执行单元映射到无数个处理器时间单元上。在0和进程执行中由第一个执行单元所映射的处理器时间单元之间，所存在的处理器时间单元数量被称为进程执行起始时间；0到进程执行中由最后一个执行单元所映射的处理器时间单元之间，所存在的处理器时间单元数称为进程执行完成时间。假如调度中，每个进程执行的起始时间大于或等于进程执行的释放时间或请求时间，并且进程的完成时间小于或等于进程的执行时限，那么该调度是有效的。
4.进程分段
每个进程p均可由有限的分段序列p[0]、p[1]、...p[n[p]]组成，其中p[0]表示进程p的第一个分段，p[n[p]]则表示进程p的最后一个分段。给定进程p的释放时间rp、时限dp和进程p中每个分段p[i]的运算时间，能够简单地计算出每个分段的释放时间和时限。
5.优先和排斥关系
进程分段有序对之间能够存在各类关系，如优先关系(precedence relation)和排斥关系(exclusion relation)。
假如只有当进程分段i执行完成，进程分段j才能开始执行，则称进程分段i优先于进程分段j。当某些进程分段需要由其他进程分段产生的信息时，这些进程分段之间就可能存在优先关系。
假如从进程分段i开始执行运算到结束运算之间，不能执行任何进程分段j的运算，则称进程分段i排斥进程分段j。当某些进程分段必须防止其他进程分段同时访问共享资源(如数据和I/O设备)时，这些进程分段之间就可能存在排斥关系。
优先级调度和运行前调度概述
下面，本文将简要介绍优先级调度和运行前调度方法。
1.优先级调度方法
大多数优先级调度方法均遵循两个基本假定：a)调度在进程运行时执行；b)进程分配有固定的优先级，当两个进程竞争同一处理器时，具备较高优先级的进程将获得处理器资源。
速率单调调度(Rate Monotonic Scheduling)是最具代表性的优先级调度方法。该方法假定任何的进程都是周期性的，并且进程的主要特性在运行之前都已确定，即预先了解进程在最坏情形下的执行时间和周期。
设计工程师可根据进程的周期设定固定的优先级：周期越短，优先级越高。任何时候，只要任何进程中具备最高优先级的进程就绪，即可分配到处理器。而且在运行前，还可根据已知的进程特性进行可调度性分析。假如满足特定的方程，即可在运行中执行实际的调度，并假定运行中能够满足任何的时限需要。
优先级最高限度协议(Priority Ceiling Protocol)的假定和速率单调调度相同，只是进程可能具备由旗语(semaphores)保护的临界区，并提供专门的协议来处理这些临界区。每个旗语均分配一个优先级最高限度值，优先级最高限度和使用该旗语的最高优先级进程具备相等的优先级。具备最高优先级的进程一旦就绪，即可分配到处理器资源。任何进程p进入其临界区之前，必须首先获取监控临界区的旗语S的优先级锁定。假如进程p的优先级不高于当前除p以外，其他进程锁定的旗语中具备最高优先级的最高限度，那么进程p将被阻塞，S上的锁定将被拒绝。当进程p阻塞了更高优先级的进程，那么p将继承被p阻塞的进程的最高优先级。
当p离开临界区，则进程p将恢复其进入临界区时的优先级。假如进程p不试图进入临界区，并且其优先级(继承或分配的优先级)高于另一正在执行的进程pi的优先级，则可占先运行。
假如满足以下条件，则速率单调调度(周期越短，优先级越高)能够调度(即满足任何时限需要)采用优先级最高限度协议的n个周期性进程：其中Ci 表示执行时间，Ti 表示周期，Bi 表示最坏情形下由较低优先级进程引发的pi阻塞时间。
2.运行前调度方法
采用运行前调度，一般进程的调度是离线计算；同时，该方法还需要能够预先了解系统中进程的主要特性。
文章整理：西部数码--专业提供域名注册、虚拟主机服务
http://www.west263.com
以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!
