进程调度算法

进程的调度方式

通常有以下两种进程调度方式：
1. 非剥夺（非抢占）调度方式：当一个进程正在处理机上执行时，即使有某个更为重要或者紧迫的进程进入就绪队列，仍然让正在执行的进程继续执行，直到该进程完成或发生某种事件而进入阻塞态时，才把处理机分配给更为重要或紧迫（优先级更高）的进程。其优点是实现简单，系统开销小，适用于大多数批处理系统，但它不能用于分时系统和大多数实时系统。
2. 剥夺（抢占）调度方式：当一个进程正在处理机上执行时，若有某个更为重要或紧迫的进程（优先级更高）的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给这个更重要的进程。这种方式对提高系统吞吐率和响应效率都有明显的好处。但抢占也要遵循一定原则。

调度的基本准则

主要有以下几种：
1. CPU利用率：CPU是计算机系统中最重要和最昂贵的资源之一，所以应该尽可能使得CPU保持忙的状态，资源利用率尽可能高。
2. 系统吞吐量：单位时间内CPU完成的作业数量。长作业需要消耗较长的处理机时间，会降低系统的吞吐量。对于短作业，他们所需消耗的处理机时间较短，因此能提高系统吞吐量。调度算法和方式不同，也会对系统的吞吐量产生较大影响。
3. 周转时间：周转时间是指从作业提交到作业完成所经历的时间，是作业等待、在就绪队列中排队，在处理机上运行及输入输出操作所花费的时间的总和。
4. 等待时间：进程处于等处理机状态的时间之和。等待时间越长，用户满意度越低。实际上，处理机调度算法实际上并不影响作业执行或输入输出操作的时间，只影响作业在就绪队列中等待所花的时间。因此，衡量一个调度算法的优劣，常常只需简单地考察等待时间。
5. 响应时间：用户提交请求到系统首次产生响应所用的时间。在交互式系统中，周转时间不可能是最好的评价准则，一般采用响应时间作业衡量调度算法的重要准则之一。从用户角度来看，调度策略应该尽量降低响应时间，使得响应时间处在用户能接受的范围之内。
总之，想得到一个满足所有用户和系统要求的算法几乎是不可能的。设计调度程序，一方面要满足特定系统用户的要求（比如，实时和交互进程的快速响应要求），另一方面要考虑系统整体的效率（比如，减少整个系统的进程平均周转时间），同时还要考虑调度算法的开销等。

几种典型的调度算法

先来先服务（FCFS）调度算法
短作业优先（SJF）调度算法
优先级调度算法
高响应比优先调度算法
- 在每次进行作业调度时，先计算后备队列中每个作业的响应比，从中选出响应比最高的作业投入运行。
- 响应比 = (等待时间+要求服务时间) / 要求服务时间
- 根据公式可知：
  1. 作业的等待时间相同时，要求服务时间约旦，响应比越高，有利于短作业。
  2. 要求服务时间相同时，作业的响应比由其等待时间决定，等待时间越长，其响应比越高，因而它实现的是先来先服务。
  3. 对于长作业，作业的响应比可以随等待时间的增加而提高，等待时间足够长时，其响应比便可升到很高，从而可以获得处理机，不会饿死。
时间片轮转调度算法
1. 时间片轮转调度算法主要适用于分时系统。在这种算法中，系统将所有就绪进程按到达时间的先后次序排成一个队列，进程调度程序总是选择就绪队列中的第一个进程执行，即先来先服务的原则，但是仅能运行一个时间片。在使用完一个时间片后，即使进程并未完成其运行，它也必须释放出（被抢占）处理机给下一个就绪的进程，而被抢占的进程返回到就绪队列的末尾重新排队，等候再次运行。
2. 在时间片轮转的调度算法中，时间片的大小对系统性能有很大影响。如果时间片足够大，以至于所以进程都能在一个事件内执行完毕，则时间片轮转调度算法就退化成FCFS算法。如果时间片很小，则处理机将在进程间过于频繁地切换，使得处理机开销增大，而真正用于运行用户进程的时间将减少。因此，时间片的选择要适当，可以根据系统响应时间、就绪队列中的进程数目和系统的处理能力等决定。
多级反馈队列调度算法
1. 设置多个就绪队列，并为各个队列赋予不同的优先级，第一级队列的优先级最高，第二级队列次之，其余队列的优先级逐次降低。
2. 赋予各个队列中进程执行时间片的大小各不相同。在优先级越高的队列中，每个进程的运行时间片越小。例如，第二级队列的时间片要比第一级队列的时间片长一倍…第i+1级队列的时间片要比第i级队列的时间片长一倍。
3. 当一个新的进程进入内存后，首先将它放入第一级队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时候，如果它能在时间片内完成，便可准备撤离系统；若它在一个时间片结束时尚未完成，调度程序便将该进程转入第二级末尾，再同样按FCFS原则等待调度执行；若它在第二级队列中运行一个时间片后仍未完成，再以同样的方法进入第三级队列…如此下去，当一个长进程从第一级队列一次降到第n级队列后，在第n级队列中便采用时间片轮转方式进行。
4. 仅当第一级队列为空时，调度程序才调度第二级队列中的进程进行；仅当第1到（i-1）级队列均为空，才会调度第i级队列中的进程运行。若处理机正在执行第i级队列中的某个进程，此时又有新的进程进入优先级较高的队列（第1到（i-1）级的任意一级），则此时行进程将抢占正在运行的处理机，即由调度程序把正在运行的进程放回第i级队列末尾，把处理机分配给新到的更高优先级进程。
- 这种调度方法优势如下：
  1. 终端型作业用户：短作业优先。
  2. 短批处理作业用户：周转时间较短。
  3. 长批处理作业用户：经过前面几个队列得到部分执行，不会饿死。