本篇文章来自 https://www.xiaolincoding.com/os/ 阅读总结和归纳

CPU

CPU 执行程序

图灵机工作原理 = 读写头+控制器+存储器+运算器 (如果是读不需要运算器)

冯诺伊曼体系，CPU 读写内存时 「总线」交互的流程

• 首先通过「地址总线」来指定内存的地址
• 然后通过「控制总线」控制读或写命令
• 最后通过「数据总线」来传输数据

位宽分「线路位宽」和「CPU」位宽

• 线路位宽 = cpu 能寻址最大的内存地址
• 32 位 CPU 最大只能操作 4GB 内存，即使装 8 GB 内存条也没用
• 64 位 CPU 寻址范围理论最大为 2^64
• cpu 位宽 = cpu 能运算最大的数字长度

CPU 指令周期

• 控制单元将程序计数器通过「地址总线」发给内存
• 内存通过数据总线发回指令
• 指令存到寄存器，程序计数器自增
• 根据指令 = 计算还是存储，决定由计算单元还是控制单元处理

指令周期的四个阶段

• 取指：控制器从存储器拿到后放到寄存器
• 译码：控制器执行
• 执行：运算器从寄存器拿到后计算
• 回写

指令段 (正文段) 和 数据段 分别存 指令 和 数据

• 图中指令以汇编为样例 ，实际为二进制：下面以 MIPS 指令编码方式为例
• 指令类型：传输 (eg. store mov)、运算、跳转、信号 (trap 中断)、闲置 (nop 空转)
• 大多数指令不能在一个时钟周期完成，通常需要若干个时钟周期

程序执行效率

• 执行时间 = CPU 时钟周期数 CPU Cycles * 时钟周期时间 Clock Cycle Time
• 时钟周期数 = 指令数 * 每条指令平均时钟周期数 Cycles Per Instruction (简称 CPI)

32位/64位

• 硬件 64 位和 32 位指「CPU」的位宽
• 软件 64 位和 32 位指「指令」的位宽
• 32 位软件兼容后可以跑在 64 位机器上，反之不行：指令位宽超过寄存器位宽
• 64 位机器单条指令计算更大数据，但前提是确实存在大位宽数据的需求
• 64 位的地址总线位宽是 48，支持的寻址空间更大

磁盘/内存

• 内存数据存储在电容中，需要不断刷新对冲漏电问题
• 查看 CPU 缓存的命令；查看 cache line 的大小

CPU 提速

内存地址和 cacheline 对照关系 「CPU」

• 根据地址中「索引部分」找到映射的 line
• 根据 line「valid 部分」得知是否有效
• 根据地址「tag 部分」和「line」的 tag 比对得知是否是需要的那个行：多个地址可映射到同一 line
• 根据地址「偏移部分」拿到 line 里的对应数据：即 word 字

提升缓存命中率

• Linux 提供 sched_setaffinity 方法支持将线程绑定在某个核心提升 cache 命中率
• 提升数据缓存命中率：充分利用连续分布的内存 (经典两层 for 循环的例子)
• 提升指令缓存命中率：if 预测更加准确 (先 sort 再 for 判断比反过来要好)

CPU 缓存一致性

解决缓存一致性

• 写传播：CPU A 写的数据 CPU D 也能感知
• 事务串行：CPU A 和 CPU B 同时在写
• CPU C 收到的是 A 先 B 后
• CPU D 收到的是 B 先 A 后
• 那么 C 和 D 实例存的就不一样了

CPU 任务执行

伪共享

• 因为 cache line 实例存的数据量可能是所需量的超集，两个核心分别需要地址连续的变量 a 和 b
• 虽然两者的数据毫不相关，也出现互相两对方设置对方的 cache line 为不生效
• 通过 __cacheline_aligned_in_smp 可以避免伪共享
• 用空间换时间：强行将在 cache line 后面填充零，浪费部分缓存空间换来性能提升

进程调度

• 进程和线程都是用 task_struct 类，不同调度类有不同的 run queue
• 同一「调度类」可能存在多个调度策略，例如 realtime 类有 fifo 和 rr

• 每个 CPU 都有自己的 run queue，具体包含三个运行队列
• Deadline 运行队列 dl_rq
• Realtime 运行队列 rt_rq
• CFS 运行队列 cfs_rq
• Linux 选择下个任务执行时，会按照此优先级顺序进行选择
• 即先从 dl_rq 里选任务，然后从 rt_rq 里选任务，最后从 cfs_rq 里选任务

优先级和权重

• 任务「优先级」一般是指任务落到那个调度类的意思
• vruntime 通过 nice 值调整的叫「权重」

中断

• 关中断：不响应中断：类比为有人给你电话时其他人给你电话会因为占线打不进来
• 硬中断/软中断，以网卡为例
• 上半部分：中断当前执行的程序，关网卡中断，触发软中断
• 下半部分：从内存读数据过协议栈，每个 CPU 都有个专门处理软中断的内核线程
• 比如 ksoftirqd/0 就是 0 号 CPU 那个线程
• 除了硬中断的下半部分，软中断还包括：内核调度等、RCU 锁等软件触发的情况

• 查看软中断和硬终端
• /proc/interrupts；/proc/softirqs
• 每个 CPU 都有自己累计的不同类型软中断的次数
• 理论上每个 CPU 软中断次数会比较均衡

浮点数精度

• 补码：采用补码的优势是可使得加减法操作不需要特判，像正数一样按位加即可
• 转换：十进制整数转二进制整数的方式是除以 2，小数转二进制小数的方式是乘 2

精度问题

• 小数受限于单个数字的字节长度限制，无法准确表达而不得不丢失精度，比如 0.1 就无法准确表示
• 「浮点数」：对固定字节长度来说，小数点点的位置是不固定的
• 符号位 + 指数位 (确定小数点的位置，即尾数位向左或者向右移动几位，永远是正数，以127为界，小于127则往左移大于则往右移) + 尾数位
• 因为精度问题最终 0.1+0.2 的结果不完全等于 0.3

操作系统

linux 设计的核心点

• MultiTask 多任务：CPU 并发和并行
• SMP 对称多处理：每个 CPU 的行为一致且对称
• ELF 可执行文件链接格式：ELF 加载到内存后执行
• Monolithic Kernel 宏内核：所有驱动和文件系统等模块是内部的一部分，可动态加载

内核实现方式的区别

• 微内核是指内核只包含少量核心功能，上述模块工作在用户态
• 优势是扩展性可插拔，劣势是用户态到内核态切换：折中是混合内核

Linux VS Windows

• 内核模式：Linux 内核采用宏内核，Window 内核采用混合内核
• 可执行文件格式：Linux 可执行文件格式叫 ELF，Windows 可执行文件格式叫 PE

内存管理

虚拟内存

单片机没有操作系统，必须把程序烧进去运行，每次改程序都要重新烧

分段机制

• 分段机制下的虚拟地址由两部分组成：「段选择因子」和「段内偏移量」
• 分段里最关键就是段表，段表里保存：段基地址、段界限、特权等级等
• 分段机制的核心在于物理内存是按照段的大小按需分配的连续空间
• 没有内部碎片
• 会有外部碎片：需要 swap out 外 swap in 达到重新整理的效果

分页机制

• 分页的核心是页表：页表本身存储在内存中
• 每个进程有自己的页表：进程越多页表占用空间越大；每个进程所需的页表大小上完全相同
• 多级页表：第一级页表肯定都要存在的 (覆盖全部的地址)，但后续的几级页表都可以按需加载
• 64 位系统页表分为 4 层，都有各自的名字

Intel 为兼容历史上的「段式内存」，采用的是 [段页式内存管理] 模式

• 逻辑地址是「段式内存管理」转换前的地址
• 线性地址是「页式内存管理」转换前的地址

Linux 操作系统兼容 [段页式内存管理] 模式，但实际生效的只有「页式内存管理」

• 系统中每个段都是从 0 地址开始的整个 4GB 虚拟空间，所有段的起始地址都一样
• 即操作系统本身的代码和应用程序的代码，所面对的都是线性地址空间 (虚拟地址)
• 相当于屏蔽处理器中的逻辑地址概念，段只被用于访问控制和内存保护

我们平时常说的进程内存分布是指虚拟内存分布

查看命令

• /proc/pid/maps 或者 pmap pid：查看进程用户态虚拟内存空间的实际分布
• cat /proc/iomem：查看进程内核态虚拟内存空间的的实际分布

Malloc

• malloc 是用户态函数库，申请的是「虚拟内存」而不是「物理内存」
• 如果需要内存小于 128 KB：用 brk 系统调用申请「堆」内存
• 否则：用 mmap 系统调用申请「匿名文件映射」内存

• malloc(1) 不只分配 1 字节
• 小于 128 KB，brk 系统调用向堆空间申请
• cat /proc/pid/maps 最右边有 [heap] 标识

• malloc 分配内存的前 16 字节用于存当前申请的内存块的大小
• free 时根据改前 16 字节可以知道需要释放多少内存

brk/mmp

• brk 申请：free 释放内存时不把内存归还给操作系统，而缓存在 malloc 内存池 (用户态) 待下次使用
• 减少系统调用带来的上下文切换开销
• 减少缺页异常次数开销
• mmap 申请：free 释放内存时把内存归还给操作系统，内存得到真正释放
• 不全部用堆内存是避免堆中出现过多碎片 (虚拟内存地址碎片)

内存满操作

• 内存满的处理步骤：后台内存回收 -> 直接内存回收 -> oom
• /proc/meminfo：活跃/不活跃 的 匿名页 (堆栈) /文件页 (磁盘数据和文件数据)

回收

• 回收内存都会发生磁盘 I/O，如果回收内存操作频繁则会导致磁盘 I/O 次数很多，影响系统性能
• swappiness 设置得越大越倾向于回收文件页
• /proc/sys/vm/swappiness
• sar -B 1 可以看内存回收的情况
• pgscank/s：kswapd 每秒扫描的 page 个数
• pgscand/s：应用程序在内存申请过程中每秒直接扫描 (直接回收) 的 page 个数
• pgsteal/s: pgscank+pgscand
• pgscand 数值很大大概率因为直接内存回收导致

/proc/sys/vm/zone_reclaim_mode 设置 NUMA 架构下的回收策略

• 0 默认值：回收本地内存前，在其他 Node 寻找空闲内存
• 1：只回收本地内存
• 2：只回收本地内存，在本地回收内存时可将脏页写回硬盘
• 4：只回收本地内存，在本地回收内存时可用 swap 方式回收内存

预读/污染

PageCache 和 BufferCache 参照如下示意图

• [预读失效] 导致缓存命中率下降
• 通过冷热两个链表 (即 active 和 inactive) 解决
• 预读但没用的只会放到冷链表头，热链表被淘汰的会先放到冷链表头
• [缓存污染] 导致缓存命中率下降
• 提升进入热链表的门槛，访问两次以上才从 inactive 提升到 active

虚拟内存管理

虚拟内存地址空间

• 不同段的 (虚拟内存) 地址存在内核数据结构中
• 全局变量和静态变量在程序编译后也存储在二进制文件中

不同区的说明

• 保留区：C 语言中将无效指针设置为 NULL，指向的就是保留区
• 文件映射与匿名映射区：动态链接库中代码段+数据段+BSS 段；通过 mmap 系统调用映射的共享内存区
• 栈区：start_brk 标识堆起始位置，brk 标识堆当前结束位置
• 堆区：start_stack 标识栈起始位置，RSP 寄存器保存栈顶指针，RBP 寄存器保存栈基地址

cat /proc/pid/maps 或 pmap pid 查看某进程的虚拟内存布局

• [canonical addres] 是 64 位机器中 [内核态地址] 和 [用户态地址] 间的空洞
• 通过前置位是否全 0 或者全 1 快速定位到地址是属于用户态还是内核态

数据结构

• 用户进程数据结构 task_struct 里包含 mm_struct，专门记录虚拟内存信息：copy_process() -> copy_mm()
• 新建线程的 task_struct 和父进程共享 mm_struct 指针
• vfork/clone
• 新建进程的 task_struct 的 mm_struct 是父进程的 deep copy
• fork
• 内核线程的 mm_struct 为 nil
• 内核在调度内核线程时将上个线程的 mm_struct 直接复制给内核线程
• 因为所有线程的内核虚拟地址空间完全一样，所以任意复制一个就行
• 总结
• 父进程/子进程的区别，进程/线程的区别，内核线程/用户态线程的区别：都围绕 mm_struct 展开

mm_struct

• mm_struct 中 task_size 定义用户态地址空间与内核态地址空间之间的分界线

• mm_struct 结构体中记录用于划分虚拟内存区域的变量 (即各个段的起始地址)

• mm_struct 结构体中定义虚拟内存与物理内存映射内容相关的统计变量
• total_vm：进程虚拟内存空间中与物理内存映射的页总数 (不代表真正分配内存)
• locked_vm：被锁定不能换出的内存页总数
• pinned_vm：既不能换出，也不能移动的内存页总数
• data_vm：数据段中映射的内存页数目
• exec_vm：代码段中存放可执行文件的内存页数目
• stack_vm：栈中所映射的内存页数目

vm_area_struct

• 每个 vm_area_struct 结构对应虚拟内存空间中的虚拟内存区域 VMA
• 描述 [vm_start，vm_end) 左闭右开的虚拟内存区域
• vm_area_struct 里定义每个虚拟内存区域的权限
• vm_flags：定义整个虚拟内存区域的访问权限以及行为规范 (截图+理解典型的 flag)

• vm_area_struct 完整的内存相关数据结构的关系图
• vm_area_struct 同时包含红黑树和双向链表两种组织方式，分别应用查找和遍历的场景
• pmap pid 是通过遍历 vma_area_struct 双向链表实现的
• 二进制文件在磁盘中通过 section 的方式组织
• 磁盘中的多个 section 会映射成内存中同一 segment
• text，.rodata 等只读 section 被映射到内存的一个只读可执行的代码段
• .data，.bss 可读写 section 会被映射到内存具有读写权限的数据段，BSS 段
• ...

虚拟内存操作

malloc

• 申请小块内存 (< 128K) 用 do_brk 系统调用，调整堆 brk 指针增加或回收堆内存
• 大块内存则调用 mmap 在虚拟内存空间中的文件映射与匿名映射区创建出一块 VMA 内存区 (即匿名映射)
• 该匿名映射区域用 struct anon_vma 结构表示

mmap 文件映射

• vm_file 属性用来关联被映射的文件，vm_pgoff 表示映射进虚拟内存中的文件内容在文件中的偏移

svm_operations_struct 中定义对虚拟内存区域 VMA 的操作函数指针；

同理，file/io 都是如此，和 interface 的思路比较类似

内核态虚拟内存空间

进入内核态后操作的仍然是虚拟地址空间

• 直接映射区
• 3G 到 3G+896m 这块 896M 大小的虚拟内存会直接映射 0 到 896M 这块 896M 大小的物理内存上
• 虽然是直接映射，内核访问时同样还是走虚拟内存查询页表
• 直接映射区存什么数据
• 前 1M 在启动时被占用
• 后面存内核代码段+数据段+BSS段：系统启动时加载从 ELF 文件到内存
• 进程相关的数据结构
• 进程的内核栈：固定大小放进程的调用链
• ...
• 动态映射区
• [VMALLOC_START, VMALLOC_END)
• 通过 vmalloc 申请：其申请的虚拟内存是连续的，但是映射后的物理内存不连续 (以 page 为单位)
• 长期映射区
• [PKMAP_BASE, FIXADDR_START)
• 允许建立虚拟内存和物理内存间的永久映射：kmap
• 固定映射区
• [FIXADDR_START, FIXADDR_TOP)
• 和直接映射区类似：提供类似延迟的机制
• 虚拟内存地址已经固定，但在内核加载过程中不想等内存管理模块加载完
• 临时映射区
• 将用户缓冲区的数据拷贝到 page cache
• ZONE
• Zone 的划分是针对物理内存而言的，896M 以上区域被为 ZONE_HIGHMEM 即高端内存
• 分类
• ZONE_DMA：直接映射区的部分，DMA 只能对物理内存的前 16M 寻址
• ZONE_NORMAL：直接映射区的部分，剩下的 16M-896M 是 zone_normal
• ZONE_HIGHMEM：非直接映射区的部分，896M 以上区域
• 空洞：ZONE_HIGHMEM 上有一段 8M 大小的内存空洞

内存物理结构

物理结构

• 内存 -> 存储器模块 -> DRAM 芯片 -> supercell (8bit 数据)
• 每个 DRAM 芯片有两个 addr 引脚 (索引 supercell 的行和列)，八个 data 引脚 (传输 8 bit 数据)

总线

• IO Bridge 将不同总线中的电子信号互相传递

数据读写

• CPU 以 word size (64 字节) 为单位从内存中读取数据，所以需要 8 个 DRAM 芯片 * 8 个 存储器模块

物理内存管理

虚拟内存的碎片会导致 malloc 失败，物理内存的碎片会导致大页分配不出来

内存模型

PFN (Page Frame Number)

• 和表示物理页结构的 struct page 一一对应
• page_to_pfn 和 pfn_to_page 实现互相转化
• 每个物理页的 PFN 全局唯一的：不只是其所在 NUMA 节点内唯一

平坦模型

• mem_map 全局数组保存 PFN

连续内存模型

• 内存空间拆分成多个 node
• 每个 node 内部用 node_mem_map，node 间用 pglist_data 组织

稀疏内存模型

• 将 node 的概念缩小到更小的 section
• 物理页 = 4k 则 section = 128M；物理页 = 16k 则 section = 512M

内存热插拔

• 将 section 置为 online/offline 然后进行内存迁移
• 业务进程只感知虚拟内存所以无感知
• 像直接映射区标记为不支持热插拔即可

NUMA-概述

UMA 的问题：随着核数变多，总线带宽吃紧+长度变长

numa 内存分配策略

数据结构

• node_data 管理所有 numa 节点：以数组方式组织
• 每个 numa 节点用 pglist_data 管理：pglist_data 核心字段及含义如图

NUMA-Zone

• 只有第一个 numa 可以包含 zone_dma
• 所有 numa 都可以包含 zone_normal 和 zone_high

• NUMA 节点内按照功能不同划分成不同的内存区域
• 内核为每个内存区域分配一个 [伙伴系统] 管理该内存区域下物理内存的分配和释放
• [伙伴系统] 管理的是 [物理内存] 的分配

NUMA-内存挤压

• 高位内存区域 (内存不够时可以) 对低位内存区域进行挤压
• 每个内存区域可按照一定的比例来计算自己的预留内存的
• cat /proc/sys/vm/lowmem_reserve_ratio

NUMA-内存回收

• 每个 NUMA 节点分配一个 kswapd 进程用于回收不经常使用的页面
• kswapd 指向内核为 NUMA 节点分配的 kswapd 进程
• kswapd_wait 用于 kswapd 进程周期性回收页面时使用到的等待队列
• 每个 NUMA 节点分配一个 kcompactd 进程用于内存的规整避免内存碎片
• kcompactd 指向内核为 NUMA 节点分配的 kcompactd 进程
• kcompactd_wait 用于 kcompactd 进程周期性规整内存时使用到的等待队列

水位线

• 关于更多 [文件页]/[匿名页] 的回收 (swap ...) 在后续 IO 章节展开介绍

cat /proc/zoneinfo 查看 [不同 NUMA] 中 [不同内存区域] 中的水位线

NUMA-冷热页

• 热页：已经加载进 CPU 高速缓存中的物理内存页
• 冷页：还未加载进 CPU 高速缓存中的物理内存页

数据结构

• 冷热页的管理封装在 struct per_cpu_pageset 中
• 每个 CPU 对应一个 per_cpu_pageset 结构
• zone 结构中的 pageset 数组包含的是系统中所有 CPU 的高速缓存页

• count ：集合中包含的物理页数量
• 如果是热页集合，则表示加载进 CPU 高速缓存中的物理页面个数
• list_head list ：双向链表保存当前 CPU 的热页或者冷页
• batch：每次批量向 CPU 高速缓存填充或者释放的物理页面个数。
• high：如果 count 值超过 high，内核从高速缓存中释放 batch 页面到物理内存区域的 [伙伴系统]

内存分配

内核内存页分配两种方式

• 以页为单位分配使用：向相应内存区域 zone 里的 伙伴系统 申请/释放
• 分配小块内存 (几十个字节)：内核使用 slab allocator 分配器分配
• slab = 对象池，基本原理是从伙伴系统中申请整页内存，划分成多个大小相等的小块内存被 slab 所管理据。

进程管理

进程/线程

• 进程状态
• 阻塞：进程在等待事件
• 挂起：进程因为没在执行，其状态被 swap 到磁盘中 (比如二进制)
• 阻塞挂起：进程在外存 (硬盘) 并等待某个事件出现
• 就绪挂起：进程在外存 (硬盘) 且只要进入内存即刻立刻运行
• 父子进程
• 父进程清理退出子进程时需要清理子进程 PCB 相关数据结构
• 进程切换
• 需要保存内容：虚拟内存、栈、全局变量等 “用户空间资源”，内核堆栈、寄存器等 “内核空间资源”
• 切换时机：时间片耗尽，等待资源，主动睡眠，硬件中断，高优抢占
• 线程切换
• 需要保存内容：虚拟内存共享 (切换时保持不动)，只需切换线程私有数据、寄存器等

线程实现

用户级线程

• 库函数维护：切换也由线程库函数完成 -> 无需用户态与内核态切换速度特别快
• 操作系统不感知：用户线程不支持抢占，阻塞后可能会导致卡住

内核线程

• 内核维护：线程上下文信息，线程创建、终止和切换都通过系统调用开销比较大
• 如果某内核线程发起系统调用而阻塞不会影响其他内核线程，内核会负责平衡内核线程的时间片

lwp 轻量级线程

• 轻量级线程其实就是用户线程，只不过用户线程可以直接映射到内核线程 (可能存在 m 对 n 的关系)

线程上限

• 同一个进程可创建的线程上限
• 虚拟内存大小：相同进程里的线程共享虚拟内存空间，每个线程都会独立分配栈空间 (即下图 stack-size)

• 系统的配置：最大线程数 && 最大 pid 数
• /proc/sys/kernel/threads-max：系统支持的最大线程数，默认 14553
• /proc/sys/kernel/pid_max：系统全局 PID 数值限制，默认 32768
• /proc/sys/vm/max_map_count：限制单进程可拥有 VMA (虚拟内存区域) 数量，默认 65530

线程崩溃

线程崩溃时会给进程 (父线程) 发信号

• 线程共享虚拟内存，如果虚拟内存搞乱了可能会影响其他线程，为保险不如退出
• 如果没捕获就会导致进程退出：类似 JVM 这种自己处理信号的可能就不会退出

进程通信

管道

• 原理：内核里的缓存，从管道拿着 fd 从一端写入数据后缓存在内核中，另一端拿着 fd 从内核中读取数据
• 没人读会导致写卡主；管道数据无格式

• 父子：管道在父子间通信的原理是 fork 可以 copy fd
• 为避免混乱，保证父子进程可以 (分别只留读 fd 和 写 fd) 确保到同时写入和读出

• shell：通过 | 传递信息也是匿名管道，实际上就是创建多个子进程
• 编写 shell 脚本时，能用一个管道搞定的就不要多用个管道，减少创建子进程系统开销

消息队列

• 原理：可以传递结构化数据；生命周期一直存在，而匿名管道的生命周期随进程
• 参数：内核中两个 MSGMAX 和 MSGMNB 以字节为单位分别定义一条消息的最大长度和一个队列的最大长度
• 开销：消息队列通信中存在用户态与内核态间的数据拷贝开销
• 进程写入数据到内核中的消息队列时，会发生从用户态拷贝数据到内核态，同理进程读也是

共享内存

• 原理：不同虚拟地址空间映射到相同物理内存
• 开销：消息队列个管道需要用户态内核态数据拷贝，共享内存不需要

信号量/信号

• 信号量：解决使用共享内存中的互斥问题
• 信号：给进程的通知机制

socket

• socket 走协议栈既支持同主机又支持跨主机

多线程同步

• 锁
• 忙等待锁：等于 "自旋锁"，必须配合抢占式调度 (不然不会主动 yield)
• 无等待锁：当没获取到锁时把当前线程放到锁的等待队列，执行调度程序把 CPU 让给其他线程
• 信号量
• 使用信号量可实现临界区的互斥访问
• 使用信号量实现同步：a ready 了才可以做 b
• 经典问题：生产者/消费者
• 经典问题：哲学家就餐
• 经典问题：读者/写者

锁

死锁

• 死锁条件 (四元素)
• 互斥访问 + 持有然后等待 + 不可抢占 + 环路等待
• 死锁检测 (工具)
• jstack (java) / pstack(c) 可以看到线程等锁的情况 (多次查询都在等锁大概率因为死锁)
• 在怀疑死锁后通过 gdb 可以具体查看持有锁/等待锁的具体线程

锁分类

• 基础锁
• 互斥锁：获取失败则主动释放 CPU，会陷入内核态做线程切换
• 自旋锁：获取失败则忙等，依赖内核抢占
• 实现上，"自旋" 借助 CPU CAS 指令，"等待" 借助 CPU Pause 指令
• 读写锁：根据唤醒时机可分为 "读优先" (下图 1)，"写优先" (下图 2)，"公平"

• 乐观/悲观锁
• "基础锁" 和 "读写锁" 都是 "悲观锁"：所有操作前必须先加锁
• "乐观锁" 是先操作然后在后置进行冲突检查，典型的比如 MVCC 和 CAS
• 解释下：只用 CAS 是乐观锁，配合 pause while 检查的自旋锁实现则是悲观锁

调度算法

• 调度需要考虑的因素
• 利用率；吞吐；周转时间；等待时间；响应时间
• 进程调度
• 算法：先进先出；短作业优先；高响应比优先；时间片轮转；优先级；多级反馈优先级
• 高响应比优先问题：响应比需要知道进程实例运行时间，但是不好预估
• 磁盘寻道算法
• 算法：先来先服务，最短寻道时间，电梯算法 (look 改进)，循环电梯算法 (c-look 改进)

• 页面置换算法
• 算法：先进先出，最久未用(计访问时刻)，最不常用 (计访问次数)，时钟置换 (带衰减的访问次数)
• 页表项：有该页在磁盘上的地址 (通常是物理块号)

• 缺页：从磁盘加载缺页时会保存当前 CPU 状态 (内核态执行加载操作)

文件系统

• inode vs dentry
• inode：物理上存储在磁盘
• dentry：内核维护的数据结构 (既能表示目录又能表示文件)
• 硬链接的实现是对同一文件 (对应唯一的 inode) 构造了多个 dentry
• 磁盘块区
• 超级块：在文件系统挂载时加载到内核
• 索引块：在访问时加载到内核
• 数据块：存储文件或目录数据
• 进程：系统为每个进程维护独立的打开文件表，表中的每项就是文件描述符
• 使用：用户进程以字节为单位操作文件，系统以 块 (多个扇区组合成块) 为单位操作文件

文件存储

文件在磁盘存储方式：系统以 “块” (即多个扇区) 为单位操作文件

• 连续存储：将连续的块组合起来，会产生碎片，inode 记录起始块和块长度

• 隐式连接表：inode 记录起始块，每个块里留空间存下个块的指针
• 图中的 "文件头" 就是就等同于 inode

• 显式连接表：inode 记录每个块的位置
• 和隐式的区别是：查找第 n 个块，前者要读 n 次盘，后者是内存操作
• 索引表：inode 记录索引块的位置，索引块里记录每个数据块的位置
• 一级索引不够就用多级索引

实现对比

unix (ext 2/3) 实现

• unix 文件系统综合了连接表和索引表，前者用在小文件，后者用在大文件
• 存放文件所需数据块 < 10 块：直接查找 (连接表)
• 存放文件所需数据块 > 10 块：采用一级间接索引
• 还不够存放大文件：采用二级间接索引
• 还不够存放大文件：采用三级间接索引
• 优势
• 小文件：直接查找可减少索引数据块开销
• 大文件：多级索引的方式在访问数据块时需要大量查询

空间管理

• 空闲表 / 空闲链表：两者都不适合大文件，因为表和链表本身的空间都很大
• 空闲链表还需要遍历链表拿指针效率更低

• 位图
• 估算
• 每块 4K，每个数据块 1bit，共可表示 4*1024*8=2^15 空闲块
• 每个数据块 4K，最大可表示的空间为 2^15*4*1024=2^27 byte = 128M
• 解决：文件系统都由大量块组组成；每块
• 分类
• 超级块：文件系统信息，eg. inode 总数、块总数、每块组的 inode 数、每块组的块个数 ...
• 块组描述符：文件系统中各块组的状态，eg. 块组中空闲块和 inode 的数目 ...
• 每个块组都包含文件系统中 [所有块组的组描述符信息]
• 数据 / inode 位图：对应的数据块或 inode 是空闲的还是被使用中
• inode 列表：块组中所有的 inode
• 数据块：文件的有用数据
• 说明
• 每块组有很多重复的信息：比如超级块和块组描述符表 (冗余)

目录存储

• 目录里头的数据
• hash 表：当目录里的文件过多时，先哈希再遍历可增加查找的效率

软/硬链接

硬链接

• 多个 dentry 中的 inode 指向一文件
• inode 不可跨越文件系统：硬链接不可跨文件系统
• 只有删除文件的所有硬链接以及源文件时，系统才会彻底删除该文件

软链接

• 软链接文件有独立 inode：但其内容是另一个文件的路径
• 访问软链接时实际相当于访问到另外的文件：软链接可以跨文件系统
• 目标文件被删除后链接文件还在，只是指向的文件再也找不到

文件 IO

• 缓冲/非缓冲：库函数自身的缓存
• 直接/非直接：内核的缓存，区别是 "用户态 <-> 内核态" 是否发生数据交换
• 而 "内核态 -> 磁盘" 的数据更新是异步的
• 同步 IO
• 阻塞：“磁盘->内核态” 和 "内核态->用户态" 都需要同步阻塞
• 非阻塞：“磁盘 -> 内核态“ 马上返回靠轮询，“内核态->用户态“ 仍然同步阻塞
• 多路复用：可以在一个线程里等待多个 socket，阻塞情况和非阻塞一样
• 异步 IO：两步都是异步的

Page Cache

• 进程写文件然后奔溃，文件内容不会丢，因为会有 page cache
• pagecache 由内核维护；/proc/meminfo 可查看其信息
• page-cache = buffers + cached + swap-cached

• pagecache 有预读机制

swappiness

• 参数范围是 0-100
• 高数值：较高频率的 swap，进程不活跃时主动将其转换出物理内存
• 低数值：较低频率的 swap，确保交互式不因为内存空间频繁地交换到磁盘而提高响应延迟

VS buffer-cache

• page-cache 缓存文件的页数据，buffer-cache 缓存块设备的块数据
• 页是逻辑概念：page-cache 与 "文件系统" 同级
• 块是物理概念：buffer-cache 与 "块设备驱动程序" 同级
• 低版本内核中 pagecache 和 buffer 是完全正交的
• 这样会导致数据被缓存两次 (以 1k block 和 4k page 为例)
• 新版本内核中 pagecache 也包含了 buffer 的语义

脏页回写

• pagecache 回写相关系统调
• fsync(fd)：将 fd 文件的 [脏数据] 和 [脏元数据] 全刷新至磁盘
• fdatasync(fd)：将 fd 文件的 [脏数据] (和必要的 [元数据]) 刷新至磁盘
• 例如：文件大小是必要的，文件修改时间是不必要的
• sync()：将所有脏文件的 [元数据] 刷新至磁盘
• 脏页回写时

1. 应用程序主动调用 (上述) 回系统调用
2. 管理线程周期性唤醒设备回写线程
3. 某些应用程序/内核任务发现内存不足，而回收部分缓存页面

• 回写线程
• 管理线程全局唯一，刷脏页线程内核设备一个
• 管理线程监控设备脏页面情况：一段时间没有脏页就销毁设备的刷新线程；若监测有脏页面则创建刷新线程

设备管理

IO 控制流程

1. CPU -> DMA：告知从哪儿读到哪儿
2. DMA -> 磁盘控制器： 同上
3. 磁盘控制器 -> 内存：发送数据
4. 磁盘控制器 -> DMA：发送信号
5. DMA 产生中断

设备层级

• "设备控制器" 属于硬件
• "设备驱动程序" 属于操作系统："设备驱动程序初" 始化的时候需要注册 "中断处理程序"

通用块层

• 处于 “文件系统” 和 “磁盘驱动程序” 之间
• 用途：提供标准接口 + IO 请求的排队和调度

IO 分层架构

• 文件系统层+通用块层+设备层
• ioctl：设备输入输出控制接口，配置和修改特定设备的属性
• 缓存：文件系统有缓存 (pagecache/inode) + 块设备也有缓存 (设备缓冲区)

设备硬件

• 设备缓冲区：设备 (磁盘) 控制器从键盘里写，设备 (磁盘) 驱动程序读
• CPU 收到中断后由 CPU 调用中断处理程序
• 分类
• 块设备：可寻址，硬盘/USB
• 字符设备：不可寻址，鼠标
• 块设备的数据传输量较大，所以需要缓冲区，字符设备通常只需要寄存器就够 (不需要数据缓冲区)

网络管理

零拷贝

零拷贝的典型使用系统：kafka/nginx

• 带 DMA 和 不带 DMA：磁盘缓冲区到内核缓冲区的拷贝是不是 CPU 做的

• 带 DMA 的读操作：两次系统调用 + 四次上下文切换 + 四次数据拷贝

实现： mmp

[四次] 上下文切换+ [两次] 系统调用+ [三次] 数据拷贝 (内核态 内核缓冲区->网卡缓冲区)

实现： sendfile

[两次] 上下文切换 + [一次] 系统调用 + [两次] 数据拷贝 (无需 CPU 参与/都是 DMA)

page-cache/IO 模式

所谓 “内核缓冲区” 就是 page-cache 作为缓存；page-cache 还有预读功能

• 在传输大数据文件时 page-cache 反而有负向影响：零拷贝也没用
• 绕开 pagecache 就是 "直接 IO"；使用 pagecache 就是 "缓存 IO"
• 磁盘的 “异步 IO” 只支持 “直接 IO”
• "直接 IO" 的用途
• 用户程序已经实现用户态缓存
• 大文件传输；page-cache 只会让热点失效
• "直接 IO" 的劣势：绕过 page-cache
• 预读逻辑失效
• 内核 IO 调度算法本可以合并多次 IO 请求

IO 多路复用

socket

• socket 数据结构中有两个 sk_buff 对象：收队列和发队列
• sk_bff 里的指针 data 随协议栈变化而逐渐指向对应层的内容

影响单机连接数的因素：内存，文件描述符数，IP/端口数，网络 IO 模型 ...

多进程

• 父进程负责管理连接 (listen)，子进程负责读写

多线程

• 父进程负责管理连接 (listen)，子线程负责读写
• 子线程通过 “队列“ + ”线程池” 减少线程 创建/删除 开销

select/poll

• 两次遍历 (内核态/用户态各一次) 两次列表传输
• select 用 bitmap 固定大小，poll 用链表 变长大小
• 传递的内容都是 [文件描述符集合]

epoll

• epoll 基本操作
• create：创建红黑树
• ctrl：向红黑树添加文件描述符节点
• wait：内核用就绪的节点构造序列，拷贝到用户态

高性能网络模式

reactor 模式

IO 多路复用监听事件，收到事件后根据事件类型分配给 进程/线程

• 单 reactor 单进程/线程
• 模块：reactor 负责 select+dispatch；acceptor 负责 accept；handler 负责 read+send
• 缺点：无法充分利用 CPU；某个连接的 handler 卡主可能影响别的连接
• 案例：redis 是该方案，都是内存操作性能不在 CPU

• 单 reactor 多线程
• 模块： handler 仍然负责 read/send
• 缺点：数据处理过程由独立线程处理，线程数据处理需要加锁 (效率并不高)

• 单 reactor 多进程
• 需要处理父子进程间的数据通信
• 一般不用：实现难度复杂
• 多 reactor 多进程/线程
• 模块：主线程负责接收连接，子线程负责后续的数据事件；两者都有 select
• 对比：单 reactor 需要处理所有事件的监听和响应，容易成为性能瓶颈
• 案例：netty/memcache

proactor 模式

• IO 分类
• 同步
• 阻塞 IO：等待内核数据和内核到用户拷贝数据
• 非阻塞 IO：等待内核到用户拷贝数据
• 异步：两者都不等待
• reactor：非阻塞同步；selector 收到事件后需要主动调 read
• proactor：异步
• proactor 基于内核能力
• linux 是用户态模拟的且只支本地文件不支持网络
• windows 是内核实现的

网络命令

• 网络配置：ifconfig/ip
• socket：netstat/ss
• 网络吞吐 pps：sar
• 网络联通和延时：ping

一致性 Hash

引入虚拟节点的优势：节点越多越容易均衡数据；单点下线故障域越小