操作系统的调度算法

1、算法思想：

主要从“公平”的角度考虑（类似于我们生活中排队买东西的例子）。

2、算法规则：

按照作业（或进程）到达的先后顺序进行服务。

3、FCFS用于作业（或进程）调度时考虑的方面：

1、用于作业调度时，考虑的是哪个作业先到达后备队列。

2、用于进程调度时，考虑的是哪个进程先到达就绪队列。

4、FCFS是非抢占式的算法（上一个进程结束后才运行下一个进程）。

5、FCFS的优点：公平、算法实现简单。

FCFS的缺点：排在长作业（或进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。

所以，FCFS算法对长作业有力，对短作业不利。

例如：排队坐车，有的人坐一站，有的人坐到终点站。坐一站的人或许坐车5分钟到目的地，做到终点站的人或许需要50分钟。这样的话，如果他们等的时间越长对坐一站的人来说体验极差，因为坐车5分钟，等车半小时，而对于坐到终点站的人来说等20分钟还可以接受，毕竟坐车都要50分钟。

6、FCFS算法不会导致饥饿（概念见下面注意事项）。

1、算法思想：

追求最少的平均等待时间、最少的平均周转时间、最少的平均带权周转时间。

2、算法规则：

最短的作业（或进程）优先得到服务（所谓“最短”是指要求服务时间最短）。

3、SJF即可用于作业调度，也可用于进程调度。用于进程调度时称为“短进程优先（SPF,Shortest Process First）算法”。

4、SJF和SPF是非抢占式的算法。

但是也有抢占式的版本：最短剩余时间优先算法（SRFN，Shortest Remaining Time Next）.

5、SJF的优点：“最短的”平均等待时间、平均周转时间。

SJF的缺点：不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业（或进程）的运行时间是由用户提供的，并不一定真实，不一定做到真正的短作业优先。

6、SJF算法会导致“饥饿”。如果有源源不断的短作业（或进程）到来，可能使长作业（或进程）长时间得不到服务，产生“饥饿”现象。如果一直得不到服务，则称作业（或进程）“饿死”。

1、算法思想：

要综合考虑作业（或进程）的等待时间和要求服务的时间。

2、算法规则：

在每次调度时先计算各个作业（或进程）的响应比，选择响应比最高的作业（或进程）为其服务。

响应比 = （等待时间 + 要求服务时间）/ 要求服务 时间

3、HRRN即可用于作业调度，也可用于进程调度。

4、HRRN是非抢占式的算法。因此只有当前运行的作业（或进程）主动放弃处理机时，才需要调度，才需要计算响应比。

5、HRRN综合考虑了等待时间和运行时间（要求服务时间）。

等待时间相同时，要求服务时间段的优先（SJF的优点）。

要求服务时间相同时，等待时间长的优先（FCFS的优点）。

6、HRRN不会导致“饥饿”。对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题。