wordpress做小说网站吗,自己建设房源网站,企业大黄页,WordPress文章小工具0 前言
接上一篇文章#xff1a;进程调度#xff08;1#xff09;#xff1a;FIFO#xff08;先进先出#xff09;算法 原理与实践
1 前提铺垫
请参考上一篇文章的前提铺垫部分#xff0c;本文与之完全一致。
2 SJF 原理
SJF#xff08;Shortest Job First#x…0 前言
接上一篇文章进程调度1FIFO先进先出算法 原理与实践
1 前提铺垫
请参考上一篇文章的前提铺垫部分本文与之完全一致。
2 SJF 原理
SJFShortest Job First短任务优先也就说对于Ready的多个进程先执行最短的内一个。
2.1 算法
这种算法在我们的《算法与数据结构》中也是常见的对于多个即将执行的任务每一次都选择最短的先执行执行完之后再执行次短的以此类推这样一来每个任务的周转时间都是最小的平均周转时间也就是最小的。
单纯从平均周转时间这个性能指标来说这个算法还是不错的
2.1.1 实例1
我们先来看一个实例例如有4个任务放宽每个任务时间都一样的假设
A10B1C4D100
假定4个任务同时到达根据SJF的原则我们的执行顺序应该是
B
C
A
D对应的Average Turnaround Time (1 5 15 115) / 4 34 (平均周转时间是34s)
2.1.2 实例1的模拟
我们直接将后面部分要将的实践搬到这里一部分让你有一个直观的感受
ARG policy SJF
ARG jlist 10,1,4,100Here is the job list, with the run time of each job: Job 0 ( length 10.0 )Job 1 ( length 1.0 )Job 2 ( length 4.0 )Job 3 ( length 100.0 )** Solutions **Execution trace:[ time 0 ] Run job 1 for 1.00 secs ( DONE at 1.00 )[ time 1 ] Run job 2 for 4.00 secs ( DONE at 5.00 )[ time 5 ] Run job 0 for 10.00 secs ( DONE at 15.00 )[ time 15 ] Run job 3 for 100.00 secs ( DONE at 115.00 )Final statistics:Job 1 -- Response: 0.00 Turnaround 1.00 Wait 0.00Job 2 -- Response: 1.00 Turnaround 5.00 Wait 1.00Job 0 -- Response: 5.00 Turnaround 15.00 Wait 5.00Job 3 -- Response: 15.00 Turnaround 115.00 Wait 15.00Average -- Response: 5.25 Turnaround 34.00 Wait 5.25
具体含义在上一篇文章已经解释过了不再细说。
这样来看SJF在这种情况下的确是最优的从数学角度来说也是最优的
但是如果我们放宽任务同时到达的条件事情可能又比较糟糕了……
2.2 缺点非抢占式调度
什么是非抢占式调度呢我们先来看一个假设
假设任务A在CPU执行任务B到达了并且B的运行时间比A小但是A在B到达之前已经在执行了B就只能等着A执行完再执行尽管B比A的运行时间少。
这就是非抢占式调度后来者即便比正在运行的进程时间短也不能抢占它的位置来运行自己。
这样的话会造成什么问题呢我们来看一个实例
A100B10C20
三个进程A先到达时刻到达随后B、C到达B、C同时在时刻10到达。
程序的执行情况
A
B
C对于后来的B和C虽然远比A运行时间小但是由于SJF的非抢占它们只能等着A执行完然后再执行B再执行C因为B比C时间少。 这显然是糟糕的此时Average Turnaround Time (100 110 120) / 3 110。看起来又退化到了FIFO算法……
显然非抢占式调度也不是很好。所以人们又提出了新的算法……是的当旧算法出现问题自然会催生新算法诞生人类的科技就是这样一步步变得越来越强大和复杂。
3 SJF 实践
你可以充分阅读README.md文档然后自己尝试一些数字并计算之后再参考答案。
值得说明的是模拟程序并不是很完美默认是多任务同时到达并且没有提供修改选项。
4 重要思想
对于同时到达的任务采取花费时间少的优先执行这能够让我们的Average Turnaround Time这一性能指标达到最优。但是不同时到达的任务可能不太好用因为它“不会抢地盘”只会“傻等着”后续我们也会介绍解决方案。
后续我们会介绍更多的性能指标你就会发现仅仅只有平均周转时间最优是远远不够的。
5 预告进程调度2bSTCF最短完成时间优先 算法 原理与实践
基于SJF的非抢占式调度的缺点STCF做了改进实现了抢占式调度。
下一篇链接进程调度2bSTCF最短完成时间优先 算法 原理与实践
