Exercise 3.49: Give a scenario where the
deadlock-avoidance mechanism described above does not work. (Hint: In the
exchange problem, each process knows in advance which accounts it will need to
get access to. Consider a situation where a process must get access to some
shared resources before it can know which additional shared resources it will
require.)
Concurrency, time, and communication
We’ve seen how programming concurrent systems requires controlling the ordering
of events when different processes access shared state, and we’ve seen how to
achieve this control through judicious use of serializers. But the problems of
concurrency lie deeper than this, because, from a fundamental point of view,
it’s not always clear what is meant by “shared state.”
Mechanisms such as test-and-set! require processes to examine a global
shared flag at arbitrary times. This is problematic and inefficient to
implement in modern high-speed processors, where due to optimization techniques
such as pipelining and cached memory, the contents of memory may not be in a
consistent state at every instant. In contemporary multiprocessing systems,
therefore, the serializer paradigm is being supplanted by new approaches to
concurrency control.
The problematic aspects of shared state also arise in large, distributed
systems. For instance, imagine a distributed banking system where individual
branch banks maintain local values for bank balances and periodically compare
these with values maintained by other branches. In such a system the value of
“the account balance” would be undetermined, except right after
synchronization. If Peter deposits money in an account he holds jointly with
Paul, when should we say that the account balance has changed—when the
balance in the local branch changes, or not until after the synchronization?
And if Paul accesses the account from a different branch, what are the
reasonable constraints to place on the banking system such that the behavior is
“correct”? The only thing that might matter for correctness is the behavior
observed by Peter and Paul individually and the “state” of the account
immediately after synchronization. Questions about the “real” account
balance or the order of events between synchronizations may be irrelevant or
meaningless.
The basic phenomenon here is that synchronizing different processes,
establishing shared state, or imposing an order on events requires
communication among the processes. In essence, any notion of time in
concurrency control must be intimately tied to communication. It is intriguing that a
similar connection between time and communication also arises in the Theory of
Relativity, where the speed of light (the fastest signal that can be used to
synchronize events) is a fundamental constant relating time and space. The
complexities we encounter in dealing with time and state in our computational
models may in fact mirror a fundamental complexity of the physical universe.
练习 3.49：请给出一个上述死锁规避机制不起作用的场景。（提示：在交换问题中，每个进程事先知道需要访问哪些账户。试考虑这样一种情形：进程必须先获取某些共享资源，才能确定还需要哪些额外的共享资源。）
并发性、时间与通信
我们已经看到，并发系统的程序设计需要在不同进程访问共享状态时控制事件的顺序，也看到了如何通过审慎使用串行器来实现这种控制。但并发问题比这更为深刻，因为从根本的观点来看，“共享状态”的含义并不总是清晰的。
test-and-set! 等机制要求进程在任意时刻检查一个全局共享标志。在现代高速处理器中，由于流水线 (pipelining) 和缓存内存 (cached memory) 等优化技术，内存内容在每个时刻未必处于一致状态，因此这种做法实现起来既有问题又低效。因此，在当代多处理器系统中，串行器范式正逐渐被并发控制的新方法所取代。
共享状态的问题方面同样出现在大型分布式系统中。例如，设想一个分布式银行系统，各分支机构维护账户余额的本地值，并定期与其他分支维护的值进行比对。在这样的系统中，“账户余额”的值是不确定的，只有在同步之后立刻查看才有明确含义。如果 Peter 向他与 Paul 共同持有的账户存款，我们应当说账户余额在何时发生了变化——是在本地分支的余额改变时，还是要等到同步之后？如果 Paul 从另一家分支访问该账户，对银行系统施加怎样的合理约束才能使其行为是“正确的”？对于正确性而言，真正重要的可能只是 Peter 和 Paul 各自观察到的行为，以及同步之后立刻的账户“状态”。关于“真实”账户余额，或两次同步之间事件顺序的问题，可能是无关紧要的，乃至毫无意义的。
这里的基本现象在于：同步不同的进程、建立共享状态或对事件施加顺序，都需要进程之间的通信。从本质上说，并发控制中任何关于时间的概念都必须与通信密切相连。耐人寻味的是，时间与通信之间类似的联系也出现在相对论 (Theory of Relativity) 中——光速（能用于同步事件的最快信号）是关联时间与空间的基本常数。我们在处理计算模型中的时间与状态时所遭遇的复杂性，或许正是物理宇宙根本复杂性的镜像。