操作系统chapter3.ppt
《操作系统chapter3.ppt》由会员分享,可在线阅读,更多相关《操作系统chapter3.ppt(156页珍藏版)》请在三一文库上搜索。
1、第三章 处理机调度与死锁,第三章 处理机调度与死锁,3.1 处理机调度的层次 3.2调度队列模型和调度准则 3.3调度算法 3.4实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测和解除,3.1 处理机调度的层次,在多道程环境下,进程数目往往多于处理机数目,致使它们争用处理机。这就要求系统能按某种算法,动态地把处理机分配给就绪队列中的一个进程,使之执行。分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。,进程调度要解决的问题,WHAT:按什么原则分配CPU 进程调度算法 WHEN:何时分配CPU 进程调度的时机 HOW: 如何分配CPU
2、 CPU调度过程(进程的上下文切换),3.1 处理机调度的层次,处理机是计算机系统中的重要资源 处理机调度算法对整个计算机系统的综合性能指标有重要影响 可把处理机调度分成三个层次: 高级调度 中级调度 低级调度,3.1.1 高级调度,高级调度又称为作业调度或长程调度。长程调度决定哪些作业可参与竞争CPU和其他资源,即决定给哪个作业分配一台虚拟处理机,它的调度对象是作业,它是处理机的宏观调度。,1作业和作业步,(1)作业(Job)。它不仅包含了通常的程序和数据,而且还应配有一份作业说明书,系统根据该说明书来对程序的运行进行控制。在批处理系统中,是以作业为基本单位从外存调入内存的。,(2) 作业步
3、(Job Step)。通常,在作业运行期间,每个作业都必须经过若干个相对独立,又相互关联的顺序加工步骤才能得到结果,我们把其中的每一个加工步骤称为一个作业步,各作业步之间存在着相互联系,往往是把上一个作业步的输出作为下一个作业步的输入。,1作业和作业步,1作业和作业步,(3) 作业流。若干个作业进入系统后,被依次存放在外存上,这便形成了输入的作业流;在操作系统的控制下,逐个作业进行处理,于是便形成了处理作业流。,2作业控制块JCB(Job Control Block),每个作业进入系统时由系统为其建立一个作业控制块JCB(Job Control Block),其中保存了系统对作业进行管理和调度
4、所需的全部信息. 通常包含的内容有:作业标识、用户名称、用户帐户、作业类型、作业状态、调度信息、资源需求、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等。,3.作业调度,作业调度的主要功能是根据作业控制块中的信息,审查系统能否满足用户作业的资源需求,以及按照一定的算法,从外存的后备队列中选取某些作业调入内存,并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列,准备执行。因此,有时也把作业调度称为接纳调度(Admission Scheduling)。,3作业调度,作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转变。 作业调度功能:
5、 1.记录已进入系统的各作业的情况(JCB,Job Control Block); 2.按一定的调度算法,从后备作业中选择一个或几个作业进入系统内存; 3.为被选中的作业创建进程,并且为其申请系统资源; 4.作业结束后作善后处理工作。,3作业调度,每次执行作业调度时,都须做出以下两个决定 1) 决定接纳多少个作业 作业调度每次要接纳多少个作业进入内存,取决于多道程序度(Degree of Multiprogramming), 2) 决定接纳哪些作业 应将哪些作业从外存调入内存,这将取决于所采用的调度算法。,作业与进程的关系,每一个作业将动态地转换成了一组运行实体进程组,并由此来完成该作业所需要
6、完成的一系列加工步骤,当作业所对应的进程完成时,作业便进入了完成状态,整个作业也就完成了。,3.1.2 低级调度,通常也把低级调度称为进程调度或短程调度,它所调度的对象是进程(或内核级线程)。进程调度是最基本的一种调度,在多道批处理、分时和实时三种类型的OS中,都必须配置这级调度。,1低级调度的功能,低级调度的任务是控制协调进程对CPU的竞争,按一定的调度算法决定就绪队列中的哪个进程应获得处理机,然后再由分派程序执行把处理机分配给该进程的具体操作。 (1) 保存处理机的现场信息。 (2) 按某种算法选取进程。 (3) 把处理器分配给进程。,2进程调度中的三个基本机制,为了实现进程调度,应具有如
7、下三个基本机制: (1) 排队器。将系统中所有的就绪进程按照一定的方式排成一个或多个队列,以便调度程序能最快地找到它。 (2) 分派器。分派器把由进程调度程序所选定的进程,从就绪队列中取出该进程,然后将处理机分配给它 (3) 上下文切换机制。当对处理机进行切换时,会发生两对上下文切换操作。,3进程调度方式,进程调度可采用下述两种调度方式。 1) 非抢占方式(Nonpreemptive Mode) 在采用这种调度方式时,一旦把处理机分配给某进程后,不管它要运行多长时间,都一直让它运行下去,决不会因为时钟中断等原因而抢占正在运行进程的处理机,也不允许其它进程抢占已经分配给它的处理机。,3进程调度方
8、式,在采用非抢占调度方式时,可能引起进程调度的因素可归结为如下几个: (1) 正在执行的进程执行完毕,或因发生某事件而不能再继续执行; (2) 执行中的进程因提出I/O请求而暂停执行; (3) 在进程通信或同步过程中执行了某种原语操作,如P操作(wait操作)、Block原语、Wakeup原语等。,3进程调度方式,非抢占方式的优点:系统开销小;采用非抢占方式时,程序员可以在某种程度上预知进程的运行轨迹,程序设计相应简化。 缺点:损失了系统的并发性,使系统不能根据内部的并发事件及时实施进程调度,难以实现要求比较严格的实时调度要求。,3进程调度方式,2) 抢占方式(Preemptive Mode)
9、 这种调度方式允许调度程序根据某种原则去暂停某个正在执行的进程,将已分配给该进程的处理机重新分配给另一进程。抢占方式的优点是,可以防止一个长进程长时间占用处理机,能为大多数进程提供更公平的服务,特别是能满足对响应时间有着较严格要求的实时任务的需求。抢占调度方式是基于一定原则的:,3进程调度方式,(1) 优先权原则。通常是对一些重要的和紧急的作业赋予较高的优先权。允许优先权高的新到进程抢占当前进程的处理机。 (2) 短作业(进程)优先原则。短作业(进程)可以抢占当前较长作业(进程)的处理机。 (3) 时间片原则。各进程按时间片轮流运行,当一个时间片用完后,便停止该进程的执行而重新进行调度。,3.
10、1.3 中级调度,又称中程调度,对换调度。为提高内存的利用率和系统的呑吐量,中级调度决定哪些进程被允许参与竞争处理器资源,哪些进程调至外存上去等待,在合适的情况下,再重新调入内存,并将其挂在就绪队列上,以恢复对处理器资源的竞争。,3.2 调度队列模型和调度准则,3.2.1 调度队列模型 1仅有进程调度的调度队列模型 在分时系统中,通常仅设置了进程调度,用户键入的命令和数据都直接送入内存。对于命令,是由OS为之建立一个进程。系统可以把处于就绪状态的进程组织成栈、树或一个无序链表,至于到底采用其中哪种形式,则与OS类型和所采用的调度算法有关。,1仅有进程调度的调度队列模型,每个进程在执行时都可能出
11、现以下三种情况: (1) 任务在给定的时间片内已经完成,该进程便在释放处理机后进入完成状态; (2) 任务在本次分得的时间片内尚未完成,OS便将该任务再放入就绪队列的末尾; (3) 在执行期间,进程因为某事件而被阻塞后,被OS放入阻塞队列。,图 仅具有进程调度的调度队列模型,2具有高级和低级调度的调度队列模型,在批处理系统中,不仅需要进程调度,而且还需有作业调度,由后者按一定的作业调度算法,从外存的后备队列中选择一批作业调入内存,并为它们建立进程,送入就绪队列,然后才由进程调度按照一定的进程调度算法选择一个进程,把处理机分配给该进程。,3同时具有三级调度的调度队列模型,当在OS中引入中级调度后
12、,人们可把进程的就绪状态分为内存就绪(表示进程在内存中就绪)和外存就绪(进程在外存中就绪)。类似地,也可把阻塞状态进一步分成内存阻塞和外存阻塞两种状态。在调出操作的作用下,可使进程状态由内存就绪转为外存就绪,由内存阻塞转为外存阻塞;在中级调度的作用下,又可使外存就绪转为内存就绪。,3同时具有三级调度的调度队列模型,3.2.2选择调度方式和调度算法的若干准则,1面向用户的准则 (1)周转时间短 所谓周转时间是指从作业被提交给系统开始,到作业完成为止的这段时间间隔。包括:1、作业在外存后备队列上等待调度的时间,2、进程在就绪队列上等待进程调度的时间,3 、进程在CPU上执行的时间,4 、进程等待I
13、/O操作完成的时间。,1面向用户的准则,作业的周转时间: ti = tci-tsi ti:作业周转时间 tci:作业完成时间 tsi: 作业提交时间,其中,n为被测定作业流中的作业数,1面向用户的准则,T:衡量不同调度算法对同一个作业流的性能 W:同一调度算法对不同作业流的性能衡量,1面向用户的准则,(2)响应时间快 所谓响应时间是指从用户通过键盘提交一个请求开始,直至系统首次产生响应为止的时间。包括:1、从键盘输入的请求信息传送到处理机的时间,2、处理机对请求信息进行处理的时间,3、以及将所形成的响应信息送回到终端显示器的时间。,1面向用户的准则,(3)截至时间的保证 所谓截止时间是指某任务
14、必须开始执行的最迟时间,或者必须完成的最迟时间。 (4)优先权准则 为了便于让某些紧急的作业能得到及时的处理,在选择调度算法时还应该遵循优先权准则。,2面向系统的准则,(1)系统吞吐量高 所谓吞吐量是指在单位时间内系统所完成的工作量。 (2)处理机利用率好 (3)各类资源的平衡使用,3.3 调 度 算 法,先进先出(FIFO)算法 短作业(进程)优先调度算法 高优先权优先调度算法 时间片轮转法 多级反馈队列,3.2.1 先来先服务和短作业(进程)优先调度算法,1先来先服务调度算法 将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列,并按照先来先服务的方式进行调度处理,是一种最普遍和最简
15、单的方法。它优先考虑在系统中等待时间最长的作业,而不管要求运行时间的长短。,1先来先服务调度算法,该调度方式属于非抢占方式,获得处理机的进程将一直运行,直到该进程完成或因进程本身发生某事件而阻塞后,才放弃处理机。,1先来先服务调度算法,FCFS算法比较有利于长作业(进程),而不利于短作业(进程)。下表列出了JOB1、JOB2、JOB3、JOB4四个作业分别到达系统的时间、要求服务的时间、开始执行的时间及各自的完成时间,并计算出各自的周转时间和带权周转时间。,1先来先服务调度算法,这种调度从形式上讲是公平的,但它使短作业要等待长作业的完成,重要的作业要等待不重要作业的完成。从这个意义上讲又是不公
16、平的。 先进先出调度使响应时间的变化较小,因此它比其它大多数调度都可预测。由于这种调度方法不能保证良好的响应时间,在处理交互式用户时很少用这种方法。 这种调度算法突出的优点是实现简单,但效率较低。,2短作业(进程)优先调度算法,短作业优先调度算法(SJF)是指对短作业优先调度,即从后备队列中选择一个或若干个估计运行时间最短的作业,将它们调入内存。 短进程优先调度算法(SPF),是指对短进程优先调度,即从就绪队列中选择一个或若干个估计运行时间最短的进程,为它们分配处理机,使之投入运行。,2短作业(进程)优先调度算法,图 FCFS和SJF调度算法的性能,FCFS和SJF的性能比较,2短作业(进程)
17、优先调度算法,SJ(P)F调度算法也存在不容忽视的缺点: 该算法对长作业不利。 (2) 该算法完全未考虑作业的紧迫程度,因而不能保证紧迫性作业(进程)会被及时处理。 (3) 由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的,使该算法不一定能真正做到短作业优先调度。,3.3.2 高优先权优先调度算法,使用该算法前,系统将根据某些因素赋予每一个作业或进程一个对应的优先权,当用于作业调度时,从后备队列中选择若干个优先权最高的作业调入内存;当用于进程调度时,则把处理机分配给就绪队列中优先权最高的进程。 优先权在调度过程中所起的作用与系统对进程调度采用非抢占式调度策略还是抢占式调度策略有关,
18、1优先权调度算法的类型,1) 非抢占式优先权算法 在这种方式下,系统一旦把处理机分配给就绪队列中优先权最高的进程后,该进程便一直执行下去,直至完成;或因发生某事件使该进程放弃处理机时,系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中;也可用于某些对实时性要求不严的实时系统中。,1优先权调度算法的类型,2) 抢占式优先权调度算法 在这种方式下,系统同样是把处理机分配给优先权最高的进程,使之执行。但在其执行期间,只要又出现了另一个其优先权更高的进程,进程调度程序就立即停止当前进程(原优先权最高的进程)的执行,重新将处理机分配给新到的优先权最高的进程。,2优先权的类
19、型,该算法总是把处理机分配给就绪队列中具有最高优先权的进程。首先考虑的问题是如何确定进程的优先数,一种是静态优先数,另一种是动态优先数。 静态优先数法:静态优先权是在创建进程时确定的,在整个运行期间不再改变。,2优先权的类型,确定进程优先权的依据有如下三个方面: (1) 进程类型。通常,系统进程(如接收进程、对换进程、磁盘I/O进程)的优先权高于一般用户进程的优先权。 (2) 进程对资源的需求。如进程的估计执行时间及内存需要量的多少,对这些要求少的进程应赋予较高的优先权。 (3) 用户要求。这是由用户进程的紧迫程度及用户所付费用的多少来确定优先权的。,2优先权的类型,动态优先权是指在创建进程时
20、所赋予的优先权,但在其生命周期内优先权可以动态变化。如随进程的推进或随其等待时间的增加而改变的,以便获得更好的调度性能。,3高响应比优先调度算法,先来先服务和短作业优先算法都有其片面性,先来先服务调度算法只考虑作业的等待时间,而忽视了作业的运行时间,短作业优先算法则相反,只考虑了作业的运行时间,而忽视了作业的等待时间。响应比高者优先调度算法是介于这两种算法之间的一种拆衷的算法。,3.高响应比优先调度算法,优先权的变化规律可描述为:,由于等待时间与服务时间之和,就是系统对该作业的响应时间,故该优先权又相当于响应比RP。据此,又可表示为:,算法特点,(1) 作业的等待时间相同,则要求服务的时间愈短
21、,其优先权愈高,因而该算法有利于短作业。 (2) 服务的时间相同时,作业的优先权决定于其等待时间,等待时间愈长,其优先权愈高,因而它实现的是先来先服务。 (3) 对于长作业,作业的优先级可以随等待时间的增加而提高,当其等待时间足够长时,其优先级便可升到很高,从而也可获得处理机。,3.3.3 基于时间片的轮转调度算法,1时间片轮转法 1)基本原理 进程调度程序总是选择就绪队列中的第一个进程,也就是说按照先来先服务原则调度,但一旦进程占用处理机则仅使用一个时间片。在使用完一个时间片后,进程还没有完成其运行,它必须释放出处理机给下一个就绪的进程,返回到就绪队列的末尾重新排队等待再次运行。,简单轮转法
22、的调度模型,1时间片轮转法,2) 时间片大小的确定 在轮转法中,时间片长度的选取非常重要,时间片长度的选择会直接影响系统开销和响应时间。 当时间片很大时,每个进程得到比完成该进程多的处理机时间,此时轮转调度模式退化为先进先出模式。 当时间片非常小时,进程间的转换开销就成了决定因素,系统性能降低,大多数时间都消耗在处理机的转换上,只有少许用在用户的计算上。,1时间片轮转法,时间片的大小是该算法中的一个重要因素。应综合考虑以下几个因素来确定: 系统对响应时间的要求。系统要求对用户的响应时间短,则时间片要短;反之,时间片可以长一些。 就绪队列中进程的数目。进程数目多,则时间片应短一些。 系统的处理能
23、力。 CPU运行速度快,则时间片可以短;反之,时间片可以长一些。,图 q=1和q=4时的进程运行情况,图 q=1和q=4时进程的周转时间,2多级反馈队列调度算法,在多级反馈队列调度下,就绪队列被分为若干个独立子队列。 但进程不是根据其性质或类型固定地分属于一个队列,而是根据其使用CPU时间的长短来动态地决定进程属于哪级队列。,2多级反馈队列调度算法,(1) * 首先系统中设置多个就绪队列 * 每个就绪队列分配给不同时间片,优先级高的为第一级队列,时间片最小,随着队列级别的降低,时间片加大 * 各个队列按照先进先出调度算法,最后一级采用时间片轮转,(2) * 一个新进程就绪后进入第一级队列末尾
24、* 进程由于等待而放弃CPU后,进入等待队列,一旦等待的事件发生,则回到原来的就绪队列 * 如果它在一个时间片结束时尚未完成,调度程序便将该进程转入第二队列的末尾,如果它在第二队列中运行一个时间片后仍未完成,再依次将它放入第三队列,,2多级反馈队列调度算法,2多级反馈队列调度算法,(3) *系统从第一级调度,仅当第一队列空闲时,调度程序才调度第二队列中的进程运行;仅当第1(i-1)队列均空时,才会调度第i队列中的进程运行。 * 当有一个优先级更高的进程就绪时,可以抢占CPU,被抢占进程回到原来一级就绪队列末尾。,2多级反馈队列调度算法,3多级反馈队列调度算法的性能,多级反馈队列调度算法具有较好
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 操作系统 chapter3
链接地址:https://www.31doc.com/p-3112597.html