博客

1.FCSF算法（先来先服务）

算法思想

当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是最优先考虑在系统中等待时间最长的作业，不管作业执行时间的长短。

在进程调度中，采用FCFS算法时，每次调度就是从就绪队列中选择最先进入该队列的进程，为其分配处理机，运行。

优点

简单，容易实现

缺点

平均等待时间波动较大

I/O资源和CPU资源的利用率低，对短作业不利

2.短作业优先（SJF）

算法思想

系统从进程队列中选择执行时间最短的进程优先执行，时间越短，优先级越高

优点

降低了短作业的等待时间，平均周转时间减小了

系统吞吐量提高

缺点

很难准确预估作业运行时间

对长作业不利，可能等待长时间得不到执行

也未考虑作业的紧迫程度

3.优先级调度算法（PSA)

算法思想

基于作业紧迫程度，赋予作业响应的优先级，系统从后备队列获取优先级高的进程优先执行

优点

紧迫作业可以优先执行

适合分时、实时系统

缺点

低优先级的进程需要等待很久或者永远执行不了

4.高响应比优先调度算法

算法思想

系统从后备队列中选择响应比高的进程优先执行

响应比

响应比 = （作业等待时间 + 作业运行时间）/ 作业运行时间 = 1 + 作业等待时间 / 作业运行时间

优点

优先级动态变化，既可以考虑到作业进入系统的次序，又能考虑到作业运行的时间

保证长作业等待足够时间必然能执行

缺点

每次调度都要计算相应比，开销大

示例

解释：

1.FCSF

顺序：A -> B -> C -> D

T = (2 + 2 + 1.6 + 1.3 ) / 4 = 1.725

W = (1 + 4 + 16 + 6.5) / 4 = 6.875

2.SJF

顺序：A -> C – >D -> B

T = ( 2 + 2.3 + 1.1 + 0.8) / 4 = 1.55

W =(1 + 4.6 + 11 + 4) / 4 = 5.15

3.PSA

顺序：A -> B -> D -> C

T = ( 2 + 2 + 1.8 + 1.2) / 4 = 1.75

W = (1 + 4 + 18 + 6 ) / 4 = 7.25

4.HRRN

响应比：

B: 1 + (10 – 8.5) / 0.5 = 4

C: 1 + (10 – 9.0) / 0.1 = 11

D: 1 + (10 – 9.5) / 0.2 = 3.5

顺序：A -> C -> B -> D

T = ( 2 + 2.1 + 1.1 + 1.3 ) / 4 = 1.625

W = ( 1 + 4.2 + 11 + 6.5 ) / 4 = 5.675

over!