操作系统第三章调度与死锁

单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章,调度与死锁,进程调度的核心是调度算法。,进程调度是实现多道程序系统的关键，直接影响到操作系统的性能，是本章讨论的主要问题。,3.1,调度的基本概念,(一）,作业从进入系统到完成,，,可能要经历三级调度过程：,一、调度的类型和模型,1、高级调度,又称为,作业调度,，它决定将哪些在外存上处于后备状态的作业调入主机内存，准备执行。因此，有时把它称为接纳调度。,2、低级调度,又称为,进程调度,，它决定就绪队列中哪个进程将获得处理机，并实际执行将处理机分配给进程的操作。执行分配处理机的程序称为,分派程序,。,3、中级调度,中级调度的主要作用是在内存和外存之间进行进程交换，以解决内存紧张的问题。如它将内存中处于等待状态的某些进程调至外存对换区，以腾出内存空间，而将外存对换区上已具备运行条件的进程重新调入内存，准备运行。故又称为,交换调度,。,阻塞,状态,就绪,状态,执行,状态,调度,I/O请求,进程,释放,时间,片到,后备作业队列,3.1,调度的基本概念,(二）,CPU,就绪队列,内存,外存,阻塞队列,作业调度,等待事件,中级,调度,即交换调度,交换文件,就绪队列,阻塞队列,三级调度的模型,3.1,调度的基本概念,(三）,作业调度是确定,哪些作业,可以被,调入内存,。,进程调度是确定,哪,个,进程,可以,占有CPU,并执行。,作业调度是进程调度的基础，作业被,调入内存,后，,是以,进程的形式执行,的。,在一个OS中进程调度与作业调度的算法是一致的。,？问题？,1。进程调度与 作业调度之间（功能、调度算法）有,何区别和联系？,2。三级调度中，最核心的是那一级调度？为什么,？,各级调度间的关系,3.1,调度的基本概念,(四）,作业步,将一个作业划分为若干个顺序处理的步骤，作,业步相互独立又相互关联。,作业,是用户请求计算机系统执行的一次独立的上机任,务，是能够共享公共资源区域的一族有关进程（家族）。,从静态观点看，作业由 控制命令系列、程序集、数据,集三部分构成。,补充：关于作业的概念,作业控制块,JCB（Job Control Block）用于描述作业。,定义为记录类型（作业名、优先级、建立时间、状态外,存地址、大小等）。,作业状态,作业在其生命期中，共有四种状态：,关于作业的状态,作业状态,作业在其生命期中，共有四种状态：,进入、后备、运行、完成,完成,执行,就绪,阻塞,进入,后备,内存,运行,提交,作业调度,完成,问题：引起进程调度的,原因有哪些？,3.1,调度的基本概念,(五）,非抢占式（非剥夺式）,进程 一旦被调度，就一直占有CPU，直到完成或因发生某事件而被阻塞（I/O请求）。,抢占式（剥夺式）,进程未执行完，可由调度程序剥夺其CPU，另分配给别的进程。,抢占的原因有：优先级、时间片、短进程等。,在OS中，进程调度的方式分为两类。,二、进程调度的方式,3.1,调度的基本概念,(六）,记录系统中所有进程的执行情况,确定分配处理机的原则（调度算法）,分配处理机给进程,回收处理机、进行进程上下文切换,三、进程调度的功能,显然，进程调度的核心问题是调度算法。,3.1,调度的基本概念,(七）,1。周转时间短,周转时间TT（Tumaround Time）,对作业从作业提交到完成。,对进程第一次进入就绪队列到运行结束。,平均周转时间ATT（Average Tumaround Time）,ATT=,T,i,带权平均,W,=,其中：,T,i,各进程的TT,T,r,i,实际执行时间,2.,响应时间快,响应时间RT（Response Time）输入键盘命令到屏幕显示结果。,四.调度算法准则,调度算法应该尽可能,提高资源利用率，减少CPU空闲时间,公平服务。,可从以下方面考虑：,1n,i=1,n,T,i,T,ri,i=1,n,1 n,3.2,调度算法,（一）,先来先服务（FCFS）算法,最短CPU运行期优先（SCBF）算法,最高优先权（HPF）算法,时间片轮转（RR）算法,多级反馈队列算法,思考题,1、,各种调度算法的特点、性能如何？适宜于 哪类 OS？,2。最高优先权算法中，动态优先权有何实际意义？,常用调度算法,3.2,调度算法,（二）,一.、先来先服务（FCFS）算法,FCFS（First Come First Server ）法，又称为先进先出（FIFO）算法，就绪进程按照进入的先后次序排列，调度程序总是选择队首的进程执行。,这是一种非剥夺式的,调度算法，简单、易实现。,对短进程易出现等待时间长，服务质量差。,该算法有利于CPU繁忙型的进程，不利于I/O繁忙型的进,程。,该算法只能用于辅助算法。,3.2,调度算法,（二）,二、最短CPU运行期优先（SCBF）算法,n+1,n,n,t,该算法优于FCFS，但长进程等待时间长，估算误差较大。,SCBF（Shortest CPU Burst First），即调度程序总,是选择CPU运行时间最短的进程执行。,其中 为估计的第n个CPU 周期。,t,n,为实际值。,为控制值，0,1，,常取,0.5,n,对,最短CPU运行期的估算，依赖于系统的下一个CPU周,期中，实现较困难。进程的,CPU,时间 的估算公式：,n+1,3.2,调度算法,（三）,三、最高优先权（HPF）算法,调度程序每次都将CPU分配给就绪队列中具有最高优先级（Highest Priority）的进程。该,算法的核心是,优先级的确定。调度方式分为,剥夺式,和,非剥夺式,。,静态优先级,在创建进程时根据进程的特性或者用户要求赋予，在进程的整个生命期中,不能改变,。,简单、易实现，但是调度性能不高，优先级低的进程可能长期等待。,动态优先级,在创建进程时为进程赋予一个,基本优先级,，在进程的执行过程中可随进程的特性,动态改变,。,引起优先级改变的原因：,进程等待CPU时间长短，执行所需CPU时间长短等。,分两类优先级：,3.2,调度算法（四）,三、最高优先权（HPF）算法,确定进程优先级的一般原则：,1.进程的类型,例如：系统进程高于用户进程；,前台进程高于后台进程；,实时进程高于一般进程。,2.对资源的需求量及类型,占用CPU时间少的，使用内存资源少的进程优先级高。,3.按作业到达系统的时间顺序,4.按用户类型和要求,3.2,调度算法,（五）,四、时间片轮转（RR）算法,该,算法主要用于分时系统，按照公平服务的原则，为进程分配,CPU,时间片。是一种剥夺式的算法。,轮转法的关键是时间片的选取：,时间片太大，则轮转法蜕化为FCFS法。,时间片太小，则增加,CPU,的额外开销。,影响时间片设置的主要因素：,系统响应时间,R,、就绪进程数,N,、计算机处理能力等。,时间片长度：,q=R/N,max,3.2,调度算法（六）,五、高响应比优先调度算法（HRN）,HRN（Highest Response ratio Next）,算法将短进程优先与动态优先级相结合。所谓高响应是指进程获得调度的响应，即优先数,R,。,R=（W+T）/T=1+W/T,T,估计进程执行的时间。,W,进程等待的时间。,随着进程等待时间的增加，优先权动态增加。,对等待相同时间的短进程比长进程优先权增加得多。,长进程随着等待时间增加也会被调度。,3.2,调度算法（七）,六、多级队列调度,根据作业性质不同分为若干个就绪队列，如：系统进程队列，交互进程队列，批处理队列等。对各队列采用不同的调度算法。,3.2,调度算法,（八）,亦称多级反馈轮转法（Round Robin with Multiple Feedback）,实现基本思想：,1。按优先级分别设置,N个就绪队列,，优先级愈高的队列分配,的时间片愈小。,2。系统总是,先调度当前优先级最高的,队列中的进程，只有当,最高优先级队列为空时，才去调度低一优先级队列中的进,程。,3。进程被调度后，若未执行完时间片到，则,优先级降低,，进,程排入相应优先级队列的,队尾,。,4。同一优先级队列，按照,FCFS算法调度,。,多级反馈队列是一种,综合调度算法,，对进程就绪队列进,行动态调度和管理。,七、多级反馈队列,3.2,调度算法,（九）,七、多级反馈队列,3.3,进程调度实例,(一）,一。VMS,进程调度,综合调度算法：,以优先级为基础的多级反馈队列。,VMS,中的优先级：,1。硬件优先级（IPL）中断优先级，存储在硬件PCB中。,2。软件优先级 （0 31级）存储在软件PCB中。,1631,实时优先级,（,静态优先级,），用于实时进程。,不受时间片影响，进程一旦被调度，一直执行,到 结束。,0 15,正常,优先级,（,动态优先级,），用于非实时进程，,为每个优先级队列设置不同的 时间片。优先级,愈高，时间片愈短。,系统中的进程按照,优先级,排成,32个就绪队列,，系统总是按FCFS算法,先,调度,当前,优先级最高的,队列中的进程。对实时,进程和正常进程采用不同的调度策略。,3.3,进程调度实例,(二）,正常,优先级进程（0,15）在创建时，系统为其分配了,基本优先级,：交互进程为,4,，批处理进程为,3,。,优先级提升,幅度的原则：,随着进程等待时间增加，优先级提升幅度增加。,因进程类型而定；,受 I/O 限制的进程,提升幅度大于受计算限制的进程。,VMS中进程优先级的动态提升,在进程运行过程中，优先级会有不同幅度（0 6）的提,升，使进程获得调度的可能性。,进程,优先级下降,：当进程因为时间片到或者等待某事件发生而释放CPU时，优先级下降。,优先级改变后的进程排到相应队列的队尾。,优先级队列,31,30,15,16,14,0,静态优先级,动态优先级,CPU,等,待,队,列,优先级下降,进程按照,优先级,排成,32个就绪队列。,每个,就绪队列按照FCFS算法排队。,优先级越高时间片越小。,3.3,进程调度实例,(三）,进程的优先权分31级（1-31），为动态优先级：在基本优先级的基础上波动,+,2级。,基本优先权设置（4组）,优先权等级 优先权范围,Idle （,闲置,）1 6,Normal （,标准）,6 10,High （,高级）,11 15,Realtime（,实时）,16 31,进程调度过程中优先权的动态提升有何实际意义？,WINDOWS NT,的进程优先级,问 题,3.5 线程的基本概念,（一）,为了减少进程并发执行的开销，提高系统性能。将资源分配与调度分开引入线程。,1。,构成,一个进程可由一个或者多个线程构成。其中一定有一个主线程。,进程是分配资源的基本单位，线程是可调度的基本单位。,进程用PCB块描述，线程用TCB块（Thread control Block）描述。,线程是进程内一个可调度的实体。具有独立的程序计数器。,一。,为什么引入线程（Thread）,二。,线程与进程,3.5 线程的基本概念,（二）,线程1的TCB,线程2的TCB,线程3的TCB,TCB,CPU 状态,堆栈,程序计数器,.,.,.,寄存器,PCB,进程标识,资源清单,.,.,.,TCB,输入线程,主线程,计算线程,输出线程,图1,图2,主线程,创建,线,程 1 。,创建,线,程,n,图3,2,.,线程 的并发性,同一进程 的多个线程具有并发执行的特性，线程之间相互约束，线程执行过程呈现间断性。线程也具有就绪、,阻塞和执行三种基本状态。,3.,线程资源,线程可以与其它同属一个进程的线程共同拥有该进程的资源。,3.5 线程的基本概念,（三）,4,.线程的调度,线程作为调度的基本单位，在windows,NT,等32位OS,中，采用按优先级调度的策略。,线程的调度算法与进程类似，对CPU的分配也分,抢占,式,和,非抢占式。,3.5 线程的基本概念,（四）,5。系统开销,从以下方面比较进程与线程的开销。,创建撤消的,开销,PCB 比 TCB 复杂,调度,开销,同一进程内的线程切换的开销小于进程切换开销，,不会引起进程切换。,资源开销,线程一般不拥有资源，但可访问所