第四课调度和死锁( g and Deadlock) 教学目的: 在多道程序系统中,一个作业从提交到执行完成,要经历 多级调度,调度的好坏要影响系统的运行性能,因此调度是 多道系统的关键。为了改善系统资源的利用率和提高系统处 理能力,多道程序系统中采用多个进程的并发执行,但它也 可能发生死锁的危险,研究死锁的原因和产生条件,采用预 防死锁、避免死锁、检测死锁和解除死锁等多种方法防止死 锁是多道程序系统重要的研究课题
第四课 调度和死锁(Scheduling and Deadlock ) 教学目的： 在多道程序系统中，一个作业从提交到执行完成，要经历 多级调度，调度的好坏要影响系统的运行性能，因此调度是 多道系统的关键。为了改善系统资源的利用率和提高系统处 理能力，多道程序系统中采用多个进程的并发执行，但它也 可能发生死锁的危险，研究死锁的原因和产生条件，采用预 防死锁、避免死锁、检测死锁和解除死锁等多种方法防止死 锁是多道程序系统重要的研究课题
教学要求: 1熟悉处理机三级调度概念和处理机调度模型,掌握作业的 状态和作业调度的功能 掌握进程调度的方式和功能,熟悉调度方式和算法的选 择准则,掌握七种调度算法及适合范围。 2掌握死锁的定乂和产生死锁的原因,掌握死锁的四个必要 条件;熟悉预防死锁的方法,熟练掌握银行家算法及其在 死锁避免中的应用;掌握资源分配图的简化及其死锁定理, 熟悉解除死锁的方法
教学要求： 1 熟悉处理机三级调度概念和处理机调度模型，掌握作业的 状态和作业调度的功能。 掌握进程调度的方式和功能，熟悉调度方式和算法的选 择准则，掌握七种调度算法及适合范围。 2 掌握死锁的定义和产生死锁的原因，掌握死锁的四个必要 条件；熟悉预防死锁的方法，熟练掌握银行家算法及其在 死锁避免中的应用；掌握资源分配图的简化及其死锁定理， 熟悉解除死锁的方法
4.1调度( Scheduling)的类型和模型 作业经提交-外存—作业调度—内存—进程—进程调度一运行 分时系统一登陆一进程一调度一运行 4.1.1调度类型 高级( ong-term)调度一一作业调度 作业调度用于决定把外存输入井上处于作业后备队列上的哪些 作业调入内存,并为它们创建进程、分配必要的资源,然后再 将新创建的进程排在就绪队列上,准备执行。在批处理系统中, 作业是先驻留在外存的输入井上的,因此需要有作业调度。然 而在分时系统中,通过键盘输入的命令和数据直接进入内存, 无需作业调度。在实时系统中,也通常无需作业调度
4.1调度(Scheduling)的类型和模型 作业经提交--外存—作业调度—内存—进程—进程调度—运行 分时系统—登陆—进程—调度—运行 4.1.1 调度类型 1。高级(Long-term)调度――作业调度 作业调度用于决定把外存输入井上处于作业后备队列上的哪些 作业调入内存，并为它们创建进程、分配必要的资源，然后再 将新创建的进程排在就绪队列上，准备执行。在批处理系统中， 作业是先驻留在外存的输入井上的，因此需要有作业调度。然 而在分时系统中，通过键盘输入的命令和数据直接进入内存， 无需作业调度。在实时系统中，也通常无需作业调度
4.1调度( Scheduling)的类型和模型 宏观上:作业调度 微观上:进程调度 作业调度 (提交) 运行 完成 集火广 就绪 执行(等待 后备 作业调度
宏观上：作业调度 微观上：进程调度 4.1调度(Scheduling)的类型和模型
4.1调度( Scheduling)的类型和模型 1。作业的状态 作业从进入到运行结束,一般需要经历“提交”、“后备”、“运行”和 “完成”四个阶段。 提交状态 个作业被提交给机房后正在通过 SPOOLing系统进行输入或用户通过终 端向计算机中键入其作业时所处于的状态为提交状态。 后备状态 作业已经过 SPOOLing系统输入到磁盘输入井,等待调入内存运行,此时 作业处于后备状态。为了管理和调度作业,为每个作业设置一个作业控制 块(JCB)。作业控制块记录了作业类型和资源要求等有关信息。作业控 制块按作业类型组成一个或多个后备作业队列。 运行状态 个在后备作业队列的作业被作业调度程序选中后,分配必要的资源,建立一组 相应的进程后,调入内存,该作业就进入运行状态。进程各状态(进程运行态 内存进程就绪态、内存阻塞态、外存进程就绪态、外存进程阻塞态等)都对应作 业运行状态 完成状态 当进程正常运行结束或因发生错误而终止时,作业进入完成状态。终止作业程序 将负责善后处理
1。作业的状态 作业从进入到运行结束，一般需要经历“提交” 、 “后备” 、 “运行”和 “完成”四个阶段。 提交状态 一个作业被提交给机房后正在通过SPOOLing系统进行输入或用户通过终 端向计算机中键入其作业时所处于的状态为提交状态。 后备状态 作业已经过SPOOLing系统输入到磁盘输入井，等待调入内存运行，此时 作业处于后备状态。为了管理和调度作业，为每个作业设置一个作业控制 块（JCB）。作业控制块记录了作业类型和资源要求等有关信息。作业控 制块按作业类型组成一个或多个后备作业队列。 运行状态 一个在后备作业队列的作业被作业调度程序选中后，分配必要的资源，建立一组 相应的进程后，调入内存，该作业就进入运行状态。进程各状态（进程运行态、 内存进程就绪态、内存阻塞态、外存进程就绪态、外存进程阻塞态等）都对应作 业运行状态。 完成状态 当进程正常运行结束或因发生错误而终止时，作业进入完成状态。终止作业程序 将负责善后处理。 4.1调度(Scheduling)的类型和模型
4.1调度( Scheduling)的类型和模型 作业调度的功能: 作业调度的主要任务是完成作业从后备状态到执行状态和 从执行状态到完成状态的转变。 作业调度功能: 1.记录已进入系统的各作业的情况(JCB, Job Control Block) 2.按一定的调度算法,从后备作业中选择一个或几个作业 进入系统内存;(接纳多少个作业一多道程序并发度?接 纳那些个作业? 3.为被选中的作业创建进程,并且为其申请系统资源 4.作业加束后作善后处理工作
作业调度的功能： 作业调度的主要任务是完成作业从后备状态到执行状态和 从执行状态到完成状态的转变。 作业调度功能： 1.记录已进入系统的各作业的情况（JCB，Job Control Block）； 2.按一定的调度算法，从后备作业中选择一个或几个作业 进入系统内存；（接纳多少个作业—多道程序并发度？接 纳那些个作业？） 3.为被选中的作业创建进程，并且为其申请系统资源； 4.作业加束后作善后处理工作。 4.1调度(Scheduling)的类型和模型
4.1调度( Scheduling)的类型和模型 作业控制块(CB, 匚作业名 Job Control Block 估计运行时间 最迟完成时间 每个作业进入系统时国资源要求要求的内存量 由系统为其建立 要求外设的类型及台数 个作业控制块JCB 要求文件量和输出量 Job Control 进入系统的时间 Block),它是存放 开始运行的时间 年业控制和管理信黄漂使用情[适行的时间 息的数据结构,主 外设台号 要信息见右图 类型 控制方式 (在外存) 「作业类型 优先级 状态
作业控制块（JCB， Job Control Block） 每个作业进入系统时 由系统为其建立一 个作业控制块JCB （Job Control Block)，它是存放 作业控制和管理信 息的数据结构，主 要信息见右图 。 （在外存） 4.1调度(Scheduling)的类型和模型
4.1调度( Scheduling)的类型和模型 2。低级( Short-term)调度一一进程调度 进程调度决定就绪队列中哪个进程将获得处理机,然后由 分派程序执行把处理机分配给该进程的操作。进程调度是最 基本的调度,任何操作系统都有进程调度 1)非抢占式 直执行直到完毕或自阻塞 适用于大多数的批处理系统, 运行 但不适合实时系统。 2)抢占式 新建进程 时间片: 生 优先级(PCB): 就绪(等待 事件已发生 短作业(进程)(PCB、JCB
2。低级(Short-term)调度――进程调度 进程调度决定就绪队列中哪个进程将获得处理机，然后由 分派程序执行把处理机分配给该进程的操作。进程调度是最 基本的调度，任何操作系统都有进程调度。 1）非抢占式 一直执行直到完毕或自阻塞。 适用于大多数的批处理系统， 但不适合实时系统。 2）抢占式 时间片： 优先级（PCB）： 短作业（进程）（PCB、JCB）： 4.1调度(Scheduling)的类型和模型
进程调度的方式 非抢占方式 采用这种调度方式时,一旦把处理机分配给某进程后,便 让进程一直执行,直到该进程完成或发生某事件而被阻塞时, 才把处理机分配给其它进程,决不允许某进程抢占已经分配 出去的处理机。 这种调度方式的优点是实现简单、系统开销小,适用于大 多数批处理系统环境。缺点是难以满足紧急任务的要求,不 适用于实时、分时系统要求
进程调度的方式 非抢占方式 采用这种调度方式时，一旦把处理机分配给某进程后，便 让进程一直执行，直到该进程完成或发生某事件而被阻塞时， 才把处理机分配给其它进程，决不允许某进程抢占已经分配 出去的处理机。 这种调度方式的优点是实现简单、系统开销小，适用于大 多数批处理系统环境。缺点是难以满足紧急任务的要求，不 适用于实时、分时系统要求
抢占方式( Preemptive mode) 这种调度方式,允许进程调度程序根据某个原则,去仃 止某个正在执行的进程,将已分配给进程的处理机,重新 分配给另一个进程。抢占的原则有: 时间片原则。各进程按时间片运行,当一个时间片用完后 便仃止该进程的执行而重新进行调度。这个原则适用于分 时系统。 优先权原则。通常是对一些重要的和紧急的进程赋予较高 的优先权。当这种进程进入就绪队列时,例如由阻塞态转 换为就绪态,或从静止就绪态转为活动就绪态时,或新创 建进入就绪态的进程进入就绪队列时,如果其优先权比正 在执行的进程优先权高,便仃止正在执行的进程,将处理 机分配给优先权高的进程,使之执行
抢占方式（Preemptive mode） 这种调度方式，允许进程调度程序根据某个原则，去仃 止某个正在执行的进程，将已分配给进程的处理机，重新 分配给另一个进程。抢占的原则有： 时间片原则。各进程按时间片运行，当一个时间片用完后， 便仃止该进程的执行而重新进行调度。这个原则适用于分 时系统。 优先权原则。通常是对一些重要的和紧急的进程赋予较高 的优先权。当这种进程进入就绪队列时，例如由阻塞态转 换为就绪态，或从静止就绪态转为活动就绪态时，或新创 建进入就绪态的进程进入就绪队列时，如果其优先权比正 在执行的进程优先权高，便仃止正在执行的进程，将处理 机分配给优先权高的进程，使之执行