《调度与死锁》PPT课件.ppt

第4章调度与死锁,调度类型与准则,调度算法,死锁的预防与避免,死锁的基本概念,死锁的检测与解除,2,调度是操作系统的基本功能，几乎所有的计算机资源在使用之前都要经过调度。CPU是计算机中最主要的资源，经过调度，才把CPU分配给合适的资源。进程调度是多道程序运行的根本，通过进程之间的切换CPU,操作系统才可以提高计算机的效率。操作系统必须为多个进程分配计算机资源。对于处理机而言，可分配的资源是在处理机上的执行时间。处理机是操作系统中的重要资源，处理机调度算法不仅对处理机的利用率和用户进程的执行有影响，同时还与内存等其他资源的使用密切相关，对整个计算机系统的综合性能指标也有重要影响。,处理机？,3,处理机processor计算机系统中存储程序和数据，并按照程序规定的步骤执行指令的部件。程序是描述处理机完成某项任务的指令序列。指令则是处理机能直接解释、执行的信息单位。处理机包括中央处理器，主存储器,输入-输出接口。处理机加接外围设备就构成完整的计算机系统。,4.1调度类型与准则,在多道程序系统中，内存中有多个进程，每个进程或者正在使用处理机，或者正在等待I/O的执行或其他事情的发生。处理机执行某个进程而保持忙碌状态，而此时其他进程处于等待状态。多道程序的关键是调度。处理机的调度有三种：高级调度、中级调度和低级调度。,4.1调度类型与准则,调度类型高级调度低级调度中级调度,6,调度的层次,又称作业调度、宏观调度任务：决定将外存上后备队列中的哪些作业调入内存。调度工作决定接纳多少作业：取决于多道的程度，即内存允许放多少个作业。接纳哪些作业：有调度算法决定。适用于批处理系统,又称进程调度、微观调度任务：决定就绪队列中的哪些进程将获得处理机。调度方式非剥夺式剥夺式抢占原则时间片优先权进程长短适用于分时、实时、批处理系统,又称对换程序主要作用：内存和外存对换区之间进行进程对换，以解决内存紧张问题。,7,进程调度方式,不可剥夺方式不可剥夺方式也被称为非抢占方式。采用这种调度方式时，一旦把处理机分配给某个进程，该进程将一直执行下去，直到运行完毕或因某种原因不能运行，才把处理机分配给其它进程，决不允许其它进程强占正在运行进程占有的处理机。优点：实现简单、系统开销小，适用于批处理系统。缺点：但是难以满足有紧急任务的进程要求，不适用对时间要求比较严格的实时系统。,8,进程调度方式,可剥夺方式可剥夺方式也被称为抢占方式。在这种方式下，允许一个进程按照某种原则，抢占其它进程占有的处理机。抢占采用优先权原则的比较多，也就是说，如果一个进程比正在运行进程的优先级高，则它可以抢占处理机而运行。,9,进程调度时机,进程退出：当一个进程退出时必须进行调度。因为进程退出后CPU空闲必须从就绪队列中选择一个进程投入运行。如果没有就绪进程，通常操作系统提供空转进程。进程阻塞：当进程由于等待I/O、信号或其他原因而放弃CPU时，就必须选择另一个进程运行。,10,进程调度时机,在另一些情况下，尽管在逻辑上不是必须的，但还是会经常发生：新进程创建：在新进程创建时，新进程的优先级可能高于正在运行的进程，在可剥夺方式下，进程调度程序需要决定是否让新进程投入运行。中断发生：当I/O设备完成了其他工作而发出I/O中断时，原来等待该设备的那个进程就会从阻塞状态变为就绪状态，此时，进程调度程序要决定是否选择该进程投入运行。时钟中断：时钟中断发生时，有可能一个进程运行的时间片到了，进程调度程序要决定是否选择其他进程投入运行。,11,调度的性能准则,面向用户的准则响应时间快响应时间：从用户通过键盘提交请求到首次得到响应的时间周转时间短：周转时间：作业从提交到完成的时间间隔。优先权准则：按照进程的紧急程度、进程的大小、进程的等待时间等多种因素给每个进程规定一个优先级，系统调度室，安装优先级的高低选择进程截止时间的保证：包括截止开始时间和截止完成时间,12,周转时间定义,周转时间Ti：一个用户作业被提交到完成的时间间隔。平均周转时间带权周转时间平均带权周转时间,13,调度的性能准则,面向系统的准则系统吞吐量单位时间内完成的作业数。处理机利用率一般系统中处理机的利用率是40%-90%各类资源平衡利用一个好的调度算法应尽可能使系统中的所有资源都处于忙碌状态。公平在没有用户或者系统的特殊要求时，进程应该被公平地对待，尽量避免进程“饿死”。,14,调度算法是指根据系统的资源分配策略所规定的资源分配算法。对于不同的系统目标，通常采用不同的调度算法。下面介绍一些常用的算法。,4.2调度算法,15,先来先服务调度算法（FCFS）短作业（进程）优先调度算法(SJF)时间片轮转调度算法(RR)优先权调度算法多级反馈队列(MFQ),4.2调度算法,16,先来先服务FCFS,算法思想对于作业调度，从后备作业中选择最先进入该队列的作业，将他们调入内存，为它们分配资源、创建进程，然后放入就绪队列。对于进程调度，从就绪队列中选择最先进入该队列的进程，分配处理机，使之运行。特点易于实现有利用长作业，不利于I/O繁忙的作业。,17,短作业优先SJF,算法思想短作业优先是从后备队列中选择估计运行时间最短的作业，将它们调入内存。短进程优先是从就绪队列中选择估计运行时间最短的进程，将处理机分配给它，使之执行并一直到完成或因发生某事件而阻塞放弃处理机时，再重新调度。特点极端情况下，长作业得不到调度。作业或进程的长短只能估计，不准确。完全不考虑紧迫程度，使紧急事件得不到处理。,18,FCFS与SJF比较,周转时间=完成时间-到达时间带权周转时间=周转时间/服务时间,19,时间片轮转调度算法(RR),算法思想进程按FCFS在就绪队列排队，调度程序把CPU分配给队首进程，令其执行一个时间片，一个时间片执行完毕将进程排在队尾，同时从就绪队列首，选择另一个进程运行。时间片轮转法中，时间片的长度是影响算法的一个主要指标，可以考虑两种极端的情况，如果时间片很长，长到大多数进程在一个时间片内都能够完成，该算法就退化为FCFS.,20,时间片轮转调度算法(RR),算法思想相反，如果时间片很短，短到用户的一次交互需要几次调度才能完成，系统切换的频率很高，频繁的系统切换会导致用户程序响应时间的增长。因此，时间片的长度的选择要适当，一般要保证一个基本的交互过程在一个时间片内完成。,21,时间片轮转调度算法(RR),时间片大小的确定响应时间T=进程数目N*时间片q响应时间T当N一定，T与q成正比。T若要求快，则q也要小。就绪队列的进程数NT一定，q与N成反比。N越多，q要小。系统的处理能力保证用户键入的常用命令能在一个时间片内处理完毕。,22,时间片大小,23,系统处理能力比较,24,算法思想从后备队列中选择若干优先权最高的作业，将它们调入内存。或从就绪队列中选择优先权最高的进程，将处理机分配给它。进程调度中使用优先权调度算法时又可把算法分成两种方式：可剥夺方式和不可剥夺方式可剥夺方式：系统吧处理机分配给优先权最高的进程，使之运行。一旦系统中出现另一个优先级更高的进程，调度程序将停止正在运行的进程，把处理机分配给新出现的优先权更高的进程。,优先权调度算法,25,进程调度中使用优先权调度算法时又可把算法分成两种方式：可剥夺方式和不可剥夺方式不可剥夺方式：当系统中出现比现在运行的进程优先级更高的进程时，不会剥夺正在运行进程对处理机的占有，该进程会一直运行下去，直到完成，或因发生某种事件放弃处理机。,优先权调度算法,26,优先权确定的方式静态优先权在进程创建时确定该进程的优先权，且该进程的优先权在其整个运行期间保持不变。确定因素：进程类型、进程对资源的需求、用户要求。系统进程的优先权通常高于用户进程；对处理机和内存等资源要求较少的进程具有较高的优先权,优先权调度算法,27,优先权确定的方式动态优先权指进程的优先权可以根据进程的不断推进而改变，以期得到更好的性能。确定因素：进程的等待时间、占有处理机的时间，具体的说，随着进程等待时间的增加，该进程的优先权将以某种速率增加这样的目的是使优先权较低的进程在等待足够的时间后，其优先权提高，进而被调度执行；,优先权调度算法,28,优先权确定的方式动态优先权当一个进程占有处理机的时间不断增长是，其优先权会以某种速率降低。目的是使持续执行的进程在运行一段时间后将处理机让给其他进程，以防止一个进程长期垄断占有处理机。,优先权调度算法,29,算法思想根据作业的性质和类型不同，将就绪队列再分为若干个子队列，每个进程分属于一个队列。在多级队列的基础上，不但设多个队列，且为每个队列赋予不同的优先权，第一个队列的优先权最高，第二个队列次之，其余队列的优先权逐个降低。各个队列中的进程执行时间片大小逐渐增大。新进程投入第一个队列。调度从第一个队列进行，仅当第一个队列为空时，才调度第二个队列中的进程。,多级反馈队列调度算法,30,多级反馈队列调度算法,31,多级反馈队列调度算法,在实际系统中，还可以使用更复杂的动态优先级调整策略。例如：为了保证I/O操作能及时完成，可以在进程发出I/O请求后进入最高优先权队列，并执行一个时间片，以及时响应I/O交互。,32,4.3死锁的基本概念,死锁是发生在一组相互合作或竞争的线程或进程中的一个问题。在同步问题中很容易死锁。通常情况下，死锁发生在两个或多个不同程序对应的进程或线程同时执行时，相同程序对应的多个进程或线程由于一些复杂资源的使用也会发生死锁。,33,4.3死锁的基本概念,34,4.3死锁的基本概念,死锁不像并发进程管理的其他问题，这类问题没有一种有效的通用的解决方案。死锁涉及两个或更多的进程因对资源的需求所引起的冲突。,35,产生死锁的原因,资源数要求该种资源的进程数进程的推进顺序非法,进程Pget(A);get(B);release(A);release(B);,进程Qget(B);get(A);release(B);release(A);,A、B分别代表某种资源,36,进程的推进顺序不当,死锁,(1)、(2)、(4)、(5)正常运行(3)、(6)发生死锁,37,进程的推进顺序合适,不死锁,进程P对资源的申请、释放次序改变后不死锁！,38,交换P操作的位置,voidproducer()/生产者进程while(true)produceanitemindata_p;P(empty);P(mutex);bufferi=data_p;i=(i+1)%n;V(mutex);V(full);,voidconsumer()/消费者进程while(true)P(mutex);P(full);data_c=bufferj;j=(j+1)%n;V(mutex);V(empty);consumetheitemindata_c;,？,消费者先行死锁！因full初始值为0，不能再进行P(full),39,产生死锁的四个必要条件,不剥夺条件,互斥条件,请求保持条件,环路条件,40,产生死锁的四个必要条件,互斥条件：指进程对所分配的资源进行排他性使用，即在一段时间内某资源只能有一个进程占有。请求和保持：进程已经占有了至少一个资源，但又提出了新的资源请求，而该资源已经被其他进程占有，此时进程阻塞，但对已经获得的资源保持不变。不可剥夺条件：进程已经获得了资源，在它使用完毕前，不能被剥夺，只能使用完毕自己释放。环路条件：在一个进程与资源的环链。在该链中，每一个进程都正在等待一个被占用的资源。,41,互斥是资源的固有属性，如对于文件，可以允许多个进程同时读，但不允许多个进程同时写，必须做到写互斥。对于软件资源是这样，对于某些硬件资源更是如此，打印机，只能等到一个进程使用完毕，另一个进程才可以使用。打印机的使用也必须是互斥的。,互斥条件不可禁止,死锁的预防,4.4死锁的预防与避免,42,采用预先静态分配方法系统要求所有进程一次性地申请其所需的全部资源，如资源不足，就阻塞这个进程，直到所有的请求都得到满足为止。优点：方法简单缺点：进程延迟运行资源浪费用户有时提不出他要使用的全部资源,死锁的预防,4.4死锁的预防与避免,去掉“请求保持条件”,43,方法占有某些资源的进程，当它有新的资源请求被拒绝时，该进程停止运行，并释放它所占有的资源。当它再次被执行时，重新申请资源。如果一个进程请求另一个进程占有的资源，操作系统可以剥夺后者占有的资源，要求它释放资源并将资源分配给前者使用。,死锁的预防,4.4死锁的预防与避免,去掉“不剥夺条件”,44,缺点该策略实现起来比较复杂，而且要付出很大代价。反复申请、释放，使进程执行无限延迟，不仅延迟了周转时间。还增加了系统开销，降低了系统吞吐量。,死锁的预防,4.4死锁的预防与避免,去掉“不剥夺条件”,45,去掉“环路“条件,采用资源的有序分配令所有资源排队，并赋予不同的序号。当进程请求资源时，必须严格按递增的次序提出，从而消除了环路。缺点：定好序号后，增加新设备类型受到限制。尽管定序号时考虑大多数作业使用资源的顺序。但会发生使用顺序与规定顺序不一致的情况，造成资源浪费。限制用户简单、自主地编程。,死锁的预防,4.4死锁的预防与避免,46,死锁的预防措施低效！,死锁的预防,4.4死锁的预防与避免,47,安全状态是指系统至少存在一个安全序列，按照这个序列为进程分配资源，直到满足最大需求，每个进程都可顺序完成。若系统不存在这样一个安全序列，则系统处于不安全状态。,避免死锁是通过明智的选择，确保系统永远不会到达死锁点。即动态地决定是否分配资源给进程！,死锁的避免,48,系统有三个进程P1、P2、P3，共有12台磁带机，进程P1要求10台，P2要求4台，P3要求9台。在T0时刻，进程P1、P2、P3已获得5、2、2台，尚有3台未分配，问：系统是否处于安全状态？,存在安全序列,！,安全状态,49,银行家算法,进行资源预分配实施安全检测安全：真正资源分配不安全：回到预分配前状态,算法描述,50,安全状态,实例,(a)初始状态：4个进程3类资源(b)让P1运行，不行让P2运行，OK(c)让P1运行，OK(d)让P3运行，OK存在安全序列,51,不安全状态,图（a）定义的矩阵，假设P2请求1个R1和1个R3，如果同意了这个请求，系统的状态回到上图的（a），前面已经分析了这是一个安全状态。但假如在图（a）的状态下P1请求1个R1和1个R3，如果满足P1的请求，则系统就有了图2-31（b）的状态，状态(b)是不是安全呢？答案是：不安全。,实例,！,52,检测死锁的基本思路是：系统保存资源请求和分配信息，利用某种算法对这些信息加以检查，以判断系统是否出现了死锁。资源分配图死锁检测算法主要是检查系统中的进程是否有循环等待。把系统中进程和资源的申请和分配情况描述成一个有向图，通过检查有向图中是否有循环来判断死锁的存在。具体地说，有向图的顶点有两类：一类是资源，另一类是进程。,4.5死锁的检测与解除,53,资源分配图该图是由一组结点N和一组边E组成的一对偶G=（N，E）N被分成两个互斥的子集，一组进程结点P=p1,p2,pn，一组资源结点R=r1,r2,rn，N=PUR凡属于E中的一个边eE，都连接着P中的一个结点和R中的一个结点，e=pi,rj是资源请求边，由进程pi指向资源rj，它表示进程pi请求一个单位的资源rj。e=rj，pi是资源分配边，由资源rj指向进程pi，它表示一个单位的资源rj分配给进程pi。,4.5死锁的检测与解除,死锁的检测,54,在图中找出一个既不阻塞又非独立的进程结点pi，消去pi所有的请求边和分配边，使之成为孤立结点。在进行一系列简化后，能消去图中所有的边，使所有进程都成为孤立结点，则称该图是可以完全简化的，否则若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。,当且仅当S状态的资源分配图是不可完全简化的，S为死锁状态。,资源分配图的简化,55,死锁的解除,撤消所有死锁进程：撤消的原则是为解除死锁状态所需撤消的进程数目最小。撤消进程所付出的代价最小把每个死锁的进程恢复到前面定义的某个检查点，并重新运行这些进程。