当前位置：文档之家 › 第3章 处理机调度与死锁(计12级课堂最新)

第3章 处理机调度与死锁(计12级课堂最新)

  • 格式：ppt
  • 大小：4.84 MB
  • 文档页数：95

下载文档原格式

  / 95

合集下载

第三章 处理机调度与死锁

第三章 处理机调度与死锁
8
第三章 处理机调度与死锁
3. 分时系统的目标 (1) 响应时间快
响应时间指用户提交请求到系统首次响应为止的时 间。
(2) 均衡性。 系统响应时间的快慢应与用户所请求的复杂性相适
应。
9
第三章 处理机调度与死锁
4. 实时系统的目标 (1) 截止时间的保证。 (2) 可预测性。
10
第三章 处理机调度与死锁
第三章 处理机调度与死锁
第三章 处理机调度与死锁
3.1 处理机调度的层次和调度算法的目标 3.2 作业与作业调度 3.3 进程调度 3.4 实时调度 3.5 死锁概述 3.6 预防死锁 3.7 避免死锁 3.8 死锁的检测与解除 习题
1
第三章 处理机调度与死锁
3.1 处理机调度的层次和调度算法的目标
为了提高系统效率，应当让管理输入输出的I/O进程与计算 进程搭配起来，并给予I/O进程较高的优先级。这样，一旦 I/O进程被唤醒就可很快得到运行，启动低速外设，而后再 被阻塞起来让计算进程使用CPU，使主机和外设高度并行 运行。
24
第三章 处理机调度与死锁
2. 高响应比优先调度算法(Highest Response Ratio Next，HRRN)
16
第三章 处理机调度与死锁 17
第三章 处理机调度与死锁
FCFS算法的优缺点 • 比较有利于长作业（进程），而不利于短作业（进
程）。 上图中短作业C的带权周转时间高达100，不能容忍。 而D仅为1.99。 • FCFS算法有利于CPU繁忙型作业（该类型的作业需 要大量CPU时间进行计算，很少I/O。）不利于I/O繁 忙型作业（频繁的请求I/O服务的作业）
5
第三章 处理机调度与死锁
2. 批处理系统的目标 (1) 平均周转时间短。 对每个用户而言，都希望自己作业的周转时间最短。但 作为计算机系统的管理者，则总是希望能使平均周转时间最 短，这不仅会有效地提高系统资源的利用率，而且还可使大 多数用户都感到满意。应使作业周转时间和作业的平均周转 时间尽可能短。否则，会使许多用户的等待时间过长，这将 会引起用户特别是短作业用户的不满。可把平均周转时间描 述为：

第三章_调度与死锁(课件)

第三章_调度与死锁(课件)

• 因此，第二个应该调度作业1运行，因为它的响应比最 高。它运行了1.5后完成，这时的时间是11.4。第三个 调度的是作业3，它运行了1.0后完成，这时的时间是 12.4。整个实施过程如下。
• 作业的调度顺序是2→1→3。各自的周转时间为：作业 1为0.9；作业2为2.6；作业3为2.9。
4、 时间片轮转（RR）算法
该算法主要用于分时系统，按照公平服务的原则， 为进程分配CPU时间片。是一种剥夺式的算法。 轮转法的关键是时间片的选取： 时间片太大，则轮转法蜕化为FCFS法。 时间片太小，则增加CPU的额外开销。 影响时间片设臵的主要因素：
系统响应时间R、就绪进程数N、计算机处理能力等。 时间片长度：
q = R / N
2。三级调度中，最核心的是那一级调度？为什么？
补充：关于作业的概念
作业 — 是用户请求计算机系统执行的一次独立的上机任 务（相当于一个程序），是能够共享公共资源区域的一族 有关进程（家族）。 从静态观点看，作业由 控制命令系列、程序集、数据 集三部分构成。 作业步 — 将一个作业划分为若干个顺序处理的步骤，作 业步相互独立又相互关联。 作业控制块 — JCB（Job Control Block）用于描述作业。 定义为记录类型（作业名、优先级、建立时间、状态外 存地址、大小等）。
三级调度的模型
内存 外存
CPU
等待事件
执行 状态
时间 片到 释放
即交换调度
交换文件
I/O请求 阻塞 状态
进程 调度
就绪 状态
中级调度
就绪队列
阻塞队列
阻 塞 队 列
就 绪 队 列
作业调度
后备作业队列
思考与讨论
各级调度间的关系

chapter3处理机调度与死锁

chapter3处理机调度与死锁

1.先进先出(FIFO)算法
• FCFS有利于长作业，而不利于短作业。
– 该算法短作业C的带权周转时间为100，这是无法容忍的， 而长作业D的带权周转时间仅为1.99。
• 所以，FCFS有利于CPU繁忙型作业（如科学计算）， 而不利于I/O繁忙型作业。目前大多数的事务处理都 属于I/O繁忙型作业
2.短作业(进程)优先调度算法
图 3-7 A和B任务每次必须完成的时间
在刚开始时(t1=0)，A1必须在20ms时完成，而它本身运 行又需 10 ms，可算出A1的松弛度为10ms；B1必须在50ms 时完成， 而它本身运行就需25 ms，可算出B1的松弛度为25 ms，故调度程序应先调度A1执行。在t2=10 ms时，A2的松弛 度可按下式算出： A2的松弛度=必须完成时间-其本身的运行时间-当前时间 =40 ms-10 ms-10 ms=20 ms 类似地，可算出B1的松弛度为15ms，调度程序应选择 B1运行。t3=30 ms时，A2的松弛度已减为0，B1的松弛度为 15 ms，于是调度程序应抢占B1的处理机而调度A2运行…….
2.进程调度的任务
进程调度的任务是控制协 调进程对CPU的竞争,即按一定 的调度算法从就绪队列中选中 一个进程，把CPU的使用权交 给被选中的进程
3.确定法的原则
• 具有公平性 • 资源利用率高（特别是CPU利用 率） • 在交互式系统情况下要追求响应 时间（越短越好） • 在批处理系统情况下要追求系统 吞吐量
3.最高优先权优先调度算法
• 动态优先数法：在进程创建时创立一个优 先数，但在其生命周期内优先权可以随进 程的推进或随其等待时间的增加而改变的， 以便获得更好的调度性能。
4.高响应比优先调度算法
优先权的变化规律可描述为：

操作系统 chapter3 处理机调度与死锁PPT课件

操作系统 chapter3 处理机调度与死锁PPT课件

阻 塞， 挂 起队 列 事
件 出
挂起
现
阻 塞队 列
等 待事 件
图 3-3 具有三级调度时的调度队列模型
3.3 调 度 算 法
3.3.1 先来先服务和短作业(进程)优先调度算法
1. 先来先服务调度算法
图 3-4 FCFS和SJF调度算法的性能
就 绪 队 列1 就 绪 队 列2 就 绪 队 列3 就 绪 队 列n
② 执行中的进程因提出I/O请求而暂停执行； ③ 在进程通信或同步过程中执行了某种原语操作，如P 操作(wait操作)、Block原语、Wakeup原语等。 优点：实现简单、系统开销小。
缺点：难以满足紧急任务的要求——立即执行，实时系统中 不宜采用这种调度方式。
2、抢占方式(Preemptive Mode) 抢占的原则有： • 优先权原则。 (2) 短作业(进程)优先原则。 (3) 时间片原则。 优点：防止长进程长时间占用处理机，适合实时任务 缺点：系统开销大
第三章 处理机调度与死锁
3.1 处理机调度的层次 3.2 调度队列模型和调度准则 3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除
1、非抢占方式(Non-preemptive Mode) 引起进程调度的因素可归结为这样几个：
① 正在执行的进程执行完毕，或因发生某事件而不能再 继续执行；
4. 具有快速切换机制
该机制应具有如下两方面的能力：
(1) 对外部中断的快速响应能力。为使在紧迫的外部 事件请求中断时系统能及时响应，要求系统具有快速硬件 中断机构，还应使禁止中断的时间间隔尽量短，以免耽误 时机(其它紧迫任务)。
(2) 快速的任务分派能力。在完成任务调度后，便应 进行任务切换。为了提高分派程序进行任务切换时的速度， 应使系统中的每个运行功能单位适当的小，以减少任务切 换的时间开销。

第三章 处理机调度与死锁PPT课件

第三章 处理机调度与死锁PPT课件
第三章 处理机调度与死锁
3.1 处理机调度的层次 3.2 调度队列模型和调度准则 3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除
1
第一部分
整体概述
THE FIRST PART OF THE OVERALL OVERVIEW, PLEASE SUMMARIZE THE CONTENT
✓ 当一个进程运行完毕，或由于某种错误而终止运行 ✓ 当一个进程在运行中处于等待状态（等待I/O） ✓ 在进程通信中，执行中的进程执行了某种原语操作
（P操作，阻塞原语，唤醒原语） ✓ 分时系统中时间片到 ✓ 当有一个优先级更高的进程就绪
1) 非抢占方式(Non-preemptive Mode)
2) 抢占方式(Preemptive Mode)
2
3.1 处理机调度的层次
处理机三级调度
1.高级调度――作业调度
在批处理系统中，作业是先驻留在外存的输入井上 的，因此需要有作业调度。然而在分时系统中，通过键 盘输入的命令和数据直接进入内存，无需作业调度。 2.低级调度――进程调度
进程调度决定就绪队列中哪个进程将获得处理机， 然后由分派程序执行把处理机分配给该进程的操作。进 程调度是最基本的调度，任何操作系统都有进程调度。 3.中级调度——对换
作业 调度 后备队列
时间片完 就绪队列
进程调度 进程完成 CPU
事件1出现
等待事件1
事件2出现
等待事件2
… … … …
事件n出现
等待事件 n
具有高、低两级调度的调度队列模型
15
3.同时具有三级调度的调度队列模型
作业调度
时间片完

第3章-处理机调度与死锁

第3章-处理机调度与死锁
S2 就绪队列 2
S3 就绪队列 3
就绪队列 n
(时 间片 ： S1＜S2＜S3)
20
第三章 调度与死锁
最短剩余时间
21
第三章 调度与死锁
3.3.2 高优先权优先调度算法
适合于作业调 度和进程调度
1. 优先权调度算法旳类型 1)非抢占式优先权算法（用于批处理、要求不严旳实时）
系统一旦把处理机分配给就绪队列中优先权最高旳进 程后，该进程便一直执行下去，直至完毕；或因发生某事 件使该进程放弃处理机时，系统方可再将处理机重新分配 给另一优先权最高旳进程。
1 1.17
2.25
18 12 2.4
20 12 6
8. 60 2.56
• 完 周转 带权周转 毕 时间 时间
3时 3
1
9间 7
1.17
15 11 2.75
20 14 2.8
11 3
1.5
7.60 1.84
例1 FCFS和SJF调度算法旳性能比 较
第三章 调度与死锁
例2. FCFS和SJF调度算法旳性能比较
31
第三章 调度与死锁
(2) 时间片大小旳拟定
退化成
• 时间片太大
FCFS算法
• 时间片过小切换开销大。
时间片大小拟定要考虑旳原因： (1) 系统对响应时间旳要求。（顾客数一定时，成正比）
(2)就绪队列中旳进程数目。（确保响应时间，成反比）
(3)系统旳处理能力。（确保顾客键入旳命令能在一种时 间片内处理完毕）
优点:简朴、系统开销小，合用于大多数批处理系统环境。 缺陷：难以满足紧急任务旳要求——立即执行，在要求比较 严格旳实时系统中，不宜采用这种调度方式。
3
第三章 调度与死锁

《处理机调度与死锁》PPT课件


当这些进程重又具备运行条件且内存又稍有空闲时，由 中级调度来决定把外存上的那些又具备运行条件的就绪进程 重新调入内存，并修改其状态为就绪状态，挂在就绪队列上 等待进程调度。
中级调度实际上就是存储器管理中的对换功能。
整理ppt15Fra bibliotek第三章 处理机调度与死锁
在上述三种调度中，
• 进程调度的运行频率最高，在分时系统中通常是10～100 ms便进行一次进程调度，因此把它称为短程调度。为避免进 程调度占用太多的CPU时间，进程调度算法不宜太复杂。
（2） 分派器(分派程序)。
（3）上下文切换机制。当对处理机进行切换时，会发生
两对上下文切换操作。在第一对上下文切换时，操作系统将
保存当前进程的上下文，而装入分派程序的上下文，以便分
派程序运行；在第二对上下文切换时，将移出分派程序，而
把新选进程的CPU现场信息装入到处理机的各个相应寄存器
中。
应当指出，上下文切换将花去不少的处理机时间，即使是现代计算
3.1.3 中级调度(Intermediate Level Scheduling) 又称中程调度(Medium-Term Scheduling)。 引入中级调度的主要目的是为了提高内存利用率和系统 吞吐量。
使那些暂时不能运行的进程不再占用宝贵的内存资源， 而将它们调至外存上去等待，把此时的进程状态称为就绪驻 外存状态或挂起状态。
作业调度或长程调度（LongTerm Scheduling）
1．作业和作业步
(1) 作业(Job)。作业不仅包含了通常的程序和数据，而且 还应配有一份作业说明书，系统根据该说明书来对程序的运 行进行控制。
在批处理系统中，是以作业为基本单位从外存调入内存的。
整理ppt

计算机操作系统第三章处理机调度与死锁 ppt课件


2决定接纳哪些作业
选用何种调度算法：先来先服务、 短作业优先、基于作业优先级、响 应比高者优先。
PPT课件
6
注意
批处理系统中，作业是首先进入外存， 然后经由作业调度分批进入内存；
分时系统及实时系统中，由于对响应 时间有要求，因此用户输入的命令和数据 等是直接进入内存的，无须配置作业调度 机制。
PPT课件
PPT课件
14
同时具有三级调度的调度队列模型
作业 调度
后备队列
中级 调度
时间片完 就绪队列 就绪、挂起队列
进程调度
进程完成
CPU
挂起
事件出现
事件发生
阻塞、挂起队列 阻塞队列
挂起 等待事件
具有高、低、中三级调度的调度队列模型
PPT课件
15
选择调度方式和调度算法的若干准则
• 面向用户的准则
– 周转时间短（批处理） – 响应时间快（分时） – 截止时间保证（实时） – 优先权准则（all）
4
2 作业控制块
多道批处理系统中，为每个作业配备一个作业 控制块（JCB），它是作业在系统中存在的标志。
作业运行期间，系Biblioteka 按照JCB中的信息对作业进行 控制。
JCB中保存了系统对作业进行管理和调度所需 的全部信息。例如：作业标识、用户名称、用户帐 户、作业类型、作业状态、调度信息、资源需求、 进入系统时间、开始处理时间、作业完成时间、作 业退出时间、资源使用情况等。
第三章 处理机调度与死锁
要解决的三个问题：
WHAT：按什么原则分配CPU？ —进程调度算法
WHEN：何时分配CPU？ —进程调度的时机
HOW： 如何分配CPU？ —CPU调度过程（进程的上下文切换）

第三章处理机调度与死锁讲义

ri 为某作业i的实际执行时间
Page 7
第三章 处理机调度与死锁 3.1 处理机调度的层次和调度算法的目标 3.1.2 处理机算法的目标
2 批处理系统的目标
（2）系统吞吐量 （3）处理机利用率高
3 分时系统的目标
4 实时系统的目标
（1）响应时间快 （2）均衡性
（1）截止时间的保证 （2）可预测性
（4）缺点
＊增加系统开销
Page 18
第三章 处理机调度与死锁 3.2 作业与作业调度 3.2.4 优先级调度算法和高响应比优先调度算法
2 高响应比优先权调度算法（HRRN）
（5）例子
到达t 服务t 开始t 完成t
A
0
4
0
4
B
1
3
4
7
C
2
D
3
E
4
平均
5
9
14
2
7
9
4
14 18
Page 19
T
W
4
Page 12
第三章 处理机调度与死锁 3.2 作业与作业调度 3.2.3 先来先服务和短作业优先算法
作业 到达t 服务t 开始t 结束t T
W
A 0 10 1 11
B 1 100 1 101 100 1
C 2 1 101 102 100 100
D 3 100 102 202 199 1.99
平均周转时间：t=100 带权平均周转时间w=25.9975
Page 16
第三章 处理机调度与死锁 3.2 作业与作业调度 3.2.4 优先级调度算法和高响应比优先调度算法 2 高响应比优先权调度算法（HRRN）
（1）HRRN是介于FCFS和SJP（F）之间的一种折中算法 （2）优先权

处理机调度与死锁ppt课件

第三章 处置机调度与死锁
3.1 处置机调度的层次 3.2 调度队列模型和调度准那么 3.3 调度算法 3.4 实时调度 3.5 产生死锁的缘由和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除
第三章 处理机调度与死锁
处置机调度与死锁(Scheduling and Deadlock )
教学目的： 在多道程序系统中，一个作业从提交到执行完
第三章 处理机调度与死锁
2) 抢占方式(Preemptive Mode)
这种调度方式允许调度程序根据某种原那么去暂停某个 正在执行的进程，将已分配给该进程的处置机重新分配给另 一进程。抢占方式的优点是，可以防止一个出息程长时间占 用途置机，能为大多数进程提供更公平的效力，特别是能满 足对呼应时间有着较严厉要求的实时义务的需求。但抢占方 式比非抢占方式调度所需付出的开销较大。抢占调度方式是 基于一定原那么的，主要有如下几条：
第三章 处理机调度与死锁
2．进程调度中的三个根本机制
为了实现进程调度，应具有如下三个根本机制：
(1) 排队器。为了提高进程调度的效率，应事先将系统 中一切的就绪进程按照一定的方式排成一个或多个队列，以 便调度程序能最快地找到它。
(2) 分派器(分派程序)。分派器把由进程调度程序所选 定的进程，从就绪队列中取出该进程，然后进展上下文切换， 将处置机分配给它。
成，要阅历多级调度，调度的好坏要影响系统的运 转性能，因此调度是多道系统的关键。为了改善系 统资源的利用率和提高系统处置才干，多道程序系 统中采用多个进程的并发执行，但它也能够发生死 锁的危险，研讨死锁的缘由和产生条件，采用预防 死锁、防止死锁、检测死锁和解除死锁等多种方法 防止死锁是多道程序系统重要的研讨课题。
第三章 处理机调度与死锁
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
作业调度
低级 调度
进程调度
操作系统原理 课程
引例
生活中随处可见的排队现象。
讲个“先来后到”
操作系统原理 课程
3.2 调 度 算 法
一、 先来先服务算法 First Come First Serve --FCFS
1.原则：发生调度时，按照作业（或进程）提交（或就绪） 的先后次序来调度。 “非剥夺式” 2.适用范围： 同时适用于高级和低级调度。 3.实例分析： 4.评价： 优:实现简单
操作系统原理 课程 第20张
3.2 选择调度方式和调度算法的若干准则
2. 面向系统的准则
(1) 系统吞吐量高。
(2) 处理机利用率好。 (3) 各类资源的平衡利用。
操作系统原理 课程 第21张
回顾导入：
作业从提交开始到结束可能经历三级调度:
选择=调度
处理机 调度层次
中级 调度
交换调度
高级 调度
操作系统原理 课程
第3 章
处理机调度与死锁
1
北华大学.计算机科学技术学院
本章目标
掌握作业调度和进程调度的功能；理解作业调度与进程 调度的关系；理解作业的四种状态：提交、后备、执行 和完成。 掌握常用调度算法的评价指标：吞吐量、周转时间、平 均周转时间、带权周转时间和平均带权周转时间。 掌握基本调度算法的实现思想，并能进行评价指标的计 算。 掌握进程死锁的概念、产生的必要条件及解决死锁的方 法。 掌握银行家算法的思想，能应用银行家算法解决资源分 配问题。
3.1 处理机调度的基本概念
3.1.2 调度的层次
1. 高级调度 (High Level Scheduling)：
又称“作业调度”、“长程调度”、“接纳调度”。
1）主要任务： ①按一定的原则对外存输入井上的大量后备作业进行选择，给选 出的作业分配内存、 I/O 设备等必要的资源，并建立相应的进程 排在就绪队列中，以使该作业的进程获得竞争处理机的权利。
2）3个基本机制：排队器、分派器、上下文切换机制
操作系统原理 课程 第11张
3.1 处理机调度的基本概念
3.1.2 调度的层次
3. 低级调度（Low Level Scheduling）： 3）两种调度方式： ①不可抢占方式：进程在处理机上执行时，除非执行完、阻塞、
等待同步信号或消息，才会重新调度新的进程。
②当该作业执行完毕时，还负责回收系统资源。
注意：分时系统、实时系统没有作业调度
操作系统原理 课程 第8张
3.1 处理机调度的基本概念
3.1.2 调度的层次
1. 高级调度 (High Level Scheduling)：
2）两个决定：
①每次选择多少个作业：取决于“多道程序度” ②选择哪些作业：取决于“调度算法”
3.2 选择调度方式和调度算法的若干准则
1. 面向用户的准则 (1) 周转时间短。
Ti ：作业i的周转时间 T完成i：作业i的完成时间 T提交i： 作业i的提交时间
Ti=T 完成 Tei Tsi 作业的周转时间为： Ti i-T 提交 i
1 可把平均周转时间描述为：T Ti n i 1
操作系统原理 课程 第2张

本章结构
处理机调度的基本概念
处理机调度 调对队列模型和调度准则 调度算法 实时调度
处理机调度 与死锁
产生死锁的原因和必要条件 死锁
预防死锁的方法
死锁的检测与解除
操作系统原理 课程 第3张
3.1 处理机调度的基本概念
3.1.1 作业的状态及其转换
1.作业(Job) 用户在一次计算过程中，或者一次事务处理过程中，要求计算 机系统所做工作的总称。 2.作业步(Job Step) 一般情况下，一个作业可划分成若干个部分，每个部分称为一 个作业步。在作业运行期间，各作业步之间存在着相互联系，往往上一
q= R / Nmax
（2）时间片种类:
① 固定时间片 ② 可变时间片
操作系统原理 课程
例：考虑4个进程P1P2P3P4信息如下，请分析按照时间片轮转（RR）调度算 法时各进程执行过程（时间片为2ms），并计算 每个进程的周转时间（假设忽略
进程的调度时间）。
进程 P1 P2 P3 P4 创建时刻 0 2 4 6 运行时间／ms 2 4 2 4
操作系统原理 课程 第16张
3. 2 调度队列模型
3. 同时具有三级调度的调度队列模型
作业调度 后备队列 批量作业 交互型作业 中级调度 时间片完 就绪队列
进程调度
CPU
进程完成
就绪，挂起队列 事件出现
阻塞，挂起队列 事 件 出 现 阻塞队列 等待事件 挂起
操作系统原理 课程 第17张
强调：进程执行时出现的三种情况
n i
作业的周转时间 T 与系统为它提供服务的时间 TS 之比，即 W=T/TS，称为带权周转时间，而平均带权周转时间则可表
示为:
1 n Ti W n i 1 TSi
操作系统原理 课程 第19张
3.2 选择调度方式和调度算法的若干准则
1. 面向用户的准则
(2) 响应时间快。 (3) 截止时间的保证。 (4) 优先权准则。
T4＝12-6＝6
3.2 调 度 算 法
四、 高优先权优先算法
Highest Priority First -- HPF
1. 任务在当前时间片执行完后，若能全部完成，则变为“完成” 状态，再也不参与竞争处理机。 2. 任务在当前时间片执行完后，若尚未完成，则排在就绪队列 末尾。（注意在应用计算时，可能会出现同一时间也有新进程进入就绪队
列的情况，一般先排新进程）
3.在执行期间，若进程被阻塞，则将其置入相应阻塞队列。
操作系统原理 课程 第18张
操作系统原理 课程 第13张
3.1 处理机调度的基本概念
3.1.3 有关于优先权
2. 动态优先权 在进程创建时创立一个优先数，但在其生命周期内优先数可以动 态变化。 评价： 相对公平 系统开销大（需计算优先级）
操作系统原理 课程 第14张
3. 2 调度队列模型
1. 仅有进程调度的调度队列模型
时间片完 进程调度 进程完成
（注意在应用计算时，可能会出现同一时间也有新进程进入就绪队列的情况，一般先 排新进程）
3.在执行期间，若进程被阻塞，则将其置入相应阻塞队列。
操作系统原理 课程
3.2 调 度 算 法
三、时间片轮转调度算法---RR
4.时间片选择问题： （1）与时间片大小有关的因素:
① 系统响应时间 ② 就绪进程个数 ③ CPU能力
进程的调度时间）。
进程 P1 P2 P3 P4 创建时刻 0 2 4 6 运行时间／ms 2 4 2 4
10 就绪队列模拟 （ 12
ms 时）
P4
12ms时P4完成
解：执行过程如下
进程
P1 P2
T1＝2-0＝2 T2＝8-2＝6
T3＝6-4＝2
0 2
4 6 8 10 12 时间
体现用户的控制意图，主要包含三方面的内容：作业的基本描述、 作业的控制描述和资源要求描述，它是用作业控制语言书写的 。
操作系统原理 课程 第5张
3.1 处理机调度的基本概念
3.1.1 作业的状态及其转换
5.作业控制块（Job Control Block-JCB） 作业存在的唯一标志，是系统为管理作业所设置的一个数据结构， 存放了管理和控制作业所必需的信息。
个作业步的结果作为下一个作业步的输入。
操作系统原理 课程 第4张
3.1 处理机调度的基本概念
3.1.1 作业的状态及其转换
3.作业流 一次有一批作业进入系统，并在操作系统控制下，一个接一个地
进行处理。
4.作业的组成 作业由程序、数据、作业说明书组成。 其中程序和数据完成用户所要求的业务处理工作；作业说明书则
“抢占式”
操作系统原理 课程
3.2 调 度 算 法
三、时间片轮转调度算法---RR
3.调度模型：
时间片完 进程调度 进程完成
交互用户 事 件 出 现
就 绪 队 列
CPU
阻 塞 队 列
等待事件
1.任务在当前时间片执行完后，若能全部完成，则变为“完成”状态，再也 不参与竞争处理机。 2.任务在当前时间片执行完后，若尚未完成，则排在就绪队列末尾。
缺:没考虑优先级
操作系统原理 课程 第24张
引例
银行窗口取钱的苦恼。
站错队了！
操作系统原理 课程
3.2 调 度 算 法
二、 短作业(进程)优先算法 Short Job(Process)First--SJ(P)F
1.原则：发生调度时，选择要求服务时间即运行时间最短的 作业（或进程）来调度。 “非剥夺式” 2.适用范围： 同时适用于高级和低级调度。 3.实例分析： 4.评价： 优:系统吞吐量高 缺:不利于长作业，甚至会“饿死”； 完全未考虑作业的紧迫程度； 运行时间的估计也有问题
1.调度原则： Round Robin 轮叫调度 把CPU的处理时间划分成若干时间片,初始时按FCFS顺序赋 给就绪队列中的每一个进程，进程轮流占有CPU，当时间片用 完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该
进程排在就绪队列末尾，同时系统选择另一个进程运行。 2.适用范围： 只适用于低级调度（进程），分时系统中常常使用。
操作系统原理 课程 第9张
3.1 处理机调度的基本概念
3.1.2 调度的层次
2. 中级调度（Intermediate Level Scheduling）：
又称“交换调度”、“中程调度”。
主要任务： 为提高内存利用率和系统吞吐量，按照给定的原则和策略，
将处于外存交换区中的就绪状态或等待状态的进程调入内存，