本文是学习宋宝华老师《Linux 进程、线程和调度》视频的笔记。视频中相关的代码位于 21cnbao/process-courses。

第一部分

  1. 进程是资源分配的单位；线程是调度的单位。

  2. 进程控制块 PCB：Linux 中为结构体 task_struct。

  3. 如何组织系统中的所有 task_struct：同时使用了链表、树、哈希表等数据结构，以适应不同的需求场景（以空间换时间）。

  4. 进程生命周期：Linux 中的进程有六种状态：就绪、运行、浅度睡眠、深度睡眠、僵尸、暂停。

    • 就绪：进程刚被 fork 出来或者处于可以被调度的状态。
    • 运行：真的有在被 CPU 执行呢。
    • 睡眠：正在等待资源（阻塞）。深浅睡眠都可以在资源就绪时唤醒，浅度睡眠还可以在收到信号时唤醒。深度睡眠不响应信号，适用于某些需要避免无限递归的情形，例如发生 page fault 时。
    • 僵尸：进程刚死的时候，其所依附的资源已经释放了，但是 task_struct 还没有消失，目的是让父进程有机会通过调用 wait4() 获取子进程的死因。如果父进程总是不调用 wait4()，那么子进程会继续处于僵尸状态，且没有办法用信号 9 等杀死子进程，此时释放僵尸进程的唯一方法是把父进程也干掉。
    • 暂停：收到 STOP 信号，如被 Ctrl+Z 或 gdb 调试时。

  5. 内存泄漏：不是指进程死了，内存没释放；而是指进程活着，运行越久，耗费内存越多。

  6. fork()：父进程返回子进程的 PID；子进程中返回 0；失败返回 -1。

第二部分

  1. fork()：调用后操作系统为子进程创建 task_struct，但最开始其中的资源相关的字段与父进程的 task_struct 中一样（复制了一份），除了 mm，它需要进行写时复制（Copy-On-Write）。

  2. 写时复制：最开始，MMU 负责映射进程的虚拟地址 virt1 到物理地址 phy1 上，此时内存的权限是 R+W。调用 fork() 之后，父子进程的 virt1 依然映射到物理地址 phy1 上，但是将对应的页表权限修改为只读，在此之后，无论是父进程还是子进程，在试图修改内存时都会导致 CPU 收到缺页中断。在处理此中断时，Linux 修改写内存的进程的页表，将 virt1 指向新分配的内存，物理地址为 phy2，并将 phy1 中的内容复制到 phy2 中，之后两个进程的页表权限都恢复成 R+W。

  3. vfork()：会阻塞父进程；新创建的 task_struct 中的 mm 直接指向父进程 task_struct 中的 mm。

  4. pthread_create()：Linux 创建线程的 API，最终是调用了 clone()。新创建的 task_struct 中所有资源相关的字段直接指向父进程 task_struct 中的对应字段。

  5. clone()：创建 task_struct 的底层函数，可以通过指定哪些资源要和父进程共享，那些资源需要复制一份新的来创建“人妖（不完全是进程也不完全是线程）”。

  6. PID 和 TGID：在内核看来，每个 task_struct 有一个不同的 PID，同一个进程的所有线程共享一个相同的 TGID（可能是 Thread Group IDentifier？）。在用户空间看来，同一个进程的所有线程都有相同的 PID。搞这么麻烦是为了遵循 POSIX 标准。

  7. 托孤：父进程死了之后，子进程沿着进程树向上寻找 subreaper，如果找到了就成为它的子进程，如果没找到就成为 1 号进程的子进程。一个进程可以通过系统调用把自己声明为 subreaper。

  8. 睡眠：使用等待队列实现。

  9. 进程 0 和 1：1 号进程是由 0 号进程创建出来的，之后 0 进程退化成 IDLE 进程，会将 CPU 置于一个省电的模式，直到中断到来。

第三部分

  1. 吞吐 vs 响应：提高响应需要更频繁地进行上下文切换，这会导致 cache 命中率降低，从而降低吞吐。

  2. 内核编译选项：menuconfig → Kernel Features → Preemption Model 中可以选择抢占模型（Server / Desktop / Low-Latency Desktop），如果打上了 RT 补丁，还会出现一个选项叫做 Real-Time，见下文。

  3. 进程的类型：I/O 消耗型 vs CPU 消耗型。I/O 消耗型任务通常影响用户体验，它对调度到的时长和 CPU 的算力不敏感，但是需要被及时调度到，因此通常优先级要高于 CPU 消耗型。

  4. ARM big.LITTLE：大小核分别用于上面的两种进程。

  5. Linux 2.6 早期的调度器：0~99 优先级是 RT 的，100~139 优先级是非 RT 的。优先级数字越低，优先级越高（这是在内核看来的；用户空间对进程优先级进行设置的时候是反过来的）。RT 进程全部跑完了才会调度非 RT 的进程（后期版本可以配置 RT 进程在一个周期内最多占用的 CPU 时间，默认通常 950000us/1000000us = 95%）。

    • RT 的两种策略：
      • SCHED_FIFO：FIFO 表示 First In First Out。对不同优先级的进程，总是运行优先级高的进程，直到该进程自己放弃 CPU，下一个优先级的进程才能跑。对于同等优先级的进程，先进先出。
      • SCHED_RR：RR 表示 Round Robin。对不同优先级的进程，同样总是运行优先级高的进程，直到该进程自己放弃 CPU，下一个优先级的进程才能跑。但是对于同等优先级的进程，轮转调度。
    • 非 RT 的策略： 不同的优先级（对应一个 nice 值）的进程都同时参加轮转。高优先级进程的优势：1. 更多的时间片；2. 调度时可以抢占低优先级进程。运行的时候，Linux 在 ±5 范围内动态调整进程的 nice 值，越是 I/O 消耗型任务，nice 值变得越低（优先级变高）；越是 CPU 消耗型任务，nice 值变得越高（优先级变低）。

      有一个工程师，中午不睡觉认真干活，不好意思优先级降低 1，动态 nice 值 +1；下午认真干活，优先级降低 2；晚上还加班，优先级降低 3；周末还来，优先级降低 5。 你中午睡午觉，优先级 +1；下午打酱油，优先级 +2；明天 11 点钟才出现，优先级增高 3；星期五就找不到人了，优先级直接升高 5。

  6. 完全公平调度 CFS：取代了原先的 SCHED_NORMAL，即非 RT 策略。优先级越高，virtual runtime 增长越慢。每次调度通过红黑树，选择 virtual runtime 最小的任务来运行。这样一来，假设有两个优先级相同的进程，分别是 I/O 消耗型和 CPU 消耗型，前者喜欢睡眠，导致每次调度到之后其 virtual runtime 只增加了一点点，而后者运行完了整个时间片，所以其 virtual runtime 增加的比前者多（即便二者优先级相同，virtual runtime 增加的速率是相同的），这样就完成了上述动态 nice 值调整的功能。

第四部分

  1. 负载均衡：Linux 可以运行在有多个核的 CPU 上，会在各个核心上进行负载均衡，每个核上的调度算法都如前文所述。task_struct 可以在各个核之间 push / pull。首先保证 RT 任务分配到核心。对于普通进程（SCHED_NORMAL），会周期性地检查各个核心的负载情况，并进行负载均衡；当某个核没有任务需要执行了，即将运行 IDLE 进程前，也会尝试从其他核获取任务；调用 fork() 和 exec() 时也会将 task_struct 推送到最空闲的核上去运行。

  2. Affinity: 亲和力。可以通过掩码指定线程允许运行的 CPU；可以在线程运行的代码中主动设置，也可以利用应用程序（如 taskset）在线程运行时设置。

  3. 中断的负载均衡：对于硬中断，设置 /proc/irq/<XXX>/smp_affinity，可以指定一个处理某中断所使用的核心。对于软中断，设置 /sys/class/.../queues/.../rps_cpus，可以指定多个用于处理某软中断的核心（这是 RPS 补丁的功能，原先的行为是软中断也要在原来的那一个核心上运行）。

  4. cgroup：进程的分群。这是一种分层调度，先在群之间完全公平调度，再在群内部完全公平调度。在 /sys/fs/cgroup/cpu/ 下创建一个文件夹即可新建一个 cgroup，新文件夹中会自动创建相应的文件，修改这些文件即可操作 cgroup，如修改权重、将进程加入 cgroup 等。cgroup 的另一个用途是设置 cgroup 的 period 和 quota（完全类似于前文所述的可以对 RT 进程设置最大使用率），quota 可以比 period 大，这在多核的情况下才有意义。Android 和 docker 中利用了/可以使用 cgroup 功能。

  5. 硬实时：可预期性——高优先级的实时任务从被唤醒/创建到被执行，这之间的时间不超过一个确定值。cyclictest 工具可以测试系统的实时性。

  6. 不可抢占的时机：Linux 系统运行的时间可分为 1. 中断、2. 软中断、3. 进程；只有在进程上下文中才可以调度，特别地，若在进程中获取了 spin_lock，则该 CPU 上也不可调度。即，只有在进程上下文且未持有 spin_lock 时才可以调度，其他时间不可调度。无论是在中断还是软中断的处理函数中，或是进程持有 spin_lock 期间，唤醒的进程都不能调度，即使它是高优先级的 RT 进程。

  7. 中断和软中断的唯一区别：软中断中可以中断，中断中不能再中断（从 Linux 2.6.32 起不再允许中断嵌套）。

  8. PREEMPT_RT 补丁：1. spin_lock 变成了 mutex、2. 实现了优先级继承协议（用于应对优先级反转问题）（已经 merge 成为 Linux 自带的功能了）、3. 中断线程化、4. 软中断线程化。这样就将前文所述的不可抢占时机都变成了可以抢占的，仅剩下一些零星的、很短暂的不可抢占的时机，从而使 Linux 支持硬实时。