理想情况下，对操作系统中运行的进程作出如下假设：

1.每一个工作运行相同的时间

2.所有的工作同时到达

3.工作一旦开始，每个工作保持运行直到完成．

4.所有工作只是用的ＣＰＵ（即他们不执行ＩＯ操作）

5.每个工作的运行时间是已知的．

先放宽假设１，即任务的运行时间可以存在差异．最短任务优先调度策略是从运筹学中借鉴到计算机领域中的一种调度算法，它描述的策略可以简单概括为：先运行最短的任务，最后是次短的任务，如此下去。

假设存在任务Ａ，Ｂ，Ｃ同时在时刻到达，其中A执行需要100ms,B和Ｃ分别需要10ms.

则ＳＪＦ 调度策略可以表示为：



定义周转时间

周转时间 = 完成时间 - 到达时间

周转时间是一个性能指标，另一种指标是公平，性能和公平在调度系统中是矛盾的，如调度程序可以优化性能，但代价是阻止一些任务运行，这就降低了公平．

可以计算在这个例子中SJF调度策略的平均周转时间为：



事实上，考虑所有工作同时到达的假设，可以证明SJF确实是一个最优的调度算法，现在给出证明．

假设被调度进程集合有n个元素.对这n个进程的任意排列



,便是一种调度方案.

设Ｔ为任意一种调度策略产生的平均周转时间，则



Ｔi是第i+1个执行的进程的运行时间．

对T0,T1,...,Tn-1递增排序,得Tk0 ， Tk1， …… ，Tkn-1,设T'位SJF策略生成的调度方案的平均周转时间,则:

T' = [ Tk0 + (Tk0 + Tk1)+……+( Tk0 + Tk1 + ……+ Tkn-1)]/n

对比构成T和T'的每个累加项,后者永远不大于前者,T'是T中最小值.故,能够产生T'的调度方案必为理论最优,而T2调度方案是SJF生成的,得证.

因此，找到了一个用ＳＪＦ进行调度的好方法，但是所有任务同时到达仍然是不符合实际的，现在假设任务可以随时到达，而不在是同时到达，会导致什么玩儿你他．

假设A在t=0时刻到达，且需要运行100ms,而Ｂ和Ｃ在Ａ之后不久(t=10ms)到达，他们仍然被迫等到Ａ完成，从而遭遇到护航问题.



 



为了解决这个问题，需要放宽条件（工作必须保持运行直到完成），还需要调度程序本省的一些机制，由于系统提供了时钟终端和上下文切换，当Ｂ和Ｃ到达时调度程序可以做一些事情，比如抢占Ａ，运行另外一个工作．根据前面的定义，工作一旦开始，必须继续直到完成，所以ＳＪＦ是一种非抢占式的调度程序，因此存在上述问题．

所以这里就引出了另外一种调度程序，叫做(STCF, shortest-time  to completion First)或抢占是最短作业优先算法．每当新工作进入系统时，它就会确定剩余工作和新工作作用，谁的剩余时间最少，然后调度剩余时间最少的工作．因此，在ＳＴＣＦ中，上面的例子将按照如下时间线运行：



平均周转时间变为:



和同时到达的sjf模式一样，考虑到新的假设，STCF可以证明是最优的．考虑到所有工作同时到达，SJF是最优的．所以可以看到，ＳＴＣＦ的最优性是符合直觉的．

结束！

假设系统按单值方式运行且采用最短作业优先算法，有J1,J2,J3,J4共4个作业同时到达，则以下哪几种情况下的平均周转时间为10分钟?




正确答案: B C   你的答案: B C (正确)

执行时间J1:1分钟 J2:5分钟 J3:9分钟 J4:13分钟


执行时间J1:1分钟 J2:4分钟 J3:7分钟 J4:10分钟


执行时间J1:2分钟 J2:4分钟 J3:6分钟 J4:8分钟


执行时间J1:3分钟 J2:6分钟 J3:9分钟 J4:12分钟


添加笔记

求解答(9)

收藏

纠错





首先，短作业优先则短时间的作业利用资源，其余的作业等待

根据平均周转时间概念，将所有作业"等待时间"加上"运行时间"除以"作业数量"即可得到平均周转时间

A： (J1执行1分钟 + J2等待1分钟 + J2执行5分钟 + J3等待6分钟 + J3执行9分钟 + J4等待15分钟 + J4执行13分钟) / 4  = 50/4 = 12.5

B：  (J1执行1分钟 + J2等待1分钟 + J2执行4分钟 + J3等待5分钟 + J3执行7分钟 + J4等待12分钟 + J4执行10分钟) / 4  = 40/4 = 10

C： (J1执行2分钟 + J2等待2分钟 + J2执行4分钟 + J3等待6分钟 + J3执行6分钟 + J4等待12分钟 + J4执行8分钟) / 4    = 40/4 = 10

D：  (J1执行3分钟 + J2等待3分钟 + J2执行6分钟 + J3等待9分钟 + J3执行9分钟 + J4等待18分钟 + J4执行12分钟) / 4  = 50/4 = 12.5




选BC

各种调度算法的学习思路：

调度算法的评价指标：

一、先来先服务算法（FCFS）：First Come First Serve



二、最短作业优先算法（SJF非抢占式）：Shortest Job First



三、最短剩余时间优先算法SRTN（等价于抢占式SJF）：Shortest Remaining Time Next




注意几个小细节：

如果题目中未特别说明，所提到的“短作业/进程优先算法”默认是非抢占式的
很多书上都会说“SJF最短作业优先调度算法的平均等待时间、平均周转时间最少”

严格来说，这个表述是错误的，不严谨的。之前的例子表明，SRTN最短剩余时间优先算法得到的平均等待时间、平均周转时间更少！

应该加上一个条件“在所有进程同时可运行时，采用SJF调度算法的平均等待时间、平均周转时间最少”；或者说“在所有进程都几乎同时到达时，采用SJF调度算法的平均等待时间、平均周转时间最少”；如果不加上述前提条件，则应该说“抢占式的短作业/进程优先调度算法（最短剩余时间优先，SRNT算法）的平均等待时间、平均周转时间最少”
虽然严格来说，SJF的平均等待时间、平均周转时间并不一定最少，但相比于其他算法（如FCFS），SIF依然可以获得较少的平均等待时间、平均周转时间
如果选择题中遇到“SJF算法的平均等待时间、平均周转时间最少”的选项，那最好判断其他选项是不是有很明显的错误，如果没有更合适的选项，那也应该选择该选项


四、最高响应比优先算法HRRN：Highest Response Ratio Next
响应比 = （等待时间 + 要求服务时间）/ 要求服务时间

注意： 这里的要求服务时间其实就是等待时间！




五、对四种算法的总结：

题目:
若被调度进程集合恒定,考察指标为平均周转时间,试证明SJF策略生成的调度方案理论最优


证明:
假设被调度进程集合有n个元素.对这n个进程的任意排列{P0,P1,P2,...,Pn-1},便是一种调度方案.


设T1为任意进程调度方案产生的平均周转时间,注意:此处T1是值不确定的!T1=[M0+(M0+M1)+...+(M0+M1+...+Mn-1)]/n;Mi是第i+1个执行的进程的运行时间!!!


对M0,M1,...,Mn-1递增排序,得Mk0 ， M k1， …… ，M k n-1,设T2位SJF策略生成的调度方案的平均周转时间,则:
T2 = [ Mk0 + (Mk0 + M k1)+……+( Mk0 + M k1 + ……+ M k n-1]/n


对比构成T1和T2的每个累加项,后者永远不大于前者,T2是T1中最小值.故,能够产生T2的调度方案必为理论最优,而T2调度方案是SJF生成的,得证.


本人微信公众号:Yongf.欢迎关注,与我交流