操作系统汤子英课件第4章处理机调度及死锁.ppt

一个批处理型作业，通常需要经过： 方能获得处理机。 1. 作业的概念 一个作业是指在一次应用业务处理过程中，从输入开始到输出结束，用户要求计算机所做的有关该次业务处理的全部工作。 用户的观点：在一次业务处理过程中，从输入程序和数据到输出结果的全过程。作业步：形成中间结果文件。 系统的观点（针对作业进行资源分配）：作业由程序及数据（作业体）和作业说明书（作业控制语言） 作业由不同的顺序相连的作业步组成。 作业步是在一个作业的处理过程中，计算机所做的相对独立的工作。 1、高级调度(High Scheduling) 又称为作业调度或长程调度。 功能：用于决定把外存上处于后备队列中的那些作业调入内存。 具体操作是： 处理机调度（二） 2、低级调度(Low Level Scheduling)* 又称进程调度或短程调度 功能：用来决定就绪队列中的哪个进程应获得处理机。 进程调度即：进程3基本状态转换的调度。 处理机调度（三） 3、中级调度(Intermediate-Level Scheduling) 又称中程调度 目的：是为了提高内存利用率和系统吞吐量。 功能： －暂时不能运行的进程挂起，释放宝贵的内存资源。 －具备条件时：把外存上的就绪进程，重新调入内存，挂在就绪队列上等待进程调度。 处理机调度之间的关系 进程调度算法 1、先来先服务(FCFS)调度算法 算法：每次调度是从就绪队列中，选择最先进入的进程，为之分配处理机，使之执行，该进程一直执行到完成或发生阻塞事件为止。 三、进程调度算法 2、短进程优先调度算法 算法：是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。 缺点： 该算法对长进程不利。 该算法完全未考虑进程的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。 进程调度的功能： a.选择占有处理机(CPU)的进程； b.记录系统中所有进程的执行情况； c.进行进程上、下的转换。 进程调度算法 3、高优先权(FPF)优先调度算法 非抢占式优先权算法 在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成； 或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。 抢占式优先权调度算法 在执行期间，只要出现了另一个优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。 三、进程调度算法 4、基于时间片的轮转调度算法 算法：就绪进程按先来先服务的原则，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，将它送往就绪队列的末尾；依次执行下个进程。 优点：保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。 调度算法实施原则如下： (1) 设置多个就绪队列。 (2)各个队列优先级不同。 (3)各个队列中进程执行时间片的大小也各不相同。优先权愈高，执行时间片就愈小。 多级反馈队列算法 (Round Robin with Multiple Feedback) 多级反馈队列 算法应用实例 音视频同步的视频服务器简介： 2路视频、 1路音频 适时压缩、并通过网络传输。 2个视频进程、 1个音频进程（优先权高） 算法应用： 基于时间片轮转算法 抢占式高优先权算法 基于时间片轮转调度算法（就绪队列） 改进前 改进后 先来先服务算法 抢占式高优先权算法 4.5 调度算法应用举例 假设在单道批处理环境下有四个作业，已知它们进入系统的时间、估计运行时间： 应用先来先服务、最短作业优先和最高响应比优先作业调度算法，分别计算出作业的平均周转时间和带权的平均周转时间 4.5 调度算法应用举例 先来先服务算法计算结果 4.5 调度算法应用举例 最短作业优先算法计算结果 4.5 调度算法应用举例 最高响应比算法计算结果 实时调度的特点（实现实时调度的基本条件 ） 要求更详细的调度信息：如，就绪时间、开始或完成截止时间、处理时间、资源要求、绝对或相对优先级（硬实时或软实时）。 采用抢先式调度。 快速中断响应，在中断处理时（硬件）关中断的时间尽量短。 快速上下文切换：相应地采用较小的调度单位（如线程）。 4.4.1 与单处理机调度的区别 注重整体运行效率（而不是个别处理机的利用率） 更多样的调度算法 多处理机访问OS数据结构时的互斥（对于共享内存系