Warning
本题的解答有误,正等待修复中,具体请见: https://github.com/huangz1990/SICP-answers/pull/14
定义 P
为 (set! x (* x x))
,定义 Q
为 (set! x (* x x x))
,以下是并行执行 P
和 Q
时可能产生的计算序列( ?
符号表示执行过程被其他操作打断):
P
–> Q
Q
–> P
(set! x (* x ?))
–> Q
–> x
–> (set! x (* x x))
(set! x (* x ? ?))
–> P
–> x
–> x
–> (set! x (* x x x))
(set! x (* x x ?))
–> P
–> x
–> (set! x (* x x x))
以上计算序列会产生以下结果:
(set! x (* 10 10))
=> x = 100
=> (set! x (* 100 100 100))
=> x = 1,000,000
(set! x (* 10 10 10))
=> x = 1,000
=> (set! x (* 1000 1000))
=> x = 1,000,000
(set! x (* 10 ?))
=> (set! x (* 10 10 10))
=> x = 1,000
=> (set! x (* 10 1000))
=> x = 10,000
(set! x (* 10 ? ?))
=> (set! x (* 10 10))
=> x = 100
=> (set! x (* 10 100 100))
=> x = 100,000
(set! x (* 10 10 ?))
=> (set! x (* 10 10))
=> x = 100
=> (set! x (* 10 10 100))
=> x = 10,000
Note
以下是 @ZHHY 提供的答案修正信息:
以上解释符号不太清晰
P:(set! x (* x x))``应理解为两次读取``x``与一次写入``x
,我们分别记作r11,r12,w1
Q:(set! x (* x x x))``应理解为三次读取``x``与一次写入``x
,我们分别记作r21,r22,r23,w2
在保持r11,r12,w1和r21,r22,r23,w2各自内部顺序不变,可以交错排序,因此有 7!/(3!4!) = 35 种不同排法
但考虑到正真影响最后结果的却是 (1)w1,w2 的顺序 (2)w1,r21,r22,r23 的顺序 (3)w2,r11,r12 的顺序
考虑(1)将影响最后的写入操作、(2)将影响Q的读取操作进而影响w2、(3)将影响P的读取操作进而影响w1
分两类
类一:最后完成写操作的是w1,因此它始终在r21,r22,r23之后,所以没有(2)的影响,也就不会影响w2的结果,w2 == 1,000,这时只考虑(3) (i) w2-r11-r12:r11和r12都读取 x=1,000,故 w1 = 1,000,000 (ii) r11-w2-r12:r11读取 x=10,r12读取,x=1,000,故 w1 = 10,000 (iii) r11-r12-w2:r11和r12都读取 x=10,故 w1 = 100
类二:最后完成写操作的是w2,因此它始终在r11,r12之后,所以没有(3)的影响,也就不会影响w1的结果,w1 == 100,这时只考虑(2) (i) w1-r21-r22-r23:r21,r22和r23都读取 x=100,故 w2 = 1,000,000 (ii) r21-w1-r22-r23:r21读取 x=10,r22和r23读取,x=100,故 w2 = 100,000 (iii) r21-r22-w1-r23:r21和r22都读取 x=10,r23读取 x=100,故 w2 = 10,000 (iv) r21-r22-w1-r23:r21,r22和r23都读取 x=10,故 w2 = 1,000
综合以上结果,最后可能的值一共有5种:100,1,000,10,000,100,000,1,000,000
如果将串行化之后的过程 (s (lambda () (set! x (* x x))))
定义为 P1
, (s (lambda () (set! x (* x x x))))
定义为 P2
,那么 P1
和 P2
有以下可能的计算序列:
P1
–> P2
P2
–> P1
它们分别计算出以下结果:
(* 10 10)
=> 100
=> (* 100 100 100)
=> 1,000,000
(* 10 10 10)
=> 1000
=> (* 1000 1000)
=> 1,000,000
因为乘法的交换率原则,只要 P1
和 P2
的执行步骤不交错的话,那么它们之间的运行先后顺序是没有关系的,这也是加速一些并行操作常用的技巧。