当前位置：文档之家 › 第4章 处理机调度

第4章 处理机调度

  • 格式：ppt
  • 大小：462.50 KB
  • 文档页数：58

下载文档原格式

  / 58

合集下载

处理机调度算法实验总结

处理机调度算法实验总结

处理机调度算法实验总结1. 引言处理机调度算法是操作系统中的重要组成部分，它决定了如何合理地分配处理机资源，以提高系统的性能和效率。

本次实验旨在通过实际操作和实验数据的分析，对不同的处理机调度算法进行比较和总结，以便更好地理解和应用这些算法。

2. 实验设计在本次实验中，我们选择了三种常见的处理机调度算法进行比较，分别是先来先服务（FCFS）、最短作业优先（SJF）和时间片轮转（RR）。

我们设计了以下实验方案：2.1 实验环境•操作系统：Windows 10•开发工具：C语言编译器2.2 实验步骤1.设计并实现三个处理机调度算法的代码；2.编写测试用例，包括不同作业的到达时间和服务时间；3.运行代码，记录每个作业的等待时间和周转时间；4.分析和比较三种算法的性能指标；5.总结实验结果。

3. 实验结果经过实验运行和数据记录，我们得到了以下实验结果：3.1 先来先服务（FCFS）•等待时间：1.作业1：02.作业2：103.作业3：15•周转时间：1.作业1：102.作业2：203.作业3：253.2 最短作业优先（SJF）•等待时间：1.作业1：02.作业2：53.作业3：10•周转时间：1.作业1：52.作业2：153.作业3：203.3 时间片轮转（RR）•等待时间：1.作业1：102.作业2：53.作业3：0•周转时间：1.作业1：202.作业2：153.作业3：104. 结果分析根据实验结果，我们可以得出以下结论：4.1 先来先服务（FCFS）•优点：简单易实现；•缺点：平均等待时间较长，不适用于长作业。

4.2 最短作业优先（SJF）•优点：平均等待时间最短；•缺点：无法预测作业的运行时间，可能导致长作业等待时间过长。

4.3 时间片轮转（RR）•优点：对长作业有较好的响应时间；•缺点：平均等待时间较长，不适用于短作业。

5. 实验总结通过本次实验，我们深入了解了三种常见的处理机调度算法，并通过实验数据对其进行了比较和分析。

计算机操作系统习题及答案

计算机操作系统习题及答案

第一章操作系统引论一、单项选择题1．操作系统是一种__________。

A．通用软件 B．系统软件C．应用软件 D．软件包2，操作系统的__________管理部分负责对进程进行调度。

A．主存储器 B．控制器C．运算器D．处理机3．操作系统是对__________进行管理的软件。

A．软件B．硬件C，计算机资源 D．应用程序4．从用户的观点看，操作系统是__________。

A．用户与计算机之间的接口B．控制和管理计算机资源的软件C．合理地组织计算机工作流程的软件D．由若干层次的程序按一定的结构组成的有机体5，操作系统的功能是进行处理机管理、_______管理、设备管理及文件管理。

A．进程 B．存储器C．硬件 D．软件6，操作系统中采用多道程序设计技术提高CPU和外部设备的_______。

A．利用率 B．可靠性C．稳定性 D．兼容性7．操作系统是现代计算机系统不可缺少的组成部分，是为了提高计算机的_______和方便用户使用计算机而配备的一种系统软件。

A. 速度B．利用率C. 灵活性 D．兼容性8．操作系统的基本类型主要有_______。

A．批处理系统、分时系统及多任务系统B．实时操作系统、批处理操作系统及分时操作系统C．单用户系统、多用户系统及批处理系统D．实时系统、分时系统和多用户系统9．所谓_______是指将一个以上的作业放入主存，并且同时处于运行状态，这些作业共享处理机的时间和外围设备等其他资源。

A. 多重处理 B．多道程序设计C. 实时处理 D．并行执行10. _______操作系统允许在一台主机上同时连接多台终端，多个用户可以通过各自的终端同时交互地使用计算机。

A．网络 D．分布式C．分时 D．实时11．如果分时操作系统的时间片一定，那么_______，则响应时间越长。

A．用户数越少B．用户数越多C．内存越少 D. 内存越多12，分时操作系统通常采用_______策略为用户服务。

A．可靠性和灵活性 B．时间片轮转C．时间片加权分配 D，短作业优先13. _______操作系统允许用户把若干个作业提交给计算机系统。

操作系统原理第四章 处理机调度习题

操作系统原理第四章 处理机调度习题

第四章处理机调度4.3 习题4.3.1 选择最合适的答案1．某系统采用了银行家算法，则下列叙述正确的是（）。

A.系统处于不安全状态时一定会发生死锁B.系统处于不安全状态时可能会发生死锁C.系统处于安全状态时可能会发生死锁D.系统处于安全状态时一定会发生死锁2．银行家算法中的数据结构包括有可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need，下列选项正确的是（）。

A.Max[i,j]=Allocation[i,j]+Need[i,j]B.Need[i,j]= Allocation[i,j]+ Max[i,j]C.Max[i,j]= Available[i,j]+Need[i,j]D.Need[i,j]= Available[i,j]+ Max[i,j]3．下列进程调度算法中，（）可能会出现进程长期得不到调度的情况。

A.非抢占式静态优先权法B.抢占式静态优先权法C.时间片轮转调度算法D.非抢占式动态优先权法4．在下列选项中，属于预防死锁的方法是（）。

A.剥夺资源法B.资源分配图简化法C.资源随意分配D.银行家算法5．在下列选项中，属于检测死锁的方法是（）。

A.银行家算法B.消进程法C.资源静态分配法D.资源分配图简化法6．在下列选项中，属于解除死锁的方法是（）。

A．剥夺资源法 B.资源分配图简化法C．银行家算法 D.资源静态分配法7．为了照顾紧迫型作业，应采用（）。

A.先来服务调度算法B.短作业优先调度算法C.时间片轮转调度算法D.优先权调度算法8．在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和（）相同。

A.先来先服务调度算法B.短作业优先调度算法C.时间片轮转调度算法D.长作业优先调度算法9．作业从后备作业到被调度程序选中的时间称为（）。

A.周转时间B.响应时间C.等待调度时间D.运行时间10．资源静态分配法可以预防死锁的发生，它们使死锁四个条件中的（）不成立。

第四章 操作系统处理机调试(张尧学)

第四章 操作系统处理机调试(张尧学)

等待事件
4.1.2 作业与进程
作业是用户向计算机提交任务的任务实体 进程是计算机为了完成用户任务实体而设置
的执行实体，是系统分配资源的基本单位
第四章 处第理9机页调度
4.2 作业调度
作业调度主要是完成作业从后备状态到执行状态的转 变，以及从执行状态到完成状态的转变
第四章 处第理1机0页调度
第四章 处第理1机9页调度
4.3.2 进程调度的时机
(1) 正在执行的进程执行完毕。 (2) 执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等待状态。 (3) 执行中进程调用了P原语操作，从而因资源不足而被阻塞；或调用
了V原语操作激活了等待资源的进程队列。 (4) 执行中进程提出I／O请求后被阻塞。 (5) 在分时系统中时间片已经用完。 (6) 在执行完系统调用
第四章 处第理1机2页调度
图4.3 作业调度中状态的转换过程 第四章 处第理1机3页调度
4.2.2 作业调度目标与性能衡量
作业调度的功能最主要的是从后备作业队列中选取一批作 业进入执行状态。
调度目标主要是以下4点: (1) 对所有作业应该是公平合理的； (2) 应使设备有高的利用率； (3) 每天执行尽可能多的作业； (4) 有较快的响应时间。
主要功能是按照一定的策略选择一个处于就绪状态的进程， 使其获得处理机执行。根据不同的系统设计目的，有各种各样 的选择策略，例如系统开销较少的静态优先数调度法，适合于 分时系统的轮转法和多级反馈轮转法等。这些选择策略决定了 调度算法的性能 (3) 进行进程上下文切换
一个进程的上下文（context）包括进程的状态、有关变量 和数据结构的值、硬件寄存器的值和PCB以及有关程序等
高级调度"。从用户工作流程的角度，一次提交的若干个流程， 其中每个程序按照进程调度。时间上通常是分钟、小时或天 (2) 交换调度：中级调度，从存储器资源的角度。将进程的部分 或全部换出到外存上，将当前所需部分换入到内存。指令和数据 必须在内存里才能被CPU直接访问。 (3)进程或线程调度：低级调度（微观调度），又称为"微观调度 "、"低级调度"。从CPU资源的角度，执行的单位。时间上通常 是毫秒。因为执行频繁，要求在实现时达到高效率

第4章 处理机调度

第4章 处理机调度

分级调度
调度的层次 中级调度：又称交换调度、平衡负载调度或中 程调度（Medium-term Scheduling）。 中级调度根据存储资源量和进程的当前状态来决 定辅存和主存中的进程的对换，它所使用的方法是 通过把一些进程换出主存，从而，使之进入“挂起” 状态，不参与低级调度，起到短期平滑和调整系统 负荷的作用。 交换调度主要涉及到内存管理与扩充。
调度的层次 一般来说，处理机调度可以分为三级： 高级调度：又称作业调度或长程调度（Longterm Scheduling） 。 其主要任务是按一定的原则对外存输入井上的 大量后备作业进行选择，给选出的作业分配内存、 输入输出设备等必要的资源，并建立相应的进程， 以使该作业的进程获得竞争处理机的权利。 另外，当该作业执行完毕时，回收系统资源。
调度算法
最短作业优先SJF（Shortest Job First ） SJF 算法是非抢占式的，可以改进成抢占式的调 度算法。 当一个作业正在执行时，一个新作业进入就绪状 态，如果新作业需要的CPU 时间比当前正在执行 的作业剩余下来还需的CPU 时间短，抡占式短作 业优先调度算法强行赶走当前正在执行的作业， 这种方式叫最短剩余时间优先算法SRTF （Shortest Remaining Time First）算法。 此算法适用于作业调度和进程调度。
调度算法
先来先服务（FCFS） 在实际操作系统中，尽管很少单独使用FCFS算 法，但和其他一些算法配合起来，FCFS算法还是 使用得相当多的。 例如基于优先级的调度算法就是对具有同样优先 级的作业或进程采用的FCFS方式。
调度算法
先来先服务（FCFS） 下面三个作业同时到达系统并立即进入调度： 例：下面三个作业同时到达系统并立即进入调度：

逄 第四章处理机调度习题课

逄 第四章处理机调度习题课

进入时间 离开时间 周转时间 执行时间 带权 周转时间
1 2 3 4 5
0 0 0 0 0
10 11 13 14 19
10 11 13 14 19
13.4
10 1 2 1 5
1 11 6.5 14 3.8
7.26
0 J1 J2 J3 J4 J5
2
4
6
8
10 12 14 16 18 20 T
RR
0 J1 J2 J3 J4 J5
解： 先调度作业1 1）先调度作业1。 周转时间为T1=Tw1+Tr1=0+2.0=2.0 周转时间为T1=Tw1+Tr1=0+2.0=2.0 带权周转时间为W1=2.0/2.0=1 带权周转时间为W1=2.0/2.0=1 在作业1运行的完成时刻10:00分别计算作业2 10:00分别计算作业 2）在作业1运行的完成时刻10:00分别计算作业2、3、4的响 应比R 应比R 作业2等待时间10:00 8:50=1时10分=1.17小时 10:00小时, ①作业2等待时间10:00-8:50=1时10分=1.17小时, R=1+1.17/0.5=3.34 作业3等待时间10:00 9:00=1时=1.0小时 10:00小时, ②作业3等待时间10:00-9:00=1时=1.0小时, R=1+1.0/0.1=11.0 ③作业4等待时间10:00-9:50=10分=0.17小时, 作业4等待时间10:00-9:50=10分=0.17小时, 10:00 小时 R=1+0.17/0.2=1.85 故应调度作业3,周转时间T3=1.0+0.1=1.1小时, 3,周转时间T3=1.0+0.1=1.1小时 故应调度作业3,周转时间T3=1.0+0.1=1.1小时,带权周转时间 W3=1.1/0.1=11.0

第四章--调度PPT课件

14
3、常用作业调度算法
先来先服务（First-Come First-Served：FCFS）
最早提交的作业最先调入内存
短作业优先（Shortest Job First :SJF） 运行时间最短的作业优先调入内存
最短剩余时间优先（ Shortest Remaining Time Next：SRTN) 剩余运行时间最短的作业优先调度运行
23
系统中n个作业的平均周转时间为：
T
n
Ti
i1
1 n
带权周转时间W
W = T/R
T 为周转时间，R为实际运行时间。
平均带权周转时间：
Win1Wi1nin1TRii 1n
4．就绪等待时间：作业在就绪队列中的等待时间 5．响应时间：从提交第1个请求到产生第1个响应
所用的时间
4.5 调度算法
行某些进程
⑥ 开销 ：系统开销不应太大
22
4.4.2 调度性能评价准则
1．CPU利用率：CPU价格昂贵 2．吞吐量：单位时间内CPU完成作业的数量 3．周转时间 从作业提交到作业完成的时间间隔就是周转时间。
Ti = tci - tsi tsi 表示作业i 的提交时间 tci 表示作业i 的完成时间。
15
4.3 进程调度
进程调度也叫低级调度 进程调度程序也叫低级调度程序，它完
成进程从就绪状态到运行状态的转换。 将一台物理CPU虚拟成多台CPU
16
4.3.1 进程调度的功能
（1）保存现场
进程放弃CPU时，进程调度程序需将现场信 息保存到PCB中
（2）挑选进程 （3）恢复现场
为选中的进程恢复现场信息，把CPU控制权 交给该进程。
10
提交状态

操作系统-第4章题

1.（c ）算法综合考虑作业的等待时间和计算时间。

A．先来先服务B．计算时间短的作业优先C．响应比高者优先D．优先级1．（ ）FIFO调度算法是最公平的调度算法。

3．(6分)假设有四个作业，它们的提交时间和需要的计算时间如表2所示。

这些作业在一台处理机上按单道方式运行，如采用响应比高者优先调度算法，请给出这些作业的执行顺序？答：(2分)第一次调度时间是7：00，此时只有J1为后备作业，因而被调度。

它执行完的时间是9：00。

(2分)第二次调度时间是9：00，此时J2、J3和J4都为后备作业。

J2、J3和J4作业的相关参数如表5所示。

J3的响应比最高，J3被调度。

它执行完的时间是9：20。

(1分)第三次调度时间是9：20，此时J2和J4为后备作业。

J2和J4作业的相关参数如表6所示。

J2的响应比最高，J2被调度。

它执行完的时间是10：20。

(1分)第四次调度时间是10：20，此时只有J4为后备作业，J4被调度。

它执行完的时间是11：00。

综上这些作业的执行顺序为J1、J3、J2、J4。

表5 J2、J3和J4作业的相关参数2．在分级反馈轮转调度中，分配给各就绪队列的时间片是相等的。

（错）3．说明Linux系统中引起进程调度的原因。

答：Linux系统中进程调度的原因有如下几种：①CPU执行的进程发生状态转换，如进程终止、进程睡眠等。

进程在执行过程中调用sleep()、exit()或wait()等函数将引起其状态转变，这些函数的执行会调用调度程序进行进程调度。

②就绪队列中增加了新进程。

③正在执行的进程所分配的时间片用完。

④执行系统调用的进程返回到用户态。

⑤系统内核结束中断处理返回到用户态。

2．（7分）假设有四个作业，它们的提交时间和需要的计算时间如表3所示。

这些作业在一台处理机上按单道方式运行，若采用下列作业调度算法：（1）先来先服务（2）短作业优先；请分别给出这些作业的执行顺序、每个作业的周转时间及平均周转时间和加权平均周转时间。

进程作业四：处理机调度

进程作业四：处理机调度
一、在一个单道批处理系统中，设有4个作业P1，P2，P3,P4，到达时间分别为0,5,10,15，所需CPU时间分别为20,15,5,10.
请问：
（1）用先来先服务（FCFS）调度算法的平均周转时间和平均带权周转时间。

（2）用最短作业(SJF)调度算法的平均周转时间和平均带权周转时间。

（3）用最短剩余时间（SRTF）调度算法的平均周转时间和平均带权周转时间。

备注：SRTF算法：把SJF算法改为抢占式的。

一个新作业进入就绪状态，如果新作业需要的CPU时间比当前正在执行的作业剩余所需的CPU时间短，SRTF强行赶走当前正在执行的作业，调度新作业运行。

二、在一个单道批处理系统中，设有5个作业P1，P2，P3,P4,P5在0时刻同时到达系统，所需CPU时间分别为10,1,2,1,5.优先级分别为3,1,4,5,2(数小级高) 请计算用非抢占式优先级调度算法的平均周转时间和平均带权周转时间。

三、在一个单道批处理系统中，设有4个作业P1，P2，P3,P4同时到达系统，依次进入就绪队列，所需CPU时间分别为12,5,3,6.时间片为1.
请计算当时间片分别为1和4时，用时间片轮转（RR）调度算法的平均周转时间和平均带权周转时间。

计算机操作系统教程(张尧学 史美林 张高)(第三版)第四章


精品课程系列-计算机学院版权所有
重庆大学计算机学院 《操作系统》教程
4.2
作业调度
制 制 作 作 者 者 ： ： 郭 郭 平 平 、 、 王 王 在 在 模 模 、 、 何 何 静 静 媛 媛
作业调度是按照某种规则，从后备作业 队列中挑选作业进入内存，参与处理机的竞 争的过程。
精品课程系列-计算机学院版权所有
从后备队列中选 出一个作业 审核资源要求 否 放弃作业 资源要求 能满足吗？ 是 分配资源 建立进程 进程调度 (a) 后备状态到执行状态的转变
回收分配给作业的全部资源 计算作业的执行费用 撤消作业的所有进程，以及JCB 调度下一个作业
(b) 执行状态到完成状态的转变
精品课程系列-计算机学院版权所有
外存
就绪
等待
提交状态
收容状态
就绪 等待
交换调度 执行状态 完成状态 执行
作业注册
作业调度
进程调度
内存
线程调度
作业的状态及转换
返回
精品课程系列-计算机学院版权所有
重庆大学计算机学院 《操作系统》教程
4.1.2 调度的层次
制 制 作 作 者 者 ： ： 郭 郭 平 平 、 、 王 王 在 在 模 模 、 、 何 何 静 静 媛 媛
又称为作业调度，用于决定把外存上处于后备队列中的作业调入 内存，并为它们创建进程、分配必要的资源，然后，将新创建的进程 排在就绪队列中，准备执行。在作业调度中，必须解决两个问题： 1） 接纳多少个作业：多道程序的度数的确定应该系统的规模和运行 速度，做适当的折中。 2） 接纳哪些作业：应该将作业从外存中调入内存，将取决于所采用 的调度算法。关于各种不同的调度算法将随后讨论。
精品课程系列-计算机学院版权所有
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
在定性衡量方面，调度的可靠性、算法的 简洁性是衡量进程调度的重要指标。 定量评价包括CPU的利用率、进程在就绪队 列中的等待时间与执行时间之比等。


4.4 调度算法
本节讨论常用的6种进程（作业）调度算法
1、先来先服务（FCFS）调度算法

按作业的提交顺序和进程进入就绪队列的 先后次序进行调度。这种算法优先考虑在 系统中等待时间最长的作业或进程，而不 考虑执行时间的长短。
平均周转时间: T=1.625 (>1.55=SJF), 平均带权周转时间: W=5.675 (>5.15=SJF)。
4.5 算法评价（P97-103）
本节从数学上分析了FCFS算法、轮转法、线性优 先级算法的性能。第k轮调度的平均响应时间分别 如下： FCFS算法：Rfc(k)=1/(μ-λ)
轮转法：Rrr(k)=kqμ/(μ-λ)
(5)在分时系统中时间片已经用完。
(6)在执行完系统调用，系统进程执行完毕， 从而可调度一个新的用户进程执行。 (7)如果CPU执行方式是可剥夺的，当就绪队列 中的某个进程的优先级高于当前执行进程 的优先级时，也将引起进程调度。
4.3 进程调度
4.3.3 进程调度性能评价

进程调度性能的衡量方法可分为定性和定 量两种。
(1)正在执行的进程执行完毕。这时，如果不选择 新的就绪进程执行，将浪费处理机资源。
(2)正在执行的进程自己调用阻塞原语进入睡眠等 待状态。
(3)正在执行的进程调用了P原语操作，因资源不 足而被阻塞；或调用了V原语操作激活了等待 资源的进程。
4.3 进程调度
(4)执行中进程提出I／O请求后被阻塞。
第4章 处理机调度
主要内容： 1、分级调度、作业调度、进程调度 2、调度算法、算法评价
3、实时系统调度方法
基本概念

处理机调度是操作系统选择一个作业或进程 分配处理机执行的过程。
衡量调度策略的几个指标是：周转时间、吞 吐率、响应时间以及设备利用率等。 周转时间是指将一个作业提交给计算机系统 后到该作业的结果返回给用户所需要的时间。


4.4 调度算法

在轮转法中，时间片长度的选取非常重要。 如果时间片过短，那么进程上下文切换次 数就大大增加，从而加重了系统开销。反 过来，如果时间片过长，轮转法就变成了 先来先服务算法。 时间片长度的选择是根据系统对响应时间 的要求R和就绪队列中所允许的最大进程数 Nmax确定的。表示为：q=R/Nmax。
(1)对所有作业应该是公平合理的；
(2)应使设备有较高的利用率；
(3)每天执行尽可能多的作业； (4)有较快的响应时间。
4.2 作业调度
作业调度算法的性能衡量
1.周转时间

作业i的周转时间Ti为： Ti=Tei-Tsi
其中Tei为作业i执行完成时的时间，Tsi为作业 i提交完成时的时间。

n（n>=1）个作业的平均周转时间为：



多级反馈队列方式是在系统中设置多个就绪队 列，并赋予各队列不同的优先级。第一个队列 的优先级最高，第二个队列次之，其余各队列 的优先级依次降低。 较高优先级的队列分配的时间片较短。 调度算法先从高一级就绪队列中选取进程，同 一队列中的进程按FCFS原则排列。 时间片用完而未完成的进程加入低一级就绪队 列中。
线性优先级算法： Rsr(k)=1/(μ-λ)-(1-kqμ)/(μ-λ) 其中：μ是服务率、λ是进程（作业）到达率、q 是时间片。
4.5 算法评价

对于服务时间短的进程，其响应时间：
Rrr<Rsr<Rfc

对于服务时间长的进程，其响应时间：
Rfc<Rsr<Rrr
4.6 实时系统调度方法
4.6.1 实时系统的特点

4.4 调度算法
0 (a)q=1 A B C D 1 2 3 4 5 A B C D 6 7 8 9 10 11 12 13 14 15 16 17 A B C C A t
E
E
E
E
(a)q=4
进程名
到达时间 服务时间 RR q=1 完成时间 周转时间 带权周转 时间 RR q=4 完成时间 周转时间 带权周转 时间
究竟哪个作业的哪个进程能获得处理机而真正在执 行，要依靠进程调度来决定。


4.1 分级调度

完成状态：当作业运行完毕，但它所占用的 资源尚未全部被系统回收时，该作业处于完 成状态。
在这种状态下，系统需要做打印结果、回收 资源等处理工作。

4.1 分级调度
4.1 分级调度
4.1.2 调度的层次
平均周转时间: T=1.55 (<1.725=FCFS), 平均带权周转时间: W=5.15 (<6.875=FCFS)。
4.4 调度算法
6、最高响应比优先法

响应比定义：R=(W+T)/T，其中W是等待时间， T是执行时间。
响应比＝周转时间/执行时间 选择响应比最高的作业执行。显然，短作业 容易得到较高响应比，但是长作业等待时间 足够长，也将获得足够高的响应比，不至于 长时间等待下去。 该算法适用于作业调度和进程调度。
A
0 4 15 15 3.75 4 4 1
B
1 3 12 11
C
2 4 16 14
D
3 2 9 6 3 13 10
E
4 4 17 13 3.33 17 13 3.33
平均
11.8 3.46
3.67 3.5 7 6 2 11 9
8.4 2.5
2.25 5
4.4 调度算法
3、多级反馈轮转法(只适用于进程调度)
4.4 调度算法
5、最短作业（进程）优先法

该算法是以作业所要求的CPU时间长短为标 准，选取计算时间最短的作业执行。
该算法适用于作业调度和进程调度。

4.4 调度算法
提交 作业 完成 时间 1 8 2 3 4 8.5 9 9.5 运行 运行 时间 开始 时间 2 8 0.5 0.1 0.2 10.3 10 10.1 运行 完成 时间 10 10.8 10.1 10.3 周转 带权周转时 时间 间 2 2.3 1.1 0.8 1 4.6 11 4



4.4 调度算法
提交 作业 完成 时间 1 8 2 3 4 8.5 9 9.5 运行 运行 时间 开始 时间 2 8 0.5 0.1 0.2 10.1 10 10.6 运行 完成 时间 10 10.6 10.1 10.8 周转 带权周转时 时间 间 2 2.1 1.1 1.3 1 4.2 11 6.5


基本概念

吞吐率是指在给定的时间内，一个计算机系 统所完成的总工作量。
响应时间则是指从用户向计算机发出一个命 令到计算机把相应的执行结果返回给用户所 需要的时间。


设备利用率主要指输入输出设备的使用情况。
4.1 分级调度
4.1.1 作业的状态及其转换

一个作业从提交给计算机系统到执行结束退 出系统，一般都要经历提交、收容、执行和 完成等4个状态。
(2)交换调度：又称中级调度。其主要任务是按 照给定的原则和策略，将外存交换区中处于就绪 状态或等待状态的进程调入内存，或把内存中处 于就绪状态或等待状态的进程交换到外存交换区。 交换调度主要用于内存管理与扩充。 (3)进程调度：又称微观调度（低级调度）。其 主要任务是按照某种策略和方法选取一个处于就 绪状态的进程占用处理机执行。
Wi=Ti/Tri n个作业的平均带权周转时间为：
1 n W = Wi n i=1

4.3 进程调度
4.3.1 进程调度的功能
进程调度的具体功能可总结如下：
(1)记录系统中所有进程的执行情况 (2)选择占有处理机的进程 (3)进行进程上下文切换
4.3 进程调度
4.3.2 进程调度的时机
引起进程调度的原因有以下7类：
4.1 分级调度
(4) 线程调度：选取一个处于就绪状态的线程 占用处理机执行。 通常，我们所说的处理机调度一般是指进程调 度。
4.1 分级调度
4.1.3 作业与进程的关系

作业是用户向计算机提交任务的任务实体， 进程则是计算机为了完成用户任务而设置的 执行实体，是系统分配资源的基本单位。
一个作业由一个或多个进程组成。
4.4 调度算法
进程的静态优先级按以下原则确定：
① 按进程的类型给予不同的优先级。
② 将作业的静态优先级作为它所属进程的优 先级。
4.4 调度算法
（2）动态优先级
进程的动态优先级一般根据以下原则确定：
① 根据进程占有CPU时间的长短来决定。一个 进程占有CPU的时间越长，则被阻塞之后再 次获得调度的优先级就越低。 ② 根据就绪进程等待CPU的时间长短来决定。 一个进程在就绪队列中等待时间越长，它 获得的优先级就越高。
4.4 调度算法
4.4 调度算法
4、优先级法


优先级法适用于作业调度和进程调度。
首先，系统或用户按某种原则为作业或进 程指定一个优先级来表示其优先权。 该算法的核心是确定进程或作业的优先级。 确定优先级的方法可分为静态法和动态法。

4.4 调度算法
（1）静态优先级 作业的静态优先级按以下原则确定： ① 用户根据作业的紧急程度输入一个适当的 优先级。 ② 系统或操作员根据作业类型指定优先级。 ③ 系统根据作业要求资源情况确定优先级。
4 16 6.5
平均周转时间:T=(2+2+1.6+1.3)/4=1.725,
平均带权周转时间:W=(1+4+16+6,5)/4=6.875
4.4 调度算法