再次入门进程

os
asm, c, cpu

这是对 Operating System: Three easy pieces 一书和现代操作系统-原理与实践的结合阅读和实践记录, 第一篇看进/线/纤程部分

0x00. 序章

引言提到的书的中文版叫”操作系统导论”, 感觉这个名字翻译的确没有原名好, 听起来有些学究的感觉, 封面也不如原本的黑色 cool, 然后我的具体操作环境基于 Ubuntu20/21 , 关于 OS 的背景可简要回顾在线 slide

PS: 教材依赖的 code/lib/homework 在参考资料可下载, 后续不再复述, 中文版里缺乏了部分习题和说明, 原版才有.

为何要接触进线程?

书中提到的设计与抽象角度肯定是一个主要方面, 但既然是再次入门, 还是得从不同的角度来理解一下, 首先还是从简单的单处理器开始, 之前提到过一个关键概念就是”程序 = 状态机“, OS 对程序而言, 就是 syscall

几个小实验, bash 中同时执行多个进程

1
2
3
4
5
6
7
8
./cpu a & ./cpu b & ./cpu c & # 模拟最简单的多进程

# 然后看看 memory 的情况, 我们启动两个进程, 要求开辟一个新的空间, 那么得到的虚拟地址会一样么
# 默认OS 开启了地址随机化, 修改为0代表关闭 (2是默认)
echo 0 > /proc/sys/kernel/randomize_va_space
# 这样运行两个进程后可看到输出相同的"虚拟地址
(pid=440144) addr pointed to by p: 0x55945b89e2a0
(pid=440145) addr pointed to by p: 0x55a08bb4b2a0

mem.c 的代码

1
2
3
4
5
6
7
8
9
10
int main(int argc, char *argv[]) {
    int *p;
    p = malloc(sizeof(int));
    assert(p != NULL);
    printf("(%d) addr pointed to by p: %p\n", (int) getpid(), p);
    *p = atoi(argv[1]); // assign value to addr stored in p

    }
    return 0;
}

关于 io, 核心得想一下文件创建和读取的流程, 以及为何需要关闭文件 close(), 不调用会怎么样 (close 的目的是确保 fd 释放, 以及避免内存中的写缓冲数据没有正常进入 flush 流程, 否则在程序退出时, 可能才会刷盘)

0x01. 什么是进程

OS 提供最基础的抽象就是”进程“, 简单来说也是对”运行中的程序/任务“的抽象, 1960年就提出来了

从这章开始, 会反复提到 “机制 –> 策略“ 的概念, 个人觉得这两个词本身就很抽象, 还容易记反关系. 我一般用”接口 –> 实现“, 或者是 “抽象 –> 具体“ 这样来记忆理解, 或者是 “What (做什么) –> How (怎么做)” 的过程, 当然这样的类比不一定严谨, 但是我觉得总比”入门”就记错或者纠结名词本身要好得多.

然后在 PA(计算机原理) 课程里我们就学到了 “计算” 本身是一个简单的状态机, 再简单一点就是一个读取指令 –> 不断执行的过程, 所以计算的过程本身也依赖存储器 (也就是书中提到的”寄存器+PC”), 然后这里先插入了进程的几个核心 API, 关键三个:

  • create
  • destroy
  • wait/suspend

下面讲进程 create 的例子, 这个对破开”进程”的迷雾确很关键. 进程到底是啥, 如何启动的: 最简单的理解就是它也就是一个磁盘文件(例如 a.out 被存储在磁盘上), 执行 ./a.out 的时候把它加载到内存中, 除此之外 create 会分配它特有的一些堆栈空间 + 寄存器, 最后等待 OS 把 cpu 资源/控制权给自己开始运转, 这就完成了一个最简单的进程启动过程.

Switch Context

另外上下文(context) 到底是什么呢, 在 xv6-OS 的实现里, 它其实也很简单, 就是一个结构体, 然后里面放了常见的 8 个寄存器 (包括 esp/ebp/ebx 等), 所谓切换上下文, 也就是对应的至少把这 8 个寄存器的状态给存起来, 之后切回来再继续执行. 下面是 xv6 切换上下文的核心汇编, 也不多: (这里省略了 PC 的保存/恢复, 因为它一般不算普通寄存器)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
switch:
# Save old regs
movl 4(%esp), %eax # put old ptr into eax(return value reg)
popl 0(%eax) # save the old IP
movl %esp, 4(%eax) # and stack
# 其它通用寄存器
movl %ebx, 8(%eax) # mov [eax + 8], ebx
movl %ecx, 12(%eax)
movl %edx, 16(%eax)
movl %esi, 20(%eax)
movl %edi, 24(%eax)
movl %ebp, 28(%eax)

# Load new regs
movl 4(%esp), %eax # put new ptr into eax
# 后进先出, 从 ebp 开始弹栈
movl 28(%eax), %ebp
movl 24(%eax), %edi
movl 20(%eax), %esi
movl 16(%eax), %edx
movl 12(%eax), %ecx
movl 8(%eax), %ebx
# stack is switched here
movl 4(%eax), %esp
pushl 0(%eax) # return addr put in place

ret # finally return into new ctxt

除了保存上下文, 我们还需要整体的思考, 进程是如何进行上下文切换的呢? 一个进程在用户态, 不能施展魔法就进入了保存上下文的状态, 那么这里主要是通过 “中断“ & “syscall“ 两个方式进入内核的, 如图:

image-20220408111944381

作业

这里开始有了 Homework, README 里有详细说明, 第一个 py 程序是./cpu-intro/process-run.py, 参数可以连写, ./process-run.py -cpl 1:3, 这个程序目的就是简单的作为一个进程模拟器, 来方便我们实操一些实验功能:

  • 自定义的使用 CPU (可指定当前进程需要执行的指令数)
  • 发出 I/O 请求, 并可设置 IO 占比 (这里假定 IO 发起和结束同样占用1条 CPU 指令)
  • 轻松模拟多个进程, 并通过顺序调整调度顺序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# ./process-run.py -cpl 5:60,1:5,2:80 # 模拟三个进程, 并安插部分IO占比
Time        PID: 0        PID: 1        PID: 2           CPU           IOs
  1         RUN:io         READY         READY             1
  2        WAITING        RUN:io         READY             1             1
  3        WAITING       WAITING       RUN:cpu             1             2
  4        WAITING       WAITING       RUN:cpu             1             2
  5        WAITING       WAITING          DONE                           2
  6        WAITING       WAITING          DONE                           2
  7*   RUN:io_done       WAITING          DONE             1             1
  8*        RUN:io         READY          DONE             1
  9        WAITING   RUN:io_done          DONE             1             1
 10        WAITING          DONE          DONE                           1
 11        WAITING          DONE          DONE                           1
 12        WAITING          DONE          DONE                           1
 13        WAITING          DONE          DONE                           1
 14*   RUN:io_done          DONE          DONE             1
 15        RUN:cpu          DONE          DONE             1
 16        RUN:cpu          DONE          DONE             1
 17        RUN:cpu          DONE          DONE             1

Stats: Total Time 17
Stats: CPU Busy 11 (64.71%)
Stats: IO Busy  11 (64.71%)

Q1: 先来看 Q2/Q3, 分别设置两个进程参数 4:100,1:0 和 1:0,4:100 (默认 IO 等待时间为 5)

  1. 对前者, p0 直接占用 4 cpu 时间, 然后 p1 需要占用 1 + 5 + 1 的时间, 总耗时 11
  2. 对后者, 则 p0 占用 1 发出 io 后让出, p1 使用 4 cpu, 然后 p0 还需等 1, 然后结束 io, 总 1 + 4 + 1 + 1 = 7

Q2: 调整-S/-I改变 I/O 时 OS 的做法, 前者控制是 IO 发生时否切换上下文, 后者控制 IO 完成后优先做什么, 那 3:0,5:100,5:100,5:100 -I IO_RUN_LATER 的意思是什么呢?

  1. p0 总执行三次 io, 首先执行一次然后让出 cpu, 然后 p1/p2/p3 依次执行 5 次 cpu, 最后 p0 执行完剩余 io 操作, 总耗时 31
  2. 如果换成IO_RUN_IMMEDIATE, 那么就会优先执行 IO 的进程, 也就是说 p0 会连续执行 3 次 io 操作, 中间时间其 3 进程工作

这几个例子是让大家思考进程/任务执行的优先级问题, 如何处理 IO 操作对提高 OS 资源利用率尤为重要, 理想状态期望 CPU 能一直都在干活.

0x02. 初探进程 API

这里说的 API 指的是 fork(), wait(), 以及exec()三个兄弟, 最关键的是 fork()

1. fork()

首先, 它在 linux 中语义是 “为调用 fork 的进程创建一个一模一样的新进程“ (与 Github 的 fork 是一样的意思)

它是 linux 下最经典的创建进程函数 (在 windows 中创建进程的需传入大量参数), 但是在 Linux下是非常简单的无参函数, 直接返回子进程 pid/0, 简单的背后本质是 OS 帮忙做了不少事, 理解 fork() 有几个关键点:

  • 子进程从何处开始执行 (假设父进程是从 main 函数开始)
  • 子进程如何从父进程拷贝, 又是如何分离的?
  • 父子进程执行代码的顺序和关联 (读写同一个文件会如何?)
  • 父子进程是否会共享数据? (内存/文件)

COW (写时复制)

  1. 早期 fork() 实现就是直接把父进程完整拷贝一份, 存在两个主要问题
    • 性能弱: 父进程使用内存
    • 效率低: 指的是子进程如果调用 exec() 类函数, 花了大功夫拷贝的内存就作废了 (无用功)
  2. 当前 fork() 思路: 只复制内存映射/指针, 不会真正拷贝内存
    • 性能提高: 一条映射至少对应到一个 4k 的内存 page, 维护成本降低为映射表
    • 效率提升: 调用 exec() 的情况时, 也就修改映射即可

那方案 2 用后, fork() 还有弊端么? 主要有二

  1. 可扩展性差 (详见 spawn)
  2. 组合性弱 (例如 fork + pthread 不可组合)

PS: 关于 COW 的原理, 之后单独抽一篇文章来描述 (结合文件系统/不同 COW 实现)

2. wait()

也可以简单理解为程序语言中的 sleep()/Object.wait() 的底层调用, 但要注意的是 wait() 和 sleep() 仍然有很大区别, 是什么呢? man wait 就能知道了, 它是专门用来等子进程结束操作的, sleep() 挂起后没有其他保障

wait, waitpid, waitid - wait for process to change state

The wait() suspends execution of the calling thread until one of its children terminates. The call wait(&wstatus) is equivalent to waitpid(-1, &wstatus, 0)

The waitpid() suspends execution of the calling thread until a child specified by pid argument has changed state. By default, waitpid() waits only for terminated children, but
this behavior is modifiable via the options argument, as described below

其他没有太多需要说的, 等 homework 再巩固

3. exec()

和 fork() 组合使用的执行函数, 给指定进程执行一个单独的程序, 另外还有一个很关键的作用 —- exec() 加载完可执行文件后会 reset 地址空间 (也就是如果 fork 拷贝的父进程空间在这会全部失效)

扩展知识

在许多其他书(LKD, 深入理解 Linux 内核等)里容易看到举例了许多fork/exec 家族的接口, 这是为何呢? 原因就是 fork() + exec() 的原生实现性能较差, 对用户极致的简洁的同时也会给 OS 带来更大的复杂度, 所以引出了一些必须了解的替代品

  1. vfork():

    • 核心是 share, 而不是拷贝, 相比现代的 fork(), 它连内存映射都不拷贝, 直接共享父进程的地址
    • 可保证子进程先运行, 不再无序

    最早是为了优化 fork() 的完全拷贝内存时的性能, 现在因为 fork 已经被大幅优化, 而且共享地址容易产生安全问题 并不推荐使用 vfork 了

  2. spawn(): 相当于 fork + exec 的组合

    • 优点: 可扩展性/性能更好
    • 缺点: 耦合了 exec, 不如原本拆分开灵活

  3. clone(): 进阶版的 fork(), 可选择的拷贝/不拷贝内存(地址)

    • 优点: 定制化版本的 fork, 相当于带参/选项的 fork.
    • 缺点: 接口更复杂, 部分拷贝容易出错

Homework & Test

1. 下面的代码执行后会输出多少个+, 为何?
1
2
3
4
5
6
7
8
9
10
11
12
int main(void){
   int i;
   for(i=0; i<2; i++){
      fork();
      printf("+"); // 末尾可加上'\n'
   }

   wait(NULL);
   wait(NULL);

   return 0;
}

0x03. 初探线程

上面大体说了进程的核心点, 那么自然的大家都知道了现代 CPU/程序语言都常以线程为调度分配单位, 那线程的诞生和上下文是什么样的呢?

先看看进程的不足:

  1. 创建进程开销较大, 就算使用 COW 只拷贝内存映射, 也包括了 (代码段 + 数据段 + 堆 + 栈等)
  2. 进程间通信(IPC)开销更高 (缘于进程的隔离性更强)
  3. 进程内部无法直接并行化

然后在 LKD 和经典书籍上已经以 Linux 为例介绍了常见的线程: “轻量级的进程“ or “轻量级的运行时抽象“

  1. 一个进程内可有多个线程, 共享静态代码块/数据段部分 + 堆空间 + 地址空间 (这样线程交互比 IPC 方便得多)
  2. 线程只包含”运行时“ (动态)的状态和独立空间 (寄存器 + 栈 + 调度信息)
image-20220411184909911

在这先停下来思考, 为何线程要独享栈, 而共享堆呢? 只是因为栈空间小而堆大么?

  • 线程间也有频繁的数据共享/交互, 最常见的方式就是通过堆空间的共享, 这样性能快 (另一个常见方式是发消息, 更安全)
  • stack 主要存放的都是自动释放变化很多的变量/函数调用, 共享的话多个线程访问则非常乱

改变

到线程时代, 它就变成了 CPU 调度的基本单位, 一个进程内的多个线程, 可以在不同的 CPU 上同事执行, 维护自己的状态, 此时比起之前只有进程的上下文切换, 现在更多的就是 thread context switch了 (另外, 如果每个进程只有1个线程, 那切换线程, 其实就是在切换进程了), 而且因为 Linux 中的线程都有自己的 task_struct, 所以实际切换进程和线程开销差别并不大. (win 则很大)

思考题:

  1. 位于同一个进程内的线程切换, 和两个不同进程的线程切换, 有区别么?
  2. 有了线程上下文切换后, 进程上下文切换还需要保留么, 意义是什么?
  3. 假设每个进程只有1个线程, 此时线程上下文切换和进程切换有啥区别, 如何判断会发生哪一个?
  4. 为何进程上下文切换需要刷新 TLB, 不刷新会怎么样, 有办法优化么?

0x04. 线程 API

类似进程有常见的 API, 线程自然也有创建/暂停/退出等操作, 这里以 pthreads 为代表, 关注核心的:

  • create:
  • join: 这是线程特有的一个操作, A 线程可等待 B 线程执行完成后, 获取它的结果合二为一? 如果 fork() 是由一生二, 那么可简单理解 join 就是它的逆向操作

TLS (Thread Local Storage)

常见于高级语言中的 ThreadLocal 的底层实现, 也就是除了栈这种不可控的私有区域外, 扩展的线程私有存储.

0x05. 初探协/纤程

其实从 “进程 —> 线程” 的过程和历史, 就利于我们进一步思考现在热门的 “协程/纤程”, 而类似 linux 中我们可以把线程称为 “轻量级进程”, 一般也可以把由用户态创建的协/纤程称为 “用户态线程“ (与之对应的就是内核态创建的线程)

在讨论协/纤程前, 先继续看看线程调度的历史, 你会发现其实最早就有了前者的”多对一”线程映射模型: 把多个用户态线程映射到1个内核态线程. (现在已经被主流 OS 弃用, 但是它就是协程的本质)

那么最常见的1对1的线程模型的局限性自然也很明显, 就是在有些场景下存在:

  1. 内核线程数过多, 申请/切换/调度开销水涨船高
  2. web 请求类线程“生命周期”极短, 却仍要触发内核上下文切换
  3. 用户无法控制和选择自定义的调度策略

那么 fiber/corontine 这样的用户态线程库的诞生, 其实就是重新在被 OS 抛弃的多对一模型上, 重新发挥它的价值的体现.

在常见 OS 中的底层体现:

  1. Linux: 底层支持是 ucontext (包括创建/切换/保存, 每个 ucontext 可视为一个纤程)
  2. Windows: 底层提供 Fiber 库, 命名更加见名知意 (createFiber/switchFiber 等), 还原生支持纤程的 local storage (FLS)

那为啥大家常听到的程序语言 (go/lua/c++/rust) 等都说的是”协程“呢, 这里可以看做是程序语言对 OS (纤程)的一种支持/封装, 这有两个原因:

  1. 因为 OS 中提供的都只是一个个单独的 api, 你并不能直接通过 go func(xx) 这样简单的使用它, 就像 sync 这样的关键字/管程, 本质也是对底层 OS 的同步原语的大幅封装
  2. 因为用户态线程内核其实是不感知的, 它就像一段用户写的普通程序代码, 那么各个语言自己实现它和选择合适的调度测试, 而不一定直接使用 OS 提供的默认实现, 也就不足为奇了

Homework

  1. 以 Linux 为例, 使用纤程 api 实现生产消费模型的代码和性能对比

0x06. 调度的诞生

上面两节简单说了进程的基础知识, 以及进程切换的核心流程, 那么这节主要是探讨清楚两个问题:

  1. 为何进程切换上下文需要用户态切到内核态, 增加了不少流程和开销? 如何减少抽象的性能代价
  2. 操作系统也是程序, 那么如何在运行普通进程时, 还能保留它对 CPU 的最高控制权?

Q2 其实也是 Q1 的部分解释, 如果一个进程运行后可以无限的霸占 CPU 资源, 做任何操作, 那 OS 很容易就乱套失控了. 就像公司也一样会遇到这样的问题, 容易想到的是建立一个 “权限分离“ 机制, 普通员工只能访问普通文件/楼层, 而高管才能访问机密/核心的信息, 普通员工要访问机密信息, 得得到特殊的授权. 这对应到 OS 中, 最简单的体现就是 “user mode” & “kernel mode” (用户/内核态)

Trap (下陷)

类似普通工卡和管理员工卡需要特殊的”授权“, OS 里把这样切换的机制称之为 trap, 而我们常说的 syscall/POSIX API, 算是封装给用户层面的调用, 在调用 read()/write() 接口的时候, OS 会自动执行特定的 trap 指令从而进行提权/授权, 然后切换到内核态, 完成操作后再 re-trap 降权回来(用户态) [另: trap 相关操作一般由汇编来实现, 从 trap table 读取主要信息]

image-20220412184436335

Interpt (中断)

待补充

0x0n. 补充

1. 删减与翻译

删减部分过时的内容我觉得倒合理, 翻译质量总体阅读起来还是问题不小, 很多地方翻的比较拗口, OS 这门课理论和实践都多, 拗口的翻译会让人容易耗时间在原本简单的概念上, 另外倒是建议每章开头不明所以的”每章一乐”删减或去掉, 看半天基本都是无效阅读… (包括很多不明所以的笑话, 还影响阅读体验和效率)

2. 并发编程

这里也可以说成是多CPU/处理器编程, 只是为了简易还是用并发好点, 因为并发的内容比较多, 需要实际训练, 所以单独一篇来说了. 这里抛出问题:

  • 绝大部分的并发问题, 是否都可以用一个带锁的任务队列来解决?

  • (许多并发问题是由于编译器改变了原本的执行顺序导致) 那CPU的”乱序/预测执行”是否也可以视为”动态编译器”?

  • 并发程序 = 共享内存的多个执行流? (state machine)

  • 内存屏障和 lock/cas 是两回事, 区别在哪, 如何使用?

  • 为何说 X86 已经是硬件体系里限制最强的内存模型了? ARM/RISC-V 为何松散的多?

    1. X86的内存模型可参考(TSO in Hardware memory models by Russ Cox)

      image-20220604142342706

    2. ARM/RISC-V 中为何没有写缓存队列? ARM 为何使用弱一致限制? (减少复杂性, 使低功耗设备的单核执行性能更高)

参考资料:

  1. OS: Three easy pieces - BookCode
  2. OS: Three easy pieces - Homework/QA
  3. 现代操作系统: 原理与实践 - SJTU - Process
  4. OS: Design & Implement - NJU - JYY - 2022