3.4　实时调度

3.4.1实现实时调度的基本条件

1．系统提供有关任务的必要信息

  (1) 就绪时间。这是该任务成为就绪状态的起始时间。周期任务：是事先预知的一串时间序列。

 (2)开始截止时间和完成截止时间。

 (3)处理时间。

   指一个任务从开始执行直至完成所需的时间。

 (4)资源要求。

 (5)优先级。 “绝对”优先级； “相对”优先级。 

2．系统处理能力强

  若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。假定系统中有m个周期性的硬实时任务，它们的处理时间可表示为Ci，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件：

限制条件简化：假定系统内有m个周期相同的硬实时任务，处理时间也相同均为c,则周期时间p应>=m xc,系统才是可调度的。

假如系统中有6个硬实时任务，周期时间都是 50 ms，而每次的处理时间为 10 ms，则不难算出系统是不可调度的。

　解决的方法是提高系统的处理能力，其途径有二：

1.仍是单处理机系统，但增强其处理能力减少对每一个任务的处理时间；

2. 采用多处理机系统。

  若系统中处理机数为N，则应将上述限制条件改为：

3．采用抢占式调度机制

  在含有硬实时任务的实时系统中，广泛采用抢占机制。但这种调度机制比较复杂。

 4．具有快速切换机制

  以保证能进行任务的快速切换。应具有两方面的能力：

  (1) 对外部中断的快速响应能力。

  (2) 快速的任务分派能力

3.4.2实时调度算法的分类

1．非抢占式调度算法

  1) 非抢占式轮转调度算法

   常用于工业生产的群控系统中，由一台计算机控制若干个相同的(或类似的)对象，为每一个被控对象建立一个实时任务，并将它们排成一个轮转队列。

   每次都选择队列第一个任务运行，该任务完成后便把它挂在轮转队列的末尾。与RR算法类似。

   这种调度算法可获得数秒至数十秒的响应时间，可用于要求不太严格的实时控制系统中。

2) 非抢占式优先调度算法

　　如果在实时系统中存在着要求较为严格(响应时间为数百毫秒)的任务，则可采用非抢占式优先调度算法为这些任务赋予较高的优先级。当这些实时任务到达时，把它们安排在就绪队列的队首，等待当前任务自我终止或运行完成后才能被调度执行。这种调度算法有可能获得仅为数秒至数百毫秒级的响应时间，因而可用于有一定要求的实时控制系统中。

2．抢占式调度算法

　　用于要求较严格的(响应时间为数十毫秒以下)的实时系统中。根据抢占发生时间不同可分以下两种调度算法。

1) 基于时钟中断的抢占式优先权调度算法

　　若实时任务优先级高于当前任务，并不立即抢占当前任务的处理机而是等到时钟中断到来时。这种调度算法能获得较好的响应效果。可用于大多数的实时系统中。

2) 立即抢占的优先权调度算法

　　若实时任务优先级高于当前任务，只要当前任务未处于临界区，便立即剥夺当前任务的执行。这种算法能获得非常快的响应，可把调度延迟降低到几毫秒至100微秒，甚至更低。

3.4.3常用的几种实时调度算法

1．最早截止时间优先(EDF)算法

  截止时间愈早，其优先级愈高。

  在实时任务就绪队列中各任务按截止时间的早晚排序；当然，截止时间最早的任务排在最前面。调度总是选择就绪队列中的第一个任务。

  既可用于抢占式调度，也可用于非抢占式调度。

1) EDF用于非周期实时任务非抢占式调度方式

　例：四个非周期任务1,2,3,4先后到达，开始截止时间排序为1,3,4,2。则任务执行顺序如下：

2) EDF用于周期实时任务抢占式调度方式

　　例:有两个周期性任务，任务A的周期时间为20 ms，每个周期的处理时间为10 ms；任务B的周期时间为50 ms，每个周期的处理时间为25 ms。图中的第一行示出了两个任务的到达时间、最后期限和执行时间图。其中任务A的到达时间为0、20、40、…；任务A的最后期限为20、40、60、…；任务B的到达时间为0、50、100、…；任务B的最后期限为50、100、150、…(注：单位皆为ms)。

若采用一般优先级调度算法：不能满足实时任务调度

采用EDF算法：可以满足实时任务调度

2．最低松弛度优先(LLF)算法

原理：根据任务紧急(或松弛)的程度，来确定任务的优先级。越紧急优先级愈高。

   例如，任务A在200 ms时必须完成，本身所需运行时间为100 ms，则该任务的紧急程度(松弛程度)为100 ms。任务B在400 ms时必须完成，本身需运行 150 ms，则其松弛程度为 250 ms。

    算法实现:实时任务的就绪队列按松弛度排序，松弛度最小的队首，调度程序总是选择队首任务执行。

   松弛度=完成截止时间-仍需运行时间-当前时间

例：周期性实时任务A,B如下表

3.4.5  优先级倒置

1.优先级倒置的形成

   优先级倒置：优先级高的进程被优先级低的进程延迟或阻塞。

    形成：大多因资源的访问

2.解决方法

   1)进入临界区后处理机不予许被抢占

   2)动态优先级继承：发生倒置时，让低优先级的进程继承高优先级进程的优先级