进程调度算法.ppt

作业:已知A,B,C,D,E五个进程分别在第0、1、2、3、4个单位时间先后到达,它们分别需要4、3、5、2、4个单位时间运行完毕。若采用先来先服务算法进行调度,计算各进程的周转时间和带权周转时间。
分析:
周转时间=完成时间-到达时间
完成时间=开始执行时间+运行时间
带权周转时间=周转时间/运行时间
A
B
C
D
E
运行时间
4
3
5
2
4
到达时间
0
1
2
3
4
周转时间
4-0=4
7-1=6
12-2=10
14-3=11
18-4=14
带权周转时间
4/4=1
6/3=2
10/5=2
11/2=
14/4=
开始/完成时间 0 4 7 12 14 18
短作业(进程)优先调度算法SJF
在作业调度中,是从后备作业队列中选择1个或多个估计运行时间最短的作业调入内存。
在进程调度中,则是从就绪队列中选出一个估计运行时间最短的进程,给它分配处理机并投入运行。直到该进程运行完成或因某事件而阻塞放弃处理机时,再重新调度。是一种非抢占方式的进程调度。
例3:已知A,B,C,D,E五个进程分别在第0、1、2、3、4个单位时间先后到达,它们分别需要4、3、5、2、4个单位时间运行完毕。若采用短作业优先算法进行调度,计算各进程的周转时间和带权周转时间。
分析:
周转时间=完成时间-到达时间
完成时间=开始执行时间+运行时间
带权周转时间=周转时间/运行时间
A
D
B
E
C
运行时间
4
2
3
4
5
到达时间
0
3
1
4
2
周转时间
4-0=4
6-3=3
9-1=8
13-4=9
18-2=16
带权周转时间
4/4=1
3/2=
8/3=
9/4=
16/5=
开始/完成时间 0 4 6 9 13 18
SJF调度算法优缺点
优点:能有效地降低作业的平均等待时间,提高系统吞吐量。
缺点:
对长作业不利。由于调度的总是短作业,也就是允许后来的短作业“加塞”,∴可能会导致长作业在(无法预计的)很长时间内得不到运行,引起长作业“无限等待”。
不能保证紧迫性作业(进程)被及时处理。
由于作业(进程)的运行时间是根据用户提供的时间而定的,而用户也可能会有意无意地缩短其作业的估计运行时间,∴该算法不一定能真正做到短作业优先调度。
高响应比优先调度算法
响应比=响应时间/估计运行时间
=(等待时间+估计运行时间)/估计运行时间
系统挑选响应比最大的后备作业投入运行。当作业等长(即估计运行时间相等)时,它就是先来先服务;当作业几乎同时到达(即等待时间相等)时,它接近于短作业优先。而且随着后备作业的延长,作业的优先级别将不断提高。这个算法既可以保持短作业优先的特性,又可以有效地避免“无限等待”的现象。
高优先权优先调度算法(FPF)
高响应比优先调度算法优点
既考虑了短作业的利益,又考虑了长作业的利益。
对于一个作业来说,响应比是变化的动态量,∵等待时间是一直变化的。刚开始时,短作业由于所需CPU时间少,因而会获得高的响应比值,会被优先投入运行。但随着时间的推移,长作业的等待时间变长,它的响应比会上升,也会被投入运行。
例4:已知A、