实时调度是为了完成实时处理任务而分配计算机处理器的.pptVIP

实时调度是为了完成实时处理任务而分配计算机处理器的调度方法。实时处理任务要求计算机在用户允许的时限范围内给出计算机的响应信号。 实时处理任务可分为 硬实时任务（hard real-time task） 软实时任务（soft real-time task）。 其中，前者要求计算机系统必须在用户给定的时限内完成，后者允许计算机系统在用户给定的时限左右处理完毕。 ⑴ 对实时系统的要求： 1提供必要的调度信息，如就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级； 2调度方式，广泛采用抢占调度方式，特别是在实时要求严格的实时系统； 3具有快速响应外部中断的能力； 4 很快的进程和线程切换速度。 ⑵ 对几种调度算法的评述： 1 时间片轮转调度算法：这是一种常用于分时系统的调度算法，它只能适用于一般实时信息处理系统，而不能用于实时要求严格的实时控制系统。 2 非抢占的优先级调度算法：常用于多道批处理系统的调度算法，也可用于实时要求不太严格的实时控制系统。 3 基于时钟中断抢占的优先级调度算法：用于大多数的实时系统中。 4 立即抢占的优先级调度算法：这种算法适用于实时要求比较严格的实时控制系统。 ⑶ 代表性的实时调度算法： 1 时限式调度法(deadline scheduling)：是一种以满足用户要求时限为调度原则的算法。有周期性调度和非周期性调度。时限有：处理开始时限（开始截止时间）和处理结束时限（完成截止时间）两种，在实际中可以使用任一种时限。 2 频率单调调度(rate monotonic scheduling)：是一种被广泛用于多周期性实时处理的调度算法。其基本原理是频率越长（周期越长）的任务优先级越低。 具有完成截止时间的周期性实时任务的调度 例：如果系统中有两个周期性的实时任务A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B要求每50ms执行一次，执行时间为25ms。任务A和B每次的开始截止时间分别为A1、A2、A3…和B1、B2、B3…见图。 为了保证不遗漏任何一次截止时间，应采用最早截止时间优先的剥夺策略。 二是将等待执行的就绪进程分配到哪一个处理机上执行的问题。 在单机系统中，由于只有一个处理机，在调度程序中选取了某个就绪状态的进程之后，不须再选择处理机。而在多机系统中，为了尽量做到让各处理机负荷平衡，可能会将处理机在进程之间进行多次切换。如果被切换进程正在执行其临界区部分或系统中进程数目相当多，这种频繁的上下文转换将会使系统效率大大下降。  为了解决进程对处理机的分配问题，在有的多处理机系统中采用了局部就绪对列的方法限制进程的转移。 局部就绪对列：就是把处于就绪状态的进程分成不同的组，并使每一组进程和一个处理机对应起来。这样，每个处理机只执行以其对应就绪对列中的进程。各个就绪对列中的进程不断发生横向转移。这种方法减少了调度程序的开销。但是，处理机的使用率却因此下降。例如：系统中某个局部就绪对列中因等待进程较多而使得对应的处理机十分繁忙，而另外的处理机则因就绪对列为空而处于空闲状态。 多处理机系统的调度目标是：以最高的可靠性，使用最少的处理机在最短的时间内完成最多的可以并行完成的进程。 多处理机的调度有两种评价模型： 一种是确定性模型，另一种是随机性模性。 确定性模型：进程调度执性之前，估计出这些被调度进程所须要的执行时间，以及这些进程之间的相互关系。 调度程序的目的：是根据给定的执行时间和相互关系，确定出一个最佳的执行顺序。 因此，确定性模型只用来确定给定进程的执行顺序，而随机性模性则常被用来研究动态调度技术。 * * 4.5 实时调度算法 实时调度实例 在事前能知道各实时任务的开始截止时间，且对调度时延要求 不太严格的情况下可以采用最早截止时间优先的非剥夺性调度策略 1 3 4 2 1 2 3 4 开始截止时间 执行任务 任务到达 t 系统首先调度任务1执行，在任务1执行期间，任务2、3 先后到达，由于任务3的截止时间早于任务2的，故系统在 任务1后将调度任务3执行。 1 3 4 2 A1(10) A2(30) A3(50) A4(70) A5(90) A6(110) A7(130) A8 0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 t 0 10 30 40 45 55 70 80 90 100