处理机调度-(3)

《处理机调度-(3)》由会员分享，可在线阅读，更多相关《处理机调度-(3)（31页珍藏版）》请在金锄头文库上搜索。

1、1. 处理机调度的概念 1）调度即按照一定的调度规则合理地分配与释放资源，处理机调度即完成处理机的分配任务。 一般认为，有三级： 作业调度、进程调度和交换调度； 2）原语：操作系统通过原语操作来实现调度控制。一般系统都有进程创建、挂起、激活、阻塞、唤醒、撤消原语。注意在操作过程中用到就绪队列、阻塞队列和PCB。,第三章 处理机调度,作业调度：又称宏观调度或高级调度。把外存上处于后备队列中的作业调入内存，并为之创建进程、分配必要的资源，然后再将新创建的进程排在就绪队列上，准备执行。用于批处理系统。在分时和实时系统，通常无须作业调度。,进程调度：微观调度或低级调度。按照某种策略和方法选取一个处于就

2、绪状态的进程，将处理机分配给它。 进程调度程序：操作系统的真正核心，负责完成进程从就绪到运行转变的工作。具体功能是记住所有进程的状态、优先数和资源请求等，确定调度算法，分配处理机给进程。 进程调度的基础是进程的组织，实际上是PCB的有效组织。,交换调度：中级调度。按照某种策略，将处于外存交换区中的重又具备运行条件的就绪进程调入内存，或将处于内存就绪状态或内存阻塞状态的进程交换到外存交换区。它主要涉及内存管理与扩充。,2 进程调度的实现 进程的调度主要考虑三个方面： 调度的方式； 调度的时机； 调度的策略； 1）调度的方式如何来分配和回收CPU 非抢占方式和抢占方式。,非抢占方式(Non pre

3、emptive mode) 一旦把CPU分配给某一进程后,便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才将CPU分给其它进程。 主要优点是简单、系统开销小，但是一个进程的运行往往可能导致多数进程长期得不到服务。通常用在批处理系统中。 抢占方式(Preemptive mode) 允许调度程序基于某种策略（优先级策略、时间片策略、短作业优先等）剥夺现行进程的CPU给其它进程。 通常用在分时系统和实时系统中，以便及时响应各进程的请求。,2）调度的时机进程并发执行过程中何时实现CPU的切换 进程运行时，时间片用完被时钟中断； 请求I/O服务时，进程需要暂时放弃CPU，以免出现CPU的“忙等待

4、”； 某些原语操作，如P操作等； 进程完成； 在可抢占方式调度中，新建进程较当前执行进程优先级高。,3）调度的策略选择进程运行的依据。 调度算法选择多从处理器利用率、吞吐量、等待时间和响应时间考虑。,了解：平均周转时间,作业的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS，称为带权周转时间，而平均带权周转时间则可表示为:,先来先服务（FCFS）：按进程进入就绪队列的先后来调度。 特点：有利于长作业，不利于短作业； 有利于CPU繁忙型，不利于I/O繁忙型； 短作业（进程）优先算法SJ(P)F:每次调度时，从就绪队列中找出下一个估计CPU执行期最短的作业（进程）优先调度； 特点：不利于

5、长作业，有利于短作业； 进程的执行时间预测困难； 没有考虑进程实际的紧迫程度； 。,优先级调度算法：每次调度时，从就绪队列中找出优先级最高的进程优先调度。 静态优先级法：在进程创建时就确定其优先级，运行过程中不再改变的方法。一般按进程类型、资源的要求、作业到达时间或用户类型确定。 动态优先级法：在运行过程中，不断调整进程的优先级。 思考：动态优先级怎么确定？, 时间片轮转法：有简单时间片轮转、可变时间片轮转、多队列轮转法。 时间片的大小确定： 系统对响应时间的要求； 就绪队列中进程的数目；（分时系统终端的数目） 系统处理能力：保证用户键入的常用命令能够在一个时间片内完成,多级反馈队列调度 就绪

6、进程的种类： 刚创建的进程； 已经被调度执行过，但还没有执行完，等待下一次调度； 因请求I/O而阻塞，当等待原因解除被唤醒进入就绪队列。 设置多个就绪队列，第一级队列的优先级最高，但占用的时间片最短，各级队列依次优先级递减，占用时间片递增。 执行进程调度时，刚进入就绪队列的进程先加入第一级队列，获得一个时间片，如时间片到而没有完成，则将该进程加入下一级。 分级调度可以使运行时间短进程优先得到调度，减少运行时间长进程的调度次数。,特点： 1）各个队列赋予不同的优先权，第一个队列的优先权最高，其余队列的优先权逐个降低。 2）各个队列中进程执行时间片的大小也不相同。 3）刚创建的进程和因请求I/O未

7、用完时间片的进程排在最高优先级队列，在这个队列中运行1个时间片未完成的进程排到下一个较低优先级队列。 4）先调度优先级高的队列。仅当该队列空时，才调度次高优先级队列，以此类推，第n个队列进程被调度时，必须是前n-1个队列为空。 5）既能使分时用户作业得到满意的响应时间，又能使批处理用户的作业获得较合理的周转时间。,3 死锁 3.1死锁的概念 各并发进程彼此互相等待对方所拥有的资源却又在自身推进之前不会释放已有的资源，从而使各进程都不能推进的状态即死锁。 死锁的起因源于并发进程的资源竟争。 产生死锁的根本原因在于系统提供的资源个数少于并发进程所要求的该类资源数。显然，由于资源的有限性，不可能为所

8、有要求资源的进程无限制地提供资源。,死锁产生原因 1）竞争资源 资源的类型 可剥夺资源：剥夺时仅终止占用进程推进。如主存、CPU。 不可剥夺资源：一旦分配，不能强收回，只能由其自动释放。如打印机、磁带机。 竞争不可剥夺资源,竞争临时性资源（进程通信）,2）进程推进顺序（不安全区D）,3.2 死锁产生的必要条件 1) 互斥条件 系统使用临界资源，各进程不能同时使用 2) 部分分配条件（动态分配） 在运行中按需分配资源 3) 保持和等待条件（循环等待） 各进程对资源的需求形成循环等待 4) 不可剥夺条件 既不能强行剥夺其他进程的资源,3.3 死锁的预防和解除 解决死锁的方法： 鸵鸟政策：不采取任何

9、措施，出现死锁后再解除。如UNIX。 假如系统中不允许死锁发生，通常有两种解决办法： 静态解决办法: 系统事先采取措施，对进程申请资源的要求加以限制，即预防死锁。 动态解决办法:在进程运行过程中提出资源申请时，系统加以检测，决定是否分配资源，即避免死锁。 假如系统中允许发生死锁，则需检测死锁是否发生，并在死锁发生时加以解除。 只要破坏死锁四个必要条件之一，就可以解除死锁。如：杀死死锁的某个进程。,1）预防死锁 限制“互斥条件”：不易有解决方案。 限制“动态分配”条件：采用静态分配，效率低。 限制“不可剥夺条件”：常见的做法。 限制“请求与保持条件”： 禁止已拥有资源的进程再申请其它资源，蜕变为

10、静态分配；或当进程提出新的资源申请时，暂时释放当前已经占用的所有资源，只有当新的资源申请成功时，才收回其原先占用的资源。约束多且效率低。 寻求合理途径来动态地分配资源？,资源有序分配法：将所有资源编号，对资源的请求只能按编号增加的原则进行，这样可以避免形成资源循环等待。缺点是可能资源编号的顺序与需求顺序不一致。,如对哲学家吃面条问题，若对所有的筷子编号，可以避免死锁。,ij ,2）避免死锁 基本思想： 允许进程动态地申请资源，一次申请一部分资源。系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，便将资源分配给进程；否则，进程等待。 安全状态： 指系统能按某种

11、顺序，如p1 , p2 , , pn (安全序列)，来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成。 如果系统无法找到这样一个安全序列，则称系统处于不安全状态。,例：Dijkstra的银行家算法(安全序列检测算法) Dijkstra把系统比作一个占有有限资源的银行家，虽然不能满足所有借款人的最大需求总和，但可以满足部分人的借款需求，待其还款后，又可以满足其他人的需求。 安全序列：即可以达到全部顺利满足各进程资源要求的资源分配顺序 安全状态：至少存在一个安全序列的状态 资源分配图（资源分配矩阵） 设有AE五个进程，系统资源为m1m4，各进程对各种资源的需求和分配情况可以用矩阵表

12、示如下： 已分配矩阵 = 最大分配矩阵 - 剩余需求矩阵 Allocation Max Need,未分配资源数 = 系统资源数 - 已分配资源数 Available（1，0，2，0）= r（6，3，4，2）- S（5，3，2，2）,已分配矩阵 = 最大分配矩阵 - 剩余需求矩阵,安全性算法： 在Need中找一未标记行，满足每一元素小于等于Available，找不到转； 标记找到的行，并将相应进程已占有的资源（Allocation中的相应行）加到Available 中； 重复转； 如果所有行都已标记，则系统是安全的，否则系统不安全；,银行家算法： 设Requesti是进程Pi的请求向量，如果Re

13、questij=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： (1) 如果RequestijNeedi,j，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 (2) 如果RequestijAvailablej，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。,(3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej=Availablej-Requestij; Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij;

14、 (4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。,3)死锁的检测 在允许发生死锁的系统中，必须有对死锁进行检测的方法。死锁的检测通常是定时进行的，时间间隔的选择很重要。选择的间隔小，死锁检测程序的执行会增加系统开销，间隔大，又不能及时检测出死锁。,资源分配图 资源分配图中有圆形及方框两类节点，分别表示进程和资源。从资源到进程的有向边表示该资源已被进程占用，从进程到资源的有向边表示进程申请该资源。,死锁定理 一种资源分配状态为死锁状态的充要条件是：当且仅当S状态的资源分配图是不可完全简化的。,4） 死锁的解除 在允许发生死锁的系统中，当检测到死锁时，应设法解除死锁。 解除死锁的一种方案是从其它进程剥夺资源给死锁进程，直至死锁解除。当然，系统必须付出一定代价。 另一种方案是撤消进程。撤消进程时，可选择撤消部分进程的方案，也可以将全部死锁进程撤消，这种方案会使系统付出很大代价。 如：Windows任务管理器下撤销进程,