计算机操作系统第4章-调度与死锁

2020/3/31第4章调度与死锁主讲：王斯锋2020/3/32本章主要目录4.1调度的类型和模型4.2调度的算法4.3实时系统中的调度4.4多处理机调度4.6死锁的基本概念4.7死锁的预防和避免4.8死锁的检测和解除本章基础要点作业课后练习题及参考答案实战练习2020/3/334.1调度的类型和模型4.1.1调度的类型一、高级调度二、低级调度三、中级调度4.1.2调度队列模型一、仅有进程调度的调度队列模型二、具有高级和低级调度的调度队列模型三、同时具有三级调度的调度队列模型4.1.3选择调度方式和算法的若干准则一、面向用户的准则二、面向系统的准则4.1.4进程调度的进一步理解4.1.5进程调度的功能2020/3/34多道程序环境下，进程数目往往多于处理机数目，致使它们争用处理机，这就要求系统能按某种算法动态地把处理机分配给就绪队列中的一个进程，使之执行进程。在多道程序系统中，一个作业从提交到执行，一般都经历多级调度。2020/3/35作业与作业管理1、作业与作业步作业：是用户要求计算机系统所做的一个计算问题或一次事务处理的完整过程。任何一个作业都要经过若干个步骤之后，才能得到结果，称每一个加工步骤为一个“作业步”。一个作业的各个作业步之间是有联系的，上一个作业步的输出是下一下作业步的输入。2、作业控制块创建一个进程时，要开辟一个进程控制块PCB，随时记录进程的信息。把一个作业提交给系统时，也要开辟一个作业控制块JCB，随时记录作业的信息。2020/3/36作业控制块的内容用户名作业名作业类别作业现行状态内存需求量作业优先数外设类型与需求数量作业提交时间作业运行时间(估计)作业控制块JCB指针其他2020/3/37作业从提交给系统直到它完成后离开系统前的整个活动常划分为若干个阶段。作业在每一阶段中所处的状况称为作业的状态。系统中的作业通常分为四种状态：2020/3/38(1)提交状态：进入外存，作业的一个暂时性的状态，其信息还没有全部进入系统，也没有建立JCB，感知不到它的存在。(2)后备状态(收容状态)：系统收到其全部信息，为其建立JCB，形成后备作业队列，系统能感知到它的存在。2020/3/39(3)运行状态：由作业调度进入了进程调度阶段。(4)完成状态：作业运行结束后的一个状态，是一个暂时性状态。2020/3/310Windows2000/XP中的作业是共享一组配额限度和安全性限制的进程集合；进程是内存资源分配和打开文件个数的基本单位；线程是操作系统调度处理器的执行单位。一个作业可以包含一个或多个进程，一个进程可以包含一个或多个线程。一个进程只能属于一个作业，一个线程只能属于一个进程。2020/3/311系统的运行性能，如：吞吐量的大小、周转时间的长短、响应的及时性等，很大程度上都取决于调度。调度成为多道系统的关键。分配处理机的任务是由进程调度程序Scheduler完成的。2020/3/3124.1调度的类型和模型从不同的角度进行分类，常用分类方法是按调度的层次，把调度分为高级、中级和低级调度；另一种分类是按OS的类型分类，调度分为批处理调度、分时调度和实时调度及多处理机调度。4.1.1调度类型作业从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，要经历下述三级调度。2020/3/313一、高级调度，又称作业调度或长程调度或宏观调度。常用于批处理系统，分时和实时都没有作业：是用户向计算机提交任务的任务实体。进程：是计算机为了完成任务实体而设置的执行实体，是系统分配资源的基本单位。一个作业总是由一个以上的多个进程组成的。2020/3/314执行作业调度时，需解决两个问题：1、接纳多少个作业作业调度接纳多少个作业进入内存，取决于多道程序度，即允许有多少个作业同时在内存中运行。2020/3/3152、接纳哪些作业2020/3/316二、低级调度，又称进程调度、短程调度、微观调度。最基本的调度，三种类型的操作系统中必须都配置。2020/3/317后备队列就绪队列I/O阻塞队列高级调度CPU低级调度I/Oend2020/3/3181、非抢占方式(非剥夺方式)nonpreemptive2、抢占方式(剥夺方式)preemptive,又称抢夺、抢用、强抢、抢先、剥夺。2020/3/319(1)时间片原则。(2)优先权原则。(3)短作业(进程)优先原则。3、完全可抢先fullypreemptive是指任何时间，不管进程处于用户态还是核心态，都可以随时被更高优先级的进程抢用CPU。2020/3/320(1)完全不可抢先或用户态不可抢先：当前进程不论在用户态或核心态时，都不可以被抢用CPU，这种操作系统称为不可抢先式的操作系统。如：windows98和windows95(2)内核完全不可抢先：当前进程在用户态时可以被抢占，但当在核心态时不可被抢占。如：传统的UNIX3或4.3BSDUNIX、windowsNT2020/3/321(3)内核的部分可抢先：用户态时可被抢占，核心态时大部分时间不可抢占，而只在某些时刻点(可抢先点，preemptionpoint)时可被抢占。UNIXSVR4(4)完全可抢先或内核完全可抢先：无论任何状态都可以被抢占。如SUN公司的Solaris2020/3/322三、中级调度，又称中程调度、交换调度。分时系统中常用，主要任务是将内存处于阻塞状态的某些进程调到外存。2020/3/323引入中级调度的目的是，为提高内存的利用率和系统吞吐量。中级调度实质上是存储器管理中的对换功能。2020/3/324三种调度，进程调度的运行频率最高，其调度算法不能太复杂，以免占用太多的CPU时间。作业调度发生在一个作业运行完毕，退出系统时又要重新调入一个作业进入内存时，调度的周期长，其调度算法花费较多的时间。中级调度的运行频率介于两种之间。2020/3/325***4.1.2调度队列模型在上述的三种调度中，都涉及进程队列，形成了三种类型的调度队列模型。一、仅有进程调度的调度队列模型分时系统中仅有进程调度。用户的命令直接送入内存，OS对每个命令命令建立一个进程，按时间片轮转运行。2020/3/326每个进程执行时，可能出现三种情况：(1)该任务在该时间片内已经完成，该进程释放处理机后进入完成状态。(2)任务在本次其对应的时间片内尚未完成，OS将该任务放在就绪队列的后面。(3)在执行期间，进程因某事件而被阻塞后，OS将它放入阻塞队列。其调度队列模型如图：2020/3/327列队绪就列队塞阻CPU等待事件进程调度进程完成交互用户时间片完事件出现内存2020/3/328二、具有高级和低级调度的调度队列模型如图示：具有高级和低级调度的调度队列模型，它与上一模型的区别：(1)OS中既引入了进程调度，又引入了作业调度。后者从外存的后备队列选择一批作业调入内存，并创建进程，然后，送入就绪队列。(2)OS中设置多个阻塞队列。每个队列对应一种引起进程阻塞的事件。2020/3/329列队绪就CPU等待事件1等待事件n等待事件2进程调度时间片完事件1出现事件2出现事件n出现作业调度后备队列2020/3/330三、同时具有三级调度的调度队列模型OS引入中级调度后，可把进程的就绪状态分为内存就绪状态(表示进程在内存中就绪即活动就绪)、外存就绪状态(进程在外存中就绪即静止就绪)。也可把阻塞状态分成内存阻塞(活动阻塞)和外存阻塞(静止阻塞)。2020/3/331三级调度的调度队列模型如图示：2020/3/332CPU阻塞队列阻塞，挂起队列就绪，挂起队列就绪队列时间片完后备队列作业调度批量作业交互型作业中级调度事件出现挂起等待事件进程完成进程调度事件出现2020/3/3334.1.3选择调度方式和算法的若干准则(面向用户和面向系统)选择调度方式和算法，取决于OS的类型和目标，选择调度方式和算法的准则，有的是面向用户的，有的是面向系统的。2020/3/334一、面向用户的准则1、周转时间短，批处理系统中。所谓周转时间，指从作业提交给系统开始，到作业完成为止的时间间隔，又称作业周转时间。包括：2020/3/335(1)作业在外存后备队列上等待(作业)调度的时间(2)进程在就绪队列上等待进程调度的时间。(3)进程在CPU上执行的时间。(4)等待I/O操作完成的时间。2020/3/336作业周转时间与系统为它提供的实际服务时间Ts之比，称为带权周转时间。W=T/Ts，平均带权时间表示为：2、响应时间快，分时系统中。用于评价分时系统的性能，是选择分时系统中进程调度算法的重要准则。2020/3/337响应时间，是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或说直到在屏幕上显示出结果为止的一段时间间隔。包括：2020/3/338(1)从键盘输入的请求信息传送到处理机的时间。(2)处理机对请求信息进行处理的时间。(3)将所形成的响应回送到终端显示器的时间。2020/3/3393、截止时间的保证，实时系统中。所谓截止时间，是指某任务必须开始执行的最迟时间（截止开始），或必须完成的最迟时间（截止结束）。2020/3/3404、优先权准则批处理、分时和实时系统中，都可引用优先权准则，让某些紧急的作业，得到及时的处理。严格的场合，还可选择抢占调度方式。二、面向系统的准则2020/3/3411、系统吞吐量高用于评价批处理系统性能的重要指标。吞吐量是指在单位时间内所完成的作业数。它与作业的平均长度有密切关系。作业的调度方式和算法，对吞吐量的大小也产生影响。2020/3/3422、处理机利用率好实际系统中，CPU的利用率在40%到90%之间。对大、中型多用户系统，处理机的利用率成为衡量性能的重要指标。2020/3/3433、各类资源的平衡利用选择适当的调度方式和算法，能保持系统中各类资源都处于忙碌状态。如：内存、外存、I/O设备等。2020/3/344进程调度的进一步理解作业调度程序在挑选作业进入主存运行时，要为该作业建立相应的进程。在作业完成后要撤消该作业的全部进程。因此作业调度程序要调用操作系统内核所提供的有关的进程管理原语，如“建立进程”原语和“撤消进程”等原语2020/3/345由于进程只能由其父进程建立，所以在一般系统中，作业调度程序都以进程的形式在系统中存在和活动，称为作业调度进程。作业调度进程可以说是系统中的祖先进程，由它完成作业调度的诸功能。2020/3/346进程调度的功能是从就绪队列中挑选一个进程到处理机上运行。负责进程调度功能的内核程序称为进程调度程序。2020/3/347读者往往不易分清作业调度程序挑选作业进入主存运行和进程调度程序挑选一个进程到处理机上运行，这两种运行之间有何区别。2020/3/348所谓作业调度程序挑选作业进主存运行是个宏观的概念，实际上被选进主存运行的作业只是具有了竞争处理机的机会(将来真正在处理机上运行的是该作业的一个进程)。而进程调度程序才是真正让某个就绪进程到处理机上运行。2020/3/349由于进程调度程序负责在就绪进程间转接对处理机的控制，所以对它的调用相当频繁，每秒要执行很多次。它是操作系统核心(常称为内核)的重要组成部分。进程调度程序在系统中以原语形式存在，它是为进程在系统内的活动提供支持。2020/3/350进程调度的功能进程调度程序的具体功能如下：1、记录系统中所有进程的有关情况及状态特征。为了实现进程调度，进程管理模块必须将系统中各进程的执行情况和状态特征记录在各进程的PCB中，同时还应根据各进程的状态特征和资源需求等信息将进程的PCB组织成相应的队列，并依据运行情况将进程的PCB在不同状态队列之间转换。进程调度模块通过PCB的变化来掌握系统中所有进程的执行情况和状态特征。2020/3/3512、选择获得处理机的进程按照一定的策略选择一个处于就绪状态的进程，使其获得处理机执行。根据不同的系统设计目标，有各种各样的选择策略。例如先来先服务调度算法、时间片轮转调度算法等。这些选择策略决定了调度算法的性能。2020/3/3523、处理机分配当正在运行进程由于某种原因要放弃处理机时，进程调度程序