写在前面这是本系列系统级编程学习笔记的最终篇。如果说之前的笔记是在榨干 CPU 的算力那么这篇笔记将带你跨越硬件与软件的边界进入操作系统的核心领域。我们将探讨程序是如何响应突发事件的异常与信号、Unix“万物皆文件”的优雅设计以及那令人又爱又恨的malloc究竟是如何在底层变魔术的。Lec 14 Exceptional Control Flow Exceptions and Processes大纲异常控制流 (Exceptional Control Flow, ECF)覆盖了从硬件、操作系统到应用层的各个级别。低级别机制异常 (Exceptions)。硬件和操作系统的结合应对系统事件如缺页、中断、除以零。高级别机制进程上下文切换 (Process Context Switch)- 操作系统和硬件定时器实现。信号 (Signals)- 操作系统软件实现。非本地跳转 (Nonlocal Jumps)-setjmp和longjmp允许程序打破常规的 Call/Return 栈模式直接跨越函数层级跳转类似 C 里的 try-catch 底层原理。系统调用错误处理 (System Call Error Handling)在 Linux 系统编程中如果系统调用失败它通常会返回-1并设置一个全局整数变量errno来指明到底出了什么错。硬性铁律 (Hard and Fast Rule)你必须检查每一个系统级函数的返回状态永远不要假设fork()或者write()会百分之百成功。例外情况只有极少数返回void的函数如exit不需要检查。execve 加载运行程序一张单程票int execve(char *filename, char *argv[], char *envp[])这是一个极其特殊的系统调用它负责在当前进程中加载并运行一个新的程序。夺舍重生它会完全覆盖当前进程的代码段、数据段、堆和栈。保留躯壳但它保留了原有的进程 ID (PID)、已经打开的文件描述符列表以及信号上下文。单程票execve被调用一次如果没有出错它永远不会返回。因为返回地址所在的栈已经被新程序抹除了这也是它令人兴奋的地方。Summary异常 (Exceptions):需要打断标准控制流的事件。可以是外部的键盘中断、网络包到达或内部的缺页故障、段错误。进程 (Processes):操作系统提供的最伟大的抽象之一。它给每个程序一种错觉仿佛自己独占了整个 CPU通过并发上下文切换和整个内存空间通过虚拟内存。Lec 15 Exceptional Control Flow Signals and Nonlocal JumpsLinux Process 层次结构在 Linux 中所有的进程都是一棵树。init(或现代的systemd) 进程是 PID 1它是所有进程的老祖宗负责系统服务。守护进程 (Daemon):在后台静默运行的进程。当用户登录时会创建一个登录 Shell 进程你运行的所有命令如ls,grep都是这个 Shell 的子孙进程。Writing Handlers (编写安全的信号处理程序)信号如CtrlC产生的SIGINT是异步的随时可能打断主程序。编写安全的 Handler 是一门艺术到处都是坑保持极简:最好只设置一个全局标志位Flag然后立刻返回让主程序去处理复杂的逻辑。只调用异步信号安全 (Async-Signal-Safe) 的函数:严禁在 Handler 中调用printf或malloc因为它们内部有锁如果在持有锁时被信号打断Handler 再去请求同一个锁就会导致死锁。保存和恢复errno:避免 Handler 内部的操作覆盖了主程序原本的errno值。阻塞信号以保护共享数据:在修改全局工作队列时暂时阻塞信号防止竞态条件。全局变量声明为volatile:这告诉编译器“这个变量可能在不知不觉中被修改每次都必须去内存里读绝对不准把它优化进寄存器里”Synchronizing Flows to Avoid Races这是SIGCHLD处理程序的经典写法。陷阱信号是不排队的如果同时有 3 个子进程死亡内核可能只会记录一次SIGCHLD。因此必须在循环中使用waitpid(-1, NULL, 0) 0来收割所有已经死亡的僵尸进程Zombie并在操作共享工作列表时使用sigprocmask严密保护。Lec 16 System Level I_OUnix I/O 的哲学万物皆文件在 Linux 系统中文件就是一个 m 个字节的序列。这种极其简单粗暴的抽象造就了 Unix 的伟大无论是磁盘分区 (/dev/sda2)、键盘终端 (/dev/tty)、网络套接字、甚至是操作系统的内核数据 (/proc)全部被抽象成了文件。你可以用同一套 API 去读写发送消息。短计数 (Short Counts)当你要求读取 50 个字节系统却只返回了 20 个字节这就是“短计数”。会发生短计数的地方读取时遇到 EOF从终端读取按行返回读写网络套接字由于网络延迟包不是一次性到达的。最佳实践编写网络程序时永远不能假设read或write一次就能完成必须将它们放在while循环中持续读取。Unix Kernal Open File (核心三个表)为了管理打开的文件内核维护了三种精巧的数据结构这是理解并发和 fork 的基础描述符表 (Descriptor Table):每个进程独有一个。记录了当前进程所有打开的文件描述符 (fd如 0stdin, 1stdout)。里面存放的是指向“打开文件表”的指针。打开文件表 (Open File Table):所有进程共享。记录了文件的当前读写位置 (File Pos) 和引用计数 (refcnt)。V 节点表 (V-Node Table):所有进程共享。包含了文件在磁盘上的实际物理信息类型、大小等。fork() 时的文件共享当调用fork()创建子进程时子进程会完美复制父进程的“描述符表”。这意味着父子进程的 fd 指向了“打开文件表”中的同一个条目它们共享了同一个读写位置。此时文件的引用计数会1。只有当父子进程都执行close()引用计数归零时文件才会被真正释放。Unix I/O vs. Standard I/O vs. RIOUnix I/O:最底层的系统调用 (read,write)。无缓冲速度快但处理短计数和文本行极度麻烦。Standard I/O:C 标准库 (printf,fread)。带有内部缓冲区处理磁盘文件极佳。RIO (Robust I/O):CSAPP 专门编写的安全 I/O 库完美包装了底层调用专为解决网络短计数问题设计。最佳实践准则处理普通磁盘或终端文件用 Standard I/O。在信号处理程序中要求绝对异步安全只能用原始 Unix I/O。在读写网络套接字 (Socket) 时绝对不要用 Standard I/O它的内部缓冲区机制在全双工网络通信中会引发致命的死锁。此时应使用 RIO或等效的现代网络库。拓展阅读推荐Unix 圣经:Advanced Programming in the UNIX Environment (APUE)Linux 圣经:The Linux Programming Interface (TLPI)Lec 17 18 Virtual Memory Concepts SystemsK 级页表 (Multi-Level Page Tables)现代操作系统使用虚拟内存。程序看到的是连续的地址OS 负责将其翻译成真实的物理地址。如果只有一层页表对于 64 位系统来说光是存页表就会耗尽所有物理内存因此引入了多级页表结构一级页表指向二级二级指向三级…… 只有当真正使用到某一块连续内存区域时才去分配对应的下级页表这极大地节省了系统内存完美应对了稀疏分布的地址空间。组织虚拟内存 (Linux VM Areas)Linux 将虚拟内存组织成一个个的“区域 (Area)”比如数据段、代码段、共享库。每一个区域在内核中都有对应的数据结构来管理它的读写权限。比如图片中提到的标志位可以指示这块内存在进程间是私有的还是共享的。Lec 19 Dynamic Memory Allocation Basic Concepts内存分配器的设计挑战没什么好说的C 语言程序员最痛苦的必修课记得free以免内存泄漏开发一个优秀的malloc分配器面临着两个互相对立的终极性能目标吞吐量 (Throughput):疯狂调用malloc和free时系统必须响应得足够快。峰值内存利用率 (Peak Memory Utilization):尽量压榨空间少浪费。万恶之源内存碎片 (Fragmentation)内部碎片 (Internal Fragmentation):分配的块比你实际需要的载荷大。这通常是因为需要“内存对齐”比如强制 8 字节或 16 字节对齐而填充的空白或是为了存放分配器本身的头部管理数据。外部碎片 (External Fragmentation):这更致命。内存中所有的空闲空间加起来足够满足请求但是它们不连续就像被切碎的瑞士奶酪。这也是为什么长时间运行的服务器如果不优化分配策略内存会越来越吃紧的原因。追踪空闲块与偷空间的魔法当调用free(p)时系统怎么知道该释放多少字节要在杂乱无章的内存堆中找到空闲块业界经历了几种迭代隐式空闲链表 (Implicit List):用 Header 记录长度挨个找。显式空闲链表 (Explicit List):在空闲块内部写上指针链起来找。分离适配链表 (Segregated Free List):数组链表按大小分类找。平衡树 (Balanced Tree):用红黑树按大小排序找。细节魔法Header 里的偷空间技巧隐式链表中每个块都需要记录自身的大小还需要 1 个 bit 记录自己是否空闲。难道要多浪费一个字节吗绝不因为内存对齐要求块的大小必须是 8 字节的倍数所以块大小二进制的最后三位一定是 0。系统极其巧妙地借用了最低位的这个0把它变成了 allocated 标志位在读取真实大小时只需要按位与Masking ~0x7把这几位遮蔽掉即可。寻找策略与边界标记 (Finding Policy Coalescing)首次适配 (First Fit):从头找碰到第一个够大的就用容易在堆前部堆积碎木片。下一次适配 (Next Fit):接着上次结束的地方找吞吐量高但容易产生外部碎片。最佳适配 (Best Fit):遍历全表找最接近请求大小的利用率极高但极慢。合并技术 (Coalescing) 与边界标记当释放一块内存时如果左右邻居也是空闲的我们应该把它们融合成一个大块。向右合并很容易通过当前大小跳到下一个 Header但怎么向左看呢计算机科学泰斗 Knuth 发明了Footer (边界标记)技术在每个块的尾部复制一份 Header。这样当前块只需指针往回减一个字就能摸到左边块的 Footer立刻知道它是否空闲并进行双向合并 (Bidirectional Coalescing)显式空闲链表的 LIFO 与地址排序当块释放时它被加入显式链表LIFO (后进先出):直接插到链表头部速度快但容易导致严重的外部碎片。地址排序 (Address-ordered):强行按内存物理地址顺序维护链表。插入慢但实验证明内存利用率极高。终极进化分离适配链表 (Segregated List)如何兼顾极速的吞吐量和极高的利用率现代操作系统给出的终极方案是Seglist。维护一组按 2 的幂次方划分大小的桶1-2, 3-4, 5-8, 9-16…。当需要分配一块内存时直接去对应大小的桶里找。这使得操作时间从线性降低到了对数时间 (O(log N))并且极其逼近“最佳适配Best Fit”的内存利用率。这也是当今高性能内存库如 Google 的tcmalloc的理论基石。垃圾回收标记清除算法 (Mark Sweep GC)不仅是 Java/Go 有垃圾回收C 语言甚至也可以写一个保守的垃圾回收器。系统将内存视为一个有向图寄存器、栈局部变量、全局变量是“根节点 (Root)”。算法分为两步标记 (Mark):顺着根节点进行深度优先遍历DFS能达到的所有堆节点涂成绿色活跃。清除 (Sweep):遍历整个堆把那些没涂色的红色节点不可达的垃圾全部释放。轻松一刻令人崩溃的 C 语言指针声明“23333 哈哈哈哈哈”这是原笔记里非常有灵性的一句留言。由于 C 语言优先级规则的存在阅读极其变态的函数指针声明往往需要利用“右左法则”。比如这个大杀器int (*(*x[3])())[5]。翻译x 是一个包含 3 个元素的数组数组元素是指针指向一个函数该函数返回一个指针该指针指向一个包含 5 个 int 的数组…。如何对抗内存恶魔 Bug内存错误如野指针、越界、重复释放、内存泄漏是 C/C 程序员永远的噩梦。GDB:擅长找因为坏指针导致的崩溃点段错误。Valgrind:终极武器Binary Translator。如果你在写 C 的时候没用过 Valgrind 检查 Leak就像蒙着眼睛在走悬崖。它会在运行时对每一条指令插桩死死盯着越界和泄漏。Lec 20 Dynamic Memory Allocation Advanced Concepts(注这部分在原课堂上主要为上述所有基础概念的代码级落地和性能分析也就是名震天下的Malloc Lab实验的理论支撑篇章纸上得来终觉浅绝知此事要躬行这就是这门课设计的精妙之处。)
写在前面这是本系列系统级编程学习笔记的最终篇。如果说之前的笔记是在榨干 CPU 的算力那么这篇笔记将带你跨越硬件与软件的边界进入操作系统的核心领域。我们将探讨程序是如何响应突发事件的异常与信号、Unix“万物皆文件”的优雅设计以及那令人又爱又恨的malloc究竟是如何在底层变魔术的。Lec 14 Exceptional Control Flow Exceptions and Processes大纲异常控制流 (Exceptional Control Flow, ECF)覆盖了从硬件、操作系统到应用层的各个级别。低级别机制异常 (Exceptions)。硬件和操作系统的结合应对系统事件如缺页、中断、除以零。高级别机制进程上下文切换 (Process Context Switch)- 操作系统和硬件定时器实现。信号 (Signals)- 操作系统软件实现。非本地跳转 (Nonlocal Jumps)-setjmp和longjmp允许程序打破常规的 Call/Return 栈模式直接跨越函数层级跳转类似 C 里的 try-catch 底层原理。系统调用错误处理 (System Call Error Handling)在 Linux 系统编程中如果系统调用失败它通常会返回-1并设置一个全局整数变量errno来指明到底出了什么错。硬性铁律 (Hard and Fast Rule)你必须检查每一个系统级函数的返回状态永远不要假设fork()或者write()会百分之百成功。例外情况只有极少数返回void的函数如exit不需要检查。execve 加载运行程序一张单程票int execve(char *filename, char *argv[], char *envp[])这是一个极其特殊的系统调用它负责在当前进程中加载并运行一个新的程序。夺舍重生它会完全覆盖当前进程的代码段、数据段、堆和栈。保留躯壳但它保留了原有的进程 ID (PID)、已经打开的文件描述符列表以及信号上下文。单程票execve被调用一次如果没有出错它永远不会返回。因为返回地址所在的栈已经被新程序抹除了这也是它令人兴奋的地方。Summary异常 (Exceptions):需要打断标准控制流的事件。可以是外部的键盘中断、网络包到达或内部的缺页故障、段错误。进程 (Processes):操作系统提供的最伟大的抽象之一。它给每个程序一种错觉仿佛自己独占了整个 CPU通过并发上下文切换和整个内存空间通过虚拟内存。Lec 15 Exceptional Control Flow Signals and Nonlocal JumpsLinux Process 层次结构在 Linux 中所有的进程都是一棵树。init(或现代的systemd) 进程是 PID 1它是所有进程的老祖宗负责系统服务。守护进程 (Daemon):在后台静默运行的进程。当用户登录时会创建一个登录 Shell 进程你运行的所有命令如ls,grep都是这个 Shell 的子孙进程。Writing Handlers (编写安全的信号处理程序)信号如CtrlC产生的SIGINT是异步的随时可能打断主程序。编写安全的 Handler 是一门艺术到处都是坑保持极简:最好只设置一个全局标志位Flag然后立刻返回让主程序去处理复杂的逻辑。只调用异步信号安全 (Async-Signal-Safe) 的函数:严禁在 Handler 中调用printf或malloc因为它们内部有锁如果在持有锁时被信号打断Handler 再去请求同一个锁就会导致死锁。保存和恢复errno:避免 Handler 内部的操作覆盖了主程序原本的errno值。阻塞信号以保护共享数据:在修改全局工作队列时暂时阻塞信号防止竞态条件。全局变量声明为volatile:这告诉编译器“这个变量可能在不知不觉中被修改每次都必须去内存里读绝对不准把它优化进寄存器里”Synchronizing Flows to Avoid Races这是SIGCHLD处理程序的经典写法。陷阱信号是不排队的如果同时有 3 个子进程死亡内核可能只会记录一次SIGCHLD。因此必须在循环中使用waitpid(-1, NULL, 0) 0来收割所有已经死亡的僵尸进程Zombie并在操作共享工作列表时使用sigprocmask严密保护。Lec 16 System Level I_OUnix I/O 的哲学万物皆文件在 Linux 系统中文件就是一个 m 个字节的序列。这种极其简单粗暴的抽象造就了 Unix 的伟大无论是磁盘分区 (/dev/sda2)、键盘终端 (/dev/tty)、网络套接字、甚至是操作系统的内核数据 (/proc)全部被抽象成了文件。你可以用同一套 API 去读写发送消息。短计数 (Short Counts)当你要求读取 50 个字节系统却只返回了 20 个字节这就是“短计数”。会发生短计数的地方读取时遇到 EOF从终端读取按行返回读写网络套接字由于网络延迟包不是一次性到达的。最佳实践编写网络程序时永远不能假设read或write一次就能完成必须将它们放在while循环中持续读取。Unix Kernal Open File (核心三个表)为了管理打开的文件内核维护了三种精巧的数据结构这是理解并发和 fork 的基础描述符表 (Descriptor Table):每个进程独有一个。记录了当前进程所有打开的文件描述符 (fd如 0stdin, 1stdout)。里面存放的是指向“打开文件表”的指针。打开文件表 (Open File Table):所有进程共享。记录了文件的当前读写位置 (File Pos) 和引用计数 (refcnt)。V 节点表 (V-Node Table):所有进程共享。包含了文件在磁盘上的实际物理信息类型、大小等。fork() 时的文件共享当调用fork()创建子进程时子进程会完美复制父进程的“描述符表”。这意味着父子进程的 fd 指向了“打开文件表”中的同一个条目它们共享了同一个读写位置。此时文件的引用计数会1。只有当父子进程都执行close()引用计数归零时文件才会被真正释放。Unix I/O vs. Standard I/O vs. RIOUnix I/O:最底层的系统调用 (read,write)。无缓冲速度快但处理短计数和文本行极度麻烦。Standard I/O:C 标准库 (printf,fread)。带有内部缓冲区处理磁盘文件极佳。RIO (Robust I/O):CSAPP 专门编写的安全 I/O 库完美包装了底层调用专为解决网络短计数问题设计。最佳实践准则处理普通磁盘或终端文件用 Standard I/O。在信号处理程序中要求绝对异步安全只能用原始 Unix I/O。在读写网络套接字 (Socket) 时绝对不要用 Standard I/O它的内部缓冲区机制在全双工网络通信中会引发致命的死锁。此时应使用 RIO或等效的现代网络库。拓展阅读推荐Unix 圣经:Advanced Programming in the UNIX Environment (APUE)Linux 圣经:The Linux Programming Interface (TLPI)Lec 17 18 Virtual Memory Concepts SystemsK 级页表 (Multi-Level Page Tables)现代操作系统使用虚拟内存。程序看到的是连续的地址OS 负责将其翻译成真实的物理地址。如果只有一层页表对于 64 位系统来说光是存页表就会耗尽所有物理内存因此引入了多级页表结构一级页表指向二级二级指向三级…… 只有当真正使用到某一块连续内存区域时才去分配对应的下级页表这极大地节省了系统内存完美应对了稀疏分布的地址空间。组织虚拟内存 (Linux VM Areas)Linux 将虚拟内存组织成一个个的“区域 (Area)”比如数据段、代码段、共享库。每一个区域在内核中都有对应的数据结构来管理它的读写权限。比如图片中提到的标志位可以指示这块内存在进程间是私有的还是共享的。Lec 19 Dynamic Memory Allocation Basic Concepts内存分配器的设计挑战没什么好说的C 语言程序员最痛苦的必修课记得free以免内存泄漏开发一个优秀的malloc分配器面临着两个互相对立的终极性能目标吞吐量 (Throughput):疯狂调用malloc和free时系统必须响应得足够快。峰值内存利用率 (Peak Memory Utilization):尽量压榨空间少浪费。万恶之源内存碎片 (Fragmentation)内部碎片 (Internal Fragmentation):分配的块比你实际需要的载荷大。这通常是因为需要“内存对齐”比如强制 8 字节或 16 字节对齐而填充的空白或是为了存放分配器本身的头部管理数据。外部碎片 (External Fragmentation):这更致命。内存中所有的空闲空间加起来足够满足请求但是它们不连续就像被切碎的瑞士奶酪。这也是为什么长时间运行的服务器如果不优化分配策略内存会越来越吃紧的原因。追踪空闲块与偷空间的魔法当调用free(p)时系统怎么知道该释放多少字节要在杂乱无章的内存堆中找到空闲块业界经历了几种迭代隐式空闲链表 (Implicit List):用 Header 记录长度挨个找。显式空闲链表 (Explicit List):在空闲块内部写上指针链起来找。分离适配链表 (Segregated Free List):数组链表按大小分类找。平衡树 (Balanced Tree):用红黑树按大小排序找。细节魔法Header 里的偷空间技巧隐式链表中每个块都需要记录自身的大小还需要 1 个 bit 记录自己是否空闲。难道要多浪费一个字节吗绝不因为内存对齐要求块的大小必须是 8 字节的倍数所以块大小二进制的最后三位一定是 0。系统极其巧妙地借用了最低位的这个0把它变成了 allocated 标志位在读取真实大小时只需要按位与Masking ~0x7把这几位遮蔽掉即可。寻找策略与边界标记 (Finding Policy Coalescing)首次适配 (First Fit):从头找碰到第一个够大的就用容易在堆前部堆积碎木片。下一次适配 (Next Fit):接着上次结束的地方找吞吐量高但容易产生外部碎片。最佳适配 (Best Fit):遍历全表找最接近请求大小的利用率极高但极慢。合并技术 (Coalescing) 与边界标记当释放一块内存时如果左右邻居也是空闲的我们应该把它们融合成一个大块。向右合并很容易通过当前大小跳到下一个 Header但怎么向左看呢计算机科学泰斗 Knuth 发明了Footer (边界标记)技术在每个块的尾部复制一份 Header。这样当前块只需指针往回减一个字就能摸到左边块的 Footer立刻知道它是否空闲并进行双向合并 (Bidirectional Coalescing)显式空闲链表的 LIFO 与地址排序当块释放时它被加入显式链表LIFO (后进先出):直接插到链表头部速度快但容易导致严重的外部碎片。地址排序 (Address-ordered):强行按内存物理地址顺序维护链表。插入慢但实验证明内存利用率极高。终极进化分离适配链表 (Segregated List)如何兼顾极速的吞吐量和极高的利用率现代操作系统给出的终极方案是Seglist。维护一组按 2 的幂次方划分大小的桶1-2, 3-4, 5-8, 9-16…。当需要分配一块内存时直接去对应大小的桶里找。这使得操作时间从线性降低到了对数时间 (O(log N))并且极其逼近“最佳适配Best Fit”的内存利用率。这也是当今高性能内存库如 Google 的tcmalloc的理论基石。垃圾回收标记清除算法 (Mark Sweep GC)不仅是 Java/Go 有垃圾回收C 语言甚至也可以写一个保守的垃圾回收器。系统将内存视为一个有向图寄存器、栈局部变量、全局变量是“根节点 (Root)”。算法分为两步标记 (Mark):顺着根节点进行深度优先遍历DFS能达到的所有堆节点涂成绿色活跃。清除 (Sweep):遍历整个堆把那些没涂色的红色节点不可达的垃圾全部释放。轻松一刻令人崩溃的 C 语言指针声明“23333 哈哈哈哈哈”这是原笔记里非常有灵性的一句留言。由于 C 语言优先级规则的存在阅读极其变态的函数指针声明往往需要利用“右左法则”。比如这个大杀器int (*(*x[3])())[5]。翻译x 是一个包含 3 个元素的数组数组元素是指针指向一个函数该函数返回一个指针该指针指向一个包含 5 个 int 的数组…。如何对抗内存恶魔 Bug内存错误如野指针、越界、重复释放、内存泄漏是 C/C 程序员永远的噩梦。GDB:擅长找因为坏指针导致的崩溃点段错误。Valgrind:终极武器Binary Translator。如果你在写 C 的时候没用过 Valgrind 检查 Leak就像蒙着眼睛在走悬崖。它会在运行时对每一条指令插桩死死盯着越界和泄漏。Lec 20 Dynamic Memory Allocation Advanced Concepts(注这部分在原课堂上主要为上述所有基础概念的代码级落地和性能分析也就是名震天下的Malloc Lab实验的理论支撑篇章纸上得来终觉浅绝知此事要躬行这就是这门课设计的精妙之处。)
