乐正

Actions speak louder than words.

Sicp-ex3-43

问题

假定在三个账户里的初始金额分别是10、20和30,现在有多个进程正在运行,交换这些账户中的余额。请论证,如果这些进程是顺序运行的,那么经过任何次并发交换,这些账户里的余额还将是按照某种顺序排列的10、20和30.请画出一个类似于图3-29中那样的时间图,说明如果采用本节中第一个版本的账户交换程序实现账户交换,那么这一条件就会被破坏。在另一方面,也请论证,即使是使用这个exchange程序,在这些账户里的余额之和也仍然能以保持不变。请画出一个时序图,说明如果我们不做各个账户上交易的串行化,这一条就可能被破坏。

解答

如果这些进程是顺序运行的,假设三个数字分别是$a$, $b$和$c$,用$D$表示两个账户的差额,用$A$表示账户的金额。那么:

$$ \begin{align} D_{ab} & = A_a - A_b \\ A_a & = A_a - D_{ab} = A_a - (A_a - A_b) = A_b \\ A_b & = A_b + D_{ab} = A_b + (A_a - A_b) = A_a \end{align} $$

这个行为对于任意两个账户来说都是成立的。所以如果按照顺序运行的话,不论多少次,这些账户里的余额还将是按照某种顺序排列的10、20和30。

draft

« sicp-ex3-42 sicp-ex3-44 »

Comments