第四课调度和死锁 (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 < G CPU scheduler Arriving n queue o囗ooo回匚 Main Memory Memor Disk Admission scheduler scheduler Three level scheduling
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系统等）， 一般采用具有进程调度和中级调度的调度模型。在该模型中 比第一种模型增加了中级调度，则相对于上模型也增加了外 存进程就绪队列和外存进程阻塞队列。中级调度时或从内存 就绪队列调到外存的就绪队列，或从内存阻塞队列调到外存 阻塞队列，或从外存进程就绪队列调到内存就绪队列