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