计算机操作系统第三章处理机调度与死锁

第三章处理机调度与死锁要解决的三个问题：WHAT：按什么原则分配CPU？—进程调度算法WHEN：何时分配CPU？—进程调度的时机HOW：如何分配CPU？—CPU调度过程（进程的上下文切换）主要内容处理机调度的层次调度队列模型和调度准则调度算法实时调度产生死锁的原因和必要条件预防和避免死锁的办法死锁的检测与解除3.1处理机调度的层次高级调度1作业和作业步作业不仅包含通常的程序和数据，还应配备一份作业说明书，系统根据作业说明书对程序的运行进程控制。在批处理系统中，是以作业为基本单位从外存调入内存。作业步作业运行期间，每个作业都必须经过若干个相对独立、又相互关联的顺序加工步骤，才能得到结果，把其中的每一个加工步骤称为一个作业步。1）编译2）连接装配3）运行作业流若干个作业进入系统后，被依次存放在外存上，形成输入的作业流；在OS的控制下，逐个作业进行处理，形成了处理作业流。编译程序对源程序进行编译，生成若干个目标程序段。将目标程序段装配成可执行的目标程序将目标程序读入内存并控制其运行2作业控制块多道批处理系统中，为每个作业配备一个作业控制块（JCB），它是作业在系统中存在的标志。作业运行期间，系统按照JCB中的信息对作业进行控制。JCB中保存了系统对作业进行管理和调度所需的全部信息。例如：作业标识、用户名称、用户帐户、作业类型、作业状态、调度信息、资源需求、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等。3作业调度（高级调度、长程调度、接纳调度）定义按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源两个决定1决定接纳多少个作业（多道程序度）2决定接纳哪些作业数目过多：每个进程可以执行的时间片就越小，单个进程的周转时间越长；数目过少：资源利用率和系统吞吐量下降，应考虑调度新的进程进入内存。选用何种调度算法：先来先服务、短作业优先、基于作业优先级、响应比高者优先。注意批处理系统中，作业是首先进入外存，然后经由作业调度分批进入内存；分时系统及实时系统中，由于对响应时间有要求，因此用户输入的命令和数据等是直接进入内存的，无须配置作业调度机制。1定义决定就绪队列中的哪个进程应获得处理机，然后由分派程序执行把处理机分配给该进程的具体操作。低级调度是最基本的一种调度，多道批处理、分时、实时系统中都必须配置。2主要功能保存当前进程的处理机现场信息按某种算法（优先数算法、轮转法）选择进程将CPU分配给该进程，恢复新进程的处理机现场，让其从断点开始执行。低级调度（进程调度、短程调度）3进程调度机制排队器将系统中的所有就绪进程按某种方式排成一个或多个队列，方便调度程序寻找。分派器将选中进程从后备队列移出，将处理机分配给它上下文切换机制两次上下文切换：保存当前进程上下文，装入dispatcher上下文；移出dispatcher上下文，装入新选中进程的上下文。4进程调度方式非抢占方式一旦把处理机分配给某进程后，一直让它运行下去，不能因为时钟中断等原因或由其它进程抢占分配给它的处理机。直至该进程完成，或因某事件阻塞，才能重新分配处理机。优点：实现简单，系统开销小；缺点：难以满足紧急任务的要求，可能造成难以预料的后果。实时系统中，不宜采用该方式。抢占方式允许调度程序根据某种原则暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。抢占原则：优先权、短作业优先、时间片。优点：防止长进程长时间占用CPU，为大多数进程提供更公平的服务，特别是能满足实时任务的要求。缺点：与非抢占方式相比，开销较大。当被挂起的进程重新具备运行条件且内存稍有空闲时，把外存上的那些具备运行条件的进程重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。中级调度3.2调度队列模型和调度准则仅有进程调度的调度队列模型仅具有进程调度的调度队列模型时间片完就绪队列阻塞队列CPU交互用户进程调度进程完成等待事件事件发生FIFO队列具有高级和低级调度的调度队列模型……具有高、低两级调度的调度队列模型就绪队列阻塞队列CPU时间片完作业调度进程调度进程完成等待事件1阻塞队列阻塞队列等待事件2等待事件n事件1发生事件2发生事件n发生后备队列优先权队列具有高、低、中三级调度的调度队列模型就绪队列绪就、挂起队列CPU时间片完作业调度进程调度进程完成事件出现阻塞队列挂起等待事件中级调度事件发生后备队列塞阻、挂起队列挂起同时具有三级调度的调度队列模型•面向用户的准则–周转时间短（批处理）–响应时间快（分时）–截止时间保证（实时）–优先权准则（all）选择调度方式和调度算法的若干准则带权周转时间：作业的周转时间与系统为它提供服务的时间之比niTTsinW11周转时间——作业被提交给系统开始，到作业完成为止的这段时间间隔。包括：在外存后备队列等待调度的时间；在内存就绪队列等待调度的时间；在CPU上执行的时间；等待I/O操作的时间。niiTnT11响应时间：用户通过键盘提交请求开始，直至系统首次产生响应为止。包括：请求信息传送到CPU的时间，CPU处理请求的时间，将响应信息回送到终端显示器的时间•面向系统的准则–系统吞吐量高–处理机利用率好–各类资源的平衡利用吞吐量：单位时间内，系统完成的作业数处理机利用率：一般在40%—90%各类资源：内存、外存和外设的平衡利用3.3调度算法根据系统的资源分配策略所规定的资源分配算法先来先服务算法短作业优先算法高优先权优先算法时间片轮转调度算法先来先服务（FCFS）•主要用于作业调度，也可用于进程调度。•用于作业调度：–每次从后备作业队列中选择最先进入的作业，将它们调入内存，为它们分配资源、创建进程，然后挂到就绪进程队列上。–有利于长作业，而不利于短作业。•用于进程调度：–每次从就绪进程队列中选择最先进入的进程，为之分配处理机，使之投入运行。–直到运行完成进程才会让出处理机--非抢占式。•性能评价：–周转时间=完成时间–到达时间–带权周转时间=周转时间/服务（运行）时间先来先服务（FCFS）进程编码到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.99短作业/进程优先（SJ/PF）•短作业优先（SJF）–从后备队列中选择估计运行时间最短的作业，调入内存运行。•短进程优先（SPF）–从就绪队列中选出估计运行时间最短的进程，将处理机分配给它，使它立即执行。–直到运行完成进程才会让出处理机--非抢占式。•缺点：–对长作业不利，有可能长期不被调度；–完全没考虑作业的紧迫程度（某些特殊的）；–用户做出的估计时间带有很大的主观性。短作业/进程优先（SJ/PF）作调业度情算况法进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间47121418周转时间461011149带权周转时间1225.53.52.8SJ/PF完成时间4918613周转时间4816398带权周转时间12.673.11.52.252.1优先级（FPF）•既能用于作业调度，也可用于进程调度。•调度思想：–从队列中选择优先权最高的调度单元，装入内存或分配给处理机。–对进程调度而言，有非抢占式和抢占式两种。把处理机分配给就绪队列中优先权最高的进程，直至完成或因某种原因阻塞，才让出处理机。主要用于批处理系统中同样是把CPU分给优先权最高的进程，但在该进程执行过程中，如有优先级更高的进程到来，则立即停止当前进程的执行，将CPU分配给新到的优先级最高的进程。常用于要求比较严格的实时系统中。•优先权(0-255)–静态优先权、动态优先权。优先权在创建进程时即确定，且在进程的整个运行期间保持不变创建进程时所赋予的优先权，随进程的推进或等待时间的增加而改变例如规定：就绪队列中的进程，随等待时间的延长，优先权以速率α增长；执行中的进程，随执行时间的延长，优先权以速率β下降。•高响应比优先调度算法–动态优先权，与作业等待时间相关。优先权=响应比（Rp）=（等待时间+要求服务时间）/要求服务时间=响应时间/要求服务时间分析：等待时间相同，要求服务时间越短，优先级越高。有利于短作业。要求服务时间相同，等待时间越长，优先级越高。即FCFS。对于长作业，优先级随等待时间的延长而升高，终能获得处理机。因此，该算法是一种折衷算法。缺点：频繁计算响应比，增加了系统开销。时间片轮转•特别适用于分时系统的调度算法。•实现方法：–由计时器发出时钟中断，引起一次轮转调度。基本思想：基于时钟的剥夺。以一定的时间间隔周期性产生一个时钟中断，当中断发生时，当前正在运行的进程被置于就绪队列末尾，然后基于FCFS选择下一个就绪进程运行。保证就绪队列中的所有进程在给定的时间内都能获得一时间片（timeslice）的处理机执行时间。执行过程1将系统中所有的就绪进程按照FCFS原则，排成一个队列。2每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。3在一个时间片结束时，发生时钟中断。4调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。5进程可以未使用完一个时间片，就出让CPU。ABCD…FCPU完成超时阻塞时间片轮转调度算法示意图最佳时间片的确定时间片的选取是实现各种调度算法的关键之处，而时间片的选定通常应考虑终端数目，处理机能力、各终端任务的急迫程度、外存传输速度等方面的因素。①当时间片很大时，大到一个进程足以完成其全部运行工作所需的时间，此时轮转调度模式退化为FCFS模式。②当时间片非常小时，调度程序剥夺处理机的次数增多，这将加重了系统开销，系统性能降低，大多数时间都消耗在处理机的转换上。多级反馈队列调度算法•以上介绍的算法，都存在一定的局限性。•现在主流的操作系统，如UNIX、WindowsNT、Linux等，都使用一种综合性的调度算法——多级反馈队列调度算法。•该算法综合了上述三种算法以及多队列调度算法的思想和优点，总体调度性能优越，适于各种类型的作业，但其实现也比较复杂。算法的基本思想是：•首先：系统按进程优先级设置了多级（比如n级，n≥2）就绪进程队列，从第一级队列到最后一级队列，优先级越来越低。•其次：每一级就绪队列对应一个不同的时间片。优先权越高的队列，进程的时间片越小。•再次：当一个新进程进入内存后，首先被放到第一级队列的队尾。按照FCFS原则排队等待调度。当轮到该进程执行时，如能在时间片内完成，便可准备撤离系统；如果在时间片内未完成，调度程序便将该进程转入第二队列的末尾，再依次按照FCFS原则等待调度。•最后：仅当第一级队列为空时，才调度第二级队列中的进程；如此下去，仅当前面的n-1级队列全部为空时，才去调度最后第n级队列中的进程。如果处理机正在第i队列中为某进程服务时，又有新的进程进入优先权高的队列（第1～(i-1)中任何一队列），则系统抢占正在运行的进程的处理机，由调度程序把正在运行的进程放回到刚才所在第i队列的队尾，重新进行处理机调度。•多级反馈队列调度算法的性能–能较好地满足各种类型用户（进程）的需要。–终端（交互）型作业用户–短批处理作业用户–长批处理作业用户……多级反馈队列调度算法示意图CPU时间片完进程调度进程完成就绪队列一就绪队列二就绪队列三就绪队列n时间片完时间片完习题设有两个优先级相同的进程P、Q，各自运行的程序如下进程PP1Y：=1；P2Y：=Y+Z；P3V（S1）；P4Z：=Y+3；P5P（S2）；P6Y：=Z+Y；进程QQ1X：=1；Q2X：=X+1；Q3P（S1）；Q4X：=X+Y；Q5V（S2）；Q6Z：=X+Z；其中，S1、S2为信号量，初值为0，已知Z=2，若调度程序执行的策略为FIFO，试问执行序列和运行结果是什么？X=5，Y=14，Z=113.5产生死锁的原因和必要条件产生死锁的原因产生死锁的必要条件处理死锁的基本方法死锁多个进程在