算法导论第三版新增27章中文版(8)

计算机科学与技术

在过程调用前面加上 spawn 关键字时，就意味着嵌套并行 ，如第 3 行中所示。 spawn 的语义和普通的过程调用不同，执行 spawn 的过程实例（ parent ）可以和被 spawn 出来的子例程（ child ）并行执行，而不像串行执行中那样去等待 child 执行完成。在本例中，当 child 在计算 P-FIB(n-1) 时， parent 可以并行地去计算第 4 行中的 P-FIB(n-2) 。由于 P-FIB 过程是递归的，因此这两个对其自身进行调用的子例程就创建了嵌套的并行性，对其 children 来说同样如此，于是就产生了一个潜在的巨大子计算树，每个子计算都并行执行。

不过，关键字 spawn 并不是一定要求过程必须和其 child 并发执行，只是表示可以 并发执行。并发关键字表达了计算中的逻辑并行性 ，表明了计算中的哪些部分可以并行的运行。哪些子计算实际上是并发运行的是由调度器 在运行时决定的，在计算进行中，调度器把子计算分配给可用的处理器。稍后，我们会讨论调度器的原理。

一个过程，仅当其执行了 sync 语句时（如第 5 行），才能够安全地使用由其 spawn 的 children 例程的返回值。关键字 sync 表示过程必须等待，直到其所 spawn 的 children 全部完成计算，才能够继续 sync 后面的语句。在 P-FIB 过程中，必须要在 return 语句（第 6 行）前增加 sync 语句，从而避免出现在 x 还没有被计算前就进行 x+y 操作的异常情况。除了 sync 语句所提供的显式同步之外，每个过程都会在其返回前隐式地执行一条 sync 语句，这样可以保证在其终止前，其所有的 children 都已经终止。

多线程执行模型