第四课调度和死锁 (Scheduling and Deadlock) 教学目的: 在多道程序系统中,一个作业从提交到执行完成, 要经历多级调度,调度的好坏要影响系统的运行性 能,因此调度是多道系统的关键。为了改善系统资 源的利用率和提高系统处理能力,多道程序系统中 采用多个进程的并发执行,但它也可能发生死锁的 危险,研究死锁的原因和产生条件,采用预防死锁、 避免死锁、检测死锁和解除死锁等多种方法防止死 锁是多道程序系统重要的研究课题
第四课 调度和死锁 (Scheduling and Deadlock ) 教学目的： 在多道程序系统中，一个作业从提交到执行完成， 要经历多级调度，调度的好坏要影响系统的运行性 能，因此调度是多道系统的关键。为了改善系统资 源的利用率和提高系统处理能力，多道程序系统中 采用多个进程的并发执行，但它也可能发生死锁的 危险，研究死锁的原因和产生条件，采用预防死锁、 避免死锁、检测死锁和解除死锁等多种方法防止死 锁是多道程序系统重要的研究课题
教学要求: 熟悉处理机三级调度概念和处理机调度模型,掌 握作业的状态和作业调度的功能。 掌握进程调度的方式和功能,熟悉调度方式和 算法的选择准则,掌握七种调度算法及适合范围。 掌握死锁的定义和产生死锁的原因,掌握死锁的 四个必要条件;熟悉预防死锁的方法,熟练掌握 银行家算法及其在死锁避免中的应用;掌握资源 分配图的简化及其死锁定理,熟悉解除死锁的方 法
教学要求： 熟悉处理机三级调度概念和处理机调度模型，掌 握作业的状态和作业调度的功能。 掌握进程调度的方式和功能，熟悉调度方式和 算法的选择准则，掌握七种调度算法及适合范围。 掌握死锁的定义和产生死锁的原因，掌握死锁的 四个必要条件；熟悉预防死锁的方法，熟练掌握 银行家算法及其在死锁避免中的应用；掌握资源 分配图的简化及其死锁定理，熟悉解除死锁的方 法
(一)调度( Scheduling (1)处理机三级调度 1。高级(Long-term)调度一一作业调度 作业调度用于决定把外存输入井上处于作业后备队列上的哪 些作业调入内存,并为它们创建进程、分配必要的资源,然 后再将新创建的进程排在就绪队列上,准备执行。在批处理 系统中,作业是先驻留在外存的输入井上的,因此需要有作 业调度。然而在分时系统中,通过键盘输入的命令和数据直 接进入内存,无需作业调度。 2。低级( Short-term)调度一一进程调度 进程调度决定就绪队列中哪个进程将获得处理机,然后由分 派程序执行把处理机分配给该进程的操作。进程调度是最基 本的调度,任何操作系统都有进程调度
（一）调度(Scheduling) （1）处理机三级调度 1。高级(Long-term)调度――作业调度 作业调度用于决定把外存输入井上处于作业后备队列上的哪 些作业调入内存，并为它们创建进程、分配必要的资源，然 后再将新创建的进程排在就绪队列上，准备执行。在批处理 系统中，作业是先驻留在外存的输入井上的，因此需要有作 业调度。然而在分时系统中，通过键盘输入的命令和数据直 接进入内存，无需作业调度。 2。低级(Short-term)调度――进程调度 进程调度决定就绪队列中哪个进程将获得处理机，然后由分 派程序执行把处理机分配给该进程的操作。进程调度是最基 本的调度，任何操作系统都有进程调度
处理机三级调度-1 3。中级( Medium-term)调度—对换 引入中级调度的目的是为了提高主存利用率和系统 吞吐量。由于在进程并发执行过程中,为了充分发 挥内存的效能,需将那些暂时不能运行的进程从内 存调到外存盘交换区去等待,而将那些在盘交换区 的等待事件已经发生急需调度运行的进程从盘交换 区调入内存。在UNIX系统中中级调度就是存储管理 中的对换,采用虚拟存储技术的分时系统往往设立 中级调度
处理机三级调度-1 3。中级(Medium-term)调度——对换 引入中级调度的目的是为了提高主存利用率和系统 吞吐量。由于在进程并发执行过程中，为了充分发 挥内存的效能，需将那些暂时不能运行的进程从内 存调到外存盘交换区去等待，而将那些在盘交换区 的等待事件已经发生急需调度运行的进程从盘交换 区调入内存。在UNIX系统中中级调度就是存储管理 中的对换，采用虚拟存储技术的分时系统往往设立 中级调度
图:处理机三级调度 作业调度 作业运行状态 外存 主存 终止作业 作业作业进程调度人运行 交一后备 态 态状态 作业完 成状态 就绪 阻塞 中级调度 外存(盘)交换区 就绪 阻塞 态 态
图：处理机三级调度 外存(盘)交换区 作 业 后 备 状态 作 业 提 交 状态 作 业 完 成状态 终止作业 就 绪 态 阻 塞 态 中级调度 主存 进程调度 运 行 态 就 绪 态 阻 塞 态 作业调度 作业运行状态 外存
Scheduling in Batch Systems CPu O
Scheduling in Batch Systems Three level scheduling
(2)作业调度 1。作业的状态 作业从进入到运行结束,一般需要经历“提交”、“后备” “运行”和“完成”四个阶段。 提交状态 个作业被提交给机房后正在通过 SPOOLing系统进行输入 或用户通过终端向计算机中键入其作业时所处于的状态为提 交状态。 后备状态 作业已经过 SPOoLing系统输入到磁盘输入井,等待调入内 存运行,此时作业处于后备状态。为了管理和调度作业,为 每个作业设置一个作业控制块(JCB)。作业控制块记录了作 业类型和资源要求等有关信息。作业控制块按作业类型组成 个或多个后备作业队列
（2）作业调度 1。作业的状态 作业从进入到运行结束，一般需要经历“提交” 、 “后备” 、 “运行”和“完成”四个阶段。 提交状态 一个作业被提交给机房后正在通过SPOOLing系统进行输入 或用户通过终端向计算机中键入其作业时所处于的状态为提 交状态。 后备状态 作业已经过SPOOLing系统输入到磁盘输入井，等待调入内 存运行，此时作业处于后备状态。为了管理和调度作业，为 每个作业设置一个作业控制块（JCB）。作业控制块记录了作 业类型和资源要求等有关信息。作业控制块按作业类型组成 一个或多个后备作业队列
作业调度- 运行状态 个在后备作业队列的作业被作业调度程序选中 后,分配必要的资源,建立一组相应的进程后,调 入内存,该作业就进入运行状态。进程各状态(进 程运行态、内存进程就绪态、内存阻塞态、外存进 程就绪态、外存进程阻塞态等)都对应作业运行状 太 完成状态 当进程正常运行结束或因发生错误而终止时,作 业进入完成状态。终止作业程序将负责善后处理
作业调度-1 运行状态 一个在后备作业队列的作业被作业调度程序选中 后，分配必要的资源，建立一组相应的进程后，调 入内存，该作业就进入运行状态。进程各状态（进 程运行态、内存进程就绪态、内存阻塞态、外存进 程就绪态、外存进程阻塞态等）都对应作业运行状 态。 完成状态 当进程正常运行结束或因发生错误而终止时，作 业进入完成状态。终止作业程序将负责善后处理
作业调度-2 2。作业状态的转换 作业调度 作业调度程序按一定算法从后备作业队列中选 建立一组相应的进程,设置该进程状态为就绪态, 并将该进程插入内存就绪队列,参加CPU争夺。 终止作业 当进程正常运行结束或因发生错误终止时,调 用终止作业程序,它负责将输出文件缓冲输出到 输出井,并调用SP0 LIng系统输出进程将作业输 出文件在打印机输出。同时回收作业所使用内 外存、I/0设备等各种资源,最后调用记帐程序 结清作业费用
作业调度-2 2。作业状态的转换 作业调度 作业调度程序按一定算法从后备作业队列中选 一个满足资源要求的作业，分配它所要求的资源， 建立一组相应的进程，设置该进程状态为就绪态， 并将该进程插入内存就绪队列，参加CPU争夺。 终止作业 当进程正常运行结束或因发生错误终止时，调 用终止作业程序，它负责将输出文件缓冲输出到 输出井，并调用SPOOLing系统输出进程将作业输 出文件在打印机输出。同时回收作业所使用内、 外存、I/O设备等各种资源，最后调用记帐程序 结清作业费用
(3)处理机调度模型 1。仅有进程调度的调度队列模型 在分时系统中通常仅设置了进程调度。此时系统有一个就 绪队列,每个进程运行一个时间片,进程运行一个时间片后 如未完成,则被放在就绪队列末尾。如进程运行中因等待某 事件(例如申请I/0而等待I/0完成),则需排入阻塞队列, 系统因阻塞的原因不同可设几个阻塞队列 2。有进程调度和中级调度队列模型 在具有虚拟存储器技术的分时系统中(例如UNIX系统等), 般采用具有进程调度和中级调度的调度模型。在该模型中 比第一种模型增加了中级调度,则相对于上模型也增加了外 存进程就绪队列和外存进程阻塞队列。中级调度时或从内存 就绪队列调到外存的就绪队列,或从内存阻塞队列调到外存 阻塞队列,或从外存进程就绪队列调到内存就绪队列
（3）处理机调度模型 1。仅有进程调度的调度队列模型 在分时系统中通常仅设置了进程调度。此时系统有一个就 绪队列，每个进程运行一个时间片，进程运行一个时间片后 如未完成，则被放在就绪队列末尾。如进程运行中因等待某 事件（例如申请I/O而等待I/O完成），则需排入阻塞队列， 系统因阻塞的原因不同可设几个阻塞队列。 2。有进程调度和中级调度队列模型 在具有虚拟存储器技术的分时系统中（例如UNIX系统等）， 一般采用具有进程调度和中级调度的调度模型。在该模型中 比第一种模型增加了中级调度，则相对于上模型也增加了外 存进程就绪队列和外存进程阻塞队列。中级调度时或从内存 就绪队列调到外存的就绪队列，或从内存阻塞队列调到外存 阻塞队列，或从外存进程就绪队列调到内存就绪队列