《三_处理机调度与死锁》由会员分享，可在线阅读，更多相关《三_处理机调度与死锁（107页珍藏版）》请在金锄头文库上搜索。
1、操作系统 Operating System,第3章 处理机调度与死锁,3.1 处理机调度的层次3.2 调度准则3.3 调度算法3.4 实时调度 3.5 死锁,本章重点：,调度层次和调度队列模型处理机调度算法及其运用如何理解实时调度的“实时”含义实时调度算法死锁概念的理解，产生死锁的原因产生死锁的必要条件死锁解决措施,本章难点：,对各种调度算法的掌握实时调度算法的理解银行家算法和安全性子算法,高级调度：即作业调度，宏观调度或长程调度。其任务是对那些提交给系统后被收容的作业, 按照一定策略选择出某些作业, 为其分配内存等必要的资源, 建立与之对应的进程, 并将进程的PCB表放入就绪队列中, 使其具
2、备参与竞争使用CPU的权利。作业状态变迁如图3-1所示。,3.1.1 三级调度,图3-1 作业调度,3.1 处理机调度的层次,低级调度：即进程调度，微观调度或短程调度。其任务是在进入内存并处于就绪队列的进程中, 确定哪个进程真正获得CPU及其使用CPU的时间。用执行指针指向选中进程的PCB表，将它从就绪队列移出并重布现场，使其运行。进程状态变迁如图3-2所示。,图3-2 进程调度,中级调度：将就绪状态细化为内存就绪和外存就绪状态， 阻塞状态细化为内存阻塞和外存阻塞状态后，中级调度完成进程在内存与外存之间的对换。其任务是周期性地将那些在内存中暂时不用的进程换出并放到外存，而将那些在外存上需要运行
3、的进程换入到内存。进程状态变迁如图3-3所示。,图3-3 中级调度,【三级调度模型】,【进程调度程序的功能】：记录系统中所有进程的状态、优先数和资源的需求情况。确定调度算法。决定将CPU分配给哪个进程及多长时间。分配处理机给进程。进行CPU现场的保护和移交，并实现CPU使用权的移交。 处理机是计算机最重要的资源, 如何提高处理机的利用率及改善系统性能, 在很大程度上取决于进程调度（亦称处理机调度）性能的好坏, 进程调度成为操作系统设计中心工作。,3.1.2 进程调度的功能,在某一给定时刻，决定哪个就绪进程运行、运行多长时间以及如何保证进程的运行，就是进程调度的主要工作,1.非抢占方式： 在非抢
4、占方式下，调度程序一旦把 CPU分配给某一进程后便让它一直运行下去，直到进程完成或发生某事件而不能运行时，才将CPU分给其它进程。 这种调度方式通常用在批处理系统中。它的主要优点是简单、系统开销小。2.抢占方式： 当一个进程正在执行时，系统可以基于某种策略剥夺CPU给其它进程。剥夺的原则有：优先权原则、短进程优先原则和时间片原则。 这种调度方式多用在分时系统和实时系统中，以便及时响应各进程的请求。,3.1.3 进程调度方式,进程调度的时机是与进程调度的方式有关的。通常当发现以下情况时，当前运行进程的CPU被收回，需要重新进行进程调度：正在执行的进程正确完成, 或由于某种错误而终止运行(陷阱或中
5、断)；执行中的进程提出I/O请求, 等待I/O完成时;在分时系统中，分给进程的时间片用完时；按照优先级调度时, 有更高优先级进程变为就绪时(抢占方式)；在进程通信或进程同步过程中, 执行中的进程执行了某种原语操作, 如 P （wait）操作、阻塞原语和唤醒原语时, 都可能引起进程调度。,3.1.4 引起进程调度的时机（因素）,可从不同的角度来判断处理机调度算法的性能。实际的处理机调度算法选择是一个综合的判断结果。1） 面向系统的调度性能准则系统吞吐量：单位时间内处理的进程数。处理机利用率：CPU利用率=CPU有效工作时间/CPU总的运行时间各种设备的均衡利用：如CPU繁忙的作业和I/O繁忙（指
6、次数多，每次时间短）的作业搭配。,3.2 进程调度算法的评价准则,周转时间：作业从提交到完成所经历的时间批处理系统。（公式中Tsi为实际运行时间）。响应时间：用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间分时系统截止时间：开始截止时间和完成截止时间实时系统。公平性：不因作业或进程本身的特性而使上述指标过分恶化。如长作业等待很长时间。优先级：可以使关键任务达到更好的指标。,2） 面向用户的调度性能准则,易于实现执行开销比 要设计一个理想的调度算法是一件十分困难的事,在实际系统中, 调度算法往往折衷考虑。大多数操作系统都采用比较简单的调度算法。,3）调度算法本身的调度性能准则,1
7、.先来先服务FCFS(先进先出调度算法，FIFO)【算法思想】：最简单的算法按照进程进入就绪队列的先后次序，分派CPU；当前进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。在进程唤醒后（如I/O完成），并不立即恢复执行，通常等到当前进程让出CPU。【特点】：比较有利于长作业，而不利于短作业。有利于CPU繁忙的作业，而不利于I/O繁忙的作业。,3.3 进程调度算法,先来先服务FCFS(先进先出调度算法，FIFO),先来先服务算法的实现过程如图所示。 设置信号量：就绪队列互斥信号量s，初值为1； 就绪队列中进程个数n，初值为0。,图3-5 先来先服务算法流程图,2.短进程优先调度算法
8、(SJF,SPF)【算法思想】：选择就绪队列中估计运行时间最短的进程投入运行。通常后来的短作业不抢先正在执行的作业。【优点】：比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；提高系统的吞吐量； 【缺点】：对长作业非常不利，可能长时间得不到执行；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业（进程）的执行时间，从而影响调度性能。,短进程优先调度算法(SJF,SPF),3.优先级调度算法(HPFHighest Priority First)【算法思想】：优先选择就绪队列中优先级最高的进程投入运行。分为：非抢占式优先级算法：仅发生在进程放弃CPU。抢占式优先级算法：可剥
9、夺当前运行进程CPU。【 优先权的类型】静态优先级：在进程创建时指定优先级, 在进程运行时优先数不变。动态优先级：在进程创建时创立一个优先级，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变。【确定优先级的依据】 进程类型、对资源的需求、根据用户要求。,静态优先数的确定：用户要求：用户可以根据作业情况提出自己的优先级要求；资源利用率：请求I/O服务密集的进程优先级较高；系统内部要求：系统进程的优先级高于用户进程的优先级。动态优先数的确定： 进程运行前被赋予一个优先数。运行中根据进程等待时间的长短、执行时间的多少、输入与输出信息量的大小等，通过计算得到新的优先数。每次调度时，仍然是从
10、就绪队列中选择优先级最高的进程率先调度，同级的采用先来先服务（FCFS）。,【确定优先级的原则】,例如：在UNIX 中，进程优先数的计算公式可表示为： 优先数=（最近使用CPU的时间）+基本用户优先数 2 优先数=min127,(p_cpu/16+PUSER+p_nice)其中：PUSER是常数，p_nice是用户为自己进程设定的优先数,P_cpu 优先数 优先权 进程被调 度到的可能性 进程被调 优先权 优先数 p_cpu 度的可能性 优先数=min127,(p_cpu/16+PUSER+p_nice),4.时间片轮转调度算法【算法思想】：通过时间片轮转，提高进程并发性和响应时间特性，从而提
11、高资源利用率。将系统中所有的就绪进程按照FCFS原则，排成一个队列。 每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。在一个时间片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过CPU现场切换执行当前的队首进程。进程可以未使用完一个时间片，就出让CPU（如阻塞）。,时间片长度的确定,【时间片长度变化的影响】：过长退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。过短用户的一次请求需要多个时间片才能处理完，CPU现场切换次数增加，响应时间长。【对响应时间的要求】： T(响应时间)=N(进程数目)*q(时间片)【
12、时间片长度的影响因素】：就绪进程的数目：数目越多，时间片越小（当响应时间一定时）。系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长。,5、多级队列调度算法【基本思想】 根据进程的类型不同，将进程就绪队列分为若干个独立的就绪队列，不同的就绪队列采用不同的调度算法，同一个就绪队列采用同一种进程调度算法。 按照用户作业的性质不同，就绪队列进行不同组织。如：按照进程优先级组织的多个进程就绪队列：,系统进程,终端用户进程,交互编辑文档进程,批处理用户作业进程,CPU,调度算法2,调度算法1,调度算法3,调度算法4,图3-6 多级队列调度算法示意
13、图,6.多级反馈队列算法(多队列轮转法)【算法思想】：设置多个就绪队列，分别赋予不同的优先级，队列1的优先级最高，其他逐级降低。每队列分配不同的时间片，规定优先级越低则时间片越长。新进程就绪后，先投入队列1的末尾，按FCFS算法调度。若一个时间片未能执行完，则降低投入到队列2的末尾；依此类推，降低到最后的队列，则按“时间片轮转”算法调度直到完成。 进程由于等待事件而放弃CPU后, 进入等待队列, 一旦等待的事件发生, 则回到原来的就绪队列。仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾
14、。,图3-7 多级反馈队列算法示意图,I/O型进程：让其进入最高优先级队列，以及时响应I/O交互。通常执行一个小时间片，要求可处理完一次I/O请求的数据，然后转入到阻塞队列。计算型进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。I/O次数不多，而主要是CPU处理的进程：在I/O完成后，放回优先I/O请求时离开的队列，以免每次都回到最高优先级队列后再逐次下降。时间片的增加和优先级的降低体现了反馈；,多级反馈队列算法补充说明,【算法优点】：为提高系统吞吐量和缩短平均周转时间而照顾短进程。为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程。不必估计进程的执
15、行时间，动态调节。 多级反馈队列调度算法，则不必事先知道各种进程所需的执行时间，仍能基本满足短进程优先和I/O频繁的进程优先的需要，因而是目前公认的较好的一种进程调度算法。在UNIX系统、WindowsNT、OS/2中都采用了类似的调度算法。,课堂练习 3.1,在所学的调度算法中，对所有进程和作业都是公平合理的调度算法是 A ；最有利于提高系统吞吐量的作业调度算法是 B ；能兼顾作业等待时间和作业执行时间调度算法是 C ；最有利于提高资源的使用率、能使短作业、长作业及交互作业用户都比较满意的调度算法是 D ；为实现人机交互作用应采用调度算法是 E ；能对紧急作业进行及时处理的调度算法是 F 。AF：(1)FCFS调度算法； (2)短作业优先调度算法； (3)时间片轮转法； (4)多级反馈队列调度算法； (5)高响应比优先算法； (6)基于优先权的剥夺调度算法。,A(1)B(2)C(5)D(4)E(3)F(6),根据进程的基本状态转换图，试问在什么条件下将会发生下面给出的因果变迁：1、一个进程从运行状态变为就绪状态，一定会引起另一个进程从就绪状态变为运行状态。2、一个进程从运行状态变为阻塞状态，一定会引起另一个进程从运行状态变为就绪状态。3、一个进程从阻塞状态变为就绪状态，一定会引起另一个进程从就绪状态变为运行状态,
