最短作业优先算法(SJF)

最短作业优先算法(SJF)

就是CPU选择先运行耗时短的任务,比如任务A需要3s,任务B需要5s,那么程序选择先运行A


5个程序ABCDE同时提交给CPU执行(虽然式同时提交,但是有先后,假装A比B快那么一点点的一点点的一点点好了)

作业名 执行时间
A 5
B 5
C 2
D 3
E 4

那么运行顺序为

平均等待时间=(任务开始时间 - 任务提交时间)/n

等待时间

A:9-0 B:14-0 C:0-0 D:2-0 E:5-0

平均等待时间=30/5=6


如果不是同时提交,那么出现非抢占式和抢占式两种情况

非抢占式:同一时间则选择先运行耗时短的任务,不同时间则按照先来先服务(FCFS)

作业名 提交时间 执行时间
A 0 5
B 1 5
C 2 2
D 3 3
E 4 4

0s时:只有A,因此先执行A,因为是非抢占式,所以BCDE提交时即使执行时间可能更短(比如C为2)也只能等待A执行完,A执行完为5s,此时BCDE相当于同时提交,情况和第一种一样,因此顺序是CDEB

等待时间

A:0-0 B:14​-1 C:5-2 D:7-3 E:10-4

平均等待时间=(0+13+3+4+6)/5=5.2


抢占式:新任务提交时,就判断正在运行中剩下的时间和新任务的执行时间,那个短先执行哪个,原任务如果被抢占,则中途暂停

仍然是这个例子

作业名 提交时间 执行时间
A 0 5
B 1 5
C 2 2
D 3 3
E 4 4

1s时:B提交,但是此时A为4,因此继续运行A

2s时:C提交,此时A为3C为2,因此抢占运行C,A被中断还剩3s

4s时:C运行完,所有任务都为提交状态,A和C为3s,因为A先来,所以先运行A

流程如下

等待时间

A:4-2(这个2是第一段的时间) B:14-1 C:2-2 D:7-3 E:10-4

平均等待时间=(2+13+0+4+6)/5=5


有了开始时间和完成时间,至于要算其他的给出公式就能计算

周转时间=作业完成时间—作业提交时间;
平均周转时间=(作业1的周转时间+…+作业n的周转时间)/n;
带权周转时间=作业周转时间/作业实际运行时间;
平均带权周转时间=(作业1的带权周转时间+…+作业n的带权周转时间)/n;

算这些不是有手就行?


sjf算法能让平均等待时间最短,因为先执行了简单任务,当然实际应用中是理想情况,因为不知道任务执行时间是多久。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×