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