进程调度算法

进程调度

在多道程序系统中，进程数量往往多于处理机的个数，因此进程竞争使用处理机的情况在所难免。处理机调度是对处理机进行分配，即从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程并发地执行。

1.调度的基本概念

1.1调度的时机、切换与过程

在操作系统中，用于调度和分配CPU的组件成为调度程序。

调度程序是操作系统的内核程序。请求调度的事件发生后，才可能运行调度程序，调度了新的就绪进程后，才会进行进程切换。

进行进程调度与切换的情况如下：

• 发生引起调度条件或当前进程无法继续运行下去（如分配时间片用尽）时，可以马上进行调度与切换。若操作系统只在这种情况下进行进程调度，则是非剥夺调度。
• 中断处理结束或自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，则可马上进行进程调度与切换。若操作系统支持这种情况下的运行调度程序，则实现了剥夺方式的调度。

1.2进程调度方式

所谓进程调度的方式，是指当某个进程正在处理机上执行时，若有某个更为重要或紧迫的进程需要处理，即有优先权更高进程进入就绪队列，此时应该如何分配处理机。

①非抢占式调度方式（非剥夺方式）： 当一个进程在处理及上执行时，即使有某个更为紧迫的任务进入就绪队列，仍然把正在执行的进程继续执行，直到该进程运行完成或发生某种事件而进入阻塞态时，才把处理机分配给其他进程。

非抢占式实现容易，但是不能用于用于分时系统（因为分时系统每次分给每一个进程时间片，时间片用完便进入就绪队列，而不能一直把当前进程运行完）。

②抢占式调度方式（剥夺方式）： 当一个进程正在处理及上处理时，若有某个更为重要或紧急的进程需要使用处理机，则允许调度程序根据某种原则暂停正在执行的进程，将处理及分配给这个更为重要或紧迫的进程。

抢占式调度方式对提高系统吞吐率和响应效率都有明显的好处。但是，抢占不是一种任意性行为，必须遵循一定的原则，主要有优先权、短进程优先和时间片原则等。

2.典型的调度算法

1.1先来先服务（FCFS）调度算法

FCFS调度算法没从从就绪队列中选择最先进入该队列的进程（作业），将处理及分配给它，使之投入运行，**直到运行完成或因为某种原因阻塞时（如等待输入或者等待某种系统资源）**才释放处理机。

FCFS算法属于不可剥夺算法。

优点：算法简单

缺点：效率低，对长作业有利，对短作业不利。

1.2短作业优先（SJF）调度算法

短作业优先调度算法是指对短作业（进程）优先调度的算法。短进程优先调度算法从就绪队列中选择一个或若干估计运行时间最短的进程，将处理机分配给它，使之立即执行，直到完成或者发生某事件而阻塞时，才释放处理机。

短进程优先调度算法属于剥夺式算法。

优点：平均等待时间最短。

缺点：对长进程不利，容易造成长进程的饥饿现象。

1.3高优先级调度算法

该算法中的优先级用于描述作业（进程）的紧迫程度。优先级段都算法每次从就绪队列中选择优先级最高的进程，将处理机分配给它，使之投入运行。

根据新的的更高优先级进程能否抢占正在执行的进程，可将该调度算法分为抢占式和非抢占式两种：

• 非抢占式： 当一个进程正在运行时，即使有更高的优先级的进程进入就绪队列，也会等待当前进程运行完。
• 抢占式： 当一个进程正在运行时有更高的优先级的进程进入就绪队列，立即暂停正在执行的进程，并将CPU分配给更高优先级的进程。

1.4时间片轮转调度算法

时间片轮转调度算法主要用于分时系统（并发系统，当前我们使用的PC都是这种系统）。在这种算法中，系统将所有就绪进程按照FCFS排列成一个就绪队列，调度程序总是选择就绪队列中第一个进程执行，但仅能执行一个时间片，如50ms。

在使用完一个时间片后，即使进程并未运行完成，也必须被剥夺CPU使用权，由下一个就绪进程使用，而被剥夺的进程放入就绪队列队尾。

时间片轮转调度算法是抢占式算法。

优点：可实现多进程的并发运行。

缺点：进程切换有时间开销，时间片太短会导致频繁切换；时间太大会导致每个进程都会在一个时间片内完成，退化成FCFS算法，因此要选择合适的时间片的大小。

1.5多级反馈队列调度算法

多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合与发展。

多级反馈队列思想如下：

• 设置多个就绪队列，并未每个队列赋予不同的优先级，每个队列内调度算法即可时抢占式又可以是非抢占式。第一级队列优先级最高，以后的依次降低。
• 赋予各个队列的进程时间片的大小各不相同。在优先级越高的队列中，每个进程的时间片就越小。例如：第i + 1级队列时间片要比第i级队列的时间片长一倍。
• 每个队列都采用FCFS算法。当新进程进入内存后，首先将它放入第一级队列队尾，等待执行完时间片后放入第二级队列队尾……依次循环。
• 按队列优先级调度。仅当第一级队列为空时，才调度第二级队列种的进程运行。

多级反馈队列调度算法结合了以上其他调度算法的优点，十分通用。