《【PPT课件】调度与死锁》由会员分享，可在线阅读，更多相关《【PPT课件】调度与死锁（73页珍藏版）》请在金锄头文库上搜索。
1、6.1 调度的层次与作业调度6.2 单处理器系统的处理机调度6.3多处理机系统6.4多处理器系统的管理与调度6.5 死锁,第六章 调度与死锁,1.调度层次调度可分为三个层次：作业调度：也称高级调度或长期调度，决定每次接收多少个作业和接纳哪些作业的问题。交换调度：主要负责内外存上的进程交换。一般是通过“挂起”和“解挂”的方法来实现，也称“中期调度”。进程/线程调度：将处理器分配给一个或多个进程/线程的调度方法，也称“低级调度”和“短期调度”和“处理器调度”。,6.1 调度的层次与作业调度,分级调度图：,6.1 调度的层次与作业调度,2.作业状态 四种状态：提交、后备、执行和完成。提交状态：作业由
2、输入设备进入外存储器（输入井）的过程中所处的状态。后备状态：提交后的作业，系统把该作业的JCB加入到后备队列中等待作业调度程程序调度的状态。执行状态：后备作业由作业调度程序分配了资源，进入内存并建立了对应PCB的状态。完成状态：作业正常运行结束或发生错误而中途终止时所处的状态。,完成状态,执行状态,作业的状态及其转换图：,6.1 调度的层次与作业调度,3.作业调度,（1）作业控制块JCB JCB是作业存在的唯一标志，批处理作业进入系统时由spooling系统为其创建JCB。JCB的主要内容：作业名作业状态资源要求（运行时间、最迟完成时间、内存容量、外设种类及数量等）作业控制方式（联机或脱机）作
3、业类型（CPU型，I/O型）作业优先级,6.1 调度的层次与作业调度,6.1 调度的层次与作业调度,（2）功能按照一定算法，从后备队列中选择一个或多个作业进入执行状态为选中的作业分配主存和必要的资源为选中的作业建立进程PCB构造和填写作业运行时所需要的数据结构，如作业表等作业执行结束进入完成状态时，回收资源和JCB以及属于该作业的PCB,（3） 作业调度的目标考虑系统的设计目标（批处理、分时或实时）提高系统资源的利用率和运行效率均衡处理系统和用户的要求保证各作业的公平性,6.1 调度的层次与作业调度,当一个作业完成或处理器空闲时，可以调入一个或多作业进入系统。,1. 调度的准则进程的调度策略主
4、要从两个方面考虑：（1）面向用户的准则 从用户的角度，主要考虑的指标有：周转时间短响应时间快优先权准则截止时间的保证,6.2 单处理器系统的进程调度,（2）面向系统的准则 系统设计目标不同，考虑指标也不同：系统吞吐量和 资源利用率（多道批处理系统）分时系统（响应时间）实时系统（实时性且不丢失信息）,6.2 单处理器系统的进程调度,2.进程调度的功能 记录系统中所有进程的执行情况 从系统中的多个进程中选择一个占有CPU的进程 执行进程上下文的切换,6.2 单处理器系统的进程调度,3.调度算法（1）先来先服务调度算法 原理：将用户作业和就绪进程按提交的顺序或变为就绪状态的先后排成队列，并按照先来先
5、服务的方式进行调度。,6.2 单处理器系统的进程调度,缺点：使短作业和实时性要求较高的作业等待的时间过长。是一种非抢占的调度方法，不适合应用于分时环境中。,例1：,在一个单道批处理系统中，一组作业的提交时刻和运行时间去表所示，请计算其平均周转时间T和平均带权周转时间W。,解：,8.0,9.0,9.5,9.7,9.0,9.5,0.7,9.8,1.0,1.0,9.7,0.7,1.0,2.0,3.5,7.0,原理：调度时从后备队列中选择若干优先权最高的个作业进入内存；或从就绪队列中选择优先权最高的进程，将处理机分配给它。类型：非抢占式优先权算法抢占式优先权调度算法,（2）基于高优先权的调度算法,6.
6、2 单处理器系统的进程调度,例：若采用抢占的 高优先级调度算法，求进程的调度次序。,执行次序为：1-2-3-4-2-1,（3）短作业（进程）优先调度算法,原理：调度时根据估计的运行时间首先调度运行占用CPU时间最短的作业或进程。,6.4 单处理器系统的进程调度,缺点：没有考虑长作业和实时任务的要求。是一种非抢占的调度方式，不适合应用于分时系统中。,例2：,解：,短作业优先调度算法产生的平均周转时间短，系统吞吐量大。,8.0,9.0,9.0,9.2,9.2,9.3,9.3,9.8,1.0,0.2,0.2,1.3,1.0,1.0,2,2.6,（4）最短剩余时间优先调度算法原理：选择运行到完成时所需
7、要的剩余时间最短的进程优先得到处理器，包括新进入系统的进程。,6.2 单处理器系统的进程调度,优点：采用抢占式调度方式，可以运行在分时系统中。缺点：需要记录各进程的运行情况，比较剩余时间的大小，抢占开销大。,原理：将CPU的处理时间分成固定大小的时间片，并将就绪进程按变成就绪状态的先后顺序排成一个队列，每次调度时把CPU分配给处在队首的进程，使其执行一个时间片，依次执行,（5）时间片轮转调度算法,6.2 单处理器系统的进程调度,时间片大小的确定：确定时间片（q）大小的因素主要有：系统对响应时间（R）的要求和系统所允许的最大进程数（N) 公式： q= R/ N,例3：假定系统规定的时间片大小为0
8、.3，作业提交情况如下表所示：,解：调度顺序：1-2-3-4-1-2-1,8.3,8.6,8.8,8.9,9.2,9.4,9.8,1.8,1.4,0.8,0.9,1.8,2.8,4,9,T=（1.8+1.4+0.8+0.9）/4=4.9/4,W=（1.8+2.8+4+9）/4=17.6/4,（6）高响应比优先调度算法,响应比Rp=,6.2 单处理器系统的进程调度,特点：若作业等待时间相同，则要求服务的时间越短，其优先权越高。若各作业要求服务的时间相同，作业的等待时间越长，其优先级越高。适用于非抢占调度策略。缺点：计算响应比的开销大。,6.2 单处理器系统的进程调度,例4：,解：,8.0,9.0
9、,9.5,9.6,9.0,9.5,9.6,9.8,1.0,1.0,0.5,0.8,1.0,2.0,5.0,4.0,T=（1.0+1.0+0.5+0.8）/4=0.825,W=（1.0+2.0+5.0+4.0）/4=3,t=9.0时刻，R2=（0.5+0.5）/0.5=2；R3=（0+0.2）/0.2=1，先执行作业2,t=9.5时刻，R3=（0.5+0.2）/0.2=3.5；R4=（0.4+0.1）/0.1=5，先执行作业4,0,0.5,0.4,0.6,就绪队列R1,就绪队列R2,就绪队列Rn,各就绪队列的关系：优先级：RiRi+1时间片：qRi+1=2qRi,新就绪进程,被抢占,时间片完,（
10、7）多级反馈队列调度算法,原理：设置多个就绪队列，当一个新进程进入系统时，被安排在第一个就绪队列的对尾。给每个就绪队列赋予不同的时间片和优先权。同一就绪队列中的进程按FCFS的方式调度。调度算法：即首先调度第一个队列处于队首的进程，若运行结束，则退出系统，调度下一个进程。若时间片完还不能运行结束，则将其插入到下一个就绪队列的队尾。只有当前i个就绪队列为空时，才能调度第i+1个就绪队列中的进程(1in)当更高优先权队列有新进程到来时，当前运行进程被抢占，被抢占的进程进入原队列的队尾。,6.2 单处理器系统的进程调度,6.2 单处理器系统的进程调度,优点：能满足各类作业的要求。输入输出型作业输入输
11、出型作业赋予较高优先权，并且，第1级就绪队列的时间片通常略大于大多数输入输出型进程产生一个输入输出要求所需的运行时间。短作业长作业,6.3 多处理机系统,1. 硬件组织总线式结构（P116图6.2，6.3）交叉开关式结构（P117图6.4）多端口存储结构P117图6.5）,2.多处理器系统的分类（1）多处理器簇（分布式系统）每个处理器都有自己的存储器，这种系统称为多计算机系统，也称为松散耦合系统。（2）共享存储器的多处理器系统多个处理器共享一个公用存储器，这种系统称为共享存储器的多处理器系统，也称为紧密耦合系统。根据系统中多个处理器的关系又可分为：,6.3 多处理器系统,主从式多处理器结构（主
12、处理器运行OS，从处理器只执行用户程序）对称式多处理器结构（SMP）,6.3 多处理器系统,3. 对称式多处理器系统SMP（1）对称式多处理器结构（SMP）系统中的多个处理器地位相同，都能运行OS的内核代码和处理中断，执行进程（线程）调度。系统中所有的处理器共享主存储器，没有自己的私用存储器，但每个处理器是自包含的，即都有自己的逻辑单元、控制单元，寄存器等。,6.3 多处理器系统,（2）多处理器OS原理和概念与单机OS没有本质区别，但是，需要解决多个处理器的同步、互斥与通信问题，多个处理器的管理与分配问题，OS代码的可重入（可重入代码在被访问过程中不允许任何进程对其进行修改）问题，以及处理器的
13、故障处理问题等。,6.3 多处理器系统,6.4 多处理器系统的处理器管理和调度,1.多处理器系统的三个特征（1）主存模型一致的主存访问（共享一个主存）非一致的主存访问（每个处理器有本地主存）非远程主存访问（2）同步支持唤醒丢失问题巨群问题：几个线程阻塞于一个资源，唤醒CPU上的所有进程可能会引起它们在不同处理器上同时被调度，引起新的竞争。,硬件同步机制是实现多处理机系统的最必要的基本条件。在多处理器系统中，通常用处理器池来管理所有的处理器，处理器之间可以通过发送跨处理器中断来进行通信。,（3）软件体系结构主/从式功能非对称式对称式2.多处理器调度模式目前的多处理器调度大多是基于线程的调度。,6
14、.4 多处理器系统的处理器管理和调度,（1）负载共享调度 系统中所有的处理器共同使用一个全局性的可运行线程队列，也称为自调度算法。常用自调度算法：先来先服务最少线程数目优先调度算法（最少未被调度的线程数的作业中的线程，优先级最高）可抢占的最少线程数目优先调度算法（允许抢占低优先级线程的处理器）,6.4 多处理器系统的处理器管理和调度,优点：不会出现各处理机的忙闲不均，只要可运行线程队列不空，就不会存在处理器空闲的情况。缺点：公用的线程队列必须互斥访问。被抢占的线程不一定能回到原来的处理器上运行。同一个进程的多个线程存在不能同时得到处理器的可能，使同一进程多个线程之间的高度协调和交互的开销增加。
15、,6.3 多处理器系统,（2）专用处理器调度模式当一个应用程序执行时，就为该应用程序的每一个线程分配一个处理器，直到该应用程序完成。 优点：一次完成整个应用程序的调度，调度开销小，几乎没有进程开关的开销。 缺点：处理器的利用率不高。,6.3 多处理器系统,（3）群调度原理： 为一个应用程序的线程集合分配一个处理器集合，并且，这种分配可以随时间的改变而改变，系统中的每个处理器属于一个处理器集合，每个处理器集合可以根据需要动态变化。优点： 减少了调度频率和调度开销。,6.3 多处理器系统,（4）调度类与多模式调度器 为满足系统中多个进程的不同调度要求，用调度类来定义系统中所有进程的调度策略。调度类至少可以分成：分时类和实时类。 对同一个系统中不同的调度类使用不同的调度算法，这种调度方式也称为多模式调度器。,6.4 多处理器系统的处理器管理和调度,（5）实时调度实现实时调度的基本条件调度信息的要求：就绪时间开始截止时间和完成截止时间处理时间资源要求优先级,6.4 多处理器系统的处理器管理和调度,系统处理能力强在n个处理器的情况下，m个周期性实时任务系统能够进行实时调度的条件为：,Ci:处理时间Pi:周期,6.4 多处理器系统的处理器管理和调度,例：,假如在一个单处理器系统中有6个实时任务，周期都为50ms，且每次的处理机时间为10ms，请问系统是否可调度？,
