线程的调度算法

发布时间：2022-09-21 15:04:23 所属栏目：Unix 来源：

导读：　　文章目录

　　一、前言

　　在业务应用开发中，若涉及线程相关，一般会将线程数目设置为CPU的逻辑核数以便最大限度利用CPU。操作系统提供了通用的调度能力，但是在某些特殊场景中需要特殊处理。例如，在

　　文章目录

　　一、前言

　　在业务应用开发中，若涉及线程相关，一般会将线程数目设置为CPU的逻辑核数以便最大限度利用CPU。操作系统提供了通用的调度能力，但是在某些特殊场景中需要特殊处理。例如，在数据库系统中，为保证高优先级线程得到快速处理（比如，事务操作）、避免被其他线程中断（分片时间到）或者被迁移到其他CPU核（导致CPU cache失效），会将相关线程与部分CPU核绑定，只留剩余的CPU核参与通用调度分配。

　　二、调度算法

　　操作系统内核调度的对象的确是线程，但是在讲解调度算法的时候，若仍然用“线程”，在某些场景会出现一些字面意思的冲突（和线程实际的执行行为），并且调度算法具有普适性，故这里做一层抽象，改用“任务（Job）”来阐述调度算法。

　　在资源一定的情况下，调度算法需要在吞吐量（Throughput）、平均响应时间（延迟，Average Response Time）、公平性、调度引起的额外开销（Overhead）等几个方面做权衡。

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

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

　　最少的任务切换开销（因为没有在任务执行过程中发生切换，故任务切换开销为0）

　　最大的吞吐量（因没有任务切换开销，在其他一定的情况下，吞吐量肯定是最大的）

　　最朴实的公平性（先来先做）

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

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

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

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

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

　　耗时长的任务迟迟得不到调度，不公平，容易形成饥饿

　　频繁的任务切换，调度的额外开销大

　　几乎无适用场景。

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

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

　　每个任务都能够得到公平的调度

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

　　任务切换引起的调度开销较大，需要多次切换任务上下文（特别是CPU的Cache，多次切换容易导致Cache完全不命中，需要重新从内存加载，这个非常耗时）

　　时间片不好设置（若设置短了，调度开销大，若设置长了，极端情况是退化到FIFO）

　　队列中是耗时差不多的任务（比如，多路视频流处理）

　　计算型任务和I/O型任务混合的队列

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

　　顾名思义，此算法是为了保证公平性，最初源自通信网络的带宽分配与控制场景。基本思路是先平均分配，若多的话，再将剩余的给其他人再次平均分配，若不够的话，需要等待。

　　场景举例，某一资源容量为10，现有4个使用方需要使用（A、B、C、D），要求的资源数分别是2、2.6、4、5，需要经过多轮计算:

　　为了体现重要性，在此基础上引入了带权重的最大最小公平算法。

　　场景举例，某一资源容量为16，给A、B、C、D分别设置权重为5、8、1、2（权重的最小粒度为1，数值越大，权重越高），要求的资源数量分别是4、2、10、4，需要经过多轮计算：

　　5.Multi-level Feedback Queue（MFQ）

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

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

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

　　为解决上述问题，会为每个CPU核分配一个MFQ，同时采用Affinity Scheduling策略，保证同一线程的执行尽量落在同一CPU核（挂起中断后重新执行）。

　　若出现某些CPU核特别繁忙，会进行Rebalancing操作，将部分线程迁移到其他空闲的CPU核执行。线程在同一个CPU核处理可以最大化利用CPU Cache，避免频繁的从内存加载数据到CPU Cache。Golang语言处理多个协程并发的时候，也会尽量保证相关的协程由同一个底层线程进行处理，也是基于重用CPU Cache的因素。

（编辑：我爱资讯网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!