练习 3.38

a)

假设银行按先来先服务(first come first service) 的方式处理业务，那么 Peter 、 Paul 和 Mary 的交易有以下六种可能的排列方式：

1. Peter -> Paul -> Mary
2. Peter -> Mary -> Paul
3. Paul -> Peter -> Mary
4. Paul -> Mary -> Peter
5. Mary -> Peter -> Paul
6. Mary -> Paul -> Peter

以上的这些排列方式会产生以下的余额值（括号里面表示的是执行操作之后的余额）：

1. Peter (110) -> Paul (90) -> Mary (45)
2. Peter (110) -> Mary (55) -> Paul (35)
3. Paul (80) -> Peter (90) -> Mary (45)
4. Paul (80) -> Mary (40) -> Peter (50)
5. Mary (50) -> Peter (60) -> Paul (40)
6. Mary (50) -> Paul (30) -> Peter (40)

b)

Warning

以下解答有误，正等待修复中，具体请见： https://github.com/huangz1990/SICP-answers/pull/14

每个交易操作可以分为三个步骤： 1)取出 balance； 2)计算新的 balance； 3)为 balance 设置新值。

如果允许进程交错的话，那么 Peter 、 Paul 和 Mary 的三个交易进程共有 3 * 3 * 3 = 27 种可能的排列方式，就算减去前面 a) 部分产生的 6 种排列方式，还有 21 种可能的排列方式未列出来，以下是其中的两个例子：

首先是一个产生余额 80 的排列：

  |      Mary               Peter          Bank          Paul
  |
  |   取得余额 100     取得余额 100      余额 100      得余额为 100
  |       |                   |                           |
  |       v                   v                           v
  |   计算余额 50      计算余额为 110                  计算余额为 80
  |       |                   |                           |
  |       v                   v                           v
  |   设置余额为 50    设置余额为 110                  设置余额为 80
  |       |                   |                           |
  |       +----------------------------> 余额 50          |
  |                           |                           |
  |                           +--------> 余额 110         |
  |                                                       |
  |                                      余额 80  <-------+
  |
  v
time

接着是一个产生余额 55 的排列：

  |      Mary               Peter           Bank         Paul
  |
  |       |            取得余额 100      余额 100      得余额为 100
  |       |                   |                           |
  |       |                   v                           v
  |       |            计算余额为 110                  计算余额为 80
  |       |                   |                           |
  |       |                   v                           v
  |       |            设置余额为 110                  设置余额为 80
  |       |                   |                           |
  |       |                   |          余额 80  <------+
  |       |                   |
  |       |                   +--------> 余额 110
  |       |
  |   获得余额 110
  |       |
  |       v
  |   计算余额 55
  |       |
  |       v
  |   设置余额 55
  |       |
  |       +----------------------------> 余额 55
  |
  |
  v
time

Note

以下是 @ZHHY 提供的答案纠正信息。

实在没看出来 3 * 3 * 3 = 27 是怎么来的，按我的想法，Peter 、 Paul 和 Mary每个人分别对应一次读和写的操作，不妨记作：A1，A2（Peter），B1，B2（Paul），C1，C2（Mary），然后对它们进行排列，一共有6!种排法，但是“读”必须在对应的“写”前面，比如对Peter，A1必须在A2前，但在6!中排法中有一半正好是这样的，因此除以2，对Paul，Mary同样操作，故一共有6!/8=90种不同的排法，也就对应90种不同交错方式，但是需要注意的是结果并没有90种，有重复。枚举列出也不是那么麻烦

分情况

1. Peter最后完成写，按不同时刻读取有结果：110， 90， 60， 50， 40
2. Paul 最后完成写，按不同时刻读取有结果：80， 90， 30， 40，35
3. Mary 最后完成写，按不同时刻读取有结果：50，55，40，45

总结一下也就是 110，90，80，60，55，50，45，40，35，30 共10中不同结果

讨论

blog comments powered by Disqus