目录
1. 基本概念
1.1 CPU-I/O执行周期
1.2 CPU调度程序（CPU scheduler）
1.3 进程状态模型
1.4 抢占调度
1.5 调度程序（dispatcher）
1.6 调度准则
2. 调度算法
2.1 先到先服务（FCFS）
2.2 最短作业优先调度（SJF）
2.3 优先级调度
2.4 轮转调度（RR）
2.5 多级队列调度
2.6 多级反馈队列调度
3 线程调度
参考资料：
进程调度的目的：在进程间切换CPU，最大化CPU利用率，通过操作系统的调度使得计算机资源分配和使用更加高效。
进程的属性：进程执行包括周期进行CPU执行和I/O等待。据此可以将程序分为CPU密集型程序和I/O密集型程序。
CPU密集型程序一般只有少量长CPU执行；I/O密集型程序一般具有大量短CPU执行。
CPU空闲时，操作系统从就绪队列中选择一个进程来执行，进程选择采用短期调度程序（short-term scheduler）或CPU调度程序。
调度程序分为：短期调度程序，中期调度程序和长期调度程序。
可以参考之前的博文——【操作系统——进程状态】。
其中七状态模型包含的情况比较全面，除了进程的创建、就绪、运行、等待、终止这五个状态，考虑在执行虚拟内存管理的操作系统中，可以将暂时不用的进程（处于就绪态和等待态的进程）换出（swap out）到外部存储设备（如硬盘）中，在适当的时间再将其换入（swap in）到内存中，此时引入了就绪挂起和等待挂起状态。
需要CPU调度的4种情况：
当一个进程从运行状态切换到等待状态（例如I/O请求，或wait()调用）
当一个进程从运行状态切换到就绪状态（例如当出现中断）
当一个进程从等待状态切换到就绪状态（例如I/O完成）
当一个进程终止。
调度方案分为两种：（1）非抢占的（nonpreemptive）或协作的（cooperative）；（2）抢占的（preemptive）。非抢占调度下，一旦某个进程分配到CPU，该进程会一直使用CPU，直到它终止或切换到等待状态。抢占调度允许第二个进程抢占第一个进程的运行，这中间可能涉及进程共享数据的一致性问题，进程同步问题。
这个调度程序在英文原书中称为“dispatcher”，与上面说的CPU调度程序（CPU scheduler）不同，CPU scheduler负责进程的选择（调度），而dispatcher负责将CPU控制交给由CPU schedule（即短期调度程序）选择的进程，CPU scheduler负责进程选择，dispatcher实现调度过程的进程切换细节，个人感觉二者属于上下游关系。
dispatcher的主要功能如下：
切换上下文；
切换到用户模式；
跳转到用户程序的合适位置，以便重新启动程序；
调度程序停止一个程序而启动另一个程序所需的时间称为调度延迟（dispatch latency）。
为了比较不同的CPU调度算法，采用一些比较准则来评价CPU调度算法的特性，具体的一些比较准则包括：
进程调度的理想情况是：最大化CPU使用率和吞吐量，最小化周转时间、等待时间和响应时间。
先到先服务（First-Come First-Served，FCFS）调度算法。通过FIFO队列实现，当一个进程进入就绪队列中的时候，它的PCB会被链接到队列尾部；当CPU空闲时，它会分配给位于队列头部的进程，并且这个进程从队列中移去。
特点：
最短作业优先（Shortest-Job-First，SJF）调度算法。将每个进程与其下次CPU执行长度关联起来，CPU空闲时会被赋给具有最短CPU执行时间（注意是下次CPU执行的时间最短而不是总的时间最短）的进程执行。另一种叫法是：最短下次CPU执行（shortest-next-CPU-burst）算法。
特点：
优先级调度（priority-scheduling）算法为每个进程关联一个优先级，具有最高优先级的进程会分到CPU；具有相同优先级的进程按照FCFS的顺序调度。SJF算法是一个简单的优先级算法，其优先级（p）为下次（预测的）CPU执行时间的导数。
特点：
轮转（Round-Robin，RR）调度算法，类似FCFS调度，但是增加了抢占以切换进程。将一个较小的时间单元定义为时间量（time quantum）或时间片（time slice），将就绪队列作为循环队列，CPU调度整个就绪队列，为每个进程分配不超过一个是时间片的CPU。
特点：
多级队列（multilevel queue）调度算法，将就绪队列分成多个单独的队列，根据进程属性（如内存大小、进程优先级、进程类型等），一个进程永久分到一个队列，每个队列有自己的调度算法。例如可有两个队列分别用于前台进程和后台进程，前台队列可采用RR算法调度，后台队列采用FCFS算法调度。
多级队列调度算法实例，有五个队列，优先级由高到低，分别为：（1）系统进程；（2）交互进程；（3）交互编辑进程；（4）批处理进程；（5）学生进程。其中每个队列与更低层队列相比具有绝对的优先，例如只有系统进程、交互进程和交互编辑进程队列都为空，批处理队列内的进程才能运行。如果一个批处理进程运行过程中有一个交互进程进入就绪队列，那么该批处理进程会被抢占。
另一种可能是，在队列之间划分时间片，每个队列具有一定比例的CPU时间，可用于调度队列内的进程。例如对于前台-后台队列例子，前台队列可有80％的CPU时间，用于进程之间的RR调度；后台队列可以有20％的CPU时间，用于按FCFS算法来调度进程。
多级反馈队列调度（multilevel feedback queue）调度算法允许进程在队列之间迁移，其特点在于：
多级反馈队列调度程序可由下列参数定义：
线程可以分为用户级（user-level）线程和内核级（kernel-level）线程。在支持线程的操作系统上，内核级线程（而不是进程）才是操作系统所调度的。这里理解为上述的进程调度算法，其实就CPU而言，并不严格区分该算法究竟是用于调度进程还是用于调度线程，而是用于调度基本的调度单元，在支持线程的操作系统上，线程才是CPU调度的基本单元，此时上述调度算法此时用于线程调度。
关于用户级线程和内核级线程：用户级线程是由线程库管理的，内核并不知道。用户级线程最后运行在CPU上，映射到相应的内核级线程，这种映射不是直接的，可能采用轻量级进程（Light Weight Process，LWP），因此内核级线程和用户级线程的调度具体实现仍有所区别。
[1] Silberschatz, A., Galvin, P. B., and Gagne, G. 操作系统概念(原书第9版) (郑扣根等译)[M]. 机械工业出版社, 2020.
