sjf算法例题
‘壹’ 以下五个作业，fcfs sjf hrrn三种调度算法平均周转时间，高响应比怎么算
作业调度算法 .
先来先服务（FCFS, First Come First Serve）是最简单的调度算法，按先后顺序进行调度。
定义：
按照作业提交或进程变为就绪状态的先后次序，分派CPU；
当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。
在作业或进程唤醒后（如I/O完成），并不立即恢复执行，通常等到当前作业或进程出让CPU。
适用场景：
比较有利于长作业，而不利于短作业。因为长作业会长时间占据处理机。
有利于CPU繁忙的作业，而不利于I/O繁忙的作业。
算法实现原理图：
2. 轮转法(Round Robin)
轮转法是让每个进程在就绪队列中的等待时间与享受服务的时间成正比例。
定义：
将系统中所有的就绪进程按照FCFS原则，排成一个队列。
每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。
在一个时间片结束时，发生时钟中断。
调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。
进程可以未使用完一个时间片，就出让CPU（如阻塞）。
时间片长度的确定：
时间片长度变化的影响
过长－>退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。
过短－>用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长。
对响应时间的要求：T(响应时间)=N(进程数目)*q(时间片)
就绪进程的数目：数目越多，时间片越小
系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长。
算法实现原理图：
3. 多级反馈队列算法(Round Robin with Multiple Feedback)
多级反馈队列算法是轮转算法和优先级算法的综合和发展。
定义：
设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如逐级加倍。
新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按“时间片轮转”算法调度直到完成。
仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。
优点：
为提高系统吞吐量和缩短平均周转时间而照顾短进程。
为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程。
不必估计进程的执行时间，动态调节
几点说明：
I/O型进程：让其进入最高优先级队列，以及时响应I/O交互。通常执行一个小时间片，要求可处理完一次I/O请求的数据，然后转入到阻塞队列。
计算型进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。
I/O次数不多，而主要是CPU处理的进程。在I/O完成后，放回优先I/O请求时离开的队列，以免每次都回到最高优先级队列后再逐次下降。
为适应一个进程在不同时间段的运行特点，I/O完成时，提高优先级；时间片用完时，降低优先级。
算法实现原理图：
4. 优先级法（Priority Scheling）
优先级算法是多级队列算法的改进，平衡各进程对响应时间的要求。适用于作业调度和进程调度，可分成抢先式和非抢先式。
静态优先级：
作业调度中的静态优先级大多按以下原则确定：
由用户自己根据作业的紧急程度输入一个适当的优先级。
由系统或操作员根据作业类型指定优先级。
系统根据作业要求资源情况确定优先级。
进程的静态优先级的确定原则：
按进程的类型给予不同的优先级。
将作业的情态优先级作为它所属进程的优先级。
动态优先级：
进程的动态优先级一般根据以下原则确定：
根据进程占用有CPU时间的长短来决定。
根据就绪进程等待CPU的时间长短来决定。
5．短作业优先法（SJF, Shortest Job First）
短作业优先又称为“短进程优先”SPN(Shortest Process Next)；这是对FCFS算法的改进，其目标是减少平均周转时间。
定义：
对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业。
SJF的特点：
(1) 优点：
比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；
提高系统的吞吐量；
(2) 缺点：
对长作业非常不利，可能长时间得不到执行；
未能依据作业的紧迫程度来划分执行的优先级；
难以准确估计作业（进程）的执行时间，从而影响调度性能。
SJF的变型：
“最短剩余时间优先”SRT(Shortest Remaining Time)（允许比当前进程剩余时间更短的进程来抢占）
“最高响应比优先”HRRN(Highest Response Ratio Next)（响应比R = (等待时间 + 要求执行时间) / 要求执行时间，是FCFS和SJF的折衷）
6. 最高响应比优先法(HRN，Highest Response_ratio Next)
最高响应比优先法是对FCFS方式和SJF方式的一种综合平衡。FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的长短。因此，这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。
响应比R定义如下： R =(W+T)/T = 1+W/T
其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。这样，即使是长作业，随着它等待时间的增加，W / T也就随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法，从而采用HRN方式时其吞吐量将小于采用SJF 法时的吞吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加。
‘贰’ 进程调度算法1——FCFS、SJF、HNNR
进程的调度方式有两种： 非剥夺调度方式（非抢占式）和剥夺调度方式（抢占方式）。
非抢占式：只允许进程主动放弃处理机。如进程运行结束、异常结束或主动请求I/O阻塞。在运行的过程中即使有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。
抢占式：当一个进程正在处理机上执行时，如果有一个更重要更紧迫的进程需要处理机，则立即暂停正在执行的进程，将处理机分配给更重要更紧迫的那个进程。
下面介绍适用于早期操作系统几种进程调度的算法
先来先服务（FCFS）：按照到达的先后顺序调度，事实上就是等待时间越久的越优先得到服务。
下面表示按照先来先服务算法的执行顺序
计算进程的几个衡量指标：
短作业优先算法是非抢占式的算法，但是也有抢占式的版本—— 最短剩余时间优先算法（STRN,Shortest Remaining Time Next） 。
用于进程的调度算法称为短进程优先调度算法（SPF,Shortest Process First）。
短作业/进程优先调度算法：每次调度时选择当前已到达且运行时间最短的作业/进程.。
因为进程1最先达到，此时没有其他线程，所以进程1先被服务。当进程1运行完后，进程2和3已经到达，此时进程3需要的运行时间比进程2少，所以进程3先被服务…
计算进程的几个衡量指标：
最短剩余时间优先算法：每当有进程 加入就绪队列改变时就需要调度 ，如果新到达的进程的所需的运行时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。此外，当一个 进程完成时也需要调度 。
通过比较上面三组的平均周转时间、平均带权周转时间和平均等待时间可以看出，短作业优先算法可以减少进程的等待时间，对短作业有利。
高响应比优先算法： 非抢占式的调度算法 ，只有当前运行的进程主动放弃CPU时（正常/异常完成、或主动阻塞），才需要进行调度，调度时计算所有就绪进程的相应比，选响应比最高的进程上处理机。
响应比 = （等待时间 + 运行时间）/ 运行时间
上面的三种调度算法一般适用于 早期的批处理系统 ，没有考虑响应时间也不区分任务的紧急程度。因此对用户来说交互性差。
如发现错误，请指正！！！
‘叁’ SJF调度算法
SJF调度算法：最短作业优先算法SJF（Shortest Job First )，SJF算法以进入系统的作业所要求的CPU时间为标准，总选取估计计算时间最短的作业投入运行。
SJF 调度算法优缺点：算法易于实现。但效率不高，主要弱点是忽视了作业等待时间;会出现饥饿现象。SJF 调度算法可证明为最佳的，这是因为对于给定的一组进程， SJF 算法的平均等待时间最小。虽然 SJF 算法最佳，但是它不能在短期CPU 调度层次上加以实现。因为没有办法知道下一个 CPU 区间的长度。
SJF算法Gantt图:
进程 区间时间
PI 6
P2 8
P3 7
P4 3
进程 P1 的等待时间是 3 ms，进程P2的等待时间为 16 ms，进程P3的等待时间为 9ms，进程P4的等待时间为 0ms。因此，平均等待时间为(3 + 16 + 9 +0) / 4 = 7 ms。
‘肆’ FSFS ，SJF ，HRN算法实例
1、设在单道批处理系统中有四道作业，它们提交的时刻及运行时间如下：
作业号 提交时刻（h） 运行时间（h）
1 8.0 1.0
2 8.5 0.5
3 9.0 0.2
4 9.1 0.1
请分别给出在算法FCFS、SJF和HRN中这组作业的调度顺序、平周转时间和平均带权周转时间。
【解答】
FCFS算法调度顺序：1，2，3，4，作业运行情况如下表
作业号 开始时间 完成时间 周转时间 带权周转时间
1 8.0 9.0 1.0 1.0
2 9.0 9.5 1.0 2.0
3 9.5 9.7 0.7 3.5
4 9.7 9.8 0.7 7.0
平均周转时间T=(1.0+1.0+0.7+0.7)/4=0.85
平均带权周转时间W=(1.0+2.0+3.5+7.0)/4=3.375
SJF算法调度顺序：1，3，4，2，作业运行情况如下表
作业号 开始时间 完成时间 周转时间 带权周转时间
1 8.0 9.0 1.0 1.0
2 9.3 9.8 1.3 2.6
3 9.0 9.2 0.2 1.0
4 9.2 9.3 0.2 2.0
平均周转时间T=(1.0+1.3+0.2+0.2)/4=0.675
平均带权周转时间W=(1.0+2.6+1.0+2.0)/4=1.65
HRN算法调度顺序：1，2，4，3，作业运行情况如下表
作业号 开始时间 完成时间 周转时间 带权周转时间
1 8.0 9.0 1.0 1.0
2 9.0 9.5 1.0 2.0
3 9.6 9.8 0.8 4.0
4 9.5 9.6 0.5 5.0
平均周转时间T=(1.0+1.0+0.8+0.5)/4=0.825
平均带权周转时间W=(1.0+2.0+4.0+5.0)/4=3.0
‘伍’ 操作系统作业调度算法求平均带权周转时间，急！！！！！！！！！！！
周转时间：从作业提交算起，直到执行完毕这段时间
带权周转时间：作业的周转时间T与系统为其提供服务的服务时间之比
平均XX时间即算这些时间的数学期望值
响应比优先权：（等待时间+要求服务时间）/要求服务时间=响应时间/要求服务时间
FCFS:
A[0-120]B[120-170]C[170-180]D[180-200]
平均周转时间（120+170-50+180-60+200-110）/4
SJF分为抢占式和非抢占式
非抢占式：A[0-120]C[120-130]D[130-150]B[150-200]
平均周转时间(120+130-60+150-110+200-50)/4
带权平均周转时间（120/120+70/10+40/20+150/50）/4
抢占式(注意看A执行50min后仍剩余70min，则与其它作业相比，时间还是过长)：
A[0-50]B[50-60]C[60-70]B[70-110]D[110-130]A[130-200]
平均周转时间（200+110-50+70-60+130-110）/4
HRRF：要考虑响应比，响应比高者优先。
A先到，服务A，用时120，此时，B,C,D都已经到达，求出其响应比分别为（70+50）/50，（60+10）/10，（10+20）/20，则执行C，用时10min；之后剩下B,D，
响应比分别为（80+50）/50，（20+20）/20，则执行B，用时50，最后是D，用时20min
A[0-120]C[120-130]B[130-180]D[180-200]
平均周转时间：（120+130-60+180-50+200-110）/4
其它几个运算都一样，我就不再多写了。
‘陆’ 处理机调度在主存中的作业均分cpu时间
系统采用SJF 被更短作业抢占。(1)分别给出6个作业的执行时间序列、即开始执行时间、作业完成
(1) J2 到达时抢占J1 ; J3 到达时抢占J2 。
(2）但J4 到达时，因不满足SJF ，故J4 不能被运行，J3 继续执行5 分钟。
(3）由于是4 道的作业系统，故后面作业不能进入主存而在后备队列等待，直到有作业结束。
(4）根据进程调度可抢占原则，J3 第一个做完。而这时J5 、J6 均己进入后备队列，而J5 可进入主存。
(5）因J5 最短，故它第二个完成。这时J6 方可进入主存。因J6 最短，故它第三个完成。
(6）然后是：J4 、J2和J1
(7) T =( 155 + 95 + 20 + 55 + 15 + 20 ) / 6 = 60
有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法，在下表所示的作业序列，作业优先数即为进程优
(1)(2)计算平均周转时间。
每个作业运行将经过两个阶段：作业调度(SJF算法) 和进程调度(优先数抢占式) 。另外，批处理最多容纳2道作业，更多的作业将在后备队列等待。
(2) 10:20，作业B 到达且优先权高于作业A ，故作业B 投入运行而作业A 在就绪队列等待。
(3) 10:30，作业C 到达，因内存中已有两道作业，故作业C 进入作业后备队列等待。
(4) 10:50，作业B 运行结束，作业D 到达，按SJF 短作业优先算法，或迅作业D 被装入内存进入就绪队列。而由于作业A 的优先级高于作业D ，故作业A 投入运行。
(5) 11:10，作业A 运行结束，作业C 被调入内存，且作业C 的优先级高于作业D ，故作业C 投入运行。
(6) 12:00，作业C 运行结束，作业D 投入运行。 (7) 12:20，作业，作业D 90。平均作业周转时间为70分钟。
某多道程序设计系统供用户使用的主存为100K ，磁带机2台，打印机1台。采用可变分
在
主存中的各作业平分CPU 时间。现求：(1)作业被调度的先后次序?(2)全部作业运行结束的时间?(3)作业平均周转时间为多少?(4)最大作业周转时间为多少? 答：(1)作业调度选择的作业次序为：作业1、作业3、作业4、作业2和作业5。 (2)全部作业尘兆运行结束的时间9:30。
(3)周转时间：作业1为30分钟、作业2为55分钟、作业3为40分钟、作业4
为40分钟和作业5为55分钟。 (4)平均作业周转时间=44分钟。 (5) )最大作业周转时间为55分钟。
分析：本题综合测试了作业调度、进程调度、及对外设的竞争、主存的竞争。 8 : 00 作业1 到达，占有资源并调入主存运行。 8 : 20 作业2 和3 同时到达，但作业2 因分不到打印机，只能在后备队列等待。作业3 资源满足，可进主存运行，并与作业1 平分CPU 时间。
8 : 30 作业1 在8 : 30 结派团租束，释放磁带与打印机。但作业2 仍不能执行，因不能移动而没有30KB 的空闲区，继续等待。作业4 在8 : 30 到达，并进入主存执行，与作业3 分享CPU
8 : 35 作业5 到达，因分不到磁带/打印机，只能在后备队列等待。 9 : 00 作业3 运行结束，释放磁带机。此时作业2 的主存及打印机均可满足，投入运行。作业5 到达时间晚，只能等待。
9 : 10 作业4 运行结束，作业5 因分不到打印机，只能在后备队列继续等待。 9：15 作业2 运行结束，作业5 投入运行。 9 : 30 作业全部执行结束。
某多道程序设计系统采用可变分区内存管理，供用户使用的主存为200K ，磁带机5台。采用静态方式分配外围设备，且不能移动在主存中的作业，忽略用户作业I/O时间。现
执行的次序及作业平均周转时间?
(1) FIFO算法选中作业执行的次序为：A 、B 、D 、C 和E 。作业平均周转时间为63分钟。详细说明：
1．先来先服务算法。说明：
(1) 8 : 30 作业A 到达并投入运行。注意它所占用的资源。 (2) 8 : 50 作业B 到达，资源满足进主存就绪队列等CPU 。
(3) 9 : 00 作业C 到达，主存和磁带机均不够，进后备作业队列等待。
(4) 9 : 05 作业D 到达，磁带机不够，进后备作业队列等待。后备作业队列有C 、D 。 (5) 9 : 10 作业A 运行结束，归还资源磁带，但注意主存不能移动（即不能紧缩）。作业B 投入运行。作业C 仍因主存不够而等在后备队列。这时作业E 也到达了。也由于主存不够进入后备作业队列。此时作业D 因资源满足（主存磁带均满足），进主存就绪队列等待。后备作业队列还有C 、E 。
(6) 9 : 35 作业B 运行结束，作业D 投入运行。这时作业C 因资源满足而调入主存进就绪队列等CPU 。而作业E 因磁带机不够继续在后备作业队列等待。
(7) 9 : 55 作业D 运行结束，作业C 投入运行。这时作业E 因资源满足而调入主存进就绪队列等CPU 。
(8) 10 : 30 作业C 运行结束，作业E 投入运行。 (9) 10 : 40 作业E 运行结束。
(2) SJF算法选中作业执行的次序为：A 、B 、D 、E 和C 。作业平均周转时间为58分钟。说明：
( 1 ) 8 : 30 作业A 到达并投入运行。注意它所占用的资源。 ( 2 ) 8 : 50 作业B 到达，资源满足进主存就绪队列等CPU 。
( 3 ) 9 : 00 作业C 到达，主存和磁带机均不够，进后备作业队列等待。
( 4 ) 9 : 05 作业D 到达，磁带机不够，进后备作业队列等待。后备作业队列有C 、D 。 ( 5 ) 9 : 10 作业A 运行结束，归还资源磁带，但注意主存不能移动（即不能紧缩）。作业B 投入运行。作业C 仍因主存不够而等在后备队列。这时作业E 也到达了，虽然该作业最短，也由于主存不够进入后备作业队列．此时作业D 因资源满足（主存磁带均满足），进主存就绪队列等待。后备作业队列还有C 、E 。
( 6 ) 9:35 作业B 运行结束，作业D 投入运行。这时作业C 和E 资源均满足，但按SJF 应把作业E 调入主存进就绪队列等CPU 。而作业C 因磁带机不够继续在后备作业队列等待。 ( 7 ) 9:55 作业D 运行结束，作业C 调入主存进就绪队列等CPU 。 ( 8 ) 10:05 作业E 运行结束，作业C 投入运行。 ( 9 ) 10:40 作业C 运行结束。
‘柒’ 利用短作业优先算法(SJF)，计算进程的周转时间和带权周转时间。非常着急！！
周转时间=进程结束的时间 - 进程到达的时间；
带权周转时间=周转时间 / 执行时间；
如：A作业2：30到达，3：30结束，需要执行40分钟。
周转时间=3：30-2：30=60分钟
带权周转时间=60分钟/40分钟=1.5