05 第三章 处理机调度与死锁 3.1-3.4.pptx

第1页：第三章 处理机调度与死锁封面

第三章 处理机调度与死锁：本页为《计算机操作系统》课件封面，标注课程名称与英文名称 Operating Systems，并列出 WINDOWS、UNIX、LINUX 等常见操作系统类型。

第2页：3.1处理机调度的层次

3.1处理机调度的层次：一个批处理型作业，从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，可能要经历的三级调度：中级调度创建静止就绪静止阻塞高级调度低级调度执行就绪阻塞终止。

第3页：3.1.1高级调度（作业调度）

3.1.1高级调度（作业调度）

• 作业调度、长程调度、接纳调度
• 主要功能
• 挑选若干作业进入内存
• 为它们创建进程、分配必要的资源
• 再将新创建的进程插入就绪队列，准备执行
• 调度对象
• 作业

第4页：作业和作业步

作业和作业步

• 1.作业和作业步
• 作业(JOB) :程序+数据+作业说明书
• 一个作业可划分成若干部分，每部分称一个作业步

第5页：作业控制块JCB

作业控制块JCB

• 2．作业控制块JCB
• JCB是作业在系统中存在的标志
• 通常应包含的内容有
• 作业的基本情况
• 作业标识、用户名称、作业状态等
• 作业的调度信息
• 优先级、作业已运行时间
• 资源需求
• 预计运行时间、要求内存大小、要求I/O设备的类型和数量

第6页：作业调度的两个决定

作业调度的两个决定

• 3．作业调度
• 须做出以下两个决定：1)决定接纳多少个作业
• 多道程序度的确定应根据系统的规模和运行速度等情况做适当的折衷。2)决定接纳哪些作业
• 调度算法
• 先来先服务、短作业优先、基于作业优先级、“响应比高者优先”

第7页：分时系统的调度要求

分时系统的调度要求

• 3．作业调度
• 分时系统要求
• 及时响应
• 无需再配置上述的作业调度机制
• 需要有某些限制性措施来限制进入系统的用户数
• 如果系统尚未饱和，将接纳所有授权用户
• 否则，将拒绝接纳
• 在实时系统中通常也不需要作业调度

第8页：3.1.2低级调度

3.1.2低级调度

• 也称为：进程调度、短程调度
• 进程调度是最基本的一种调度
• 决定就绪队列中的哪个进程应获得处理机
• 由分派程序执行把处理机分配给该进程的具体操作
• 调度的对象
• 进程(或内核级线程)
• 在多道批处理、分时和实时三种类型的OS中，都必须配置这级调度

第9页：低级调度的功能

低级调度的功能

• 1低级调度的功能1.保存处理机的现场信息
• 处理机的现场信息进程控制块(PCB)2.按某种算法选取进程。3.把处理器分配给进程
• 由分派程序把处理器分配给进程
• 恢复处理机现场
• PCB处理器相应的各个寄存器
• 把处理器的控制权交给该进程

第10页：进程调度的三个基本机制

进程调度的三个基本机制

• 2．进程调度中的三个基本机制
• （1）排队器
• 应事先将系统中所有的就绪进程按照一定的方式排成一个或多个队列
• （2）分派器(分派程序)
• （3）上下文切换机制
• 两对上下文切换操作
• ①保存当前进程的上下文，装入分派程序的上下文
• ②移出分派程序，新选进程的CPU现场信息装入到处理机的各个相应寄存器中

第11页：进程调度方式

进程调度方式

• 3进程调度方式
• 非抢占方式
• 抢占方式

第12页：非抢占方式

非抢占方式

• 一旦把处理机分配给某进程后，一直让它运行下去，直至该进程完成，自愿释放处理机，或被阻塞
• 引起进程调度的因素1.正在执行的进程执行完毕，或因发生某事件而不能再继续执行；2.执行中的进程因提出I/O请求而暂停执行；3.在进程通信或同步过程中执行了某种原语操作
• 如：P操作(wait操作)、Block原语等

第13页：抢占方式

抢占方式

• 允许调度程序根据某种原则去暂停某个正在执行的进程，将处理机重新分配给另一进程
• 抢占方式的优点是
• 可以防止一个长进程长时间占用处理机
• 能为大多数进程提供更公平的服务
• 特别是能满足对实时任务的需求

第14页：抢占原则

抢占原则

• 抢占原则1.优先权原则
• 允许优先权高的新到进程抢占当前进程的处理机。2.短作业(进程)优先原则
• 短作业(进程)可以抢占当前较长作业(进程)的处理机。3.时间片原则
• 各进程按时间片轮流运行
• 当一个时间片用完后，便停止该进程的执行而重新进行调度

第15页：3.1.3中级调度（中程调度）

3.1.3中级调度（中程调度）

• 目的
• 提高内存利用率和系统吞吐量
• 作用
• 外存内存
• 挂起状态（静止）非挂起状态（活动）
• 中级调度实际上就是存储器管理中的对换功能

第16页：三种调度的运行频率

三种调度的运行频率

• 运行频率
• 进程调度的运行频率最高
• 进程调度算法不宜太复杂
• 作业调度（长程调度）
• 往往是发生在一个(批)作业运行完毕
• 作业调度的周期较长，运行频率较低
• 允许作业调度算法花费较多的时间
• 中级调度的运行频率基本上介于上述两种调度之间

第17页：3.2调度队列模型和调度准则

3.2调度队列模型和调度准则

• 调度队列模型
• 仅有进程调度的调度队列模型
• 具有高级和低级调度的调度队列模型
• 同时具有三级调度的调度队列模型

第18页：仅有进程调度的队列模型

仅有进程调度的队列模型

• 1．仅有进程调度的调度队列模型
• 组织形式依赖于调度算法
• 把处于就绪状态的进程组织成栈、树或一个无序链表
• 在分时系统中，常把就绪进程组织成
• FIFO队列形式处理器进程调度完成时间片完就绪队列交互式用户阻塞队列等待事件

第19页：具有高级和低级调度的队列模型

具有高级和低级调度的队列模型：2具有高级和低级调度的调度队列模型处理器进程调度作业调度完成时间片完就绪队列后备队列阻塞队列等待事件2阻塞队列等待事件1。

第20页：批处理系统中的调度模型

批处理系统中的调度模型

• 2具有高级和低级调度的调度队列模型
• 在批处理系统中，最常用的是最高优先权调度算法
• 就绪队列的形式
• 优先权队列
• 无序链表就绪队列就绪队列

第21页：同时具有三级调度的队列模型

同时具有三级调度的队列模型：3同时具有三级调度的调度队列模型中级调度创建静止就绪静止阻塞低级调度执行活动就绪活动阻塞终止高级调度。

第22页：三级调度模型中的队列流向

三级调度模型中的队列流向：中级调度处理器低级调度高级调度完成时间片完就绪队列后备作业队列交互式用户阻塞队列等待事件事件出现挂起就绪队列挂起阻塞队列中级调度处理器三级调度模型。

第23页：选择调度方式和算法的准则

选择调度方式和算法的准则

• 3.2.2选择调度方式和调度算法的准则
• 面向用户的准则
• 周转时间短
• 响应时间快
• 截至时间的保证
• 优先权准则
• 面向系统的准则
• 系统吞吐量高
• 处理机利用率好
• 资源的平衡利用

第24页：周转时间

周转时间

• 通常把周转时间的长短
• 评价批处理系统的性能的重要准则之一
• 从作业被提交给系统开始，到作业完成为止的这段时间间隔
• 它包括四部分时间
• 作业在外存后备队列上等待(作业)调度的时间
• 进程在就绪队列上等待进程调度的时间
• 进程在CPU上执行的时间
• 进程等待I/O操作完成的时间
• 平均周转时间

第25页：带权周转时间和平均带权周转时间

带权周转时间和平均带权周转时间

• 带权周转时间：W = T/Ts
• T：作业的周转时间
• Ts：系统为它提供服务的时间
• 平均带权周转时间

第26页：响应时间

响应时间

• 相关指标
• 响应时间
• 评价分时系统的性能
• 从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或者说，直到屏幕上显示出结果为止的一段时间间隔
• 截止时间
• 评价实时系统性能的重要指标
• 指某任务必须开始执行的最迟时间，或必须完成的最迟时间

第27页：系统吞吐量

系统吞吐量

• 相关指标
• 系统吞吐量
• 评价批处理系统性能的重要指标
• 指在单位时间内系统所完成的作业数
• 处理的长作业多，则吞吐量低
• 资源利用率
• CPU利用率=CPU有效工作时间/CPU总的运行时间
• CPU总的运行时间=CPU有效工作时间+CPU空闲等待时间

第28页：CPU利用率示例数据

CPU利用率示例数据：CPU利用率ABC30608090100110120160210170190240230310250CPUI/O设备1I/O设备2220CPU利用率=（20+10+20+30+10+30+30+10+20+10）/310=190 / 310 = 61.3 %0。

第29页：3.3调度算法

3.3调度算法

• 调度算法
• 根据系统的资源分配策略所规定的资源分配算法
• 不同的系统和系统目标，通常采用不同的调度算法

第30页：先来先服务（FCFS）调度算法

先来先服务（FCFS）调度算法

• 1先来先服务（FCFS）调度算法
• 可用于作业调度、进程调度
• 作业调度中采用该算法时
• 按照作业进入系统后备队列的先后次序来挑选作业
• 进程调度中采用FCFS算法时
• 从就绪队列中选择一个最先进入该队列的进程
• 为之分配处理机

第31页：FCFS调度算法举例

FCFS调度算法举例

• FCFS算法调度算法举例
• 比较有利于长作业(进程)，而不利于短作业(进程)

第32页：短作业(进程)优先调度算法

短作业(进程)优先调度算法

• 2短作业(进程)优先调度算法
• 可用于作业调度、进程调度
• 短作业优先(SJF)的调度算法
• 从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行
• 短进程优先(SPF)调度算法
• 从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它

第33页：SJF调度算法举例

SJF调度算法举例：SJF算法调度算法举例1平均周转时间=(4+8+16+3+9)/5=8平均带权周转时间=（1+2.67+3.2+1.5+2.25）/5=2.10236913带权周转时间服务时间4/4=18/3=2.6716/5=3.23/2=1.5作业ABCDE435241849/4=2.25。

第34页：FCFS与SJF调度性能对比

FCFS与SJF调度性能对比：图3-4FCFS和SJF调度算法的性能。

第35页：SJ(P)F调度算法的缺点

SJ(P)F调度算法的缺点

• SJ(P)F调度算法缺点
• 对长作业不利
• 完全未考虑作业的紧迫程度
• 因而不能保证紧迫性作业(进程)会被及时处理
• 无法精确知道一个作业的运行时间
• 作业(进程)的长短只是根据用户所提供的估计执行时间而定的

第36页：3.3.2高优先权优先调度算法

3.3.2高优先权优先调度算法

• 优先权调度算法的类型
• 非抢占式优先权算法
• 用于批处理系统中
• 也可用于某些对实时性要求不严的实时系统中
• 抢占式优先权调度算法
• 常用于要求比较严格的实时系统中
• 对性能要求较高的批处理和分时系统中

第37页：优先权的类型

优先权的类型

• 2优先权的类型
• 静态优先权
• 在创建进程时确定的，且在进程的整个运行期间保持不变
• 动态优先权
• 在创建进程时所赋予的优先权
• 可以随进程的推进或随其等待时间的增加而改变的

第38页：静态优先权的确定依据

静态优先权的确定依据

• 确定静态进程优先权的依据
• 进程类型
• 系统进程(如接收进程、对换进程、磁盘I/O进程)的优先权高于一般用户进程的优先权
• 进程对资源的需求
• 要求少的进程应赋予较高的优先权
• 用户要求
• 这是由用户进程的紧迫程度及用户所付费用的多少来确定优先权的
• 静态优先权法简单易行，系统开销小，但不够精确

第39页：动态优先权的调整

动态优先权的调整

• 动态优先权调整例子
• 在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高
• 优先权初值低的进程优先权便可能升为最高，从而可以获得处理机
• 当采用抢占式优先权调度算法时，如果再规定当前进程的优先权以速率b下降
• 占有CPU时间愈长的进程逐步降低优先级
• 可防止一个长作业长期地垄断处理机

第40页：高响应比优先调度算法

高响应比优先调度算法

• 3高响应比优先调度算法
• FCFS与SJF是片面的调度算法
• FCFS只考虑作业等候时间而忽视了作业的计算时问
• SJF只考虑用户估计的作业计算时间而忽视了作业等待时间
• 高响应比优先调度算法是介乎这两者之间的折衷算法
• 既考虑作业等待时间，又考虑作业的运行时间
• 既照顾短作业，又不使长作业的等待时间过长
• 改进了调度性能

第41页：响应比的定义

响应比的定义

• 响应比定义
• 引入动态优先权，并使作业的优先级随着等待时间的增加而以速率a提高
• 该优先权的变化规律可描述为
• 优先权=RP

第42页：HRRF算法举例

HRRF算法举例

• HRRF算法举例作业作业1 0 20作业2 5 15作业3 10 5作业4 15 10
• 平均作业周转时间T=(20+(40-5)+(25-10)+(50-15))/4=26.25
• 平均带权作业周转时间W=(20/20+(40-5)/15+(25-10)/5+(50-15)/10)/4=2.46。到达系统时间所需CPU时间0 20 25 40 501+(20-5)/15=21+(20-10)/5=31+(20-15)/10=1.51+(25-5)/15=2.31+(25-15)/10=2

第43页：HRRF算法的运行结果

HRRF算法的运行结果：HRRF算法性能介于SJF与FCFS之间。T=26.25 W=2.46到达系统时间所需CPU时间。

第44页：高响应比算法的优缺点

高响应比算法的优缺点

• 分析
• 优点
• 兼顾长短作业
• 缺点
• 增加系统开销
• 每要进行调度之前，都须先做响应比的计算

第45页：3.3.3基于时间片的轮转调度算法

3.3.3基于时间片的轮转调度算法

• 在早期的时间片轮转法中，将所有的就绪进程按先来先服务的原则排成一个队列
• 每次调度时，把CPU分配给队首进程，并令其执行一个时间片
• 当这个时间片结束时，强迫一个进程让出处理器
• 让它排列到就绪队列的尾部，等候下一轮调度。处理器完成时间片到就绪队列

第46页：时间片q=1时的进程运行情况

时间片q=1时的进程运行情况：q=1时的进程运行情况ACBDE103254769811101312181743524。

第47页：时间片q=4时的进程运行情况

时间片q=4时的进程运行情况：q=4时的进程运行情况ACBDE103254769811101312181743524。

第48页：时间片大小的确定

时间片大小的确定：时间片略大于一次典型的交互所需要的时间。

第49页：多级反馈队列调度算法

多级反馈队列调度算法

• 2多级反馈队列调度算法
• 反馈循环队列或多队列策略
• 多级反馈队列调度允许进程在队列之间移动。优先级高低

第50页：多级反馈队列调度算法的性能

多级反馈队列调度算法的性能

• 3多级反馈队列调度算法的性能1.终端型作业用户
• 终端型作业用户所提交的作业通常较小，系统只要能使这些作业(进程)在第一队列所规定的时间片内完成，便可使终端型作业用户都感到满意。2.短批处理作业用户
• 其周转时间仍然较短。3.长批处理作业用户
• 用户不必担心其作业长期得不到处理

第51页：作业1：可变分区内存管理

作业1：可变分区内存管理：作业1（多道程序环境下）某多道程序设计系统采用可变分区内存管理，供用户使用的主存为200K，磁带机5台。采用静态方式分配外围设备，且不能移动在主存中的作业，进程调度采用FCFS，忽略用户作业I/O时间。现有作业序列如下：作业号进入后备队列运行时间主存需求量磁带需求量A8：3040分钟30k3B8：5025分钟120k1C9：0035分钟100k2D9：0520分钟20k3E9：1010分钟60k1现求：FCFS算法选中作业执行的次序及作业平均周转时间？。

第52页：作业2：两道作业批处理系统

作业2：两道作业批处理系统

• 作业2
• 有一个具有两道作业的批处理系统，作业调度采用短作业优先的非抢式调度算法，进程调度采用以优先数为基础的抢占式调度算法，在下表所示的作业序列中，作业优先数即为进程优先数，优先数越小优先级越高。作业到达时间估计运行时间优先数1 8：00 40分32 8：20 30分13 8：30 50分24 8：50 20分4
• （1）列出所有作业进入内存时间及结束时间
• （2）计算平均作业周转时间

第53页：3.4实时调度

3.4实时调度

• 实现实时调度的基本条件1.必要信息
• 就绪时间、开始截至时间、完成截至时间、处理时间
• 资源要求；优先级；2.系统处理能力强3.采用抢占式机制---硬实时任务；截止时间要求；4.有快速切换机制---快速响应外部中断；快速任务分派

第54页：实时调度算法的分类

实时调度算法的分类

• 非抢占式
• 轮转调度(同质任务)
• 优先调度
• 抢占式
• 时钟中断优先
• 立即抢占优先

第55页：非抢占式轮转调度算法

非抢占式轮转调度算法：非抢占式轮转调度算法。

第56页：非抢占式优先调度算法

非抢占式优先调度算法：非抢占式优先调度算法。

第57页：基于时钟中断的抢占式优先权调度

基于时钟中断的抢占式优先权调度：基于时钟中断的抢占式优先权调度算法。

第58页：立即抢占的优先权调度算法

立即抢占的优先权调度算法：立即抢占的优先权调度算法。

第59页：常用的几种实时调度算法

常用的几种实时调度算法

• 最早截止时间优先算法
• 非抢占式和抢占式
• EDF算法用于非抢占调度的调度方式

第60页：实时任务的优先级调度

实时任务的优先级调度：优先级调度。

第61页：EDF算法用于抢占调度方式

EDF算法用于抢占调度方式：EDF算法用于抢占调度方式。

第62页：最低松弛度优先（LLF）算法

最低松弛度优先（LLF）算法：松弛度=必须完成时间-本身运行时间-当前时间。

第63页：LLF调度过程（t=0）

LLF调度过程（t=0）：利用LLF算法进行调度的情况。

第64页：LLF调度过程（t=10）

LLF调度过程（t=10）：利用LLF算法进行调度的情况。

第65页：LLF调度过程（t=30）

LLF调度过程（t=30）：利用LLF算法进行调度的情况。

第66页：LLF调度过程（t=40）

LLF调度过程（t=40）：利用LLF算法进行调度的情况。

第67页：LLF调度过程（t=45）

LLF调度过程（t=45）：利用LLF算法进行调度的情况。

第68页：LLF调度过程（t=55）

LLF调度过程（t=55）

• 利用LLF算法进行调度的情况
• t6=55时，A4未进入第4周期；B2已进入第2周期

第69页：LLF调度过程（t=70）

LLF调度过程（t=70）：利用LLF算法进行调度的情况。

第70页：实时调度例题：四个周期性事件

实时调度例题：四个周期性事件：一个实时系统有四个周期性事件，周期分别为50、100、300和250ms。若假设其处理时间分别需要35、20、10和x ms，则该系统可调度允许的x值最大为多少？答：（35/50+20/100+10/200+x/250）<1x<16.75ms。

第71页：作业

作业：对下面的5个非周期性实时任务，按最早开始截至时间优先调度算法应如何进行CPU调度？进程到达时间执行时间开始截至时间A1020110B202020C402050D502090E602070。