1、1.1.处理机调度的概念处理机调度的概念1 1）调度即按照一定的调度规则合理地分配与释放资源，处）调度即按照一定的调度规则合理地分配与释放资源，处理机调度即完成处理机的分配任务。理机调度即完成处理机的分配任务。一般认为，有三级：一般认为，有三级：作业调度、进程调度和交换调度；作业调度、进程调度和交换调度；2 2）原语：操作系统通过原语操作来实现调度控制。原语：操作系统通过原语操作来实现调度控制。一般系一般系统都有进程创建、挂起、激活、阻塞、唤醒、撤消原语。统都有进程创建、挂起、激活、阻塞、唤醒、撤消原语。注意在操作过程中用到就绪队列、阻塞队列和注意在操作过程中用到就绪队列、阻塞队列和PCBPC
2、B。第三章第三章 处理机调度处理机调度 作业调度：作业调度：又称宏观调度或高级调度。把外存上处于后备又称宏观调度或高级调度。把外存上处于后备队列中的作业调入内存，并为之创建进程、分配必要的队列中的作业调入内存，并为之创建进程、分配必要的资源，然后再将新创建的进程排在就绪队列上，准备执资源，然后再将新创建的进程排在就绪队列上，准备执行。用于批处理系统。在分时和实时系统，通常无须作行。用于批处理系统。在分时和实时系统，通常无须作业调度。业调度。提交提交后备后备执行执行完成完成SPOOLing作 业 调 度作 业 调 度SPOOLing进程调度和交通控制进程调度和交通控制进程调度：进程调度：微观调度
3、或低级调度。按照某种策略和方法微观调度或低级调度。按照某种策略和方法选取一个处于就绪状态的进程，将处理机分配给它。选取一个处于就绪状态的进程，将处理机分配给它。进程调度程序：操作系统的真正核心，负责完成进进程调度程序：操作系统的真正核心，负责完成进程从就绪到运行转变的工作。具体功能是记住所有进程程从就绪到运行转变的工作。具体功能是记住所有进程的状态、优先数和资源请求等，确定调度算法，分配处的状态、优先数和资源请求等，确定调度算法，分配处理机给进程。理机给进程。进程调度的基础是进程的组织，实际上是进程调度的基础是进程的组织，实际上是PCBPCB的有的有效组织。效组织。交换调度：交换调度：中级调度
4、。按照某种策略，将处于外存交换中级调度。按照某种策略，将处于外存交换区中的重又具备运行条件的就绪进程调入内存，或将区中的重又具备运行条件的就绪进程调入内存，或将处于内存就绪状态或内存阻塞状态的进程交换到外存处于内存就绪状态或内存阻塞状态的进程交换到外存交换区。它主要涉及内存管理与扩充。交换区。它主要涉及内存管理与扩充。内存就绪换出外存就绪换入内存阻塞外存阻塞执行换出2 2 进程调度的实现进程调度的实现 进程的调度主要考虑三个方面：进程的调度主要考虑三个方面：调度的方式；调度的方式；调度的时机；调度的时机；调度的策略；调度的策略；1 1）调度的方式）调度的方式如何来分配和回收如何来分配和回收CP
5、U CPU 非抢占方式和抢占方式。非抢占方式和抢占方式。非抢占方式非抢占方式(Non preemptive mode)(Non preemptive mode)一旦把一旦把CPUCPU分配给某一进程后分配给某一进程后,便让它一直运行下去，便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才将直到进程完成或发生某事件而阻塞时，才将CPUCPU分给其分给其它进程。它进程。主要优点是简单、系统开销小，但是一个进程的运主要优点是简单、系统开销小，但是一个进程的运行往往可能导致多数进程长期得不到服务。通常用在批行往往可能导致多数进程长期得不到服务。通常用在批处理系统中。处理系统中。抢占方式抢占方式(
6、Preemptive mode)(Preemptive mode)允许调度程序基于某种策略（优先级策略、时间片允许调度程序基于某种策略（优先级策略、时间片策略、短作业优先等）剥夺现行进程的策略、短作业优先等）剥夺现行进程的CPUCPU给其它进程。给其它进程。通常用在分时系统和实时系统中，以便及时响应各通常用在分时系统和实时系统中，以便及时响应各进程的请求。进程的请求。2 2）调度的时机）调度的时机进程并发执行过程中何时实现进程并发执行过程中何时实现CPUCPU的切换的切换进程运行时，时间片用完被时钟中断；进程运行时，时间片用完被时钟中断；请求请求I/OI/O服务时，进程需要暂时放弃服务时，进程
7、需要暂时放弃CPUCPU，以免，以免出现出现CPUCPU的的“忙等待忙等待”；某些原语操作，如某些原语操作，如P P操作等；操作等；进程完成；进程完成；在可抢占方式调度中，新建进程较当前执行进在可抢占方式调度中，新建进程较当前执行进程优先级高。程优先级高。3 3）调度的策略）调度的策略选择进程运行的依据。选择进程运行的依据。调度算法选择多从处理器利用率、吞吐量、调度算法选择多从处理器利用率、吞吐量、等待时间和响应时间考虑。等待时间和响应时间考虑。niiTnT11了解了解：平均周转时间：平均周转时间作业的周转时间作业的周转时间T T与系统为它提供服务的时间与系统为它提供服务的时间T TS S之比
8、，即之比，即W=T/TW=T/TS S，称为带权周转时间，而平，称为带权周转时间，而平均带权周转时间则可表示为均带权周转时间则可表示为:niSiiTTnW11先来先服务先来先服务（FCFSFCFS）：按进程进入就绪队列）：按进程进入就绪队列的先后来调度。的先后来调度。特点：有利于长作业，不利于短作业；特点：有利于长作业，不利于短作业；有利于有利于CPUCPU繁忙型，不利于繁忙型，不利于I/OI/O繁忙型；繁忙型；短作业（进程）优先算法短作业（进程）优先算法SJ(P)F:SJ(P)F:每次调度每次调度时，从就绪队列中找出下一个估计时，从就绪队列中找出下一个估计CPUCPU执行期最执行期最短的作业
9、（进程）优先调度；短的作业（进程）优先调度；特点：不利于长作业，有利于短作业；特点：不利于长作业，有利于短作业；进程的执行时间预测困难；进程的执行时间预测困难；没有考虑进程实际的紧迫程度；没有考虑进程实际的紧迫程度；。优先级调度算法：优先级调度算法：每次调度时，从就绪队列中每次调度时，从就绪队列中找出优先级最高的进程优先调度。找出优先级最高的进程优先调度。静态优先级法：在进程创建时就确定其优先级，静态优先级法：在进程创建时就确定其优先级，运行过程中不再改变的方法。一般按进程类型、运行过程中不再改变的方法。一般按进程类型、资源的要求、作业到达时间或用户类型确定。资源的要求、作业到达时间或用户类型
10、确定。动态优先级法：在运行过程中，不断调整进程动态优先级法：在运行过程中，不断调整进程的优先级。的优先级。思考：动态优先级怎么确定？思考：动态优先级怎么确定？时间片轮转法时间片轮转法：有简单时间片轮转、可变：有简单时间片轮转、可变时间片轮转、多队列轮转法。时间片轮转、多队列轮转法。时间片的大小确定：时间片的大小确定：系统对响应时间的要求；系统对响应时间的要求；就绪队列中进程的数目；（分时系统终端的数目）就绪队列中进程的数目；（分时系统终端的数目）系统处理能力：保证用户键入的常用命令能够在一个时系统处理能力：保证用户键入的常用命令能够在一个时间片内完成间片内完成 多级反馈队列调度多级反馈队列调度
11、就绪进程的种类：就绪进程的种类：v刚创建的进程；刚创建的进程；v已经被调度执行过，但还没有执行完，等待下一次调度；已经被调度执行过，但还没有执行完，等待下一次调度；v因请求因请求I/OI/O而阻塞，当等待原因解除被唤醒进入就绪队列。而阻塞，当等待原因解除被唤醒进入就绪队列。设置多个就绪队列，第一级队列的优先级最高，但占用设置多个就绪队列，第一级队列的优先级最高，但占用的时间片最短，各级队列依次优先级递减，占用时间片递的时间片最短，各级队列依次优先级递减，占用时间片递增。增。执行进程调度时，刚进入就绪队列的进程先加入第一执行进程调度时，刚进入就绪队列的进程先加入第一级队列，获得一个时间片，如时间
12、片到而没有完成，则将级队列，获得一个时间片，如时间片到而没有完成，则将该进程加入下一级。该进程加入下一级。分级调度可以使运行时间短进程优先得到调度，减少分级调度可以使运行时间短进程优先得到调度，减少运行时间长进程的调度次数。运行时间长进程的调度次数。就绪队列就绪队列1就绪队列就绪队列2就绪队列就绪队列3就绪队列就绪队列ns1s2s3sn至至CPU至至CPU至至CPU至至CPU（时间片：（时间片：s1s2s3)特点：特点：1 1）各个队列赋予不同的优先权，第一个队列的优先权最高，）各个队列赋予不同的优先权，第一个队列的优先权最高，其余队列的优先权逐个降低。其余队列的优先权逐个降低。2 2）各个队
13、列中进程执行时间片的大小也不相同。）各个队列中进程执行时间片的大小也不相同。3 3）刚创建的进程和因请求）刚创建的进程和因请求I/OI/O未用完时间片的进程排在最未用完时间片的进程排在最高优先级队列，在这个队列中运行高优先级队列，在这个队列中运行1 1个时间片未完成的个时间片未完成的进程排到下一个较低优先级队列。进程排到下一个较低优先级队列。4 4）先调度优先级高的队列。仅当该队列空时，才调度次高）先调度优先级高的队列。仅当该队列空时，才调度次高优先级队列，以此类推，第优先级队列，以此类推，第n n个队列进程被调度时，必个队列进程被调度时，必须是前须是前n-1n-1个队列为空。个队列为空。5
14、5）既能使分时用户作业得到满意的响应时间，又能使批处）既能使分时用户作业得到满意的响应时间，又能使批处理用户的作业获得较合理的周转时间。理用户的作业获得较合理的周转时间。3 3 死锁死锁3.13.1死锁的概念死锁的概念各并发进程彼此互相等待对方所拥有的资源却又在自各并发进程彼此互相等待对方所拥有的资源却又在自身推进之前不会释放已有的资源，从而使各进程都不能推身推进之前不会释放已有的资源，从而使各进程都不能推进的状态即死锁。进的状态即死锁。死锁的起因源于并发进程的资源竟争。死锁的起因源于并发进程的资源竟争。产生死锁的根本原因在于系统提供的资源个数少于并产生死锁的根本原因在于系统提供的资源个数少于
15、并发进程所要求的该类资源数。显然，由于资源的有限性，发进程所要求的该类资源数。显然，由于资源的有限性，不可能为所有要求资源的进程无限制地提供资源。不可能为所有要求资源的进程无限制地提供资源。u死锁产生原因死锁产生原因1）竞争资源）竞争资源 资源的类型资源的类型v 可剥夺资源：剥夺时仅终止占用进程推进。如主存、可剥夺资源：剥夺时仅终止占用进程推进。如主存、CPUCPU。v 不可剥夺资源：一旦分配，不能强收回，只能由其自动不可剥夺资源：一旦分配，不能强收回，只能由其自动释放。如打印机、磁带机。释放。如打印机、磁带机。竞争不可剥夺资源竞争不可剥夺资源 打印机打印机输入机输入机进程进程1进程进程2竞争
16、临时性资源（进程通信）竞争临时性资源（进程通信）S2P1S3P3S1P2P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)D2 2）进程推进顺序（不安全区）进程推进顺序（不安全区D D）3.2 3.2 死锁产生的必要条件死锁产生的必要条件1)1)互斥条件互斥条件 系统使用临界资源，各进程不能同时使用系统使用临界资源，各进程不能同时使用2)2)部分分配条件部分分配条件（动态分配）（动态分配）在运行中按需分配资源在运行中按需分配资源3)3)保持和等待条件保持和等待条件（循环等待）（循环等待）各进程对资源的
17、需求形成循环等待各进程对资源的需求形成循环等待4)4)不可剥夺条件不可剥夺条件 既不能强行剥夺其他进程的资源既不能强行剥夺其他进程的资源 3.3 3.3 死锁的预防和解除死锁的预防和解除解决死锁的方法：解决死锁的方法：鸵鸟政策：不采取任何措施，出现死锁后再解除。如鸵鸟政策：不采取任何措施，出现死锁后再解除。如UNIXUNIX。假如系统中不允许死锁发生，通常有两种解决办法：假如系统中不允许死锁发生，通常有两种解决办法：静态解决办法静态解决办法:系统事先采取措施，对进程申请资源的系统事先采取措施，对进程申请资源的要求加以限制，即预防死锁。要求加以限制，即预防死锁。动态解决办法动态解决办法:在进程运
18、行过程中提出资源申请时，系统在进程运行过程中提出资源申请时，系统加以检测，决定是否分配资源，即避免死锁。加以检测，决定是否分配资源，即避免死锁。假如系统中允许发生死锁，则需检测死锁是否发生，并在假如系统中允许发生死锁，则需检测死锁是否发生，并在死锁发生时加以解除。死锁发生时加以解除。只要破坏死锁四个必要条件之一，就可以解除死锁。只要破坏死锁四个必要条件之一，就可以解除死锁。如：杀死死锁的某个进程。如：杀死死锁的某个进程。1 1）预防死锁）预防死锁限制限制“互斥条件互斥条件”：不易有解决方案。：不易有解决方案。限制限制“动态分配动态分配”条件：采用静态分配，效率低。条件：采用静态分配，效率低。限
19、制限制“不可剥夺条件不可剥夺条件”：常见的做法。：常见的做法。限制限制“请求与保持条件请求与保持条件”：禁止已拥有资源的进程再申请其它资源，蜕禁止已拥有资源的进程再申请其它资源，蜕变为静态分配；或当进程提出新的资源申请时，变为静态分配；或当进程提出新的资源申请时，暂时释放当前已经占用的所有资源，只有当新的暂时释放当前已经占用的所有资源，只有当新的资源申请成功时，才收回其原先占用的资源。约资源申请成功时，才收回其原先占用的资源。约束多且效率低。束多且效率低。寻求合理途径来动态地分配资源寻求合理途径来动态地分配资源？v资源有序分配法：将所有资源编号，对资源的请资源有序分配法：将所有资源编号，对资源
20、的请求只能按编号增加的原则进行，这样可以避免形求只能按编号增加的原则进行，这样可以避免形成资源循环等待。缺点是可能资源编号的顺序与成资源循环等待。缺点是可能资源编号的顺序与需求顺序不一致。需求顺序不一致。P1P2R1R2如对哲学家吃面条问题，若对所有的筷子编号，可以避免死锁。如对哲学家吃面条问题，若对所有的筷子编号，可以避免死锁。ij ij 2 2）避免死锁）避免死锁基本思想基本思想：v允许进程动态地申请资源，一次申请一部分资源。允许进程动态地申请资源，一次申请一部分资源。系统在进行资源分配之前，先计算资源分配的安系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统进入不安全
21、状态，全性。若此次分配不会导致系统进入不安全状态，便将资源分配给进程；否则，进程等待。便将资源分配给进程；否则，进程等待。安全状态安全状态：v指系统能按某种顺序，如指系统能按某种顺序，如p1,p2,p1,p2,pn(,pn(安安全序列全序列)，来为每个进程分配其所需资源，直至最，来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成。大需求，使每个进程都可顺序完成。如果系统无法找到这样一个安全序列，则称系如果系统无法找到这样一个安全序列，则称系统处于不安全状态。统处于不安全状态。例：例：DijkstraDijkstra的银行家算法的银行家算法(安全序列检测算法安全序列检测算法)Dij
22、kstraDijkstra把系统比作一个占有有限资源的银行家，虽然不能把系统比作一个占有有限资源的银行家，虽然不能满足所有借款人的最大需求总和，但可以满足部分人的借满足所有借款人的最大需求总和，但可以满足部分人的借款需求，待其还款后，又可以满足其他人的需求。款需求，待其还款后，又可以满足其他人的需求。安全序列：即可以达到全部顺利满足各进程资源要求安全序列：即可以达到全部顺利满足各进程资源要求的资源分配顺序的资源分配顺序 安全状态：至少存在一个安全序列的状态安全状态：至少存在一个安全序列的状态 资源分配图（资源分配矩阵）资源分配图（资源分配矩阵）设有设有A AE E五个进程，系统资源为五个进程，
23、系统资源为m1m1m4m4，各进程对各种资源，各进程对各种资源的需求和分配情况可以用矩阵表示如下：的需求和分配情况可以用矩阵表示如下：已分配矩阵已分配矩阵=最大分配矩阵最大分配矩阵 -剩余需求矩阵剩余需求矩阵 Allocation Max NeedAllocation Max Need M1M2M3M4A3011B0100C1110D1101E0000M1M2M3M4A4111B0212C4210D1111E2110M1M2M3M4A1100B0112C3100D0010E2110未分配资源数未分配资源数 =系统资源数系统资源数-已分配资源数已分配资源数 AvailableAvailable（
24、1 1，0 0，2 2，0 0）=r r（6 6，3 3，4 4，2 2）-S-S（5 5，3 3，2 2，2 2）已分配矩阵已分配矩阵=最大分配矩阵最大分配矩阵 -剩余需求矩阵剩余需求矩阵 安全性算法：安全性算法：在在NeedNeed中找一未标记行，满足每一元素小于等于中找一未标记行，满足每一元素小于等于AvailableAvailable，找不到转，找不到转；标 记 找 到 的 行，并 将 相 应 进 程 已 占 有 的 资 源标 记 找 到 的 行，并 将 相 应 进 程 已 占 有 的 资 源（AllocationAllocation中的相应行）加到中的相应行）加到Available
25、Available 中；中；重复转重复转；如果所有行都已标记，则系统是安全的，否则系统不安如果所有行都已标记，则系统是安全的，否则系统不安全；全；银行家算法：银行家算法：设设RequestiRequesti是进程是进程PiPi的请求向量，如果的请求向量，如果RequestiRequestij j=K K，表示进程，表示进程PiPi需要需要K K个个RjRj类型的资源。当类型的资源。当PiPi发出资源请发出资源请求后，系统按下述步骤进行检查：求后，系统按下述步骤进行检查：(1)(1)如果如果RequestiRequestij jNeedNeedi,ji,j，便转向步骤，便转向步骤2 2；否则认为
26、出错，因为它所需要的资源数已超过它所宣；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。布的最大值。(2)(2)如果如果RequestiRequestij jAvailableAvailablej j，便转向，便转向步骤步骤(3)(3)；否则，；否则，表示尚无足够资源，表示尚无足够资源，PiPi须等待。须等待。(3)(3)系统试探着把资源分配给进程系统试探着把资源分配给进程PiPi，并修改下面数，并修改下面数据结构中的数值：据结构中的数值：AvailableAvailablej j=Available=Availablej j-Requesti-Requestij j;Allocat
27、ionAllocationi,ji,j=Allocation=Allocationi,ji,j+Requesti+Requestij j;NeedNeedi,ji,j=Need=Needi,ji,j-Requesti-Requestij j;(4)(4)系统执行安全性算法，检查此次资源分配后，系系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程统是否处于安全状态。若安全，才正式将资源分配给进程PiPi，以完成本次分配；否则，以完成本次分配；否则，将本次的试探分配作废，将本次的试探分配作废，恢复原来的资源分配状态，让进程恢复原来的资源分配状态，让进程Pi
28、Pi等待。等待。3)3)死锁的检测死锁的检测 在允许发生死锁的系统中，必须有对死锁进行检测的在允许发生死锁的系统中，必须有对死锁进行检测的方法。死锁的检测通常是定时进行的，时间间隔的选择方法。死锁的检测通常是定时进行的，时间间隔的选择很重要。选择的间隔小，死锁检测程序的执行会增加系很重要。选择的间隔小，死锁检测程序的执行会增加系统开销，间隔大，又不能及时检测出死锁。统开销，间隔大，又不能及时检测出死锁。P1P2r1r2资源分配图资源分配图 资源分配图中有圆形及方框资源分配图中有圆形及方框两类节点，分别表示进程和资源。两类节点，分别表示进程和资源。从资源到进程的有向边表示该资从资源到进程的有向边
29、表示该资源已被进程占用，从进程到资源源已被进程占用，从进程到资源的有向边表示进程申请该资源。的有向边表示进程申请该资源。死锁定理死锁定理 一种资源分配状态为死锁状态的充要条件是：一种资源分配状态为死锁状态的充要条件是：当且仅当当且仅当S S状态的资源分配图是不可完全简化的。状态的资源分配图是不可完全简化的。(a)(b)P1(c)P1P2P1P2P24 4）死锁的解除死锁的解除 在允许发生死锁的系统中，当检测到死锁时，应设法在允许发生死锁的系统中，当检测到死锁时，应设法解除死锁。解除死锁。解除死锁的一种方案是从其它进程剥夺资源给死锁进解除死锁的一种方案是从其它进程剥夺资源给死锁进程，直至死锁解除。当然，系统必须付出一定代价。程，直至死锁解除。当然，系统必须付出一定代价。另一种方案是撤消进程。撤消进程时，可选择撤消部另一种方案是撤消进程。撤消进程时，可选择撤消部分进程的方案，也可以将全部死锁进程撤消，这种方案分进程的方案，也可以将全部死锁进程撤消，这种方案会使系统付出很大代价。会使系统付出很大代价。如：如：WindowsWindows任务管理器下撤销进程任务管理器下撤销进程
