3.2 调度算法（重点！！！）

• 一、先来先服务和短作业（进程）优先调度算法
• 二、高优先权优先调度算法
• 三、基于时间片的轮转调度算法

一、先来先服务和短作业（进程）优先调度算法

1、先来先服务调度算法（FCFS）

• 是一种最简单的调度算法，既可用于作业调度，也可用于进程调度。
• 进程调度采用FCFS算法时，每次调度都从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之运行。
• FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。

2、短作业（进程）优先调度算法（SJ（P）F）

• 对短作业或短进程优先调度的算法。可以分别用于作业调度和进程调度。
• 短作业优先（SJF）的调度算法：从后备队列中选择一个或者若干个估计运行时间最短的作业，将它们调入内存。
• 短进程优先（SPF）调度算法：是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行。

SJF调度算法的优缺点

二、高优先级优先调度算法

为照顾紧迫性作业，使之在进入系统后便获得优先处理，引入了最高优先权（FPF）调度算法。
此算法常用于批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度算法，还可用于实时系统中。

当用于进程调度时，它分为两种：

• 1、非抢占式优先权算法
• 2、抢占式优先权算法

1、优先权的类型

2、确定进程优先权的依据有如下三个方面：

高响应比优先调度算法（HRRN）

在批处理系统中，短作业优先算法是一种比较好的算法，其主要不足是长作业的运行得不到保证。我们为每个作业引入动态优先权，并使作业的优先级随着等待时间的增加儿以速率a提高，则可解决问题。见下式：
优先权=（等待时间+要求服务时间）/要求服务时间（重点！！！）

三、基于时间片的轮转调度算法

在分时系统中，为保证能及时响应用户的请求，必须采用基于时间片轮转式进程调度算法。在早期，分时系统中采用的是简单的时间片轮转法，进入90年代后，广泛采用多级反馈队列调度算法。下面分别介绍两种方法并比较性能。

1、时间片轮转法（RR）

时间片大小的确定

在时间片轮转算法中，时间片的大小对系统性能有很大的影响。不能太短也不能太长，一个比较可取的大小是，时间片略大于一次典型的交互所需要的时间。

2、多级反馈队列调度算法

多级反馈队列调度算法具有较好的性能，能较好的满足各类用户的需要。

• 终端型作业用户：
  大多属于较小的交互性作业，只要能使作业在第一队列的时间片内完成，便可令用户满意。
• 短批处理作业用户：
  周转时间仍然较短，至多在第二到三队列即可完成。
• 长批处理作业用户：
  将依次在1~n级队列中轮转执行，不必担心作业长期得不到处理。