Linux进程调度的逻辑是什么

这篇文章主要介绍“Linux进程调度的逻辑是什么”，在日常操作中，相信很多人在Linux进程调度的逻辑是什么问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”Linux进程调度的逻辑是什么”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！内核在选择进程进行调度的时候，会首先判断当前 CPU 上是否有进程可以调度，如果没有，执行进程迁移逻辑，从其他 CPU 迁移进程，如果有，则选择虚拟时间较小的进程进行调度。内核在选择逻辑 CPU 进行迁移进程的时候，为了提升被迁移进程的性能，即避免迁移之后 L1 L2 L3 高速缓存失效，尽可能迁移那些和当前逻辑 CPU 共享高速缓存的目标逻辑 CPU，离当前逻辑 CPU 越近越好。内核将进程抽象为调度实体，为的是可以将一批进程进行统一调度，在每一个调度层次上，都保证公平。所谓选中高优进程，实际上选中的是虚拟时间较小的进程，进程的虚拟时间是根据进程的实际优先级和进程的运行时间等信息动态计算出来的。进程上下文切换，核心要切换的是虚拟内存及一些通用寄存器。进程切换虚拟内存，需要切换对应的 TLB 中的 ASID 及页表，页表也即不同进程的虚拟内存翻译需要的 “map”。进程的数据结构中，有一个间接字段 cpu_context 保存了通用寄存器的值，寄存器切换的本质就是将上一个进程的寄存器保存到 cpu_context 字段，然后再将下一个进程的 cpu_context 数据结构中的字段加载到寄存器中，至此完成进程的切换。学过操作系统的同学应该都知道，进程调度分为如下两个步骤：根据某种算法从就绪队列中选中一个进程。执行进程上下文切换。其中第二个步骤又可以分为：切换虚拟内存。切换寄存器，即保存上一个进程的寄存器到进程的数据结构中，加载下一个进程的数据结构到寄存器中。关于虚拟开发云主机域名内存相关的逻辑，后续文章会详细剖析，这篇文章会简要概括。这篇文章，我们从内核源码的角度来剖析 Linux 是如何来实现进程调度的核心逻辑，基本上遵从操作系统理论。Linux 进程调度的主函数是 schedule() 和开发云主机域名 __schedule()，从源码中可以看出两者的关系：当一个进程主动让出 CPU，比如 yield 系统调用，会执行 schedule() 方法，在执行进程调度的过程中，禁止其他进程抢占当前进程，说白了就是让当前进程好好完成这一次进程切换，不要剥夺它的 CPU；3529 行代码表示 schedule() 调用了 __schedule(false) 方法，传递 fasle 参数，表示这是进程的一次主动调度，不可抢占。等当前的进程执行完调度逻辑之后，开启抢占，也就是说，其他进程可以剥夺当前进程的 CPU 了。而如果某个进程像个强盗一样一直占着 CPU 不让，内核会通过抢占机制（比如上一篇文章提到的周期调度机制）进行一次进程调度，从而把当前进程从 CPU 上踢出去。__schedule() 方法的框架便是这篇文章分析的主要内容，由于代码较多，我会挑选核心部分来描述。我们先来看看 Linux 内核中，进程调度核心函数 __schedule() 的框架：可以看到，__schedule() 方法中，进程切换的核心步骤和操作系统理论中是一致的（1 和 2 两个核心步骤）。此外，进程切换的过程中，内核会根据是主动发起调度（preempt 为 fasle）还是被动发起调度，来统计进程上下文切换的次数，分别保存在进程的数据结构 task_struct 中：在 Linux 中，我们可以通过 pidstat 命令来查看一个进程的主动和被动上下文切换的次数，我们写一个简单的 c 程序来做个测试：然后编译运行通过 pidstat 来查看可以看到，test 应用程序每秒主动切换一次进程上下文，和我们的预期相符，对应的上下文切换数据就是从 task_struct 中获取的。接下来，详细分析进程调度的两个核心步骤:通过 pick_next_task() 从就绪队列中选中一个进程。通过 context_switch 执行上下文切换。我们回顾一下 pick_next_task() 在 __schedule() 方法中的位置跟着调用链往下探索：从 pick_next_task() 方法的注释上也能看到，这个方法的目的就是找出优先级最高的进程，由于系统中大多数进程的调度类型都是公平调度，我们拿公平调度相关的逻辑来分析。从上述的核心框架中可以看到，3331 行先尝试从公平调度类型的队列中获取进程，3337 行，如果没有找到，就把每个 CPU 上的 IDLE 进程取出来运行：接下来，我们聚焦公平调度类的进程选中算法 fair_sched_class.pick_next_task()pick_next_task_fair() 的逻辑相对还是比较复杂的，但是，其中的核心思想分为两步：如果开发云主机域名当前 CPU 上已无进程可调度，则执行负载逻辑，从其他 CPU 上迁移进程过来；如果当前 CPU 上有进程可调度，从队列中选择一个高优进程，所谓高优进程，即虚拟时间最小的进程；下面，我们分两步拆解上述步骤。内核为了让各 CPU 负载能够均衡，在某些 CPU 较为空闲的时候，会从繁忙的 CPU 上迁移进程到空闲 CPU 上运行，当然，如果进程设置了 CPU 的亲和性，即进程只能在某些 CPU 上运行，则此进程无法迁移。负载均衡的核心逻辑是 idle_balance 方法：idle_balance() 方法的逻辑也相对比较复杂：但是大体上概括就是，遍历当前 CPU 的所有调度域，直到迁移出进程位置。这里涉及到一个核心概念：sched_domain，即调度域，下面用一张图介绍一下什么是调度域。内核根据处理器与主存的距离将处理器分为两个 NUMA 节点，每个节点有两个处理器。NUMA 指的是非一致性访问，每个 NUMA 节点中的处理器访问内存节点的速度不一致，不同 NUMA 节点之间不共享 L1 L2 L3 Cache。每个 NUMA 节点下有两个处理器，同一个 NUMA 下的不同处理器共享 L3 Cache。每个处理器下有两个 CPU 核，同个处理器下的不同核共享 L2 L3 Cache。每个核下面有两个超线程，同一个核的不同超线程共享 L1 L2 L3 Cache。我们在应用程序里面，通过系统 API 拿到的都是超线程，也可以叫做逻辑 CPU，下文统称逻辑 CPU。进程在访问一个某个地址的数据的时候，会先在 L1 Cache 中找，若未找到，则在 L2 Cache 中找，再未找到，则在 L3 Cache 上找，最后都没找到，就访问主存，而访问速度方面 L1 > L2 > L3 > 主存，内核迁移进程的目标是尽可能让迁移出来的进程能够命中缓存。内核按照上图中被虚线框起来的部分，抽象出调度域的概念，越靠近上层，调度域的范围越大，缓存失效的概率越大，因此，迁移进程的一个目标是，尽可能在低级别的调度域中获取可迁移的进程。上述代码 idle_balance() 方法的 9897 行：for_each_domain(this_cpu, sd)，this_cpu 就是逻辑 CPU（也即是最底层的超线程概念），sd 是调度域，这行代码的逻辑就是逐层往上扩大调度域；而 idle_balance() 方法的 9812 行，如果在某个调度域中，成功迁移出了进程到当前逻辑 CPU，就终止循环，可见，内核为了提升应用性能真是煞费苦心。经过负载均衡之后，当前空闲的逻辑 CPU 进程队列很有可能已经存在就绪进程了，于是，接下来从这个队列中获取最合适的进程。接下来，我们把重点放到如何选择高优进程，而在公平调度类中，会通过进程的实际优先级和运行时间，来计算一个虚拟时间，虚拟时间越少，被选中的概率越高，所以叫做公平调度。以下是选择高优进程的核心逻辑：内核提供一个调度实体的的概念，对应数据结构叫 sched_entity，内核实际上是根据调度实体为单位进行调度的：每一个进程对应一个调度实体，若干调度实体绑定到一起可以形成一个更高层次的调度实体，因此有个递归的效应，上述 do while 循环的逻辑就是从当前逻辑 CPU 顶层的公平调度实体（cfs_rq->curr）开始，逐层选择虚拟时间较少的调度实体进行调度，直到最后一个调度实体是进程。内核这样做的原因是希望尽可能在每个层次上，都能够保证调度是公平的。拿 Docker 容器的例子来说，一个 Docker 容器中运行了若干个进程，这些进程属于同一个调度实体，和宿主机上的进程的调度实体属于同一层级，所以，如果 Docker 容器中疯狂 fork 进程，内核会计算这些进程的虚拟时间总和来和宿主机其他进程进行公平抉择，这些进程休想一直霸占着 CPU！选择虚拟时间最少的进程的逻辑是 se = pick_next_entity(cfs_rq, curr); ，相应逻辑如下：上述代码，我们可以分析出，pick_next_entity() 方法会在当前公平调度队列 cfs_rq 中选择最靠左的调度实体，最靠左的调度实体的虚拟时间越小，即最优。而下面通过 __pick_first_entity() 方法，我们了解到，公平调度队列 cfs_rq 中的调度实体被组织为一棵红黑树，这棵树的最左侧节点即为最小节点：通过以上分析，我们依然通过一个 Docker 的例子来分析： 一个宿主机中有两个普通进程分别为 A，B，一个 Docker 容器，容器中有 c1、c2、c3 进程。这种情况下，系统中有两个层次的调度实体，最高层为 A、B、c1+c2+c3，再往下为 c1、c2、c3，下面我们分情况来讨论进程选中的逻辑：1）若虚拟时间分布为：A:100s，B:200s，c1:50s，c2:100s，c3:80s选中逻辑：先比较 A、B、c1+c2+c3 的虚拟时间，发现 A 最小，由于 A 已经是进程，选中 A，如果 A 比当前运行进程虚拟时间还小，下一个运行的进程就是 A，否则保持当前进程不变。2）若虚拟时间分布为：A:100s，B:200s，c1:50s，c2:30s，c3:10s选中逻辑：先比较 A、B、c1+c2+c3 的虚拟时间，发现 c1+c2+c3 最小，由于选中的调度实体非进程，而是一组进程，继续往下一层调度实体进行选择，比较 c1、c2、c3 的虚拟时间，发现 c3 的虚拟时间最小，如果 c3 的虚拟时间小于当前进程的虚拟时间，下一个运行的进程就是 c3，否则保持当前进程不变。到这里，选中高优进程进行调度的逻辑就结束了，我们来做下小结。内核在选择进程进行调度的时候，会先判断当前 CPU 上是否有进程可以调度，如果没有，执行进程迁移逻辑，从其他 CPU 迁移进程，如果有，则选择虚拟时间较小的进程进行调度。内核在选择逻辑 CPU 进行迁移进程的时候，为了提升被迁移进程的性能，即避免迁移之后 L1 L2 L3 高速缓存失效，尽可能迁移那些和当前逻辑 CPU 共享高速缓存的目标逻辑 CPU，离当前逻辑 CPU 越近越好。内核将进程抽象为调度实体，为的是可以将一批进程进行统一调度，在每一个调度层次上，都保证公平。所谓选中高优进程，实际上选中的是虚拟时间较小的进程，进程的虚拟时间是根据进程的实际优先级和进程的运行时间等信息动态计算出来的。选中一个合适的进程之后，接下来就要执行实际的进程切换了，我们把目光重新聚焦到 __schedule() 方法其中，进程上下文切换的核心逻辑就是 context_switch，对应逻辑如下：上述代码，我略去了一些细节，保留我们关心的核心逻辑。context_switch() 核心逻辑分为两个步骤，切换虚拟内存和寄存器状态，下面，我们展开这两段逻辑。首先，简要介绍一下虚拟内存的几个知识点：进程无法直接访问到物理内存，而是通过虚拟内存到物理内存的映射机制间接访问到物理内存的。每个进程都有自己独立的虚拟内存地址空间。如，进程 A 可以有一个虚拟地址 0x1234 映射到物理地址 0x4567，进程 B 也可以有一个虚拟地址 0x1234 映射到 0x3456，即不同进程可以有相同的虚拟地址。如果他们指向的物理内存相同，则两个进程即可通过内存共享进程通信。进程通过多级页表机制来执行虚拟内存到物理内存的映射，如果我们简单地把这个机制当做一个 map 数据结构的话，那么可以理解为不同的进程有维护着不同的 map；map 的翻译是通过多级页表来实现的，访问多级页表需要多次访问内存，效率太差，因此，内核使用 TLB 缓存频繁被访问的 的项目，感谢局部性原理。由于不同进程可以有相同的虚拟地址，这些虚拟地址往往指向了不同的物理地址，因此，TLB 实际上是通过 的方式来唯一确定某个进程的物理地址的，ASID 叫做地址空间 ID（Address Space ID），每个进程唯一，等价于多租户概念中的租户 ID。进程的虚拟地址空间用数据结构 mm_struct 来描述，进程数据结构 task_struct 中的 mm 字段就指向此数据结构，而上述所说的进程的 “map” 的信息就藏在 mm_struct 中。关于虚拟内存的介绍，后续的文章会继续分析，这里，我们只需要了解上述几个知识点即可，我们进入到切换虚拟内存核心逻辑：接下来，调用 check_and_switch_context 做实际的虚拟内存切换操作：check_and_switch_context 总体上分为两块逻辑：将下一个进程的 ASID 绑定到当前的 CPU，这样 TLB 通过虚拟地址翻译出来的物理地址，就属于下个进程的。拿到下一个进程的 “map”，也就是页表，对应的字段是 “mm->pgd”，然后执行页表切换逻辑，这样后续如果 TLB 没命中，当前 CPU 就能够知道通过哪个 “map” 来翻译虚拟地址。cpu_switch_mm 涉及的汇编代码较多，这里就不贴了，本质上就是将 ASID 和页表（”map”）的信息绑定到对应的寄存器。虚拟内存切换完毕之后，接下来切换进程执行相关的通用寄存器，对应逻辑为 switch_to(prev, next …); 方法，这个方法也是切换进程的分水岭，调用完之后的那一刻，当前 CPU 上执行就是 next 的代码了。拿 arm64 为例：cpu_switch_to 对应的是一段经典的汇编逻辑，看着很多，其实并不难理解。上述汇编的逻辑可以和操作系统理论课里的内容一一对应，即先将通用寄存器的内容保存到进程的数据结构中对应的字段，然后再从下一个进程的数据结构中对应的字段加载到通用寄存器中。1041 行代码是拿到 task_struct 结构中的 thread_struct thread 字段的 cpu_contxt 字段：我们来分析一下对应的数据结构：而 cpu_context 数据结构的设计就是为了保存与进程有关的一些通用寄存器的值：这些值刚好与上述汇编片段的代码一一对应上，读者应该不需要太多汇编基础就可以分析出来。上述汇编中，最后一行 msr sp_el0, x1，x1 寄存器中保存了 next 的指针，这样后续再调用 current 宏的时候，就指向了下一个指针：进程上下文切换的核心逻辑到这里就结束了，最后我们做下小结。进程上下文切换，核心要切换的是虚拟内存及一些通用寄存器。进程切换虚拟内存，需要切换对应的 TLB 中的 ASID 及页表，页表也即不同进程的虚拟内存翻译需要的 “map”。进程的数据结构中，有一个间接字段 cpu_context 保存了通用寄存器的值，寄存器切换的本质就是将上一个进程的寄存器保存到 cpu_context 字段，然后再将下一个进程的 cpu_context 数据结构中的字段加载到寄存器中，至此完成进程的切换。到此，关于“Linux进程调度的逻辑是什么”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注开发云网站，小编会继续努力为大家带来更多实用的文章！

相关推荐: 选择微软大数据解决方案处理网站大数据的优势有哪些

这篇文章主要介绍“选择微软大数据解决方案处理网站大数据的优势有哪些”，在日常操作中，相信很多人在选择微软大数据解决方案处理网站大数据的优势有哪些问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”选择微软大数据解决方案处理网站大数据的…