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

第三章,调度与死锁,进程调度的核心是调度算法。,进程调度是实现多道程序系统的关键，直接影响到操作系统的性能，是本章讨论的主要问题。,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=Ti 带权平均 W=其中：Ti 各进程的TT Tri 实际执行时间,2.响应时间快 响应时间RT（Response Time）输入键盘命令到屏幕显示结果。,四.调度算法准则 调度算法应该尽可能提高资源利用率，减少CPU空闲时间,公平服务。可从以下方面考虑：,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）算法,该算法优于FCFS，但长进程等待时间长，估算误差较大。,SCBF（Shortest CPU Burst First），即调度程序总是选择CPU运行时间最短的进程执行。,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 复杂 调度开销 同一进程内的线程切换的开销小于进程切换开销，不会引起进程切换。资源开销 线程一般不拥有资源，但可访问所属进程的资源。通信开销 进程通信具有独立的地址空间，通过共享文件等。线程通信任务通信，开销小。,3.7 死锁的基本概念（一）,死锁（deadlock）是OS的一种随机故障，是指两个或 两个以上的进程都无限制的地等待永远不会出现的 事件而发生的状态。,1、争夺资源引起死锁 例1：P1，P2两个进程争夺打印机和读卡机。,一、死锁的原因,P1,P2,打印机,读卡机,P1已经申请到打印机，又申请读卡机。P2已经申请到读卡机，又申请打印机。,打印机和读卡机为非剥夺性资源。,例3、P1，P2，P3 三个进程之间通信：P1产生消息S1，接收P3产生的消息S3；P2产生消息S2，接收P1产生的消息S1；P3产生消息S3，接收P2产生的消息S2；,按以下次序运行：P1：Request（S3）；Release（S1）P2：Request（S1）；Release（S2）P3：Request（S2）；Release（S3）,3.7 死锁的基本概念（二）,2、进程推动顺序不当引起的死锁,P1,P3,P2,S2,S3,S1,P1,P2,P3,按照以上的顺序执行会产生死锁吗？,？问题？,例2、在生产者消费者问题中如果交换两个P操作 的次序，可能引起死锁。,Si临时性资源,3.7 死锁的基本概念（三）,生产者进程：生产一个产品 m；.P（empty）；P（mutex）；将产品 m放入缓冲区；in：=（in+1）mod n；V（mutex）；V（full）；,消费者进程：P（full）；P（mutex）；从缓冲区取产品m；out：=（out+1）mod n；V（mutex）；V（empty）；,生产者消费者问题算法：,3.7 死锁的基本概念（四）,由于 产生死锁的根本原因是争夺共享资源，从而得到产生死锁的必要条件是：,二。死锁的必要条件,互斥条件 进程互斥使用临界资源。不剥夺条件 资源只能由占有它的进程释放，不能 被其它进程剥夺。非剥夺资源 部分分配条件 进程在申请新资源的同时，保持对某 些资源的占有。环路等待条件 存在循环等待链，在链中每个进程都 在等待它的前一进程所持有的资源。,3.7 死锁的基本概念（五）,显然，如果出现死锁将对操作系统造成极大的危害，甚至使系统瘫痪，如何解决死锁是操作系统设计的重要问题。,限制并发进程对于资源的需求，破坏产生死 锁的必要条件。严格限制死锁的发生。,三。解决死锁的方法,预防死锁,避免死锁,在资源的动态分配过程中，采用某种算法防止系统进入不安全状态，避免死锁发生。,检测与解除死锁,对资源的分配不加限制，系统定时运行“死锁 检测”程序，如检测到死锁，设法加以解除。,3.7 死锁的基本概念（六）,采用资源的静态分配策略，破坏“部分分配”条件。即只有当进程所需要的全部资源满足时，系统予以 一次分配。允许进程剥夺使用其他进程占有的资源，破坏“不 剥夺条件”。进程动态申请资源，当进程申请不到新资源时，应立即释放已占有的 所有资源。采用资源顺序分配法，破坏“环路等待”条件。,将系统中的所有资源按类型线性排队，并赋予唯一编号，进程申请资源时，严格按编号递增顺序分配。,预防死锁,3.7 死锁的基本概念（七）,1）系统的安全状态 在分配资源时，分析计算系统的安全性，避免系统进入不安全状态，则可避免死锁。,系统状态安全,存在一个进程序列P1，P2，。Pn，如果系统按此顺序为每个进程分配它们所需的最大资源，而不造成死锁，则称系统状态S（t）安全。,2）银行家算法 银行家算法是著名的避免死锁的算法。其基本思想是：O S 银行家 进程 借贷的客户 资源 可周转的借贷资金,避免死锁,解除死锁,一旦检测到死锁，应立即消除，常用的方法有：1、撤消进程法 逐个撤消所有死锁进程，直到解除死锁为止。撤消进程的策略：按优先级；最小代价原则撤消进程数最少、撤消路径最短。,2、挂起进程法 使用挂起/激活机构挂起一些进程，剥夺它们所占有的资源以解除死锁。,问题,在解决死锁的几种方法中，你认为哪种方法既能够解决死锁问题，对系统效率牺牲也不大？,