在计算机系统概论/操作系统的考题中，经常遇见以下形状的问题：

1
2
fork() || fork() && fork() || fork();
printf("A\n");

问代码运行会输出多少个A

这类问题乍一看非常棘手，但实际上有一套统一的做法可以完成，我称之为状态机标数法

例1：仅统计总进程数量

1
2
(fork() && fork() || fork() && fork() || fork() && fork() && fork());
printf("A\n");

上例中，fork()逻辑表达式的求值结果实际上不起作用，但由于逻辑运算符&&和||的求值是短路的（即如果进行部分求值后已经可以知道整体的值，则不会进行后续求值），因此逻辑表达式的部分求值结果会影响后续的fork()是否执行，从而影响总进程数量。最终输出的A的数量等于总进程数量。

步骤1：画出表达式状态机

为了研究上述表达式的求值过程，我们需要画出表达式状态机，这本质上是一个确定有限自动机，每个状态表示一次fork()函数调用，转移符号共有0和1两种，0表示fork()返回零值，即子进程；1表示fork()返回非零值，即父进程

本例有7个fork()，将其从左到右编号为1至7（虽然运算符有优先级，但运算符序列中的运算数永远是从左到右求值的），再加上一个完成求值的终态，建立8个自动机状态：

image-20250408142202457

接下来我们需要考虑转移边的含义。我们规定，从状态i接受符号a转移到状态j的含义是：在第i个fork()求值为a的情况下，下一步要求解的是第j个fork()

值得注意的是，C语言中&&的优先级大于||，因此上面的运算等价与(f&&f)||(f&&f)||(f&&f&&f)

考虑第1个fork()，当此fork()返回非零值时，&&表达式不短路，下一个执行2；当1返回零值时，&&表达式短路，确定值为false，但此时&&表达式的下一步||运算不短路，于是下一个执行3

我们可以如下画出转移边：

image-20250408142546367

类似地，考虑2。注意到2被执行当且仅当1返回了非零值，于是此时可以忽略1的返回值（在短路运算中，执行到某一个运算符的右侧操作数时，此运算符的左侧操作数的值一定是已知的）。当2返回非零值时，第一个&&表达式为true，于是总表达式已经可以确定为true，后面的||均被短路，直接跳转到END；当2返回零值时，第一个&&表达式为false，这相当于1直接返回零值，因此跳转到3

image-20250408142837667

类似地我们可以完成整个转移图的绘制：

image-20250408143000147

步骤2：状态机标数

接下来我们要对上面的状态机的每个状态标数，这里标的数的含义是在这个fork()执行之前，要执行此fork()的总进程数

因此，我们按如下的算法标数：

  • 对状态1标1（因为在第一个fork()执行前只有一个进程），其他状态初始化为0
  • 按编号从小到大的顺序遍历每个状态（因为fork()在每个进程内的执行顺序总是和编号顺序一致的）
    • 将此状态的两个转移边的目标状态的标数增加此状态的标数（因为有转移边说明此fork()执行后，每个进程都会产生一个进程转移到目标状态）
  • 当遍历完每个状态时，END状态的标数就是总进程数

模拟算法如下（绿色标数表示这一轮模拟到的状态，黄色标数表示被绿色状态更新的状态）：

image-20250408143432635

image-20250408143518194

image-20250408143607085

image-20250408143640709

image-20250408143707904

image-20250408143745280

image-20250408143805993

image-20250408143820997

于是我们得到结论，执行完成一共有19个进程，输出19个A

例2：统计逻辑表达式有特定结果的进程数量

1
2
if (fork() || fork() && fork() || !fork())
	printf("A\n");

在上例中，我们需要统计的进程数量变成了完成求值且求值结果为true的进程数量

为此，做法实际与例1没有本质区别，只是我们需要将原来的一个END终态变成两个终态：TRUE和FALSE，分别代表完成求值的两种结果

我们同样画出状态机图：

image-20250408144418659

对状态机标数：

image-20250408144522725

于是我们得到结论：共产生6个进程，其中4个if求值为真，2个求值为假，输出4个A

若将代码改为

1
2
3
4
if (fork() || fork() && fork() || !fork())
	printf("A\n");
else
    printf("B\n");

则会输出4个A和2个B

例3：含有for的问题

下面我们考虑这样的代码：

1
2
3
4
5
6
7
for (int i = 0; i < 2; i++) {
    if (fork() || fork()) {
        printf("A\n");
    } else {
        printf("B\n");
    }
}

我们按照上面的逻辑来分析，会得到：

i=0时，可以通过自动机标数法得到，共产生3个进程，其中2个输出A，1个输出B

这3个进程都会进入i=1的循环，在i=1的循环中它们各自作为主进程，运行模式应当与i=0时的结果完全相同，因此i=1会得到复制三份的i=0时的输出，即6个A，3个B

因此总共会得到8个A，4个B

然而，实际执行上面的代码，我得到了12个A，6个B

这个结果实在是出乎意料，于是我将代码修改成下面的样子：

1
2
3
4
5
6
7
8
for (int i = 0; i < 2; i++) {
    if (fork() || fork()) {
        printf("A, i = %d, pid = %d, ppid = %d\n", i, getpid(), getppid());
    }
    else {
        printf("B, i = %d, pid = %d, ppid = %d\n", i, getpid(), getppid());
    }
}

得到的输出为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
A, i = 0, pid = 1793, ppid = 586
A, i = 1, pid = 1793, ppid = 586
B, i = 0, pid = 1795, ppid = 1794
A, i = 1, pid = 1795, ppid = 1794
A, i = 0, pid = 1793, ppid = 586
A, i = 1, pid = 1796, ppid = 1793
A, i = 0, pid = 1794, ppid = 1793
A, i = 1, pid = 1794, ppid = 1793
A, i = 0, pid = 1793, ppid = 586
B, i = 1, pid = 1797, ppid = 1796
B, i = 0, pid = 1795, ppid = 1794
A, i = 1, pid = 1798, ppid = 1795
B, i = 0, pid = 1795, ppid = 1794
B, i = 1, pid = 1800, ppid = 1798
A, i = 0, pid = 1794, ppid = 1793
A, i = 1, pid = 1799, ppid = 1794
A, i = 0, pid = 1794, ppid = 1793
B, i = 1, pid = 1801, ppid = 1799

可以看到，其中第1 5 9行的输出是完全一样的，它们来自同一个进程的同一个迭代的同一个代码行，按理说这样的输出绝不可能出现相同的三次；甚至其中有两次的输出出现在同一进程i=1的输出之后

再仔细观察，会发现i=0的所有输出都被复制了3份，而i=1的输出和分析的一致

我将代码改成

1
2
3
4
5
6
7
8
for (int i = 0; i < 2; i++) {
    if (fork() || fork()) {
        cout << "A, i = " << i << ", pid = " << getpid() << ", ppid = " << getppid() << endl;
    }
    else {
        cout << "B, i = " << i << ", pid = " << getpid() << ", ppid = " << getppid() << endl;
    }
}

即，使用C++风格的流输出而不是C风格的格式化输出，会得到符合分析的结果：

1
2
3
4
5
6
7
8
9
10
11
12
A, i = 0, pid = 1682, ppid = 586
A, i = 0, pid = 1683, ppid = 1682
B, i = 0, pid = 1684, ppid = 1683
A, i = 1, pid = 1682, ppid = 586
A, i = 1, pid = 1685, ppid = 1682
B, i = 1, pid = 1686, ppid = 1685
A, i = 1, pid = 1683, ppid = 1682
A, i = 1, pid = 1687, ppid = 1683
B, i = 1, pid = 1688, ppid = 1687
A, i = 1, pid = 1684, ppid = 1683
A, i = 1, pid = 1689, ppid = 1684
B, i = 1, pid = 1690, ppid = 1689

共8个A，4个B

上面情况的发生可能是因为输出缓冲区的问题：cout << ... << endl是强制清空缓冲区的，得到正确的输出，而使用printf时，可能缓冲区没有被及时清空，于是当进程复制时，没有被及时冲刷的缓冲区被复制，从而得到了更多的输出

但是这与一般的解释——printf在输出\n时会冲刷缓冲区——相矛盾

为了验证上面的解释，我们测试如下的代码（这个调试的灵感来自于@ywang22thu）

1
2
3
4
5
6
7
8
9
10
for (int i = 0; i < 2; i++) {
    if (fork() || fork()) {
        printf("A, i = %d, pid = %d, ppid = %d\n", i, getpid(), getppid());
        fflush(stdout);
    }
    else {
        printf("B, i = %d, pid = %d, ppid = %d\n", i, getpid(), getppid());
        fflush(stdout);
    }
}

得到了正确的8A4B输出

因此我们可以得出结论：每个i=0的进程会在i=1时经历2次fork()，如果没有及时清空缓冲区，则之前的缓冲区会被复制2次，从而被i=1的子进程输出出来

下面我们来推导当for循环的次数改为3次时会发生什么：

如果及时清空缓冲区，则输出为：

  • i=0时，2A1B
  • i=1时，6A3B
  • i=2时，18A9B

共26A13B

如果不及时清空缓冲区，则输出为：

  • i=0时，2A1B
  • i=1时，正常输出6A3B，新产生的进程产生2倍i=0时的异常输出，即有额外的4A2B
  • i=2时，正常输出18A9B，新产生的进程产生2倍的i=0和i=1的总输出，即额外的24A12B

共54A27B

上面的分析与实际实验结果吻合