[Note] 程序员的自我修养——第 1 部分简介

Posted on 2022-03-18 In Note Symbols count in article: 6.6k Reading time ≈ 6 mins.

第 1 章温故而知新

Hello World

程序为什么要被编译器编译了之后才可以运行？
编译器在把 C 语宫程序转换成可以执行的机器码的过程中做了什么，怎么做的？
最后编译出来的可执行文件里面是什么？除了机器码还有什么？它们怎么存放的，怎么组织的？
#include <stdio.h> 是什么意思？把 stdio.h 包含进来意味着什么？C语言库又是什么？它怎么实现的？
不同的编译器（Microsoft VC、GCC）和不同的硬件平台（x86、 SPARC、 MIPS、 ARM），以及不同的操作系统（Windows、 Linux、 UNIX、 Solaris），最终编译出来的结果一样吗？为什么？
Hello World 程序是怎么运行起来的？操作系统是怎么裝载它的？它从哪儿开始执行，到哪儿结束？main 函数之前发生了什么？main 函数结束以后又发生了什么？
如果没有操作系统，Hello World 可以运行吗？如果要在一台没有操作系统的机器上运行 Hello Worid 需要什么？应该怎么实现？
printf 是怎么实现的？它为什么可以有不定数最的参数？为什么它能够在终端上输出字符串？
Hello World 程序在运行时，它在内存中是什么样子的？

计算机硬件结构

早期所有设备连在一根总线（BUS）上
南桥（Southbridge）专门处理低速设备，北桥（Northbridge, PCI Bridge）连接所有高速部件
AGP、PCI Express 等诸多总线结构和相应控制芯片
基本结构万变不离其宗：CPU、内存、I/O 控制芯片

SMP 与多核

对称多处理器（SMP, Symmetrical Multi-Processing）：每个 CPU 在系统中所处的地位和所发挥的功能都一样，相互对称
多核处理器（Multi-core Processor）：SMP 的简化版，“被打包”的处理器之间共享比较昂贵的缓存部件，只保留多个核心

系统软件的层次结构

"Any problem in computer science can be solved by another layer of indirection."
接口（Interface）：每个层次之间通信的协议
每个中间层都是对它下面的那层的包装和扩展，使得应用程序和硬件之间保持相对的独立（虚拟机技术）
应用程序编程接口（Application Programming Interface）：什么样的运行库提供什么样的 API，比如 Linux 下的 Glibc 库提供 POSIX 的 API；Windows 的运行库提供 Windows API
运行库使用操作系统提供的系统调用接口（System callInterface），往往以软件中断（Software Interrupt）的方式提供
硬件规格（Hardware Specification）：决定操作系统内核，即驱动程序如何操作硬件，如何与硬件进行通信

操作系统做什么

提供抽象的接口，管理硬件资源
不要让 CPU 打盹
- 多道程序（Multiprogramming）
  - 充分利用 CPU
  - 调度策略粗糙，不分轻重缓急
- 分时系统（Time-Sharing System）
  - 协作模式，每个程序运行一段时间后主动让出 CPU，适合交互式任务
  - 如果一个程序一直霸占着 CPU 不放，操作系统也没有办法，其他程序只能等着
- 多任务（Multi-tasking）系统
  - 操作系统接管所有硬件资源，运行在受硬件保护的级别，应用程序以进程的方式运行在权限更低的级别
  - 每个进程有独立的地址空间，相互隔离
  - 抢占式（Preemptive）：每个进程根据优先级都有机会得到 CPU，操作系统可以强制剥夺 CPU 资源并分配给它认为目前最需要的进程
  - CPU 在多进程间快速切换，造成多进程同时运行的假象，现代操作系统几乎都采用这种方式
设备驱动
- 硬件被抽象成概念
  - UNIX：硬件设备以普通文件的形式访问
  - Windows：图形硬件被抽象 GDI，声音和多媒体设备被抽象成 Directx 对象，磁盘被抽象成普通文件系统
- 硬件细节交给操作系统中的硬件驱动（Device Driver）
  - 驱动程序与内核一起运行在特权级，但二者之间又有一定的独立性，灵活性好
  - 驱动程序通常由硬件生产厂商开发，操作系统开发者提供一系列接口和框架

内存不够怎么办

早期的计算机中，程序直接运行在物理内存上，内存分配策略问题很多：地址空间不隔离、内存使用效率低、程序运行的地址不确定
解决思路：增加中间层，把程序给出的地址看做是一种虚拟地址（Virtual Address），通过某种映射将其转换成实际的物理地址
关于隔离
- 物理地址空间（Physical Address Space）：真实存在的，对于每一台计算机来说只有唯一一个，比如 32 位的机器物理空间就有 2^32 字节（4GB），但只装了 512MB 的内存，那么物理地址的真正有效部分只有 0x00000000 ~ 0x1FFFFFFF
- 虚拟地址空间（Virtual Address Space）：想象出来的，其实并不存在，每个进程都有独立的虚拟空间，且只能访问自己的地址空间，从而做到进程的隔离
分段（Segmentation）
- 把一段与程序所需要的内存空间大小的虚拟空间映射到某个地址空间，操作系统设置映射函数，实际的地址转换由硬件完成
- 做到了地址隔离，超出虚拟空间地址范围的请求会被硬件判断为非法访问
- 物理地址对程序透明，程序不关心物理地址的变化，不需要重定位
- 没有解决内存使用效率的问题：映射以程序为单位，粒度较大，如果内存不足，整个程序被换入换出到磁盘，造成大量磁盘访问
- 根据局部性原理，一个程序在运行时的某个时间段内，只频繁用到一小部分数据，因此更小粒度的内存分割和映射方法效率更高
分页（Paging）
- 把地址空间人为地等分成固定大小的页，每一页的大小由硬件决定，或硬件支持多种大小的页，由操作系统选择决定页的大小
- 目前几乎所有的 PC 上的操作系统都使用 4KB 大小的页
- 把常用的数据和代码页装载到内存中，把不常用的代码和数据保存在磁盘里，当需要用到的时候再把它从磁盘里取出来
- 虚拟空间的页叫做虚拟页（VP, Virtual Page），物理内存中的页叫做物理页（PP, Physical Page），磁盘中的页叫做磁盘页（DP，Disk Page）
- 不同程序虚拟空间的页可以被映射到同一个物理页，实现内存共享
- 当进程需要用到不在内存中的页时，硬件会捕获到这个消息，即页错误（Page Fault），此时操作系统接管进程，负责从磁盘中读出页并装入内存，然后将其与虚拟页建立映射关系
- 每个页可以设置权限属性（谁可以修改，谁可以访问等），而只有操作系统有权限修改这些属性，从而做到保护自己和保护进程
- 虚拟存储的实现需要依靠硬件的支持，几乎所有的硬件都采用一个叫 MMU（Memory Management Unit）的部件来进行页映射，一般集成在 CPU 内部

线程

程序执行流的最小单元，有时被称为轻量级进程（Lightweight Process, LWP）
一个标准的线程由线程 ID、当前指令指针（PC）、寄存器集合和堆栈组成
一个进程由一个到多个线程组成，各个线程之间共享程序的内存空间（包括代码段、数据段、堆等）及一些进程级的资源（如打开文件和信号）
使用多线程的原因
- 某个操作可能会陷入长时间等待，多线程可以有效利用等待的时间，例如等待网络响应
- 某个操作（常常是计算）会消耗大量的时间，多线程可以让一个线程负责与用户交互，另一个线程负责计算
- 程序逻辑本身就要求并发操作，例如多端下载软件 Bittorrent
- 多 CPU 或多核计算机本身具备多线程能力，单线程程序无法全面地发挥计算机的能力
- 相对于多进程应用，多线程在数据共享方面效率要高很多
线程的访问权限
- 可以访问进程内存里的所有数据，甚至包括其他线程的堆栈（如果知道其地址的话，很少见）
- 也拥有私有存储空间，包括栈、线程局部存储（Thread Local Storage, TLS）、寄存器（包括 PC 寄存器）
线程调度与优先级
- 在单处理器对应多线程的情况下，多线程程序轮流执行，每次执行一小段时间（通常是几十到几百毫秒），称为线程调度（Thread Schedule）
- 线程通常拥有至少三种状态，分别是：
  - 运行（Running）：此时线程正在执行
  - 就绪（Ready）：此时线程可以立刻运行，但 CPU 已经被占用
  - 等待（Waiting）：此时线程正在等待某一事件（通常是 I/O 或同步）发生，无法执行
- 线程调度算法
  - 轮转法（Round Robin）：即之前提到的让各个线程轮流执行一小段时间的方法，这决定了线程之间交错执行的特点
  - 优先级调度（Priority Schedule）：决定了线程按照什么顺序轮流执行。线程都拥有各自的线程优先级（Thread Priority)，高优先级的线程会更早地执行，而低优先级的线程常常要等待到系统中已经没有高优先级的可执行的线程存在时才能够执行
- 在 Windows 中，可以通过使用 SetThreadPriority 来设置优先级，而 Linux 下与线程相关的操作可以通过 pthread 库来实现
- 除了用户手动设置，系统还会根据不同线程的表现自动调整优先级。频繁等待的线程称为 IO 密集型线程（IO Bound Thread），很少等待的线程称为 CPU 密集型线程（CPU Bound Thread），前者比后者容易得到优先级的提升
- 饿死（Starvation）：一个线程优先级较低，在它执行之前，总是有较高优先级的线程试图执行，因此它始终无法执行
- 为了避免饿死现象，调度系统常常会逐步提升那些等待了过长时间的得不到执行的线程的优先级
可抢占线程和不可抢占线程
- 在不可抢占线程中，必须手动发出一个放弃执行的命令，才能让其他的线程得到执行，包括两种情况：
  - 当线程试图等待某事件时（I/O 等)
  - 线程主动放弃时间片
- 不可抢占线程调度的时机是确定的，可以避免一些因为抢占式线程里调度时机不确定而产生的问题
Linux 的多线程
- Linux 对多线程的支持颇为贫乏，并不存在真正意义上的线程概念
- Linux 将所有的执行实体（无论是线程还是进程）都称为任务（Task），每一个任务概念上都类似于一个单线程的进程，具有内存空间、执行实体、文件资源等；不过，不同任务之间可以选择共享内存空间，因而在实际意义上，共享了同一个内存空间的多个任务构成了一个进程，这些任务也就成了这个进程里的线程
- 创建一个新的任务有以下方法
  - fork：复制当前进程，和原任务共享一个写时复制（Copy on Write, Cow）的内存空间，因此速度非常快
  - exec：使用新的可执行映像覆盖当前可执行映像，可以在 fork 产生新任务之后调用，用于产生新任务
  - clone：创建子进程并从指定位置开始执行，用于产生新线程（选择共享当前进程的内存空间和文件等）
线程安全
- 原子操作
  - 单指令的操作称为原子的（Atomic），不会被打断的，很多体系结构都提供了一些常用操作的原子指令
  - 仅适用于比较简单特定的场合，在复杂的场合下（比如保证复杂数据结构更改的原子性）需要更加通用的手段：锁
- 同步与锁
  - 同步（Synchronization）：在一个线程访问数据未结束的时候，其他线程不得对同一个数据进行访问
  - 锁（Lock）：一种非强制机制，每一个线程在访问数据或资源之前首先试图获取（Acquire）锁，并在访问结束之后释放（Release）锁，在锁已经被占用的时候试图获取锁时，线程会等待，直到锁重新可用
  - 二元信号量（Binary Seraphore）：最简单的一种锁，只有两种状态：占用与非占用，适合只能被唯一一个线程独占访问的资源
  - 多元信号量（简称信号量，Semaphore）：对于允许多个线程并发访问的资源是很好的选择，一个初始值为 N 的信号量允许 N 个线程并发访问：
    - 访问资源时首先获取信号量，将信号量的值减 1，如果值小于 0，则进入等待状态，否则继续执行
    - 访问完资源后，线程释放信号量，将信号量的值加 1，如果值小于 1，唤醒一个等待中的线程
  - 互斥量（Mutex）：和二元信号量很类似，资源仅同时允许一个线程访问，但不同的是：
    - 信号量在整个系统可以被任意线程获取并释放，即同一个信号量可以被一个线程获取之后由另一个线程释放
    - 而互斥量则要求哪个线程获取了互斥量，哪个线程就要负责释放这个锁，其他线程越俎代庖去释放互斥量是无效的
  - 临界区（Critical Section）：比互斥量更加严格的同步手段。临界区的锁的获取称为进入临界区，锁的释放称为离开临界区。临界区和互斥量与信号最的区别在于：
    - 互斥量和信号量在系统的任何进程里都是可见的，即一个进程创建了一个互斥量或信号量，另一个进程试图去获取该锁是合法的
    - 而临界区的作用范围仅限于本进程，其他的进程无法获取该锁
  - 读写锁（Read-Write Lock）：对于读取频繁而仅仅偶尔写入的情况更加高效。同一个读写锁有两种获取方式，共享的（Shared）或独占的（Exclusive）：
    - 当锁处于自由状态时，试图以任何一种方式获取锁都能成功，并将锁置于对应的状态
    - 当锁处于共享状态时，其他线程以共享的方式获取锁仍然会成功，此时这个锁分配给了多个线程；如果其他线程试图以独占的方式获取已经处于共享状态的锁，那么它将必须等待锁被所有的线程释放
    - 当锁处于独占状态时，将阻止任何其他线程获取该锁，不论它们试图以哪种方式获取
    读写锁状态以共享方式获取以独占方式获取
    
    自由成功成功
    
    共享成功等待
    
    独占等待等待
  - 条件变量（Condition Variable）：作用类似于一个栅栏，可以让许多线程一起等待某个事件的发生，有两种操作：
    - 等待条件变量，一个条件变量可以被多个线程等待
    - 唤醒条件变量，此时某个或所有等待此条件变量的线程都会被唤醒并继续执行
- 可重入（Reentrant）与线程安全
  - 一个数被重入，表示这个函数没有执行完成，由于外部因素或内部调用，又一次进入该函数执行
  - 一个函数要被重入，只有两种情况：
    - 多个线程同时执行这个函数
    - 函数自身（可能是经过多层调用之后）调用自身
  - 一个函数被称为可重入的，表明该函数被重入之后不会产生任何不良后果
  - 一个函数要成为可重入的，必须具有如下几个特点：
    - 不使用任何（局部）静态或全局的非 const 变量
    - 不返回任何（局部）静态或全局的非 const 变量的指针
    - 仅依赖于调用方提供的参数
    - 不依赖任何单个资源的锁（mutex 等）
    - 不调用任何不可重入的函数
  - 可重入是并发安全的强力保障，一个可重入的函数可以在多线程环境下放心使用
- 过度优化
  - 即使合理地使用了锁，也不一定能保证线程安全，这是源于落后的编译器技术已经无法满足日益增长的并发需求
  - 很多看似无错的代码在优化和并发面前又产生了麻烦，例如：
    - 编译器为了提高速度将一个变量缓存到寄存器内而不写回（可以使用 volatile 关键字阻止）
    - CPU 动态调度以及编译器优化可能交换指令的顺序（volatile 只能阻止编译器调整顺序）
  - 现在并不存在可移植的阻止 CPU 换序的方法，通常情况下是调用 CPU 提供的 barrier 指令，阻止 CPU 将该指令之前的指令交换到 barrier 之后，反之亦然
三种线程模型
- 一对一模型
  - 对于直接支持线程的系统是最为简单的模型，一个用户使用的线程唯一对应一个内核使用的线程（但反过来不一定）
  - 一般直接使用 API 或系统调用创建的线程均为一对一的线程，例如：
    - 在 Linux 里，使用 clone（带有 CLONE_VM 参数）产生的线程
    - 在 Windows 里，使用 API CreateThread
  - 优点
    - 用户线程和内核线程一致，线程之间的并发是真正的并发，一个线程因为某原因阻塞时，其他线程执行不会受到影响
    - 让多线程程序在多处理器的系统上有更好的表现
  - 缺点
    - 由于许多操作系统限制了内核线程的数量，因此一对一线程会让用户的线程数量受到限制
    - 许多操作系统内核线程调度时，上下文切换的开销较大，导致用户线程的执行效率下降
- 多对一模型
  - 将多个用户线程映射到一个内核线程上，线程之间的切换由用户态的代码来进行
  - 优点
    - 相对于一对一模型，多对一模型的线程切换要快速许多
    - 线程数量几乎无限制
  - 缺点
    - 如果其中一个用户线程阻塞，那么所有的线程都将无法执行，因为此时内核里的线程也随之阻塞了
    - 在多处理器系统上，处理器的增多对多对一模型的线程性能也不会有明显的帮助
- 多对多模型
  - 结合了多对一模型和一对一模型的特点，将多个用户线程映射到少数但不止一个内核线程上
  - 一个用户线程阻寒并不会使得所有的用户线程阻塞，因为此时还有别的线程可以被调度来执行
  - 对用户线程的数量也没什么限制
  - 在多处理器系统上，多对多模型的线程也能得到一定的性能提升，不过提升的幅度不如一对一模型高