处理机调度与死锁.ppt
操作系统的性能在很大程度上取决于处理机调度性能的好坏，因而，处理机调度便成为操作系统设计的中心问题之一。,第四章 处理机调度与死锁,提高处理机的利用率及改善系统性能（吞吐量、响应时间）是处理机调度的主要目标。在多道程序环境下，进程数目往往多于处理机数目。这就要求系统能按照某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。本章主要讲述各种常用调度算法及评价；介绍死锁及其解决的办法。,4.1调度的基本概念,4.2调度算法,4.3实时调度算法,4.4 多处理机调度,本章主要内容,4.5死锁,4.6 解决死锁问题的方法,4.1.1 作业的状态及概念,1.作业：在一次应用业务处理过程中，从输入开始到输出结束，用户要求计算机所做的有关该次业务处理的全部工作为一个作业。如：用语言编制一个程序，系统完成如下工作：编辑 编译 链接 执行以上几个步骤总和就是一个作业。,3.作业的组成：由程序、数据和作业说明书组成。微机中：批处理文件或SHELL程序方式编写作业说明书。,2.作业步：作业步是在一个作业的处理过程中，计算机相对独立的工作。,4.1 调度的基本概念,作业说明书的主要内容,4.作业的状态及其转换,不同的阶段对应不同的状态：后备状态执行状态完成状态,分级调度,4.1.3 进程调度的功能和时机,4.1.4 调度原则与性能衡量,周转时间：,平均周转时间：,平均带权周转时间：,作业调度、中级调度、进程调度、线程调度,CPU周期；调度方式：剥夺方式和非剥夺方式,公平、有效、高吞吐量、及时响应、支持优先,响应时间、截止时间,4.2调度算法,4.2.1 先来先服务FCFS(First-come-First-Serverd),优点：实现简单，有利于长作业和CPU繁忙的进程缺点：使短作业等待长作业，重要的作业等待可能不是很重要的长作业，不能用于分时和实时系统。,4.2.2 短作业优先SF(Shortest-job/Process First),优点：有利于短作业或短进程。降低了作业的平均等待时间，提高了系统的吞吐量。缺点：用户可能有意或无意地缩短作业的估计执行时间，致使该算法不一定能真正做到短作业优先；,4.2.3 最高响应比优先HRN(Hight-Response-Next),R响应时间/需运行的时间1已等待的时间/需运行的时间,优点：HRN既照顾了短作业，也考虑了长作业；缺点：每次进行调度前，都要进行响应比计算，会增加系统的开销；不能满足紧迫作业或进程的需要。,4.2.4 优先权优先HPF(Highest-Priority-First),T23.5(ms)W3(ms),T26(ms)W3.89(ms),优点：可以使紧迫的任务得到优先执行。缺点：静态优先级易于实现，系统开销小，但作业或进程的优先级不够精确；动态优先级须计算优先级，增加系统的开销。,4.2.5 轮转法RR(Round Robin),4.2.6 多级反馈队列算法MF(Multiple Feedback),q=R/Nmax,优点：可以使用户得到及时的响应和服务。缺点：短进程用户和I/O繁忙型进程是不利的。特别是，当“紧迫型”的进程到来时，并不能及时的得到处理。,MF算法可以较好地协调长进程和短进程的执行。,4.3实时调度算法,4.3.1 实时系统的特点计算结果的正确性、时限、周期与非周期任务；快速的切换机制与抢占式的调度策略。,4.3.2 实时系统常用调度算法 1频率单调调度RMS（Rate-Monotontic Scheduling）算法 2最早截止优先EDF（Earliest-Deadline-First）算法 3最低松驰度优先LLF（Least-laxity-First）算法,4.4多处理机调度,4.4.1 多处理机系统的类型,4.4.2 多处理机系统调度方式,1紧密耦合MPS和松弛耦合MPS,2对称多处理器系统和非对称多处理器系统,1.非对称多处理机系统调度方式,2对称多处理机系统调度方式自调度和组调度,4.5.1 死锁的产生,1什么是死锁,2产生死锁的原因:系统资源不足，进程推进顺序不恰当,4.5死锁,死锁是指一组并发进程彼此互相等待对方所拥有的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源，从而使并发进程不能继续向前推进的状态。陷入死锁状态的进程称之为死锁进程。,4.5.2 死锁的必要条件,（1）互斥条件。指进程竟争的资源具有互斥性，即在一段时间内某资源被一个进程占用，如果此时还有其它进程请求使用该资源，则只能等待，直到占用该资源的进程用完后主动释放。（2）不可剥夺条件（不可抢占条件）。指已分配给某一进程的资源，在它未使用完之前，不能强行剥夺，只能在使用完后，由进程自己释放。（3）部分分配条件（请求与保持条件）。指进程已经占用了一部分资源，但又提出新的资源请求，而该资源又被其它的进程所占用，此时请求进程只能阻塞，但又对自己占用的资源保持不放。（4）环路条件（循环等待条件）。指进程发生死锁时，必然存在一个进程资源的环形链。即一组进程P1，P2，Pn，其中，P1正在等待P2占用的资源；P2正在等待P3占用的资源，Pn正在等待P1占用的资源。图47所示为两个进程竟争两个资源的环形链图。,4.6.1 死锁的预防,1防止“部分分配”条件的出现,2防止“环路等待”条件的出现,4.6.2 死锁的避免,1安全状态,T存在安全序列（p2，p1，p3），系统处于安全状态。,此时，系统进入不安全状态。,4.6解决死锁的方法,2银行家算法,（1）数据结构 银行家算法中用到下列数据结构，令n是系统中的进程数，m是资源类数。可用资源向量A（Available）。向量A的长度为m，向量元素Aj(j=1，2，m)为系统中资源类rj的当前可用数。最大需求矩阵M（Max）。M是一个nm的矩阵，矩阵元素Mi,j为进程pi关于资源类rj的最大需求数，每个进程必须预先申报。资源占用矩阵U（Use）。U是一个nm的矩阵，矩阵元素Ui,j为进程pi关于资源类rj的当前占用数。剩余需求矩阵N（Need）。N是一个nm的矩阵，矩阵元素NIi,j是进程pi还需要的资源类rj的单位数。显然有，NIi,jMi,jUi,j。（2）简记法 为了简化对算法的描述，对上述数据结构采用如下的简记法 令X和Y为长度是m的向量，若XY，当且仅当对任意的i（i1，2，m）有XiYi。对于nm的矩阵Znm，Zi（i1，2，n）表示矩阵Znm的第i个行向量。,（3）算法描述 令RRi是长度为m的进程pi的资源请求向量，元素RRi,j是进程pi希望请求分配的资源类rj的单位数。当进程pi向系统提交一个资源请求向量RRi时，系统调用银行家算法执行下述工作：若RRi Ni，则有（RRiUi）Mi，即进程pi请求的资源单位数大于它申请的最大需求数，故请求无效，作出错处理；否则进行下一步。若RRi A，则进程pi必须等待，即系统当前没有足够的资源满足进程pi当前的请求；否则进行下一步；系统进行假分配，即假设系统给进程pi分配所请求的资源，对资源分配状态作如下修改：AARRi；UiUiRRi；NiNiRRi；调用安全算法检查此次资源分配后的现行状态是否安全状态。若安全，则正式将资源分配给进程pi，完成进程pi的资源请求分配工作。否则，拒绝分配让进程等待，并恢复此次的假设分配，即撤消步骤对分配状态所作的修改。,（4）安全算法描述 设向量W（Work），向量元素Wj(j=1，2，m)表示系统可供给各个进程继续运行的j类资源数；向量F（Finish），向量元素Fi(i=1，2，n)表示系统是否有足够的资源可使进程pi完成。初始化WA，Fi=false。从进程集合中找到一个进程pi，有Fi=false且NiW，则执行步骤；如果这样的进程不存在，则转去执行步骤；进程pi可得到所需的全部资源，顺利执行完成，并释放它所占用的资源，所以执行WWUi及Fi=true，转去执行；若对所有的进程，都有Fi=true，则存在一个安全序列，现行状态是安全的，否则是不安全的。,例410,解：利用银行家算法进行检查：(1)RR2N2，即（0,4,2,0）（0,7,5,0），继续下一步。(2)RR2A，即（0,4,2,0）（1,5,2,0），继续下一步。(3)进行假分配,(4)执行安全算法,对所有的进程，都有Fi=true，得到一个安全序列（P1、P3、P2、P4、P5），故状态是安全的。（注意：安全序列不是唯一的）,银行家算法虽然能有效的避免死锁的发生，但是也存在一些缺点。如它要求系统中被分配的每类资源固定；用户进程数目保持固定不变；要求用户事先说明他们的最大资源需求；同时每次进行资源分配前都要进行安全性检查，花费处理机时间等。,4.6.3 死锁的检测与恢复,1资源分配图RAG,2死锁的检测,3解除,
