4处理机调度(4.6).ppt

4.6 实时系统调度方法 4.6.1 实时系统的特点 4.6.2 实时调度算法的分类 4.3.3 时限调度算法与频率单调调度算法 4.6.1 实时系统的特点 实时系统与其它系统的最大区别在于，其处理和控制的正确性不仅仅取决于计算的逻辑结果，而且取决于计算机和处理结果产生的时间 实时系统包括监控系统、自动驾驶系统、安全控制系统等，这些系统中，迟到的响应即使正确，也和没有响应一样糟糕。 根据对处理外部事件的时限(deadlines)要求，实时系统可分为 硬实时任务系统hard real time task 要求系统必须满足任务的时限要求 软实时任务系统sofe real time task 允许系统对任务的时限要求有一定的延迟 根据所处理外部事件可分为周期性的与非周期性的 对于非周期性任务来说，必定存在一个完成或开始进行处理的时限 周期性任务只要求在周期T内完成或开始进行处理 Ready time: 就绪时间 Starting deadline: 开始截止期 Processing time: 处理时间 Completion deadline: 完成截止期 Occurring frequency: 发生频率 随着移动通信和网络计算技术的发展，实时系统越来越重要 ，具有以下特点 有限等待时间 有限响应时间 用户控制 可靠性高 系统纠错处理能力强 实时系统的特点要求实时操作系统具有以下能力： 很快的进程或线程切换速度 根据算法选择某一个进程执行后，最重要的就是进程切换，切换速度快节省执行时间 快速的外部中断响应能力 只有对外部中断信号反应迅速，系统才能对外部事件作出迅速反应 基于优先级的随时抢先式调度策略 实时系统的目的是保证反应快 对用户的高优先级作业或进程要保证及时响应 4.6.2 实时调度算法的分类 分为四类 1.静态表格驱动类 对可能的调度条件和参数进行静态分析，并将分析结果作为实际调度结果 多用于调度处理周期性任务，参数为周期、执行时间、周期性结束时间、任务优先级等 典型：最早时限优先法－ 优先调度时限最早的任务 2. 静态优先级驱动抢先式调度算法类 也是静态分析，但是分析结果不直接产生调度结果，而只用来指定任务的优先级 频率单调调度算法 3.动态计划调度算法类 在调度任务执行之前排出调度计划，并分析调度结果是否使得任务所要求的处理时限得到满足，如果可以，则按照调度计划执行，否则修改计划 4.尽力而为调度算法类 不进行可能性分析，只对到达的事件和相关任务指定相应的优先级，并进行调度 4.3.3 时限调度算法与频率 单调调度算法 1.时限调度算法 以满足用户要求的时限为调度原则的算法 用户要求的时限有两种： 1.处理开始时限：处理机必须开始对任务进行处理的时限 2.处理结束时限：任务必须完成的时限 时限调度算法所需要的相关输入信息包括： 1.任务就绪时间或事件到达时间 2.开始时限 3.完成时限 4.处理时间 5.资源需求 6.优先级：可由分析计算后获得，也可根据时限要求由用户指定 时限调度算法的基本思想是：按照用户的时限要求顺序设置优先级，优先级高者占据处理机，也就是说，时限要求最近的任务优先占有处理机 时限调度是抢先式的，必须把新到达任务的时限要求和当前正在执行任务的时限要求进行比较，如果新到达任务的时限要求更近，则应执行新到达的任务 举例 既可以用于周期性任务调度，也可以用于非周期性任务调度 2.频率单调调度算法 基本原理是频率越低（周期越长）的任务优先级越低，广泛用于多周期性实时处理的调度算法 使用该算法的条件是（C执行时间T周期） 多处理器调度算法：进程（线程）调度 1.负载共享调度算法自调度(Self-Scheduling)方式 基本思想：进程并不分配给一个特定处理器，系统维护一个全局性就绪线程队列，当一个处理器空闲时，就选择一个就绪线程占有处理器运行。 自调度(self scheduling) 优点 ? 把负载均分到所有可用处理器上，保证了处理器效率的提高。 不足 ? 就绪线程队列将成为性能的瓶颈。 ? 被抢占的线程很难在同一个处理器上恢复运行，会带来性能下降。 2.群（成组）调度算法基本思想：把一组相互合作的进程或隶属于同一个进程的一组线程分配到一组处理器上同时运行。 优点： ?当紧密相关的进程同时执行时，同步造成的等待将减少，进程切换也相应减少，系统性能得到提高 3.处理器专派调度算法 基本思想：给一个进程指派一组处理器，一旦一个进程被调度，它的每个线程被分配一个处理器并一直占有处理器运行直到整个进程运行结束。 采用这一算法，处理器将不适用多道程序设计，即该进程的一个线程