这个练习可以分为三个子问题。
练习的第一个问题是:证明如果交换过程是按顺序执行的,那么经过任意次数的并发交换之后,这些账户的月还是按照某种顺序排列的 10
、 20
和 30
。
假如交换过程是按顺序运行的,那么交换 10
、 20
和 30
有以下可能的并发运行序列( e
代表 exchange
):
; 运行序列 ; 相应的决策树表示
(e 10 20) => (e 10 30) (e 10 20)
/ \
(e 10 20) => (e 20 30) / \
(e 10 30) (e 20 30)
(e 10 30) => (e 10 20) (e 10 30)
/ \
(e 10 30) => (e 20 30) / \
(e 10 20) (e 20 30)
(e 20 30) => (e 10 20) (e 20 30)
/ \
(e 20 30) => (e 10 30) / \
(e 10 20) (e 10 30)
对以上六个序列进行检验会发现,无论交换怎么进行,最终三个帐号的余额都会是某种排列的 10
、 20
和 30
。
练习的第二个问题是:证明如果使用未串行化的 exchange
实现账户余额交换,那么三个帐号之间的余额就可能不再是 10
、 20
和 30
的某个排列。
这个论断是正确的,以下是其中一个例子,它通过交换,产生三个余额分别为 20
、 10
和 10
的账户:
| acc-1 acc-2 acc-3
| | | |
| | | |
| +-----------------------------------------+ |
| | exchange |
| | | |
| | v |
| | acc-1 balance: 10 |
| | | |
| | v |
| | acc-2 balance: 20 |
| | | |
| | | |
| | | |
| | | |
| +---------------------------------------------------------------------------------------+
| | exchange
| | |
| | v
| | acc-1 balance: 10
| | |
| | v
| | acc-3 balance: 30
| | |
| | v
| | difference: (- 10 30) = -20
| | |
| | v
| | ((acc-1 'withdraw) -20)
| | |
| | v
| | acc-1 balance: 10 + 20 = 30
| | |
| | v
| | ((acc-3 'deposit) -20)
| | |
| | v
| | acc-3 balance: 30 - 20 = 10
| |
| v
| difference: (- 10 20) = -10
| |
| v
| ((acc-1 'withdraw) -10)
| |
| v
| acc-1 balance: 10 + 10 = 20
| |
| v
| ((acc-2 'deposit) -10)
| |
| v
| acc-2 balance: 20 - 10 = 10
|
v
time
注意,当输入为负数时,帐号执行的是反操作,比如 ((acc-1 'withdraw) -10)
,实际上执行的是 ((acc-1 'deposit) 10)
。
练习的第三个问题是:如果不对 exchange
进行串行化,无论并发如何进行,总能保证三个帐号的余额的总和不变吗?
在问题二的例子中,我们已经给出了可以计算出余额为 20
、 10
和 10
的交换运行序列,它在这里也可以作为反例,证明这个论断是错误的。