Matrix

原图 内存管理发展史 内存管理的“远古时代” 在分页机制出现之前，操作系统有很多不同的内存管理机制，如动态分区法。如图（a）所示。剩余的 4MB 内存不足以装载进程 D，如图（b）所示，因为进程 D 需要 5MB 内存，这个内存末尾就成了第一个空洞（内存碎片）。假设某个时刻，操作系统需要运行进程 D，因为系统中没有足够的内存，所以需要选择一个进程来换出，为进程 D 腾出足够的空间。假设操作系统选择进程 B 来换出，这样进程 D 就装载到了原来进程 B 的地址空间里，于是产生了第二个空洞，如图（c）所示。假设操作系统某个时刻需要运行进程 B，也需要选择一个进程来换出，假设进程 A 被换出，那么操作系统中又产生了第三个空洞，如图（d）所示。 这种动态分区法在开始时是很好的，但是随着时间的推移会出现很多内存空洞，内存的利用率随之下降，这些内存空洞便是我们常说的内存碎片，动态分区法依然存在以下问题。 进程地址空间保护问题。所有的进程都可以访问全部的物理内存，所以恶意的程序可以修改其他程序的内存数据，这使进程一直处于危险的状态下。 内存使用效率低。如果即将运行的进程所需要的内存空间不足， ...

原图 arm64 内存管理 如图所示，ARM 处理器内核的 MMU 包括 TLB 和页表遍历单元（Table Walk Unit）两个部件。TLB 是一个高速缓存。一个完整的页表翻译和查找的过程叫作页表查询，页表查询的过程由硬件自动完成，但是页表的维护需要软件来完成。 下图为进程地址空间和物理地址空间的映射关系，左边是进程地址空间视图，右边是物理地址空间视图。进程地址空间又分成内核空间（Kermel Space）和用户空间（User Space）。无论是内核空间还是用户空间都可以通过处理器提供的页表机制映射到实际的物理地址。 页表 在 AArch64 架构中的 MMU 支持单一阶段的页表转换，同样也支持虚拟化扩展中两阶段的页表转换。 单一阶段的页表转换，把虑虚拟地址（VA）翻译成物理地址（PA）。 两阶段的页表转换：包括两个阶段。在阶段 1，把虚拟地址翻译成中间物 （Intermediate Phvsical Address，IPA）；在阶段 2，把 IPA 翻译成最终 PA 另外，ARMv8 架构支持多种页表格式。具体如下。 ARMv8 架构的长描述符页表格式（Long ...

原图 声明： 本文转载自 Cache 的基本原理 和 Cache 组织方式 多级 cache 存储结构 我们在 L1 cache 后面连接 L2 cache，在 L2 cache 和主存之间连接 L3 cache。等级越高，速度越慢，容量越大。不同等级 cache 速度之间关系如下： 经过 3 级 cache 的缓冲，各级 cache 和主存之间的速度最萌差也逐级减小。在一个真实的系统上，各级 cache 之间硬件上是如何关联的呢？我们看下 Cortex-A53 架构上各级 cache 之间的硬件抽象框图如下： 在 Cortex-A53 架构上，L1 cache 分为单独的 instruction cache（ICache）和 data cache（DCache）。L1 cache 是 CPU 私有的，每个 CPU 都有一个 L1 cache。一个 cluster 内的所有 CPU 共享一个 L2 cache，L2 cache 不区分指令和数据，都可以缓存。所有 cluster 之间共享 L3 cache。L3 cache 通过总线和主存相连。 多级 cache 之间的配合 ...

原图 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 所有必须保存下来的寄存器信息，以便当前进程 ...