Exercise 3.47: A semaphore (of size n) is a
generalization of a mutex. Like a mutex, a semaphore supports acquire and
release operations, but it is more general in that up to n processes can
acquire it concurrently. Additional processes that attempt to acquire the
semaphore must wait for release operations. Give implementations of semaphores
in terms of mutexes
in terms of atomic test-and-set! operations.
Deadlock
Now that we have seen how to implement serializers, we can see that account
exchanging still has a problem, even with the serialized-exchange
procedure above. Imagine that Peter attempts to exchange a
1 with a
2
while Paul concurrently attempts to exchange a
2 with a
1. Suppose that
Peter’s process reaches the point where it has entered a serialized procedure
protecting a
1 and, just after that, Paul’s process enters a serialized
procedure protecting a
2. Now Peter cannot proceed (to enter a serialized
procedure protecting a
2) until Paul exits the serialized procedure
protecting a
2. Similarly, Paul cannot proceed until Peter exits the
serialized procedure protecting a
1. Each process is stalled forever,
waiting for the other. This situation is called a
deadlock.
Deadlock is always a danger in systems that provide concurrent access to
multiple shared resources.
One way to avoid the deadlock in this situation is to give each account a
unique identification number and rewrite serialized-exchange so that a
process will always attempt to enter a procedure protecting the lowest-numbered
account first. Although this method works well for the exchange problem, there
are other situations that require more sophisticated deadlock-avoidance
techniques, or where deadlock cannot be avoided at all. (See Exercise 3.48
and Exercise 3.49.)
练习 3.47：大小为 n 的信号量 (semaphore) 是互斥体的一种推广。信号量与互斥体一样，支持获取和释放操作，但更为通用——最多可有 n 个进程同时获取它。试图获取信号量的其他进程必须等待释放操作。请分别给出以下两种情形下信号量的实现：
用互斥体实现
用原子的 test-and-set! 操作实现
死锁
现在我们已经知道如何实现串行器，我们也能看到账户交换仍然存在问题，即使使用了上面的 serialized-exchange 过程也是如此。设想 Peter 试图将账户 a1 与 a2 互换，而 Paul 同时试图将 a2 与 a1 互换。假设 Peter 的进程执行到已进入保护 a1 的串行化过程，而就在此时，Paul 的进程进入了保护 a2 的串行化过程。现在 Peter 无法继续（无法进入保护 a2 的串行化过程），直到 Paul 退出保护 a2 的串行化过程为止。同样地，Paul 也无法继续，直到 Peter 退出保护 a1 的串行化过程为止。每个进程都永远停滞，等待对方。这种情形称为死锁 (deadlock)。死锁在提供对多个共享资源并发访问的系统中始终是一种危险。
在这种情形下，避免死锁的一种方法是给每个账户赋予唯一的标识号，并重写 serialized-exchange，使进程总是先尝试进入编号较小的账户对应的保护过程。尽管这种方法对交换问题行之有效，但仍存在其他情形需要更复杂的死锁规避技术，或根本无法避免死锁（见练习 3.48 和练习 3.49）。