电子科技大学计算机操作系统―第三章 调度与死锁

第三章进程调度的核心是调度算法。进程调度是实现多道程序系统的关键，直接影响到操作系统的性能，是本章讨论的主要问题。许家珆3.1调度的基本概念(一）作业从进入系统到完成，可能要经历三级调度过程：一、调度的类型和模型1、高级调度又称为作业调度，它决定将哪些在外存上处于后备状态的作业调入主机内存，准备执行。因此，有时把它称为接纳调度。2、低级调度又称为进程调度，它决定就绪队列中哪个进程将获得处理机，并实际执行将处理机分配给进程的操作。执行分配处理机的程序称为分派程序。3、中级调度中级调度的主要作用是在内存和外存之间进行进程交换，以解决内存紧张的问题。如它将内存中处于等待状态的某些进程调至外存对换区，以腾出内存空间，而将外存对换区上已具备运行条件的进程重新调入内存，准备运行。故又称为交换调度。许家珆阻塞状态就绪状态执行状态调度I/O请求进程释放时间片到后备作业队列3.1调度的基本概念(二）CPU就绪队列内存外存阻塞队列作业调度等待事件中级调度即交换调度交换文件就绪队列阻塞队列三级调度的模型许家珆3.1调度的基本概念(三）作业调度是确定哪些作业可以被调入内存。进程调度是确定哪个进程可以占有CPU并执行。作业调度是进程调度的基础，作业被调入内存后，是以进程的形式执行的。在一个OS中进程调度与作业调度的算法是一致的。？问题？1。进程调度与作业调度之间（功能、调度算法）有何区别和联系？2。三级调度中，最核心的是那一级调度？为什么？各级调度间的关系许家珆3.1调度的基本概念(四）作业步—将一个作业划分为若干个顺序处理的步骤，作业步相互独立又相互关联。作业—是用户请求计算机系统执行的一次独立的上机任务，是能够共享公共资源区域的一族有关进程（家族）。从静态观点看，作业由控制命令系列、程序集、数据集三部分构成。补充：关于作业的概念作业控制块—JCB（JobControlBlock）用于描述作业。定义为记录类型（作业名、优先级、建立时间、状态外存地址、大小等）。作业状态—作业在其生命期中，共有四种状态：许家珆关于作业的状态作业状态—作业在其生命期中，共有四种状态：进入、后备、运行、完成完成执行就绪阻塞进入后备内存运行提交作业调度完成问题：引起进程调度的原因有哪些？许家珆3.1调度的基本概念(五）非抢占式（非剥夺式）进程一旦被调度，就一直占有CPU，直到完成或因发生某事件而被阻塞（I/O请求）。抢占式（剥夺式）进程未执行完，可由调度程序剥夺其CPU，另分配给别的进程。抢占的原因有：优先级、时间片、短进程等。在OS中，进程调度的方式分为两类。二、进程调度的方式许家珆3.1调度的基本概念(六）记录系统中所有进程的执行情况确定分配处理机的原则（调度算法）分配处理机给进程回收处理机、进行进程上下文切换三、进程调度的功能显然，进程调度的核心问题是调度算法。许家珆3.1调度的基本概念(七）1。周转时间短周转时间TT（TumaroundTime）对作业—从作业提交到完成。对进程—第一次进入就绪队列到运行结束。平均周转时间ATT（AverageTumaroundTime）ATT=[∑Ti]带权平均W=[∑]其中：Ti各进程的TTTri实际执行时间2.响应时间快响应时间RT（ResponseTime）—输入键盘命令到屏幕显示结果。四.调度算法准则调度算法应该尽可能提高资源利用率，减少CPU空闲时间,公平服务。可从以下方面考虑：1ni=1nTiTrii=1n1n许家珆3.2调度算法（一）先来先服务（FCFS）算法最短CPU运行期优先（SCBF）算最高优先权（HPF）算法时间片轮转（RR）算法高响应比优先调度算法（HRN）多级反馈队列算法思考题1、各种调度算法的特点、性能如何？适宜于哪类OS？2、最高优先权算法中，动态优先权有何实际意义？常用调度算法许家珆3.2调度算法（二）一.、先来先服务（FCFS）算法FCFS（FirstComeFirstServer）法，又称为先进先出（FIFO）算法，就绪进程按照进入的先后次序排列，调度程序总是选择队首的进程执行。这是一种非剥夺式的调度算法，简单、易实现。对短进程易出现等待时间长，服务质量差。该算法有利于CPU繁忙型的进程，不利于I/O繁忙型的进程。该算法只能用于辅助算法。许家珆3.2调度算法（二）二、最短CPU运行期优先（SCBF）算法n+1nnt该算法优于FCFS，但长进程等待时间长，估算误差较大。SCBF（ShortestCPUBurstFirst），即调度程序总是选择CPU运行时间最短的进程执行。其中为估计的第n个CPU周期。tn为实际值。为控制值，0≤≤1，常取0.5n对最短CPU运行期的估算，依赖于系统的下一个CPU周期，实现较困难。进程的CPU时间的估算公式：n+1许家珆3.2调度算法（三）三、最高优先权（HPF）算法调度程序每次都将CPU分配给就绪队列中具有最高优先级（HighestPriority）的进程。该算法的核心是优先级的确定。调度方式分为剥夺式和非剥夺式。静态优先级在创建进程时根据进程的特性或者用户要求赋予，在进程的整个生命期中不能改变。简单、易实现，但是调度性能不高，优先级低的进程可能长期等待。动态优先级在创建进程时为进程赋予一个基本优先级，在进程的执行过程中可随进程的特性动态改变。引起优先级改变的原因：进程等待CPU时间长短，执行所需CPU时间长短等。分两类优先级：许家珆3.2调度算法（四）三、最高优先权（HPF）算法确定进程优先级的一般原则：1.进程的类型例如：系统进程高于用户进程；前台进程高于后台进程；实时进程高于一般进程。2.对资源的需求量及类型占用CPU时间少的，使用内存资源少的进程优先级高。3.按作业到达系统的时间顺序4.按用户类型和要求许家珆3.2调度算法（五）四、时间片轮转（RR）算法该算法主要用于分时系统，按照公平服务的原则，为进程分配CPU时间片。是一种剥夺式的算法。轮转法的关键是时间片的选取：时间片太大，则轮转法蜕化为FCFS法。时间片太小，则增加CPU的额外开销。影响时间片设置的主要因素：系统响应时间R、就绪进程数N、计算机处理能力等。时间片长度：q=R/Nmax许家珆3.2调度算法（六）五、高响应比优先调度算法（HRN）HRN（HighestResponseratioNext）算法将短进程优先与动态优先级相结合。所谓高响应是指进程获得调度的响应，即优先数R。R=（W+T）/T=1+W/TT—估计进程执行的时间。W—进程等待的时间。①随着进程等待时间的增加，优先权动态增加。②对等待相同时间的短进程比长进程优先权增加得多。③长进程随着等待时间增加也会被调度。许家珆3.2调度算法（八）亦称多级反馈轮转法(RoundRobinwithMultipleFeedback)实现基本思想：1、按优先级分别设置N个就绪队列，优先级愈高的队列分配的时间片愈小。2、系统总是先调度当前优先级最高的队列中的进程，只有当最高优先级队列为空时，才去调度低一优先级队列中的进程。3、进程被调度后，若未执行完时间片到，则优先级降低，进程排入相应优先级队列的队尾。4、同一优先级队列，按照FCFS算法调度。多级反馈队列是一种综合调度算法，对进程就绪队列进行动态调度和管理。七、多级反馈队列许家珆§3.2调度算法（九）七、多级反馈队列许家珆3.3进程调度实例(一）一、VMS进程调度综合调度算法：以优先级为基础的多级反馈队列。VMS中的优先级：1.硬件优先级（IPL）—中断优先级，存储在硬件PCB中。2.软件优先级（0—31级）存储在软件PCB中。16–31实时优先级（静态优先级），用于实时进程。不受时间片影响，进程一旦被调度，一直执行到结束。0–15正常优先级（动态优先级），用于非实时进程，为每个优先级队列设置不同的时间片。优先级愈高，时间片愈短。系统中的进程按照优先级排成32个就绪队列，系统总是按FCFS算法先调度当前优先级最高的队列中的进程。对实时进程和正常进程采用不同的调度策略。许家珆§3.3进程调度实例(二）正常优先级进程（0–15）在创建时，系统为其分配了基本优先级：交互进程为4，批处理进程为3。优先级提升幅度的原则：随着进程等待时间增加，优先级提升幅度增加。因进程类型而定；受I/O限制的进程提升幅度大于受计算限制的进程。VMS中进程优先级的动态提升在进程运行过程中，优先级会有不同幅度（0–6）的提升，使进程获得调度的可能性。进程优先级下降：当进程因为时间片到或者等待某事件发生而释放CPU时，优先级下降。优先级改变后的进程排到相应队列的队尾。许家珆···优先级队列313015···16140静态优先级动态优先级CPU等待队列优先级下降进程按照优先级排成32个就绪队列。每个就绪队列按照FCFS算法排队。优先级越高时间片越小。许家珆§3.3进程调度实例(三）进程的优先权分31级（1-31），为动态优先级：在基本优先级的基础上波动+2级。基本优先权设置（4组）优先权等级优先权范围Idle（闲置）1—6Normal（标准）6—10High（高级）11—15Realtime（实时）16—31进程调度过程中优先权的动态提升有何实际意义？WINDOWSNT的进程优先级问题许家珆3.4实时系统中的调度一.实时系统对调度的需求实时系统对进程的执行有特殊的要求；如响应时间、可靠性等，其中截止时间是实时系统性能的重要指标。截止时间—任务必须开始或者完成的最迟时间。1、实时调度的指标：开始截止时间、完成截止时间处理时间就绪时间资源要求优先级2、其它需求如系统处理能力强、具有高速切换能力等。许家珆3.4实时系统中的调度二.实时调度算法2。调度算法要求严格的实时系统基于时钟中断的抢先优先权调度算法立即抢占优先权调度算法一般要求的实时系统时间片轮转调度算法非抢占优先权调度算法许家珆3.5线程的基本概念（一）为了减少进程并发执行的开销，提高系统性能。将资源分配与调度分开—引入线程。1.构成•一个进程可由一个或者多个线程构成。其中一定有一个主线程。•进程是分配资源的基本单位，线程是可调度的基本单位。•进程用PCB块描述，线程用TCB块（ThreadcontrolBlock）描述。•线程是进程内一个可调度的实体。具有独立的程序计数器。一、为什么引入线程（Thread）二、线程与进程许家珆3.5线程的基本概念（二）线程1的TCB线程2的TCB线程3的TCBTCBCPU状态堆栈程序计数器...寄存器PCB进程标识资源清单...TCB输入线程主线程计算线程输出线程图1图2主线程创建线程1。。。创建线程n图3许家珆•线程有三种基本状态：执行、就绪和阻塞。线程无挂起状态，即线程是只与内存和寄存器相关的概念，它的内容不会因为交换而进入外存。•线程状态转换的5种基本操作：⑴派生：线程由进程或主线程派生，用户一般用系统调用或相应的库函数派生自己的线程。⑵阻塞：线程在执行过程中需等待某个事件发生时则被阻塞。⑶激活：当阻塞线程的事件发生，则该线程被激活并进入就绪队列。⑷调度：选择一个就绪线程进入执行状态。⑸结束：线程结束，它的寄存器上下文以及堆栈内容等将被释放。2.线程的状态许家珆3.线程的并发性线程可并发执行，其同步控制机制与进程相同。同一进程的多个线程具有并发执行的特性，线程之间相互约束，线程的执行过程呈现间断性。4.线程资源线程可以与其它同属一个进程的线程共同拥有该进程的资源。5.线程的调度线程作为调度的基本单位，在windowsNT等32位OS中，采用按优先级调度的策略。线程的调度算法与进程类似，对CPU的分配也分抢占式和非抢占式。线程许家珆Windows2000/XP的线程调度在Windows2000/XP中,调度的基本单位是线程，采用基于优先级的抢先式多处理器调度策略，即总是优先调度处于就绪状态而优先级最高的线程，并为每个线程分配了一个时间片(时间配额)。处理器的调度严格以线程为单位，不区分线程属于哪个进程。线程优先级：共分为32级，分为３组⑴实时线程优先级(16—31)：静态优先级⑵可变线程优先级(1—15)：动态优先级，基本优先级+