详解操作系统内核对线程的调度算法

原创 jameswhale jameswhale的技术人生

操作系统内核对线程的调度非常有意思，因为他的一系列思想和方法论都能从生活和业务开发中找到影子，比如：

超市收银台会分多个收银通道，快速通道针对那些提篮子的客户，慢速通道针对那些推购物车的客户，从而减少提篮子客户的付款等待时间。设想一下，若某个客户只买了几件物品，但是不巧正好排到了购买了一车物品的客户后面，他可能会很失去耐心。
银行营业厅的叫号系统，他会按照VIP客户、普通客户分出多个号段的排队序号，VIP客户的响应速度会快一些，普通客户的响应速度会慢一些。
在内容处理系统中，在处理能力一定的情况下，我们也会按照文章来源的不同进行调度处理，优先快速响应高优先级文章的处理。
在融合存储系统中，会对不同业务的主机I/O请求设置不同的优先级，优先保证重要业务的I/O性能（并发和延迟）。

两个有意思的场景

我们都知道：进程是操作系统进行”资源分配“的基本单位，线程是操作系统进行“调度”的基本单位，从这句话的字面解读，似乎进程和“调度”没有太多关系，但是实际上，内核在进行线程调度的时候会去参照线程是否属于同一个进程（当其他条件都一样的情况下，比如，优先级等）。在业务应用开发中，若涉及线程相关，一般会将Woker线程数目设置为CPU的逻辑核数以便最大限度利用CPU。若没有上面提到的策略，这样的设置实际并没有太多意义（或者说设置更多的线程，从而有提高业务线程被调度的整体次数），因为一台服务器中不可能只存在业务的那几个线程。
操作系统提供了通用的调度能力，在某些特殊场景中，我们比操作系统更了解我们的线程该如何在多个CPU核之间进行分配。例如，在数据库系统中，为保证高优先级线程得到快速处理（比如，事务操作）、避免被其他线程中断（分片时间到）或者被迁移到其他CPU核（导致CPU Cache失效），会将相关线程与部分CPU核绑定，只留剩余的CPU核参与通用调度分配。

操作系统内核对CPU的绝对掌控

在详谈操作系统内核对线程调度之前，还想提一下最前置的问题，即操作系统能否获得调度的权利，会不会出现CPU核被应用程序长期占用的情形。在文章（操作系统知识之内核与进程学习总结）有提到，操作系统内核会借助硬件定时器的帮助，重新获得对CPU的控制权，然后按照一系列复杂的调度规则去决定是继续当前线程的执行还是切换到其他线程（可能是其他进程的）。

我这里也写了一个程序，同时开启8个线程，每个线程执行一个死循环的计算逻辑。我的笔记本的CPU型号是：2 GHz 四核Intel Core i7，1个CPU，4个核，因开启了超线程技术，可同时供8个线程并发执行。程序开启后，通过Top命令观看，这个程序的CPU使用率长时间维持在700%左右，我仍然能正常写文章、浏览网页，没有受到丝毫影响。

#include <iostream>#include <thread>
void infinite_loop(){    int i = 0;    for (;;){        ++i;    }}
// 我的笔记本的CPU型号是：2 GHz 四核Intel Core i7，1个CPU，4个核，因开启了超线程技术，可同时供8个线程并发执行std::unique_ptr<std::thread> thread_array [8];
int main(){    for(int i = 0; i < 8; ++i)    {        thread_array[i] = std::make_unique<std::thread>(infinite_loop);    }    for(int i = 0; i < 8; ++i)    {        thread_array[i]->join();    }}

通用调度算法

这里说明一下，操作系统内核调度的对象的确是线程（包括Golang语言，对开发者展现的是协程，操作系统内核的调度对象仍然是线程），但是在讲解调度算法的时候，若仍然用“线程”，在某些场景会出现一些字面意思的冲突（和线程实际的执行行为），并且调度算法具有普适性，故这里做一层抽象，改用“任务（Job）”来阐述调度算法。在资源一定的情况下，调度算法需要在吞吐量（Throughput）、平均响应时间（延迟，Average Response Time）、公平性、调度引起的额外开销（Overhead）等几个方面做权衡。

1、先进先出算法（FIFO，First-In-First-Out）

按照任务进入队列的顺序，依次调用，执行完一个任务再执行下一个任务，只有当任务结束后才会发生切换。

优点：

最少的任务切换开销（因为没有在任务执行过程中发生切换，故任务切换开销为0）
最大的吞吐量（因没有任务切换开销，在其他一定的情况下，吞吐量肯定是最大的）
最朴实的公平性（先来先做）

缺点：

平均响应时间高：耗时只需10毫秒的任务若恰巧在耗时1000毫秒的任务后到来，他则需要1010毫秒才能执行完成，绝大部分时间都花在等待被调度了。

适用场景：队列中任务的耗时差不多的场景。

2、最短耗时任务优先算法（Shortest Job First， SJF）

按照任务的耗时长短进行调度，优先调度耗时短的任务，这个算法有个前提，需要预先知道每个任务的耗时情况，这在实际情况中是不大现实的。另外，这个时间是指任务剩余还需要的执行时间，举例，一个耗时1小时的任务还剩10秒执行完成，这个时候若再来一个耗时1分钟的任务，调度仍然还是继续执行完那个耗时1小时的任务，因为他剩余的时间是10秒，比1分钟短，所以此算法又叫最短剩余时间任务有限算法（SRTJ），能够解决FIFO算法中短耗时任务等待前面耗时长任务的窘境。

优点：

平均响应时间较低：这里有一点，因为将时间长的任务无限往后推移，实际计算的平均响应时间的任务都是执行较快的任务，统计出来的平均响应时间必然较低的。

缺点：

耗时长的任务迟迟得不到调度，不公平，容易形成饥饿
频繁的任务切换，调度的额外开销大

适用场景：几乎无适用场景。

3、时间片轮转算法（Round Robin）

给队列中的每个任务一个时间片，第一个任务先执行，时间片到了之后，将此任务放到队列尾部，切换到下个任务执行，这样能解决SJF中耗时长任务饥饿的问题。算法介于FIFO和SJF之间，若时间片足够大，则退化到FIFO，若分片足够小（假设不考虑任务切换的开销），则任务的完成时间顺序是以耗时从小到大排列（相比SFJ，任务执行的绝对时间会长，取决于队列中任务的个数）。

优点：

每个任务都能够得到公平的调度
耗时短的任务即使落在耗时长的任务后面，也能够较快的得到调度执行

缺点：

任务切换引起的调度开销较大，需要多次切换任务上下文（特别是CPU的Cache，多次切换容易导致Cache完全不命中，需要重新从内存加载，这个非常耗时）
时间片不太好设置（若设置短了，调度开销大，若设置长了，极端情况是退化到FIFO）

适用场景：队列中耗时差不多的任务（比如，多路视频流处理）

不适用场景：计算型任务和I/O型任务混合的队列

4、最大最小公平算法（ Max-Min Fairness ）

顾名思义，此算法是为了保证公平性，最初源自通信网络的带宽分配与控制场景。场景举例，某一资源容量为10，现有4个使用方需要使用（A、B、C、D），要求的资源数分别是2、2.6、4、5，需要经过多轮计算:

第一轮分配，4个使用方（A、B、C、D）参与分配，每个平均分得2.5个资源，A只需要使用2，还剩0.5， B、C、D在本轮都不够用，只好被推迟。
第二轮分配，3个使用方（B、C、D）参与分配，分别可获得2.5 + 0.5/3 = 2.6666, B只需要要2.6，则还剩0.06666，可给剩余2个分配，C、D在本来都不够用，只好被推迟。
第三轮分配，2个使用方（C、D）参与分配，分别获得2.5+ 0.5/3 + 0.06666/2 = 2.699999 ， C和D分别获得2.6999。（后面若还有新的资源，则可以分配给C和D，以便能满足他们的诉求）

总结来说，先平均分配，若多的话，再将剩余的给其他人再次平均分配，若不够的话，需要等待。为了体现重要性，在此基础上引入了带权重的最大最小公平算法，场景举例，某一资源容量为16，给A、B、C、D分别设置权重为5、8、1、2（权重的最小粒度为1，数值越大，权重越高），要求的资源数量分别是4、2、10、4，需要经过多轮计算：

第一轮分配，分配给A、B、C、D的资源分别是5、8、1、2， A剩余1个资源，B剩余6个资源，C、D因资源不够用，处理延期。
第二轮分配，在A和B剩余的总共7个资源中，根据C、D的权重，分别获得7 * 1 / 3、 7 * 2 / 3 个，加上第一轮分配的数量，C、D分别拥有1 + 7 / 3 、2 + 14 / 3 ，C仍然不能满足，D能够满足，D用完之后还剩2 + 14 / 3 - 4 = 2.6666，这个可以给C用。
第三轮分配，C目前拥有1+7/3 + 2.66666 = 6,仍然不够，处理延期 (后面若还有新的资源，则可以分配给C，以便能满足他的诉求)。

5、Multi-level Feedback Queue（MFQ）

此算法兼顾响应时间（ Responsiveness ）、低调度开销（Schedule overload）、饥饿避免（Starvation-Freedom）、公平（Fairness），在Windows，MacOS，Linux内核调度系统中都有使用。算法内容：

有多个Level，从上到下，优先级越来越低，分片时长越来越大。
位于高优先级Level的任务可以抢占低优先级Level的任务。
新任务首先位于高优先级Level，当一个时间片用完之后，若任务结束，则正常退出系统，若任务还没有结束，则下滑到低一等级的Level，若是因等待I/O而主动让出CPU处理，则停留在当前Level（或者提高一个Level）。
同一Level的任务采用Round Robin算法。
为避免系统中有太多的I/O任务而导致计算型任务迟迟得不到处理，MFQ算法会监控每个任务的处理耗时、确保其拥有公平的资源分配（按照最大最小公平算法）。在每个Level的所有任务，若有任务还没有用完分配给他的资源，则相应提高他的优先级，反之则降低其优先级。

6、多CPU核场景下MFQ算法的考虑

在多CPU核的场景下，若共用一个MFQ，则会出现：

随着CPU核数目不断增长，对MFQ锁的争抢会越来越严重。
因MFQ的最新状态都是存在上次执行的CPU核的Cache，当前CPU核需要从远端CPU核的Cache去拉取最新数据、然后存到Local Cache，这个行为会很耗时。

为解决上述问题，会为每个CPU核分配一个MFQ，同时采用Affinity Scheduling策略，保证同一线程的执行尽量落在同一CPU核（挂起中断后重新执行）。若出现某些CPU核特别繁忙，会进行Rebalancing操作，将部分线程迁移到其他空闲的CPU核执行。线程在同一个CPU核处理可以最大化利用CPU Cache，避免频繁的从内存加载数据到CPU Cache。Golang语言处理多个协程并发的时候，也会尽量保证相关的协程由同一个底层线程进行处理，也是基于重用CPU Cache的考虑。

操作系统内核层面的考量

上面讲了具体的调度算法，调度粒度是任务（Job），可以映射成线程。那操作系统是不是就是按照上述调度算法对系统中所有的线程进行统一调度呢？篇首也提到了，实际调度过程中会考虑进程的因素，即同一进程中的线程。有两个策略会将进程因素考虑进去：

Gang Scheduling：尽量将同一进程中的线程同时调度，而不是随机从多个进程挑选内核数目的线程进行调度。

Space Sharing：将CPU核进行划分，若同时有多个进程运行，只让某个进程占用部分CPU核来进行并发，而不是在某一时间分片内所有CPU核被同一个进程的线程占满。

总结

操作系统内核的调度系统非常复杂，综合了各种算法、策略和Tradeoff，上面的总结只是一些皮毛，后面再不断增加！

继续滑动看下一个