Matrix

原图 O（n）调度器 如何组织 task 调度器模块定义了一个 runqueue_head 的链表头变量，无论进程是普通进程还是实时进程，只要进程状态变成可运行状态的时候，它会被挂入这个全局 runqueue 链表中。由于整个系统中的所有 CPU 共享一个 runqueue，为了解决同步问题，调度器模块定义了一个自旋锁来保护对这个全局 runqueue 的并发访问。 除了这个 runqueue 队列，系统还有一个囊括所有 task（不管其进程状态为何）的链表，链表头定义为 init_task，在一个调度周期结束后，重新为 task 赋初始时间片值的时候会用到该链表。 动态优先级 对于普通进程，计算动态优先级的策略如下： 如果该进程的时间片已经耗尽，那么动态优先级是 0，这也意味着在本次调度周期中该进程已经再也没有机会获取 CPU 资源了。 如果该进程的时间片还有剩余，那么其动态优先级等于该进程剩余的时间片和静态优先级之和。之所以用（20-nice value）表示静态优先级，主要是为了让静态优先级变成单调上升。之所以要考虑剩余时间片是为了奖励睡眠的进程，因为睡眠的进程剩余的时间片 ...

原图 一个例子 下面给出一个综合案例，在一个双核处理器的系统中，在 Shell 界面下运行 test 程序。CPUO 的就绪队列中有 4 个进程，而 CPU1 的就绪缓队列中有 1 个进程。test 程序和这 5 个进程的 nice 值都为 0。 123456789#include <stdio.h>int main(){ unsigned long i = O while(1){ i++; }; return O;} 站在用户空间的角度看问题，我们只能看到 test 程序被运行了，但是我们看不到新进程是如何创建的、它会添加到哪个 CPU 里、它是如何运行的，以及 CPU0 和 CPU1 之间如何做负载均衡等。 其中的操作步骤如下： 调用系统调用 fork() 来创建一个新进程 使用 do_fork() 创建新进程： 创建新进程的 task_struct 数据结构 复制父进程的 task_struct 数据结构到新进程 复制父进程相关的页表项到新进程 设置新进程的内核栈 父进程调用 wake_up_new_task() 尝试 ...

原图 概述 Linux 内核为开发者提供了丰富的进程调度信息，这些调度信息都需要在内核配置时打开 CONFIG_SCHED_DEBUG 选项。 查看与进程相关的调度信息 有时候我们需要查看进程相关的调度信息，如进程的 nice 值、优先级、调度策略、vruntime 及量化计算能力等信息。在 Linux 的 proc 目录中，为每个进程提供一个独立的目录，该目录包含了与进程相关的信息，执行如下命令： 1vooxle@liushuai:~# cat /proc/1/sched 得到： 123456789101112131415161718192021222324252627282930systemd (1, #threads: 1)-------------------------------------------------------------------se.exec_start : 5438471989.820758se.vruntime ...

原图 概述 SMP（Symmetrical MultiProcessing）的全称是“对称多处理”技术，是指在一台计算机上汇集了一组处理器，这些处理器都是对等的，它们之间共享内存子系统和系统总线。 下图所示为 4 核的 SMP 处理器架构，在 4 核处理器中，每个物理 CPU 核心拥有独立的 L1 缓存且不支持超线程技术，分成两个簇（cluster）簇 0 和簇 1，每个簇包含两个物理 CPU 核，簇中的 CPU 核共享 L2 缓存。 调度域和调度组 根据处理器的实际物理属性，CPU 和 Linux 内核的分类如下所示。 SMT（超线程）： Linux 内核配置项 CONFIG_SCHED_SMT 一个物理核心可以有两个或更多执行线程，被称为超线程技术。超线程使用相同的 cpu 资源且共享 L1 缓存，迁移进程不会影响高速缓存的利用率 MC（多核）： Linux 内核配置项 CONFIG_SCHED_MC 每个物理核心独享 L1 高速缓存，多个物理核心可以组成族，族里的 cpu 共享 L2 高速缓存 SOC（处理器）： 内核称为 DIE SOC 级别 Linux 内核使用数据 ...

原图 公平调度思想的引入 传统调度器时间片悖论 在 O（n）和 O（1）调度器中，时间片是固定分配的，静态优先级高的进程获取更大的 time slice。高优先级的进程会获得更多的连续执行的机会，这是 CPU-bound 进程期望的，但是实际上，CPU-bound 进程往往在后台执行，其优先级都是比较低的。 RSDL 调度器 RSDL 调度器仍然沿用了 O（1）调度的数据结构和软件结构，当然删除了那些令人毛骨悚然的评估进程交互指数的代码。我们这一小节不可能详细描述 RSDL 算法，不过只讲清楚 Rotating、Staircase 和 Deadline 这三个基本概念。 首先看 Staircase 概念，它更详细表述应该是 priority staircase，即在进程调度过程中，其优先级会像下楼梯那样一点点的降低。在传统的调度概念中，一个进程有一个和其静态优先级相匹配的时间片，在 RSDL 中，同样也存在这样的时间片，但是时间片是散布在很多优先级中。例如如果一个进程的优先级是 120，那么整个时间片散布在 120～139 的优先级中，在一个调度周期，进程开始是挂入 120 的优先 ...

原图 概述 最新版本的 POSIX 标准中定义了进程创建和终止的操作系统层面的原语。进程创建包括 fork() 和 execve() 函数族，进程终止包括 wait()、waitpid()、kill() 以及 exit() 函数族。Linux 在实现过程中为了提高效率，把 POSIX 标准的 fork 原语扩展成了 vfork 和 clone 两个原语。 我们最常见的一种场景是在 shell 界面中输入命令，然后等待命令返回，如图所示： 用户空间如何创建进程 应用程序在用户空间创建进程有两种场景： 创建的子进程和父进程共用一个 elf 文件：这种情况适合于大多数的网络服务程序 创建的子进程需要加载自己的 elf 文件：例如 shell 应用程序可以通过 fork 系统调用创建进程，fork 之后，子进程复制了父进程的绝大部分的资源（文件描述符、信号处理、当前工作目录等）。完全复制父进程的资源的开销非常大且没有什么意义，特别是对于场景 2。不过，在引入 COW(copy-on-write) 技术后，fork 的开销其实也不算特别大，大部分的 copy 都是通过 share 完成 ...

原图 进程的概念 进程是处于执行期的程序以及相关的资源的总称。进程并不仅仅局限于一段可执行程序代码，通常进程还要包含其他资源，像数据段、打开的文件、挂起的信号、处理器状态、一个或多个具有内存映射的内存地址空间及一个或多个执行线程（thread of execution）等。 线程（thread），是在进程中活动的对象。每个线程都拥有一个独立的程序计数器、线程栈和一组进程寄存器，内核调度的对象是线程，而不是进程。 在现代操作系统中，进程提供两种虚拟机制：虚拟处理器和虚拟内存。 虚拟处理器给进程一种假象，让这些进程觉得自己在独享处理器 虚拟内存让进程在分配和管理内存时觉得自己拥有整个系统的所有内存资源 进程描述符 进程是操作系统中调度的实体，需要对进程所必须拥有的资源做抽象描述，这种对象描述称为进程控制块（Process Control Block，PCB）。进程控制块需要描述如下几类信息： 进程的运行状态：包括就绪、运行、阻塞、僵尸等状态 程序计数器：记录当前进程运行到哪条指令了 CPU 寄存器：主要保存当前运行的上下文，记录 CPU 所有必须保存下来的寄存器信息，以便当前进程 ...

原图 ARM64 架构介绍 ARMv8-A 架构介绍 ARMv8-A 是 ARM 公司发布的第一代支持 64 位处理器的指令集和架构。ARMv8-A 架构除了提高了处理能力外，还引入了很多吸引人的新特性。 具有 64 位宽的虚拟地址空间。 提供 31 个 64 位宽的通用寄存器，可以减少对栈的访问，从而提高性能。 提供 16KB 和 64KB 的 page，有助于降低 TLB 的未命中率（miss rate）。 具有全新的异常处理模型，有助于降低操作系统和虚拟化的实现复杂度。 具有全新的加载-获取、存储-释放指令（load-acquire，store-release instruction），专为 C++11 以及 Java 内存模型而设计。 ARM64 的基本概念 ARM 处理器实现的是精简指令集计算机（Reduced Instruction Set Computer，RISC）架构。本节介绍 ARMv8-A 架构中的一些基本概念。 处理单元： ARM 公司的官方技术手册中提到了一个概念，可以把处理器处理事务的过程抽象为处理单元（Processing Element，（PE ...

原图 概述 工作队列不完全是中断处理程序的下半部。内核的很多模块需要异步执行函数，这些模块也可以创建一个内核线程来异步执行函数。但是，如果每个模块都创建自己的内核线程，会造成内核线程的数量过多，内存消耗比较大，影响系统性能。所以，最好的方法是提供一种通用机制，让这些模块把需要异步执行的函数交给工作队列执行，共享内核线程，节省资源。 实现（扩展🙈） 首先介绍一下工作队列使用的术语。 work：工作，也称为工作项。 work_queue：工作队列，就是工作的集合，work_queue 和 work 是一对多的关系。 worker：工人，一个工人对应一个内核线程，我们把工人对应的内核线程称为工人线程。 worker_pool：工人池，就是工人的集合，工人池和工人是一对多的关系。 pool_workqueue：中介，负责建立工作队列和工人池之间的关系。工作队列和 pool_workqueue 是一对多的关系，pool_workqueue 和工人池是一对一的关系。 数据结构 工作队列分为两种。 绑定处理器的工作队列：默认创建绑定处理器的工作队列，每个工人线程绑定到一个处理器 不绑定 ...

原图 为什么有 tasklet linux kernel 已经把中断处理分成了 top half 和 bottom half，看起来已经不错了，那为何还要提供 softirq、tasklet 和 workqueue 这些 bottom half 机制。 workqueue 和 softirq、tasklet 有本质的区别： workqueue 运行在 process context，而 softirq 和 tasklet 运行在 interrupt context。因此，出现 workqueue 是不奇怪的，在有 sleep 需求的场景中需要。 softirq 更倾向于性能。软中断的种类是编译时静态定义的，在运行时不能添加或删除，同一种软中断的处理函数可以在多个处理器上同时执行，处理函数必须是可以重入的，需要使用锁保护临界区。 tasklet 更倾向于易用性。Tasklet 可以在运行时添加或删除，一个 Tasklet 同一时刻只能在一个处理器上执行，不要求处理函数是可以重入的。 数据结构 Tasklet 的数据结构如下： 12345678910111213<includ ...