fork（）与二叉树

有一个关于 fork（） 系统呼叫。

执行上述程序后将产生多少进程？

A. fork（） 系统调用将进程作为正在生长的二叉树的叶子生成。如果我们调用fork（）两次，它将生成2 ^2. =4道工序。这4个过程构成了二叉树的叶子树。一般来说，如果我们是平等的 l ，并无条件调用fork（），我们将 2. ^L 一级流程( l+1 ).它相当于一个二叉树的最大子节点数( l+1 ).

作为另一个例子，假设我们已经无条件地调用了fork（）调用三次。我们可以使用一个完整的二叉树来表示生成的过程，它有三个级别。在3级，我们将有2个 ^3. =8个子节点，对应于正在运行的进程数。

关于C/C++逻辑运算符的说明：

逻辑运算符&&的优先级高于| |，并且具有从左到右的关联性。执行左操作数后，将估计最终结果，右操作数的执行取决于左操作数的结果以及操作类型。

在AND（&&）的情况下，在对左操作数求值后，仅当左操作数求值为时，才会对右操作数求值 非零 .对于或（| |），在计算左操作数后，只有当左操作数的计算结果为时，才会计算右操作数 零 .

fork（）的返回值：

fork（）的手册页引用了以下关于返回值的摘录：，

“ 成功后，子进程的PID将在父进程中返回，并且 在子级中返回0。失败时，在父级中返回-1， 未创建任何子进程，并且已正确设置errno。 ”

PID类似于进程句柄，表示为 无符号整型 .我们可以得出结论，fork（）将在parent中返回非零，在child中返回零。让我们分析一下程序。为了便于记法，请按如下所示标记每个fork（），

#include <stdio.h>
int main()
{
   fork(); /* A */
   ( fork()  /* B */ &&
     fork()  /* C */ ) || /* B and C are grouped according to precedence */
   fork(); /* D */
   fork(); /* E */

   printf("forked");
   return 0;
}

下图提供了新工艺的图示。所有新创建的进程都在树的右侧传播，父进程在树的左侧以连续的级别传播。

前两个fork（）调用是无条件调用的。

在0级，我们只有主进程。main（图中的m）将创建子C1，两者都将继续执行。孩子们按照他们创造的顺序被编号。

在1级，我们运行m和C1，并准备执行fork（）–B（注意，B、C和D被命名为&&和| |运算符的操作数）。初始表达式B将在该级别运行的每个子进程和父进程中执行。

在2级，由于fork（）–B由m和C1执行，我们将m和C1作为父母，C2和C3作为子女。

fork（）–B的返回值在父级中不为零，在子级中为零。由于第一个运算符是&，由于返回值为零，因此子运算符C2和C3 不会 执行下一个表达式（fork（）-C）。父进程m和C1将继续使用fork（）–C。子进程C2和C3将直接执行fork（）–D，以评估逻辑OR运算的值。

在3级，我们将m、C1、C2、C3作为运行进程，将C4、C5作为子进程。表达式现在简化为（（B&&C）| | D），此时（B&&C）的值是显而易见的。在父母身上是非零的，在孩子身上是零的。因此，知道总体B&C|D结果的家长将跳过fork（）–D的执行。因为在评估为零的子项（B&C）中，他们将执行fork（）–D。我们应该注意，在2级创建的子项C2和C3也将运行fork（）–D，如上所述。

在4级，我们将m、C1、C2、C3、C4、C5作为运行进程，将C6、C7、C8和C9作为子进程。–然后无条件地执行所有这些子进程。

在5级，我们将运行20个进程。该程序（在Ubuntu Maverick上，GCC 4.4.5）打印了20次“分叉”。一次由根父级（主）执行，其余由子级执行。总的来说，将产生19个进程。

关于评估顺序的说明：

二元运算符中表达式的求值顺序未指定。详情请阅读帖子 操作数的求值顺序 但是，逻辑运算符是个例外。它们保证从左到右进行评估。

贡献者 文基 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。