操作系统第三章 - 处理机调度与死锁

(SchedulingandDeadlock)第三章处理机调度与死锁教学目的在多道程序系统中，一个作业从提交到执行完成，要经历多级调度，调度的好坏影响系统的运行性能，因此调度是多道系统的关键。为了改善系统资源的利用率和提高系统处理能力，多道程序系统中采用多个进程的并发执行，但它也存在发生死锁的危险。研究死锁的原因和产生条件，采用预防死锁、避免死锁、检测死锁和解除死锁等多种方法防止死锁是多道程序系统重要的研究课题。教学要求：熟悉处理机三级调度概念和处理机调度模型，掌握作业的状态和作业调度的功能。掌握进程调度的方式和功能，熟悉调度方式和算法的选择准则，掌握六种调度算法及适用范围。掌握死锁的定义和产生死锁的原因，掌握死锁的四个必要条件；熟悉预防死锁的方法，熟练掌握银行家算法及其在死锁避免中的应用；掌握资源分配图的简化及其死锁定理，熟悉解除死锁的方法。第三章处理机调度与死锁3.1处理机调度的基本概念3.1.1处理机三级调度3.1.2高级调度--作业调度3.1.3处理机调度模型3.1.4进程调度3.1.5调度方式和算法的选择准则3.2作业/进程调度算法3.3实时调度3.4多处理机系统中的调度3.5产生死锁的原因和必要条件3.6预防死锁的方法和死锁避免3.7死锁的检测和解除3.1处理机调度(Scheduling)的基本概念在多道程环境下，进程数目往往多于处理机数目，致使它们争用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。进程调度要解决的问题WHAT：按什么原则分配CPU—进程调度算法WHEN：何时分配CPU—进程调度的时机HOW：如何分配CPU—CPU调度过程（进程的上下文切换）返回3.1.1处理机三级调度1.高级(Long-term)调度——作业调度作业调度用于决定把外存井上处于作业后备队列上的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后再将新创建的进程排在就绪队列上，准备执行。–在批处理系统中，作业是先驻留在外存的输入井上的，因此需要有作业调度；–在分时系统中，通过键盘输入的命令和数据直接进入内存，无需作业调度。2.低级(Short-term)调度——进程调度进程调度决定就绪队列中哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。进程调度是最基本的调度，任何操作系统都有进程调度。3.1.1处理机三级调度3.中级(Medium-term)调度——对换引入中级调度的目的是为了提高主存利用率和系统吞吐量。由于在进程并发执行过程中，为了充分发挥内存的效能，需将那些暂时不能运行的进程从内存调到外存交换区去等待，而将那些在外存交换区的、等待事件已经发生急需调度运行的进程从外存交换区调入内存。在UNIX系统中的中级调度就是存储管理中的对换，采用虚拟存储技术的分时系统往往设立中级调度。三级调度的运行频率？SPOOLing是SimultaneousPeripheralOperationOn-Line（即外部设备联机并行操作）的缩写，它是关于慢速输入/输出设备如何与计算机主机交换信息的一种技术，通常称为“假脱机技术”。又称为排队转储技术。外存交换区作业运行状态作业收容状态作业提交状态作业完成状态静止就绪态静止阻塞态内存作业运行状态执行态活动就绪态活动阻塞态外存中级调度图3-1处理机三级调度图作业调度进程调度返回3.1.2高级调度--作业调度1.作业的状态作业从进入到运行结束，一般需要经历“提交”、“后备/收容”、“运行”和“完成”四个阶段。提交状态一个作业被提交给机房后，正在通过SPOOLing系统进行输入或用户通过终端向计算机中键入其作业时所处于的状态。此时作业信息尚未全部进入系统。后备/收容状态作业已经通过SPOOLing系统输入到磁盘输入井，等待调入内存运行，此时作业处于后备状态。为了管理和调度作业，为每个作业设置一个作业控制块（JCB）。作业控制块记录了作业类型和资源要求等有关信息。作业控制块按作业类型组成一个或多个后备作业队列。3.1.2高级调度--作业调度运行状态一个在后备作业队列的作业被作业调度程序选中后，分配必要的资源，建立一组相应的进程后，调入内存，该作业就进入运行状态。进程各状态（进程执行态、活动就绪态、活动阻塞态、静止就绪态、静止阻塞态等）都对应作业运行状态。完成状态当进程正常运行结束或因发生错误而终止时，作业进入完成状态。作业调度将负责善后处理：输出结果、回收资源等。3.1.2高级调度--作业调度2.作业调度作业调度程序按一定算法从后备作业队列中选一个/多个满足资源要求的作业，分配它所要求的资源，建立一组相应的进程，设置该进程状态为就绪态，并将该进程插入内存就绪队列，参加CPU争夺。接纳多少个作业接纳哪些作业返回3.1.3处理机调度模型1.仅有进程调度的调度队列模型在分时系统中通常仅设置了进程调度。此时系统有一个就绪队列（FIFO），每个进程运行一个时间片，进程运行一个时间片后如未完成，则被放在就绪队列末尾。如进程运行中因等待某事件（例如申请I/O，等待I/O完成），则需排入阻塞队列，系统因阻塞的原因不同可设几个阻塞队列，如图所示。2.具有进程调度和中级调度队列模型在具有虚拟存储器技术的分时系统中（例如UNIX系统等），一般采用具有进程调度和中级调度的调度模型。在该模型中比第一种模型增加了中级调度，则相对于上模型也增加了静止就绪队列和静止阻塞队列。中级调度是或从活动就绪队列调到静止就绪队列，或从活动阻塞队列调到静止阻塞队列，或从静止就绪队列调到活动就绪队列。3.1.3处理机调度模型CPU分时间片完等待事件完成就绪队列阻塞队列事件发生交互用户进程调度图3-2仅有进程调度的调度队列模型图返回3.1.3处理机调度模型3.具有高级调度和低级调度的调度队列模型在多道批处理系统中，一般处理机管理设置作业和进程两级调度。它比第一个模型增加了高级调度。模型增加了在磁盘的作业后备队列，作业调度的任务是从作业后备队列中至少选一个作业为它创建进程，并分配资源，将它排入内存进程就绪队列，如图所示。4.同时具有三级调度的调度队列模型在通用系统的多模式OS中，一般采用具有三级调度的调度队列模型，由于多模式OS同时支持批处理、分时和实时处理，所以它必须具有以上模型，具有三级调度的调度队列模型是第二、三两模型的综合，如图所示。3.1.3处理机调度模型分时间片完完成CPU等待事件1就绪队列阻塞队列1事件1发生后备作业队列批量作业进程调度磁盘等待事件2等待事件N事件2发生事件N发生………阻塞队列2阻塞队列N作业调度图3-3具有高、低两级调度的调度队列模型返回3.1.3处理机调度模型分时间片完返回完成CPU交互型作业等待事件活动就绪队列静止就绪队列静止阻塞队列活动阻塞队列事件发生作业调度后备作业队列批量作业中级调度调入中级调度调出磁盘进程调度中级调度调出事件发生图3-4具有三级级调度的调度队列模型3.1.4进程调度1.进程调度的方式非抢占方式采用这种调度方式时，一旦把处理机分配给某进程后，便让进程一直执行，直到该进程完成或发生某事件而被阻塞时，才把处理机分配给其它进程，决不允许某进程抢占已经分配出去的处理机。这种调度方式的优点是实现简单、系统开销小，适用于大多数批处理系统环境。缺点是难以满足紧急任务的要求，不适用于实时、分时系统要求。在这种情况下,可能引起进程调度的因素有:执行结束(正常/异常)因提出I/O请求而暂停执行因执行某种同步或通信原语操作3.1.4进程调度抢占方式（Preemptivemode）这种调度方式，允许进程调度程序根据某个原则，去停止某个正在执行的进程，将已分配给进程的处理机，重新分配给另一个进程。抢占的原则有：–时间片原则。各进程按时间片运行，当一个时间片用完后，便停止该进程的执行而重新进行调度。这个原则适用于分时系统。–优先权原则。通常是对一些重要的和紧急的进程赋予较高的优先权。当这种进程进入就绪队列时，例如由阻塞态转换为就绪态，或从静止就绪态转为活动就绪态时，或新创建进入就绪态的进程进入就绪队列时，如果其优先权比正在执行的进程优先权高，便停止正在执行的进程，将处理机分配给优先权高的进程，使之执行。–短作业优先原则。当新到达的作业比正在执行的作业明显短时，将暂停当前长作业的执行，将处理机分配给新到的短作业，使之执行。3.1.4进程调度2.进程调度的功能记录系统中所有进程的执行情况进程管理模块在各进程的PCB表中记录系统各进程的执行情况和状态特征，并将各PCB表根据进程状态特征和资源要求排成相应的队列，并进行动态队列转换。选择占有处理机进程进程调度的主要功能是按照一定的策略（由它决定的调度算法），选择一个处于就绪态的进程，使其获得处理机执行。进行进程上下文切换进程上下文实际上是进程执行活动全过程的静态描述，一个进程的执行是在进程上下文中进行的。当正在执行的进程由于某种原因要让出处理机时，系统要做上下文切换，以使另一个进程得以执行。返回3.1.5调度方式和算法的选择准则1.面向用户的准则和评价周转时间短:它是评价批处理系统的重要性能指标。作业周转时间Ti是指从作业提交给系统开始，到作业完成为止的这段时间间隔。平均周转时间T=/n平均带权周转时间W=/n一个作业的带权周转时间Wi=Ti/Tsi（作业的周转时间Ti/实际服务时间Tsi）响应时间快响应时间是评价分时系统的性能指标。响应时间是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。][1niTi]/[1niTsiTi3.1.5调度方式和算法的选择准则截止时间的保证它是用来评价实时系统的重要指标，截止时间是某任务必须开始执行的最迟时间，或完成的最迟时间。优先权准则在选择批处理、分时和实时系统的调度算法时，都可引用优先权准则，以便让那些紧急的作业（或事件），得到及时的处理。在要求较严格的场合，往往还需选择抢占调度方式，才能保证紧急作业得到及时的处理。3.1.5调度方式和算法的选择准则2.面向系统的准则达到系统设计目标系统的设计目标是选择算法的主要依据。例如批处理系统所追求的是充分发挥和提高计算机的效率，分时系统则侧重于保护用户的请求及时给予响应，实时系统所关心的是不要丢失实时信息并给予处理。系统吞吐量大这是用来评价批处理系统的重要指标。系统吞吐量是单位时间内完成的作业数，它与批处理作业的平均长度具有密切关系。处理机利用率高对于大中型多用户系统，由于CPU价格十分昂贵，所以处理机利用率成为衡量大、中型系统性能的重要指标，但对单用户微机或某些实时系统，该准则就不那么重要。各类资源的平衡利用在大中型系统中，有效地利用各类资源（包括CPU、外存、I/O设备等）也是一个重要指标，对于微型机和某些实时系统，该准则也不重要。返回3.2作业／进程调度算法1.先来先服务First-Come-First-Served(FCFS)（作业／进程）调度算法此算法的原则是按照作业到达后备作业队列（或进程进入就绪队列）的先后次序来选择作业（或进程）。–可用于作业或进程调度–FCFS算法属于非抢占方式，一旦一个进程占有处理机，它就一直运行下去，直到该进程完成或者因等待某事件而不能继续运行时才释放处理机–FCFS是一种最简单的调度算法–FCFS算法易于实现，表面上很公平，实际上有利于长作业，不利于短作业。3.2作业／进程调度算法2.短作业／进程优先(SJF/SPF)调度算法SJF:它从作业后备队列中挑选所需运行时间（估计值）最短的作业进入主存运行。SPF:从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成或阻塞。–既可采用抢占式（即最短剩余时间优先算法），也可采用非抢占式–这种调度算法主要用于作业调度，也可用于进程调度，即SPF–采用SJF有利于系统减少平均周转时间和平均带权周转时间，提高系统吞吐量–这一算法有利于短作业，对长作业不利。如果作业的到来顺序及运行