【进程调度任务】
进程调度是操作系统中必不可少的一种调度，因此在三种类型的 OS 中，无一例外的使用了进程调度，其是对系统性能影响最大的一种处理机调度
进程调度的任务有三：
- 保存处理机现场信息：在调度时需要保存当前进程的处理机现场信息
- 按某种算法选取进程：调度程序按某种算法从就绪队列中选取一个进程，将其状态改为运行状态，并准备将处理机分配给他
- 将处理机分配给进程：由分派程序将处理机分配给该进程，此时需要将选中的进程控制块内有关处理机现场的信息装入处理器相应的各个寄存器中，将处理器的控制权交予该进程，让其从上次断点处恢复运行
【进程调度方式】
非抢占方式
非抢占方式实现简单，系统开销小，适用于大多数的批处理系统，但不适用于分时系统与实时系统
非抢占方式一旦将处理机分配给某进程后，就会让该进程一直运行下去，直至进程完成或因发生某事件堵塞，绝不会因为时钟中断或其他原因去抢占当前正在运行进程的处理机
在采用非抢占方式时，可能引起进程调度的因素有：
- 正在执行的进程运行完毕
- 因发生某事件使得进程无法继续运行
- 正在执行中的进程因提出 I/O 请求而暂停
- 进程通信或进程同步中，执行了某种原语操作
抢占方式
抢占方式运行调度程序依据某种原则，去暂停某个正在执行的进程，将已分配给进程的处理机重新分配给另一进程
抢占不算一种任意性行为，而是遵循一定原则：
- 优先权原则：允许优先级高的新到进程抢占当前进程的处理机
- 短进程优先原则：运行新到的短进程抢占当前长进程的处理机
- 时间片原则：各进程按时间片轮转时，正在执行的进程的一个时间片完后，便停止该进程的执行而重新进行调度
【时间片轮转调度算法】
在分时系统中，最简单也最常用的是基于时间片轮转（Round Robin，RR）调度算法，其让就绪队列上的每个进程仅运行一个时间片，对于 n 个进程，每个进程每次大约都可获得 $\frac{1}{n}$ 的处理机时间
轮转法根据 FCFS 策略，将所有的就绪进程排成就绪队列，设置每一定时间间隔产生一次中断，激活进程调度程序，完成调度，将 CPU 分配给队首进程，当进程的时间片耗尽或运行完毕后，系统再次将 CPU 分给新的队首进程
在轮转法中，进行进程的切换分为两种情况：
- 时间片未用完，正在运行的进程已完成：将完成的进程从就绪队列中删除，再调度就绪队列队首进程，启动一个新时间片
- 时间片已用完，正在运行的进程未完成：中断程序被激活，调度程序将进程送往就绪队列尾部
时间片大小的确定对性能有很大的影响，如果选择较小的时间片，那么会有利于短作业，但会频繁的执行进程调度与进程上下文切换，增加了系统开销；如果时间片选择的过长，且每个进程都能在一个时间片内完成，那么 RR 算法就退化成了 FCFS 算法，无法满足短作业与交互用户的需求
因此，一个较为可取的时间片大小是略大于一次典型的交互所需的时间，从而使得大多数交互式进程能在一个时间片内完成
【优先级调度算法】
非抢占与抢占式优先级调度算法
优先级调度算法，是将处理机分配给就绪队列中优先级最高的进程，依据进程调度方式，其可进一步的分为以下两种：
- 非抢占式优先级调度算法：一旦将处理机分配给就绪队列中优先级最高的进程后，该进程会一直执行直至完成，除非因该进程发生某事件而放弃处理机时，系统才可将处理机分配给另一优先级最高的进程
- 抢占式优先级调度算法：将处理机分配给优先级最高的进程后，在执行期间，只要出现另一个优先级更高的进程，调度程序就会将处理机分配给这个优先级更高的进程
优先级类型
优先级调度算法的关键在于两点：一是确定进程的优先级，二是优先级类型的选择
静态优先级是创建进程时确定的，其用某一范围内的一个整数 (优先数) 来表示，在进程的整个运行期间不变；动态优先级是创建进程之初先赋予了一个优先级，然后其值随着进程的推进或时间的增加而改变
对于静态优先级来说，其简单易行，系统开销小，但不够精确，可能会出现优先级低的进程长期没有被调度的情况；对于动态优先级来说，其较为精确，但系统开销大
【多队列调度算法】
多队列调度算法将系统中的进程就绪队列从一个拆分为多个，将不同类型或性质的进程固定分配在不同的就绪队列，不同的就绪队列可以采用不同的调度算法，每个就绪队列中的进程也可以设置不同的优先级
在多处理机系统中，由于该算法安排了多个就绪队列，因此在多处理机系统中，可以很方便地为每个处理机设置一个单独的就绪队列
【多级反馈队列调度算法】
多级反馈队列调度算法不像上述算法一样，要知道各进程所需的执行时间，其调度机制描述如下：
- 设置多个就绪队列：在系统中设置多个就绪队列，并为每个队列设置不同的优先级，第一个队列优先级最高，第二个次之，其他队列优先级逐个降低，优先级越高的时间片越小，一般设置为后一个优先级的时间片长度为前一个优先级的时间片的一倍
- 每个队列采用 FCFS 算法：当新进程进入内存后，首先将其放入第一队列末尾，按 FCFS 原则进行调度，当轮到该进程时，如果其能在时间片内完成，便可撤离系统；如果其不能在时间片内完成，那么就将其转入第二队列的末尾等待调度，以此类推。当进程被降到第 $n$ 队列后，在第 $n$ 队列中采取 RR 方式运行
- 按队列优先级调度：调度程序仅当第 $1$ 到第 $i-1$ 的所有队列都为空时，才会调度第 $i$ 队列中的进程。如果处理机在第 $i$ 队列中为某进程服务时又有新进程进入 $i$ 之前的队列，那么须将正在运行的进程放回第 $i$ 进程的末尾，并将处理机分配给高优先级的进程
【基于公平原则的调度算法】
保证调度算法
保证调度算法是另一种类型的调度算法，其向用户做出的保证并不是优先运行，而是明确的性能保证，该算法可以做到调度的公平性。
如果在系统中有 n 个相同类型的进程在运行，为公平起见，那么须保证每个进程都获得相同的处理机时间 $\frac{1}{n}$
公平分享调度算法
保证调度算法分配给每个进程相同的处理机时间，对于诸进程来说，是体现了一定程度的公平，但如果各个用户拥有的进程数不同，就会发生对用户的不公平问题
在该调度算法中，调度的公平性是针对用户而言，使所有用户能获得相同的处理机时间，或所要求的时间比例
