一个不错的外企面试 Linux 开发职位, 应该说不是一道特别难或特别刁钻的题目, 但是由于 fork 函数运行机制的复杂性, 造就了当两个 fork 并排时, 问题就变得很复杂. 解这个题的关键, 一是要对 linux 下进程的机制有一定认识, 二是抓住上文提到的几个关于 fork 的关键点.
一个不错的外企面试 Linux 开发职位, 面试官出了一个如下的题目:
给出如下 C 程序, 在 linux 下使用 gcc 编译:
已知从这个程序执行到这个程序的所有进程结束这个时间段内, 没有其它新进程执行.
请说出执行这个程序后, 将一共运行几个进程.
如果其中一个进程的输出结果是 "pid1:1001, pid2:1002", 写出其他进程的输出结果(不考虑进程执行顺序).
明显这道题的目的是考察 linux 下 fork 的执行机制. 下面我们通过分析这个题目, 谈谈 Linux 下 fork 的运行机制.
预备知识:
这里先列出一些必要的预备知识, 对 Linux 下进程机制比较熟悉的朋友可以略过.
进程可以看做程序的一次执行过程. 在 Linux 下, 每个进程有唯一的 PID 标识进程. PID 是一个从 1 到 32768 的正整数, 其中 1 一般是特殊进程 init, 其它进程从 2 开始依次编号. 当用完 32768 后, 从 2 重新开始.
Linux 中有一个叫进程表的结构用来存储当前正在运行的进程. 可以使用 "ps aux" 命令查看所有正在运行的进程.
进程在 Linux 中呈树状结构, init 为根节点, 其它进程均有父进程, 某进程的父进程就是启动这个进程的进程, 这个进程叫做父进程的子进程.
fork 的作用是复制一个与当前进程一样的进程. 新进程的所有数据 (变量, 环境变量, 程序计数器等) 数值都和原进程一致, 但是是一个全新的进程, 并作为原进程的子进程.
解题的关键:
有了上面的预备知识, 我们再来看看解题的关键. 我认为, 解题的关键就是要认识到 fork 将程序切成两段. 看下图:
上图表示一个含有 fork 的程序, 而 fork 语句可以看成将程序切为 A,B 两个部分. 然后整个程序会如下运行:
step1, 设由 shell 直接执行程序, 生成了进程 P.P 执行完 Part. A 的所有代码.
step2, 当执行到 pid = fork(); 时, P 启动一个进程 Q,Q 是 P 的子进程, 和 P 是同一个程序的进程. Q 继承 P 的所有变量, 环境变量, 程序计数器的当前值.
step3, 在 P 进程中, fork()将 Q 的 PID 返回给变量 pid, 并继续执行 Part. B 的代码.
step4, 在进程 Q 中, 将 0 赋给 pid, 并继续执行 Part. B 的代码.
这里有三个点非常关键:
P 执行了所有程序, 而 Q 只执行了 Part. B, 即 fork()后面的程序.(这是因为 Q 继承了 P 的 PC - 程序计数器)
Q 继承了 fork()语句执行时当前的环境, 而不是程序的初始环境.
P 中 fork()语句启动子进程 Q, 并将 Q 的 PID 返回, 而 Q 中的 fork()语句不启动新进程, 仅将 0 返回.
解题:
下面利用上文阐述的知识进行解题. 这里我把两个问题放在一起进行分析.
从 shell 中执行此程序, 启动了一个进程, 我们设这个进程为 P0, 设其 PID 为 XXX(解题过程不需知道其 PID).
当执行到 pid1 = fork(); 时, P0 启动一个子进程 P1, 由题目知 P1 的 PID 为 1001. 我们暂且不管 P1.
P0 中的 fork 返回 1001 给 pid1, 继续执行到 pid2 = fork();, 此时启动另一个新进程, 设为 P2, 由题目知 P2 的 PID 为 1002. 同样暂且不管 P2.
P0 中的第二个 fork 返回 1002 给 pid2, 继续执行完后续程序, 结束. 所以, P0 的结果为 "pid1:1001, pid2:1002".
再看 P2,P2 生成时, P0 中 pid1=1001, 所以 P2 中 pid1 继承 P0 的 1001, 而作为子进程 pid2=0.P2 从第二个 fork 后开始执行, 结束后输出 "pid1:1001, pid2:0".
接着看 P1,P1 中第一条 fork 返回 0 给 pid1, 然后接着执行后面的语句. 而后面接着的语句是 pid2 = fork(); 执行到这里, P1 又产生了一个新进程, 设为 P3. 先不管 P3.
P1 中第二条 fork 将 P3 的 PID 返回给 pid2, 由预备知识知 P3 的 PID 为 1003, 所以 P1 的 pid2=1003.P1 继续执行后续程序, 结束, 输出 "pid1:0, pid2:1003".
P3 作为 P1 的子进程, 继承 P1 中 pid1=0, 并且第二条 fork 将 0 返回给 pid2, 所以 P3 最后输出 "pid1:0, pid2:0".
至此, 整个执行过程完毕.
所得答案:
1, 一共执行了四个进程.
(P0, P1, P2, P3)
2, 另外几个进程的输出分别为:
- pid1:1001, pid2:0
- pid1:0, pid2:1003
- pid1:0, pid2:0
进一步可以给出一个以 P0 为根的进程树:
验证:
下面我们去 linux 下实际执行这个程序, 来验证我们的答案.
程序如下图:
用 gcc 编译, 执行后结果如下:
由于我们不太可能刚巧碰上 PID 分配到 1001 的情况, 所以具体数值可能和答案有所差别. 不过将这里的 2710 看做基数的话, 结果和我们上面的解答是一致的.
总结:
应该说这不是一道特别难或特别刁钻的题目, 但是由于 fork 函数运行机制的复杂性, 造就了当两个 fork 并排时, 问题就变得很复杂. 解这个题的关键, 一是要对 linux 下进程的机制有一定认识, 二是抓住上文提到的几个关于 fork 的关键点. 朋友说, 这个题给的时间是 5 分钟, 应该说时间还算充裕, 但是在面试的场合下, 还是很考验一个人对进程, fork 的掌握程度和现场推理能力.
来源: http://os.51cto.com/art/201804/571620.htm