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