本文最后更新于：1 年前

下半学期的内容啦！！！从上层往下层再走啦！！！怎么样用好fork() ???

期中测验讲解

简答题：并发求和

如果假设 sum.c 中的 sum++ 是如下构成：

t = atomic_fetch(sum)
t++
atomic_store(sum, t)

那么 k 个线程，输出的最小 sum 是多少？

#include "thread.h"

#define N 100000000

long sum = 0;

void Tsum() {
  for (int i = 0; i < N; i++) {
    sum++;
  }
}

int main() {
  create(Tsum);
  create(Tsum);
  join();
  printf("sum = %ld\n", sum);
}

结论有些反直觉：

对于所有 n, k >= 2，sum 的最小值都是 2
只要有一个线程在最后一轮循环 “持有” 2，再保持到最后写入
- Online Judge 就送分了

好巧妙，两只脚叠着踩楼梯一样，笑死

水面下的冰山：“反直觉” 的来源

Verifying Sequential Consistency (VSC) is NP-Complete

给出若干线程的共享内存 load/store 序列，判定是否存在一个 “全局” 的读写顺序，使得线程总是读到最近写入的数值

课后习题难度 (3-SAT)

阶段 1: 赋值
- 对每个变量 x 构造 write(xx, 0) 和 write(xx, 1) 的线程
阶段 2: 判定$C_i=x∨¬y$
- (T1) read(x) = 1, write($S_i$, 1) (T2) read(y) = 0, write($S_i$, 1)
阶段 3: 收结果
- read($S_1$) = 1, read($S_2$) = 1, …
阶段 4: 收尾 (使所有线程都能顺利结束)
- write(x, 0), write(x, 1)

VSC 的变种	复杂度
刚才的证明 (一般情况)	NP-Complete
每个线程只执行 2 个操作	NP-Complete
只有 2 个变量	NP-Complete
只有 3 个线程	NP-Complete
每个读知道写者	NP-Complete
每个变量只被一个线程写入	NP-Complete

编程题：生产者-消费者

投机取巧的方法：C 标准库是线程安全的！

void Tworker() {
  while (!feof(stdin) && scanf("%d", &x) == 1) {
    long res = f(x);
    lock(&lk);
    sum += res;
    unlock(&lk);
  }
}

如果限制只有一个线程可以读，那就需要生产者-消费者了

统计结果

正确率 (OJ 实时统计通过似乎只统计了编程题……)

简答题 56/74 (75.7%)
编程题 28/74 (37.8%)

87.5% (56/64) 的问卷表示 “没有出卖灵魂”

希望大家保持！

fork() 行为的补充解释

复习：fork()

状态机的复制

fork-demo.c
- 操作系统：状态机的管理者
fork-printf.c
- 一切状态都会被复制
sh-xv6.c
- fork + execve + pipe: UNIX Shell 的经典设计
- fork 状态机复制包括持有的所有操作系统对象
- execve “重置” 状态机，但继承持有的所有操作系统对象

文件描述符

熟悉又陌生

$ man 2 open可以打开手册

1	`int open(const char *pathname, int flags);`

RTFM: O_CLOEXEC, O_APPEND

文件描述符：一个指向操作系统内对象的 “指针”

对象只能通过操作系统允许的方式访问
从 0 开始编号 (0, 1, 2 分别是 stdin, stdout, stderr)
可以通过 open 取得；close 释放；dup “复制”
对于数据文件，文件描述符会 “记住” 上次访问文件的位置
- write(3, "a", 1); write(3, "b", 1);

文件描述符的 “复制”

fd = open("a.txt", O_WRONLY | O_CREAT); assert(fd > 0);
pid_t pid = fork(); assert(pid >= 0);
if (pid == 0) {
  write(fd, "Hello");
} else {
  write(fd, "World");
}

文件中存的是什么呢？HelloWorld / WorldHello。预期：不断往后写呀！！！ -> 操作系统设计开始复杂了昂！！！

文件抽象的代价

操作系统必须正确管理好偏移量 (如果是日志文件)
- 原子性 (RTFM: write(2), BUGS section)
dup() 的两个文件描述符是共享 offset，还是独立 offset？
- RTFM again!

share file offset, 就是符合我们上面的认知了昂！！！

甚至还有bugs……

复制，但又没有完全复制(Copy on Write)

概念上状态机被复制，但实际上复制后内存都被共享

“Copy-on-write” 只有被写入的页面才会复制一份
- 被复制后，整个地址空间都被标记为 “只读”
- 操作系统捕获 Page Fault 后酌情复制页面
- fork-execve 效率得到提升
操作系统会维护每个页面的引用计数

所有的页面实际上都属于OS管理，进程本质上只拥有一个映射表（MMU）。操作系统在中间是有操作空间的！！！

操作系统有一个CR3寄存器，帮助我们进行逻辑地址 -> 物理地址的地址翻译。

Fork()完成之后，操作系统悄悄“抹掉”写权限，都是只读。你要写的时候，就会触发一个page fault(缺页中断)。进程会向操作系统发送一个SIGSEGV（访问rw页面，产生page fault）。 -> 把rw页面的饮用计数-1，然后重新分配一个相同的页面，把rw权限重新还给这个进程，进程就可以写它啦！！！

好处：很多文件都是只用不写，同一个物理地址，超多次复用。

想证明这一点？

cow-test.c: 128MB 代码 + 128MB 数据

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <fcntl.h>
#include <assert.h>
#include <string.h>

#define NPROC 1000
#define MB 128
#define SIZE (MB * (1 << 20))

#define xstr(s) str(s)
#define str(s) #s

int main() {
  char *data = malloc(SIZE); // 128MB shared memory
  memset(data, '_', SIZE);

  for (int i = 0; i < NPROC - 1; i++) {
    if (fork() == 0) break;
  }

  // NPROC processes go here

  asm volatile(".fill 1048576 * " xstr(MB) ", 1, 0x90"); // 128MB shared code

  unsigned int idx = 0;
  int fd = open("/dev/urandom", O_RDONLY); assert(fd > 0);
  read(fd, &idx, sizeof(idx));
  close(fd);
  idx %= 1048576 * MB;

  data[idx] = '.';
  printf("pid = %d, write data[%u]\n", getpid(), idx);

  while (1) {
    sleep(1); // not terminate
  }
}

创建 1000 个进程 (2GB 内存的虚拟能抗住吗)？
- 所以，整个操作系统里 libc 代码和只读数据只有一个副本！
- 推论：统计进程占用的内存是个伪命题 -> 共享内存，导致占用的内存是不好统计的昂！！！

状态机、fork() 和魔法

状态机的视角

帮助我们

理解物理世界 (Cellular Automata)
理解处理器、操作系统
调试 (record-replay)、profiler
Model checker 和 program verifier

fork() 可以复制状态机？

感觉是一个非常 “强大” 的操作
比如创造平行宇宙！

创造平行宇宙：搜索并行化

那我们不就可以加速状态空间搜索了吗？

每次探索都 fork 一个新进程

dfs-fork.c: 连回溯都可以不要了 -> 在不同的平行宇宙去探索不同的分支。平行宇宙甚至可以“并行”探索，找出所有的解，太牛了！！！dfs单机 -> fork()多进程，平行宇宙并行探测，太牛了这个想法！！！进程直接exit() -> 就可以直接退出，很方便，fork()保存了中间状态的结果，很方便！！！
单机DFS: 只有一个状态机，只能一个一个状态的探索。Fork()，同时创建多个状态机，并行探索不同的分支和状态。

创造平行宇宙：跳过初始化

假设你实现的 NEMU 需要启动很多份

./nemu dummy.elf
./nemu add.elf
./nemu add-longlong.elf…
而你的 NEMU 实现初始化又需要很长的时间？

int main() {
  nemu_init(); // only once
  while (1) {
    file = get_start_request();
    if ((pid = fork()) == 0) {
      // bad practice: no error checking
      load_file();
    }
    ...

创造平行宇宙：跳过初始化

一次初始化，多次复用！！！所有的Android应用都是这么做的！！！Java和Kotlin的依赖非常多，加载很慢。一次加载所有的依赖，后面所有来的都fork()，就能直接使用了。Android！！！

在实际中的应用（快是最重要的！！！）

Zygote Process (Android)
- Java Virtual Machine 初始化涉及大量的类加载
- 一次加载，全员使用
  - App 使用的系统资源
  - 基础类库
  - libc
  - …
Chrome site isolation (Chrome)
Fork server (AFL)

创造平行宇宙：备份和容错

要是我们总是能 “试一试”，试错了还能回到过去就好了

有 bug 的程序：我也想这样

那就用 fork() 做个快照吧

主进程 crash 了，启动快照重新执行 -> 存档重新加载，说不定就赢了！！！
- 有些 bug 可能调整一下环境就消失了 (比如并发，出了bug，重新fork存档，再来一次！！！反复重试！！！)
- Rx: Treating bugs as allergies–A safe method to survive software failures. (SOSP’05, Best Paper Award 🏅)

突如其来的广告

计算机系统里没有魔法。处理器/操作系统/程序就是状态机。

但这就是魔法啊！

~~签订契约，成为魔法少女~~ (这是什么梗)

キュウべえ和大学教授有某种程度的相似

~~总是在骗你，但从不说假话~~

欢迎报考NJU哈哈哈哈哈，笑死我了。

状态机复制：我们做对了吗？

A fork() in the road (HotOS’19)

fork太复杂啦，UNIX Fork()不好用！！！

`fork()`: UNIX 时代的遗产

fork + execve

如果只有内存和文件描述符，这是十分优雅的方案

上面这个模型是十分优雅的！！！

但贪婪的人类怎么可能满足？

在操作系统的演化过程中，为进程增加了更多的东西

信号 (信号处理程序，操作系统负责维护)
线程 (Linux 为线程提供了 clone 系统调用)

进程间通信对象
ptrace (追踪/调试)
……

创建进程：POSIX Spawn

int posix_spawn(pid_t *pid, char *path,
  posix_spawn_file_actions_t *file_actions,
  posix_spawnattr_t *attrp,
  char * argv[], char * envp[]);

在fork()之后设计出来的API，更好用之类的昂！！！

参数

pid: 返回的进程号
path: 程序 (重置的状态机)
file_actions: open, close, dup
attrp: 信号、进程组等信息
argv, envp: 同execve
- 很明显：这是一个 “后设计” 的 API

A `fork()` in the Road

fork() 的七宗罪

Fork is no longer simple
Fork doesn’t compose - fork-printf.c
Fork isn’t thread-safe
Fork is insecure - 打破了 Address Space Layout Randomization
Fork is slow - 的确……
Fork doesn’t scale - 也是……
Fork encourages memory overcommit - 呃……

但 fork() 是魔法啊：这引起了更多的思考

应用程序到底需要什么？
操作系统到底应该提供什么？

总结

本次课回答的问题

Q: 如何巧妙地使用 fork() “创建平行世界” 的功能？

Take-away messages

创建平行世界
- 搜索的加速
- 状态的复用 (Zygote)
- “时间旅行”——穿越到过去，让自己变得更强
从操作系统的角度，fork 可能不是 API 的最佳选择
- 可能可以在这个基础上做出非常基础性的工作！

南京大学操作系统

#研0自学

NJUOS-15-Fork的应用

https://alexanderliu-creator.github.io/2022/12/31/njuos-15-fork-de-ying-yong/

作者

Alexander Liu

发布于

2022年12月31日

许可协议

NJUOS-16-什么是可执行文件上一篇

NJUOS-14-C标准库的实现下一篇

NJUOS-15-Fork的应用

期中测验讲解

简答题：并发求和

水面下的冰山：“反直觉” 的来源

更多的技术处理

编程题：生产者-消费者

统计结果

fork() 行为的补充解释

复习：fork()

文件描述符

文件描述符的 “复制”

复制，但又没有完全复制(Copy on Write)

状态机、fork() 和魔法

状态机的视角

创造平行宇宙：搜索并行化

创造平行宇宙：跳过初始化

创造平行宇宙：跳过初始化

创造平行宇宙：备份和容错

突如其来的广告

状态机复制：我们做对了吗？

fork(): UNIX 时代的遗产

创建进程：POSIX Spawn

A fork() in the Road

总结

`fork()`: UNIX 时代的遗产

A `fork()` in the Road