计算机操作系统课件第十讲.pptVIP

内蒙古工业大学 * 教学目的 掌握实时系统的特点 掌握实时调度算法的分类 第九讲 实时系统调度算法 掌握时限调度算法与频率单调调度算法 教学内容 4.6 实时系统调度算法 第九讲 实时系统调度算法 第九讲 实时系统调度算法 实时系统的特点 实时系统不仅要求处理和控制的正确性，还要求计算和处理结果的产生时间。 实时任务的分类 硬实时任务（Hard real time task） 要求系统必须完全满足任务的时限要求。 第九讲 实时系统调度算法 软实时任务（soft real time task） 允许系统对任务的时限要求有一定的延迟，其时限要求只是一个相对条件。 周期性任务 要求在周期T内完成或开始处理。 非周期性任务 要求在规定的时间内完成或开始处理。 第九讲 实时系统调度算法 实时系统特点 有限等待时间（决定性） 要求所有进程在处理时间时，都必须在有限时间内开始处理。 有限响应时间 要求从系统响应外部事件开始，必须在有限时间内处理完毕。 第九讲 实时系统调度算法 用户控制 实时系统中，用户可以控制进程的优先级并选择相应的调度算法，实现对进程执行顺序的控制。 可靠性高 实时系统对外部事件的处理和控制，不允许出现错误。 系统出错处理能力强 要求系统在出错时，既能处理发生的错误又不影响当前正在执行的用户应用。 第九讲 实时系统调度算法 实时系统具有的功能 快速的进程/线程切换速度 它是实时调度的核心。实时调度算法的设计原则是满足所有硬实时任务的处理时限和尽可能多的满足软实时任务的处理时限。 快速的外部中断处理能力 快速的外部中断反应能力，是前提条件。 第九讲 实时系统调度算法 基于优先级的随时抢先调度策略 优先级+时间片轮转调度策略 基于优先级调度策略的分析 每次抢占发生必须得等到时间片结束或执行进程主动放弃处理机，本方法不适用实时系统。 第九讲 实时系统调度算法 基于优先级的非抢占式调度策略 高优先级进程只能等到低优先级进程结束或主动放弃处理机，才能得到调度。本方法不适用实时系统。 基于优先级的固定点抢占式调度策略 高优先级进程只能等到固定的时间点（小于时间片长度，满足所有硬实时任务的需要）或执行进程主动放弃处理机，才能得到调度。本方法适用实时系统。 基于优先级的随时抢占式调度策略 第九讲 实时系统调度算法 实时调度算法分类 静态表格驱动类 参数准备 周期、执行时间、周期性结束时限、优先级等 基本原理 对可能的调度条件和参数进行静态分析，并将分析结果作为实际调度结果。 第九讲 实时系统调度算法 典型算法 最早时限优先法 静态优先级驱动抢占式调度算法类 典型算法 频率单调调度算法 基本原理 静态分析的结果，用来指定任务的优先级 第九讲 实时系统调度算法 动态计划调度算法类 基本原理 在调度任务执行之前排出调度计划，并分析计划的调度结果是否使得任务所要求的处理时限得到满足。如能满足，按计划执行，否则修改计划。 第九讲 实时系统调度算法 尽力而为调度算法类 基本原理 只对到达的时间和相关任务指定相应的优先级，并进行调度。 第九讲 实时系统调度算法 时限调度算法 时限分类 处理开始时限（starting deadline） 指任务最晚开始的时刻。 处理结束时限（ending deadline） 指任务最晚结束的时刻。 第九讲 实时系统调度算法 参数准备 任务就绪时间/事件到达时间 指进程进入就绪状态，可以被调度执行的时间。对周期性任务是可预知的，对于非周期任务，需要时间驱动。 开始时限 指处理机必须开始对任务进行处理的最晚时限。 第九讲 实时系统调度算法 完成时限 指任务必须完成的最后时间 处理时间 任务如果还需要其他资源，则调度算法较复杂 资源需求 完成相关任务所需占用处理机的时间 优先级可以计算得到，也可由用户指定 优先级 第九讲 实时系统调度算法 算法基本思想 按照用户的时限要求顺序设置优先级，优先级高者占据处理机，即时限要求最近的任务优先占用处理机。 典型特点——抢占式 把新到达任务的时限和当前正在执行任务的时限要求进行比较，系统挑选时限最近的执行，即优先权最大的 第九讲 实时系统调度算法 算法实例 实时系统从两个不同的数据源DA和DB周期性的收集数据并进行处理，其中DA的时限要求以30ms为周期，DB以75ms为周期。设DA所需的处理时限为15ms，设DB所需的处理时限为38ms，与DA和DB有关进程的事件如图所示。 第九讲 实时系统调度算法 第九讲 实时系统调度算法 调度结果 第九讲 实时系统调度算法 频率单调调度算法 基本原理 频率越低（周期越长）的任务的优先级越低。 算法的必要条件 C=T C为任务执行时间，T为周期 第九讲 实时系统调度算法 算法