操作系统习题3.ppt

操作系统原理 第三章 处理机调度与死锁,计算机科学与技术学院,内 容,产生死锁的原因和必要条件,多处理机系统中的调度,实时调度,调度算法,处理机调度的基本概念,预防死锁的方法,死锁的检测与解锁,处理机调度的基本概念,高级、中级和低级调度高级调度(High Scheduling)又称为作业调度或长程调度，用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后再将新创建的进程排在就绪队列上，准备执行。有时也称接纳调度。需 要 性,批处理系统,分时系统,实时系统,分时与实时系统中，由键盘输入的命令或数据，直接送入内存，以做到及时响应。,处理机调度的基本概念,高级、中级和低级调度高级调度在每次执行作业调度时，都须做出 以下两个决定。1)接纳多少个作业 2)接纳哪些作业低级调度(Low Level Scheduling)低级调度通常又称为进程调度、短程调度，用来决定就绪队列中的哪个进程应获得处理机，然后由分派程序执行把处理机分配给该进程的具体操作。进程调度可采取下述两种方法非抢占方式抢占方式,处理机调度的基本概念,高级、中级和低级调度低级调度非抢占方式主动交出处理机实现简单，系统开销小，适用于大多批处理系统.难以解决紧急任务的要求抢占方式根据某种原则，新进程抢占当前进程处理机原则：优先权；短作业优先；时间片原则（分时系统）,处理机调度的基本概念,高级、中级和低级调度中级调度(High Scheduling)对换功能目的：提高资源利用率、系统吞吐量三种调度频率及时间,进程调度 最高 10100ms,中级调度 居中 居中,作业调度 最低 几分钟,名称 频率 周期,处理机调度的基本概念,调度队列模型仅有进程调度的调度队列模型,就绪队列为FIFO,分时系统,处理机调度的基本概念,调度队列模型具有高级和低级调度的调度队列模型,就绪队列为优先权队列,批处理系统,处理机调度的基本概念,调度队列模型同时具有三级调度的调度队列模型就绪分为内存就绪和外存就绪（挂起）阻塞分为内存阻塞和外存阻塞（挂起）通过内外存对换转换为挂起状态选择调度方式和算法的准则面向用户,（批）周转时间短 定义,（分）响应时间快 定义,（实）截止时间保证 定义,优先权准则（三种都可遵循）,处理机调度的基本概念,选择调度方式和算法的准则面向系统,系统吞吐量高,处理机处理效率好,各类资源的平衡利用,内 容,产生死锁的原因和必要条件,多处理机系统中的调度,实时调度,调度算法,处理机调度的基本概念,预防死锁的方法,死锁的检测与解锁,调度算法,先来先服务(FCFS)既可用于作业调度，也可用于进程调度算法描述有利于长作业（进程），不利 于短作业（进程）,1,101,1,1,100,1,100,199,1.99,102,202,100,0,1,101,102,其中短作业C的带权周转时间竞高达100，这是不能容忍的；而长作业D的带权周转时间仅为1.99。据此可知：FCFS调度算法有利于CPU繁忙型的作业，而不利于I/O繁忙型的作业进程。,采用FCFS调度算法时的调度性能,调度算法,短作业（进程）优先(SJF)既可用于作业调度，也可用于进程调度算法描述有效降低作业平均等待时间，提高系统吞吐量。,调度算法,.例题：1#4#任务几乎同时到达的，并先后就绪，估计运行时间分别为2、8、4、6秒，分析调度过程和性能,调度算法,采用SJ（P）F算法后，不论是平均周转时间还是平均带权周转时间都有较明显的改善，尤其是对短作业D，其周转时间由FCFS算法的11降为SJF算法中的3；而平均带权周转时间是从5.5降到1.5。,4 4 1,7 6 2,12 10 2,14115.5,18143.5,441,9 82.67,18163.2,6 31.5,13 92.25,92.8,82.1,SJ（P）F调度算法也存在不容忽视的缺点（1）该算法对长作业非常不利。（2）该算法完全未考虑作业的紧迫程度（3）不一定能真正做到短作业优先调度。,调度算法,高优先权优先调度算法既可用于作业调度，也可用于进程调度优先权调度算法类型非抢占式优先权算法主动交出CPU，用于批处理系统抢占式优先权算法被动交出CPU，实时性更好,调度算法,高优先权优先调度算法优先权类型静态优先权进程的整个运行期间保持不变特点：简单，但低优先权作业可能长期不被调度。动态优先权如：优先权随执行时间而下降，随等待时间而升高。,调度算法,调度算法,优先数调度算法（不可剥夺）例题,有5个批处理作业（A、B、C、D、E）几乎同时到达，估计运行时间分别为2、8、6、10、4分钟，它们的优先数分别为1、4、3、5、2（1为最低优先数）。求平均周转时间,调度算法,高响应比优先算法响应比Rp=特点1）短作业Rp大。2）ts（要求服务时间）相同的进程间相当于FCFS。3）长作业等待一段时间仍能得到服务。长短兼顾，又考虑到了先后次序，不饥饿缺点：需计算Rp,调度算法,例题：高响应比优先调度算法（非抢占）,在一个批处理单道系统中，采用响应比高者优先的作业调度算法。一个作业进入系统后就可以开始调度，假定作业都是仅计算，忽略调度花费的时间。现有三个作业，进入系统的时间和需要计算的时间如下表：,9:00,10:00,60分,10:25,11:10,120分,10:00,10:25,60分,基于时间片的轮转调度算法时间片轮转法时钟中断时间片大小的确定 太大：退化为FCFS；太小：系统开销过大多级反馈队列调度,调度算法,时间片：S1S2S3队列1优先级最高,基于时间片的轮转调度算法多级反馈队列调度特点：长、短作业兼顾，有较好的响应时间（1）短作业一次完成；（2）中型作业周转时间不长；（3）大型作业不会长期不处理。,调度算法,有5个批处理作业（A、B、C、D、E）几乎同时到达，估计的运行时间分别为2、4、6、8、10分钟，它们的优先数分别为1、2、3、4、5（1为最低优先数）。对下面的每种调度算法，分别计算作业的平均周转时间。（1）最高优先级优先。（2）时间片轮转（时间片为2分钟）。（3）FIFO（作业的到达顺序为C、D、B、E、A）（4）短作业优先。,调度算法,练习,内 容,产生死锁的原因和必要条件,多处理机系统中的调度,实时调度,调度算法,处理机调度的基本概念,预防死锁的方法,死锁的检测与解锁,实时调度,实时调度所具备的基本条件必要的基本信息就绪时间开始截止时间和完成截止时间处理时间资源要求优先级系统处理能力强若不够强，某些实时任务得不到及时处理，导致难以预料的后果采用抢占式调度机制保证实时任务对截止时间的要求；如果能预知任务的开始截止时间，对实时任务可采用非抢占调度机制；具有快速切换机制,实时调度算法的分类 按照调度方式的不同对调度算法进行分类非抢占式调度算法简单，易于实现，应用在小型实时系统或要求不太严格的实时控制系统中。非抢占式轮转调度算法实时任务到达时，插入就绪队列队尾非抢占式优先调度算法实时任务具有较高优先权，当到达时插入 就绪队列队首,实时调度,进程1,进程2,进程n,实时进程,调度时间,实时进程要求调度,调度实时进程运行,a 非抢占轮转调度,当前进程,实时进程,实时进程要求调度,当前进程运行完成,b 非抢占优先权调度,调度时间,实时调度,实时调度算法的分类抢占式调度算法用于要求比较严格的实时系统中，响应时间为数十毫秒以下。根据抢占发生时间的不同而进一步分成以下两种调度算法：基于时钟中断的抢占式优先权调度算法某实时任务到达时，若该任务优先级高于当前任务优先级，并不立即抢占，而是等到时钟中断到来时立即抢占的优先权调度算法见下页举例视图,实时调度,实时调度,c 基于时钟中断抢占的优先权抢占调度,当前进程,实时进程,实时进程要求调度,时钟中断到达时,调度时间,当前进程,实时进程,实时进程要求调度,抢占时刻（其它中断）,d 立即抢占优先权调度,调度时间,常用的几种实时调度算法最早截止时间优先根据任务的开始截止时间来确定任务的优先级截止时间越早，优先级越高可以是抢占式或非抢占式,实时调度,图37 EDF算法用于非抢占调度方式,1,3,4,2,1,3,4,2,1,2,3,4,t,开始截止时间,任务到达,任务执行,常用的几种实时调度算法最低松弛度优先调度算法松弛度=必须完成时间 本身运行时间 当前时间 按松弛度确定优先权，松弛度越低，优先权越高 主要用于可抢占的调度方式中例如：若A进程需在200ms时完成，其本身运行需要100ms，当前时刻是10ms，则A的松弛度为：2001001090,实时调度,实时调度,例题：若有三个周期性任务，任务A要求每20ms执行一次，执行时间为10ms；任务B要求每50ms执行一次，执行时间为10ms；任务C要求每50ms执行一次，执行时间为15ms，应如何按LLS对它们进行CPU调度。,B1,A2,A5,A1,A3,A2,B2,A4,B3,B1,C1,A3,A4,A5,0,10,25,35,55,45,70,80,90,100,A1=10B1=40C1=35,A2=5B1=15,A3=5,A4=0B2=20,A5=0,A6=10B3=40C3=35,B1=30C1=25,B2=35C2=30,B2=10A5=10,B1=5,到达时间,必须完成时间,松弛度,A1,C1,C2,C3,A6,B2,C2,0,10,25,35,55,45,70,80,90,100,A1,C1,A2,B1,A3,C2,A4,B2,A5,任务执行,内 容,产生死锁的原因和必要条件,多处理机系统中的调度,实时调度,调度算法,处理机调度的基本概念,预防死锁的方法,死锁的检测与解锁,多处理机系统中的调度,多处理机系统的类型紧密耦合MPS和松弛耦合MPS紧密耦合共享主存储器系统和I/O设备高速总线和交叉开关连接主存储器划分为若干独立访问的存储器模块，以便多个处理机能对主存进行同时访问松弛耦合每台都有自己的存储器和I/O设备通道和通信线路连接对称多处理器系统和非对称多处理器系统处理器是否结构相同,进程分配方式对称MPS系统中进程分配方式由于结构相同，可将进程分配到任一处理器上运行把处理器作为一个处理器池，将进程分配到任一处理器静态：一个进程从开始执行直到其完成，都被分配到一个固定的CPU上去执行，此时需要配置一个专用就绪队列,多处理机系统中的调度,cpu1,cpu2,cpun,专1,专2,专n,优点：调度开销小 缺点：忙闲不均,多处理机系统中的调度,进程分配方式对称MPS系统中进程分配方式动态：一个进程从开始执行直到其完成，都被分配到不同的CPU上去执行，此时需要配置一个专用就绪队列,cpu1,cpu2,cpun,公用就绪队列,优点：解决了忙闲不均问题 缺点：对松散耦合的MPS，需保存现场信息,多处理机系统中的调度,进程分配方式非对称SMP中进程分配方式大多数采用主从式结构，即核心部分驻留在一台主机上，从机上只是用户程序，进程调度只由主机执行从机空闲时，向主机发送请求信号，等待主机为它分配进程主机中保持有一个就绪队列，只要不空，便从队首摘下一进程分配给请求的从机优点：系统处理简单，因为所有进程都由一台主机独自处理缺点：主处理机故障会导致系统瘫痪,主机（os核心）,从机（用户程序）,从机（用户程序）,从机（用户程序）,就绪队列,多处理机系统中的调度,进程（线程）调度方式自调度方式直接由单处理机环境下的调度方式演变而来的所有处理器空闲时都可以到公共就绪队列中去取得一进（线）程来运行可采用FCFS,FPF和抢占式FPF优点可延用单处理器系统队列组织方法和进（线）程调度方法；不会忙闲不均缺点瓶颈问题 多个处理器共享一个就绪队列低效性 阻塞后重新获得处理器，重新建立数据拷贝多个合作线程切换频繁，难以同时获得处理器而同时运行,多处理机系统中的调度,进程（线程）调度方式成组调度方式用来解决自调度方式中线程被频繁切换的问题定义：将一个进程中的一组线程，分配到一组处理器上去执行。如何为应用程序分配处理器时间，有两种分配方式面向所有应用程序平均分配处理器时间假定系统中有N个处理器和M个应用程序，每个应用程序至多含有N个线程，则每个应用程序至多可有1/M的时间去占用N个处理器。,处理器1,处理器2,处理器N,线程1线程2线程N,应用程序1,线程1线程2线程N,应用程序2,线程1线程2线程N,应用程序M,多处理机系统中的调度,进程（线程）调度方式成组调度方式用来解决自调度方式中线程被频繁切换的问题定义：将一个进程中的一组线程，分配到一组处理器上去执行。如何为应用程序分配处理器时间，有两种分配方式面向所有应用程序平均分配处理器时间假定系统中有N个处理器和M个应用程序，每个应用程序至多含有N个线程，则每个应用程序至多可有1/M的时间去占用N个处理器。,处理器1,处理器2,处理器N,线程1线程2线程N,应用程序1,线程1线程2线程N,应用程序2,线程1线程2线程N,应用程序M,多处理机系统中的调度,进程（线程）调度方式成组调度方式如何为应用程序分配处理器时间，有两种分配方式面向所有应用程序平均分配处理器时间例子,浪费37.5%,（1/2*3/4）,多处理机系统中的调度,进程（线程）调度方式成组调度方式如何为应用程序分配处理器时间，有两种分配方式面向所有线程平均分配处理器时间例：由于应用程序A中有4个线程，B中有一个线程，因此应用程序A分配4/5的时间，B分配1/5的时间,浪费15%,（1/5*3/4）,多处理机系统中的调度,进程（线程）调度方式成组调度方式主要优点一组相互合作的进程或线程，能并行执行，减少阻塞，减少线程切换；每次调度可以解决一组线程的处理器分配问题，减少调度频率，减少调度开销。结论：成组调度方式优于自调度，目前获得广泛认可，并应用到许多种处理机系统中,多处理机系统中的调度,专用处理器分配方式在每个应用程序执行期间，每个线程一个处理器处理机严重浪费，但仍用于并发程度相当高的 MPS环境。原因如下在具有数十乃至数百个处理器的高度并行的系统中，每个处理器投资费用只占很小一部分，单个处理器的利用率已远不像在单机环境中那么重要。在一个应用程序的整个运行过程中，由于每个进程或线程专用一台处理器，因此可以完全避免进程或线程的切换，从而大大加速了程序的运行,内 容,产生死锁的原因和必要条件,多处理机系统中的调度,实时调度,调度算法,处理机调度的基本概念,预防死锁的方法,死锁的检测与解锁,产生死锁的原因和必要条件,死锁（Deadlock）1965年由Dijkstra 发现是指多个进程在运行过程中因争夺资源而造成的一种僵局（Deadly-Embrace）,当进程处于这种僵持状态，若无外力作用，它们都将无法再向前推进。多个wait,signal操作顺序不当，会产生进程死锁,产生死锁的原因和必要条件,产生死锁的原因竞争资源资源数目不足资源分可剥夺资源非剥夺资源进程间推进顺序不当请求资源和释放资源的顺序不当,产生死锁的原因和必要条件,P1Req(R1),P1Req(R2),P2Req(R1),P2Req(R2),P1Rel(R1),P1Rel(R2),P2Rel(R1),P2Rel(R2),P1,P2,D,曲线1：安全曲线2：安全曲线3：安全曲线4：不安全,D：不安全区,产生死锁的原因和必要条件,产生死锁的必要条件,互斥条件 进程对分配到资源排它使用,请求和保持条件 进程至少保持了一个资源但又 提出新的资源要求，该资源已被其它进程占有，此时进程阻塞，但对自己已获得的资源并不放弃。,不剥夺条件 已获资源未使用完，不能被剥夺,环路等待条件 必存在进程资源的环形链,二.,产生死锁的原因和必要条件,忽略此问题不做任何实际处理(鸵鸟策略),设计无死锁的系统,允许出现死锁排除之,预防死锁(deadlock prevention),避免死锁(deadlock avoidance),死锁检测(deadlock detection),死锁恢复(deadlock recovery),处理死锁的基本方法,产生死锁的原因和必要条件,处理死锁的方法 按处理时间划分预防死锁系统运行前，通过某些限制条件，去破坏一个或者几个限制条件，来预防死锁方法的广泛使用缺点：限制太严格，可能会导致系统资源利用率和吞吐量降低避免死锁在动态分配过程中，使用某种方法防止系统进入一种不安全状态加以限制条件较弱，可获得较高资利和系吞，避免死锁有一定难度，效果好,产生死锁的原因和必要条件,处理死锁的方法检测死锁允许发生死锁，通过检测确定出与死锁有关的进程和资源，然后清除死锁解除死锁检测后，撤销或挂起某些进程，回收部分资源给阻塞或者就绪进程，实现难度较大,内 容,产生死锁的原因和必要条件,多处理机系统中的调度,实时调度,调度算法,处理机调度的基本概念,预防死锁的方法,死锁的检测与解锁,预防死锁的方法,预防死锁方法使四个条件之一不能成立,但除1外，因为互斥条件是设备固有条件决定的，应该保持摒弃“请求和保持”条件运行之前，必须一次性地申请运行过程所需要的全部资源这样运行期间不会再提出资源要求，摒弃“请求”条件分配资源时，只要有一种不满足要求，一个也不分配给该进程等待时，并不保持任何资源，摒弃“保持”条件优点：简单，易于实现，且很安全缺点：有些资源已被长期利用而使该进程迟迟不能运行,预防死锁的方法,预防死锁方法摒弃“不剥夺”条件进程已占用的资源，因申请新资源未成功而暂时释放掉摒弃“不剥夺”条件缺点：付出代价大；前功尽弃摒弃“环路等待”条件为资源编号所有进程对资源请求严格按次序提出占用较高资源的进程，它以后申请的资源一定是空闲的优点：资利和系吞明显提高问题：（1）序号相对稳定，限制了新设备增加（2）作业使用资源顺序与系统规定不同（3）限制了用户简单而自主编程,预防死锁的方法,避免死锁该方法中，系统状态分为安全状态和不安全状态，只要能使系统都处于安全状态，便可避免死锁发生。安全状态：是指系统能按某种进程顺序，来为每个进程分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。,预防死锁的方法,安全状态之例假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：,2,步骤：1.取2台给P2,4,P2可以执行完，释放4个资源,2.取5台给P1,P1可以执行完，释放10个资源,3.取7台给P3,P3可以执行完，释放9个资源,10,1,5,5,9,0,10,3,12,预防死锁的方法,3.由安全状态向不安全状态的转换,步骤：1.取1台给P3,2,2.分给P2，运行完释放4个,0,3.P1？,4,4,预防死锁的方法,避免死锁利用银行家算法来避免死锁Dijkstra；用于银行系统先进贷款的发放而得名银行家算法中的数据结构可利用资源向量Available-银行现金数含m个元素的数组，Availablej=k表示j类资源有k个。最大需求矩阵Max定义了系统中n个进程中的每一个进程对m类资源的最大需求nm矩阵，Maxi,j表示进程i对j类资源的最大需求量。,银行家算法中的数据结构分配矩阵Allocation已分配给每一进程的资源数nm矩阵，Allocationi,j表示进程i已获得的j类资源数。需求矩阵Need一个进程尚需的各类资源数 Need=Max-Allocationnm矩阵，Needi,j表示进程i还需要的j类资源数。,预防死锁的方法,预防死锁的方法,避免死锁银行家算法描述Requestij=K，表示进程Pi需要K个Rj类型的资源，系统按下述步骤进行检查：(1)如果RequestijNeedi,j，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。(2)如果RequestijAvailablej，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。,预防死锁的方法,避免死锁银行家算法描述(3)尝试分配给进程Pi，并修改下面数据结构中的数值：Availablej=Availablej-Request ij;Allocationi,j=Allocationi,j+Request ij;Needi,j=Needi,j-Request ij;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。,预防死锁的方法,避免死锁安全性算法(1)设置两个向量：Work，银行现金数，Work=Available;Finish:是否有足够的资源使之运行完成初始Finishi=false;当有足够资源分配给进程时，再令Finishi=true(2)从进程集合中找到一个能满足下述条件的进程：Finishi=false;Needi,jWorkj；若Y，执行(3)；N，执行(4);,预防死锁的方法,避免死锁安全性算法(3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Workj=Worki+Allocationi,j;Finishi=true;go to step 2;(4)如果所有进程的Finishi=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。银行家算法之例 假定系统中有五个进程P0,P1,P2,P3,P4和三类资源A,B,C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图 3-15 所示。,预防死锁的方法,银行家算法之例 T0时刻的资源分配表,7 4 3,1 2 2 6 0 0 0 1 1 4 3 1,3 3 2,预防死锁的方法,银行家算法之例初始分配后第一次安检,T0时刻的安全序列,3 3 2,5 3 2,true,true,true,true,true,5 3 2,1 2 2 2 0 0,0 1 1 2 1 1,7 4 3,7 4 3 4 3 1 0 0 2 7 4 5 7 4 5 6 0 0 3 0 2 10 4 7 10 4 7 7 4 3 0 1 0 10 5 7,p1,p3,p4 p2 p0,预防死锁的方法,银行家算法之例P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查 Request1(1,0,2)Need1(1,2,2)Request1(1,0,2)Available1(3,3,2)（共4个步骤）尝试分配，并修改Available,Allocation1和Need1向量，由此形成的资源变化情况下图 中的圆括号所示（共4步）,预防死锁的方法,银行家算法之例,(3 0 2),(0 2 0),(2 3 0),预防死锁的方法,银行家算法之例 P1申请资源(1,0,2)时安全性检查(安全)(共4步),预防死锁的方法,银行家算法之例P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查：Request4(3,3,0)Need4(4,3,1);Request4(3,3,0)Available(2,3,0)，让P4等待。在P0请求资源：P0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查：Request0(0,2,0)Need(7,4,3);Request0(0,2,0)Available(2,3,0);系统暂时先假定可为P0分配资源，并修改有关数据，如下图 所示。,预防死锁的方法,银行家算法之例为P0分配（0，2，0）后的情况（不安全）结论：利用该算法可以判断每次分配是否安全，以保证系统处于安全状态,内 容,产生死锁的原因和必要条件,多处理机系统中的调度,实时调度,调度算法,处理机调度的基本概念,预防死锁的方法,死锁的检测与解锁,死锁的检测与解锁,死锁检测所有简化顺序，都能得到相同不可简化图死锁定理：S的资源分配图不可完全简化，则S为死锁死锁解除剥夺资源撤消进程,小 结,死锁产生的原因：竞争资源；进程间推进顺序不当,预防死锁：摒弃三个条件 摒弃“请求与保持”：一次申请全部资源；只要一种不满足，一个也不分配；摒弃“不剥夺”：新资源不能满足，必须释放已保持所 有资源；摒弃“环路等待”：为资源编号，按序号申请。并了解各摒弃条件的优缺点避免死锁：使系统在运行过程中，始终处于一种安全状态。每个进程申请资源时，经检查后安全则分配，否 则 不分配 方法：银行家算法，步骤如下,小 结,避免死锁 方法：银行家算法，步骤如下,初始分配并安检；,进程1请求资源：（1）（2）（3）（4）,进程2请求资源：（1）（2）（3）（4）,死锁定理：S状态时，资源分配图不可完全化简，则S为死锁状态,死锁解除,剥夺资源,撤销进程,