Читать книгу Distributed Computing Pearls - Gadi Taubenfeld - Страница 12

CHAPTER 2

One Loaf of Bread, Please

In many distributed systems, sometimes there is a need to ensure that two things will not happen at the same time. We use the too much bread problem to demonstrate the difficulty involved in such a type of synchronization when communication is restricted to sending and receiving messages.

2.1 THE TOO MUCH BREAD PROBLEM

Alice and Bob are sharing an apartment. They have decided that at any time they will try to have precisely one loaf of bread in the kitchen. Let’s assume that Alice arrives home in the afternoon, and finds that there is no bread. So, she leaves for the bakery to buy bread. After she leaves, Bob arrives, he also finds that there is no bread and goes to buy bread. In the end, each one of them buys a loaf of bread, and they end up with too much bread. So, Alice and Bob are looking for a solution to ensure the following.

1. Only one person buys a loaf of bread, when there is no bread.

2. Someone always buys a loaf of bread, when there is no bread.

A solution in which only Bob is responsible for buying bread is not acceptable. In such a solution, there is a scenario where Alice arrives home and finds that there is no bread, and waits forever for Bob to show up. A proper solution should ensure that, when there is no bread, someone always buys bread even if only one person shows up.

Alice and Bob cannot see each other, and they communicate only by sending each other short text messages. It is assumed that a message that is sent is never lost and arrives immediately to its destination. However, between the time Alice finishes checking whether she has received a message and starts sending a message, Bob may send her a message.

2.2 APPLICATIONS

To see the corresponding synchronization problem for computing systems, replace a loaf of bread in the above example with a file, and let Alice and Bob be the names of two computers that are trying to avoid updating a shared file at the same time. As already mentioned in Chapter 1, without proper synchronization, the integrity of the data may be destroyed if two computers update a common file at the same time, and as a result, deposits and withdrawals could be lost, confirmed reservations might have disappeared, etc. Alice and Bob which communicate only by sending text messages, correspond to computers which communicate by sending and receiving messages.

Figure 2.1: The code for the first incorrect attempt. The statement “if (no A)” means if Alice is not present, and the statement “if (no B)” means if Bob is not present.

More generally, concurrent access to shared resources (like files, printers, memory locations, data structures) shared among several processes must be synchronized to avoid interference between conflicting operations. Locks are the de facto mechanism for concurrency control on concurrent resources: each resource is protected by a lock, a processor accesses a resource only after acquiring the lock protecting the resource, after which the processor is guaranteed exclusive access to that resource, once the processor completes its operation it releases the lock, enabling another waiting processor to access that resource. An algorithm that solves the too much bread problem is actually an implementation of a lock for two processes.

2.3 FIRST ATTEMPT

Alice and Bob have discussed the situation and agreed that to synchronize their actions they would communicate by sending two type of text messages: acquire (an attempt to acquire permission to buy bread) and release (giving up permission to buy bread). To simplify the presentation we will use the following conventions: We say the following.

• Alice is present, if the last message Bob has received from Alice is acquire.

• Bob is present, if the last message Alice has received from Bob is acquire.

By using these messages, Alice and Bob came up with the following solution.

Alice: When Alice arrives home, she does the following: If she finds that Bob is not present and that there is no bread, she sends the message acquire, buys a loaf of bread, puts it on the kitchen table, and sends the message release.

Figure 2.2: The code for the second incorrect attempt.

Bob: When Bob arrives home, he does the following: If he finds that Alice is not present and that there is no bread, he sends the message acquire, buys a loaf of bread, puts it on the kitchen table, and sends the message release.

For readers familiar with basic programming notations, we give in Figure 2.1 the code for the first attempt to solve the problem. This and the other code segments in this chapter can be skipped without loss of continuity. In the solution, the statement “if (no A)” means if Alice is not present, and the statement “if (no B)” means if Bob is not present.

Well, the problem with this solution is that both Alice and Bob might buy bread. To see that, assume that they arrive home at the same time and recall that they cannot see each other. Now, Alice finds that Bob is not present and that there is no bread, and before she sends a message to Bob, Bob finds that Alice is not present and that there is no bread. Thus, both will send the message acquire and will go to buy bread ending up with “too much bread”.

2.4 SECOND ATTEMPT

To resolve the above problem Alice and Bob slightly modified their previous solution.

Alice: As soon as Alice arrives home, she sends the message acquire. Only then she checks, and if she finds that Bob is not present and that there is no bread, she buys a loaf of bread, puts it on the kitchen table, and sends the message release. Otherwise, if she finds that Bob is present, she sends the message release, and does nothing (until the day after, when she tries again).

Bob: As soon as Bob arrives home, he sends the message acquire. Only then he checks, and if he finds that Alice is not present and that there is no bread, he buys a loaf of bread, puts it on the kitchen table, and sends the message release. Otherwise, if he finds that Alice is present, he sends the message release, and does nothing (until the day after, when she tries again).

The code for the second attempt appears in Figure 2.2.

Well, this time Alice and Bob might end up with no bread at all! To see that, assume that they arrive home at the same time. Since it is assumed that they cannot see each other, each one sends the message acquire. Then, each one sees that the last message received from the other one is acquire, and no one buys bread.

Figure 2.3: The code for the third incorrect attempt. The statement “while (A) {skip}” means wait until Alice is not present.

2.5 THIRD ATTEMPT

Next, we present a solution which correctly works only if we make a timing assumption about the relative speed of Alice and Bob. The algorithm for Alice is the same as in the previous solution.

Alice: As soon as Alice arrives home, she sends the message acquire. Only then she checks, and if she finds that Bob is not present and that there is no bread, she buys a loaf of bread, puts it on the kitchen table, and sends the message release. Otherwise, if she finds that Bob is present, she sends the message release and does nothing (until the day after, when she tries again).

Bob: As soon as Bob arrives home, he sends the message acquire. Then, if he finds that Alice is present, he waits until Alice is not present (that is until the last message received from Alice is not acquire). Once Bob finds that Alice is not present, he checks if there is bread. If there is no bread, he buys a loaf of bread, puts it on the kitchen table, and sends the message release. Otherwise, if there is bread, he sends the message release and does nothing.

The code for the third attempt appears in Figure 2.3. As before, “if (no B)” means if Bob is not present. The statement “while (A) {skip}” means wait until Alice is not present, that is, wait until the last message received from Alice is not acquire.

For the above solution to be correct, an assumption must be made about Bob’s speed. Let’s assume that Bob is waiting for Alice to send a release message. Then, we should assume that, between the time Alice sends a release message (line 7), and the next time she sends the message acquire the day after (line 1), Bob must find out that the last message sent by Alice is a release message. That is, we must assume that Bob will not go to sleep before Alice sends a release message and will wake up only after Alice sends the message acquire the day after, never noticing that Alice’s last message is a release message. Without this assumption, Alice and Bob might never buy bread. Such an assumption, where Alice and Bob are relatively slow, may be reasonable for humans. However, it is not reasonable for computers which are very fast.

Figure 2.4: (a) A configuration where A1, A2, B2, and B1 are all present. (b) Notations used in Figure 2.5.

2.6 FOURTH ATTEMPT: A CORRECT SOLUTION

Finally, we present a correct solution. Unlike the previous solution, it is symmetric: Alice and Bob behave similarly and hence have the same chance to go and buy bread. For this solution, four types of messages are used: acquire1, release1, acquire2, and release2. To simplify the presentation we will use the following conventions: We say the following.

• A1 is present, if Bob has received at least one acquire1 message from Alice, and after the last acquire1 message received, he has not received a release1 message.

• A2 is present, if Bob has received at least one acquire2 message from Alice, and after the last acquire2 message received, he has not received a release2 message.

• B1 is present, if Alice has received at least one acquire1 message from Bob, and after the last acquire1 message received, she has not received a release1 message.

• B2 is present, if Alice has received at least one acquire2 message from Bob, and after the last acquire2 message received, she has not received a release2 message.

Figure 2.5: All the six possible configurations with A1, A2, B2, and B1.

A configuration is captured by deciding for each one of the symbols A1, A2, B2, and B1 whether it is present or not present (see Figure 2.4). For any given configuration, it is either Alice’s turn or Bob’s turn (but not both) to buy bread.

At any point, as illustrated in Figure 2.5, if Alice finds that B1 is not present, then it is Alice’s responsibility to buy bread. If Bob finds A1 is not present, then it is Bob’s responsibility to buy bread. Otherwise, when both A1 and B1 are present, a decision is made according to the status of A2 and B2. If both A2 and B2 are present or if neither of them is present then it is Bob’s responsibility to buy bread, otherwise it is Alice’s responsibility. More precisely, the solution is as follows.

Alice: When Alice arrives home, she does the following.

1. First, she sends the message acquire1. Then, if B2 is present, she sends the message acquire2, otherwise she sends the message release2. By doing so, Alice gives priority to Bob in buying bread.

2. Then, she waits as long as the following two conditions hold: (1) B1 is present and (2) either both A2 and B2 are present or neither of them is present.

3. Once Alice finds that at least one of these two conditions is not satisfied, she checks if there is bread. If there is no bread, she buys a loaf of bread and puts it on the kitchen table.

4. Finally, she sends the message release1.

Bob: When Bob arrives home, he does the following.

Figure 2.6: The code for the fourth attempt. The statement “if B2” means if B2 is present; the statement “while (B1) {skip}” means wait until B1 is not present, etc.

1. First, he sends the message acquire1. Then, if A2 is present, he sends the message acquire2, otherwise he sends the message release2. By doing so, Bob gives priority to Alice in buying bread.

2. Then, he waits as long as the following two conditions hold: (1) A1 is present and (2) either A2 or B2 are present (but not both).

3. Once Bob finds that at least one of these two conditions is not satisfied, he checks if there is bread. If there is no bread, he buys a loaf of bread and puts it on the kitchen table.

4. Finally, he sends the message release1.

The solution will also work if Alice and Bob have a way to detect whether there is bread or not remotely. The code for the fourth attempt appears in Figure 2.6. In the solution, the statement “if B2” means if B2 is present; the statement “while (B1) {skip}” means wait until B1 is not present, etc.

This last solution is rather complicated, and it is not trivial to formally prove its correctness. The moral of this story is that even for such a simple problem it is challenging to come up with a correct solution when communication is done only by sending and receiving messages.

In reality, when computers need to be synchronized, much more difficult synchronization problems have to be solved. For example, there may be many participants (not just Alice and Bob), many resources (not just one loaf of bread), and under various assumption and requirements. A solution for three participants and two resources is presented in Chapter 10.

2.7 COMMUNICATING BY READING AND WRITING OF NOTES

We have assumed that Alice and Bob communicate only by sending each other short text messages, and we examined how the too much bread problem can be solved with this type of restricted communication.

As already mentioned, communicating devices usually communicate with each other by either (1) sending and receiving of messages or (2) reading from and writing to shared memory locations. So, let’s turn our attention now to the reading and writing type of communication.

Assume that Alice and Bob cannot see each other and they communicate with each other only by writing and reading of notes. In particular, Alice cannot see that Bob is reading a note that she has written earlier. Inside their kitchen, there is a noticeboard, which is initially empty, on top of which they can leave notes and remove them later. How would we solve the problem with this type of restricted communication?

We point out that the noticeboard corresponds to a shared memory of a computer. Leaving and removing notes corresponds to writing into the shared memory, and reading of notes corresponds to reading from the shared memory. It is assumed that it is possible to atomically either read a note or leave/remove a note. However, between the time Alice finishes reading and starts updating the content of the noticeboard, Bob may access the noticeboard and possibly change its content.

Well, to solve the problem, we can essentially use the same correct solution (Solution 4) from page 13! We only need to give a different interpretation to some of the conventions used earlier. So, for this solution, four labeled notes are used: A1, A2, B1, and B2, and the following conventions are used: We say the following.

• A1 is present, if there is a note labeled A1 on the noticeboard.

• A2 is present, if there is a note labeled A2 on the noticeboard.

• B1 is present, if there is a note labeled B1 on the noticeboard.

• B2 is present, if there is a note labeled B2 on the noticeboard.

As before, a configuration is captured by deciding for each one of the four labeled notes A1, A2, B2, and B1 whether it is present or not present (see Figure 2.4).

Now in the code for Alice in Solution 4, we substitute: send acquire1 with leave note A1, send acquire2 with leave note A2, send release1 with remove note A1, and send release2 with remove note A2.

Similarly, in the code for Bob in Solution 4, we substitute: send acquire1 with leave note B1, send acquire2 with leave note B2, send release1 with remove note B1, and send release2 with remove note B2.

This is it! With these modifications to Solution 4, we get a new correct solution for the too much bread problem assuming that Alice and Bob communicate with each other only by writing and reading of notes.

2.8 CHAPTER NOTES

The too much bread problem is an adaptation of the mutual exclusion problem to a model where communication is done only by sending and receiving messages. The correct solution we have presented for this problem, Solution 4, is an adaptation of an algorithm that was developed by J.L.K. Kessels for the mutual exclusion problem [30]. Kessels’ algorithm itself is an adaptation of a mutual exclusion algorithm due to Gary Peterson [39]. Mutual exclusion algorithms were first introduced by Edsger W. Dijkstra in [13]. Since then, numerous implementations of such algorithms have been proposed. A book by Michel Raynal includes a collection of many early algorithms for mutual exclusion [44]. Detailed coverage of the topic of mutual exclusion can be found in [48].

Edsger W. Dijkstra (May 11, 1930–August 6, 2002) was a Dutch computer scientist who received the Turing Award in 1972. “For fundamental contributions to programming as a high, intellectual challenge; for eloquent insistence and practical demonstration that programs should be composed correctly, not just debugged into correctness; for illuminating perception of problems at the foundations of program design” [Extract from the Turing Award Citation]. The Turing Award is generally recognized as the highest distinction in computer science and the “Nobel Prize of Computing.” It is named for Alan M. Turing, the British mathematician who articulated the mathematical foundation and limits of computing.

Dijkstra’s fundamental contributions cover diverse areas of computing science, including compiler construction, operating systems, distributed systems, sequential and concurrent programming, programming paradigm and methodology, programming language research, program design, program development, program verification, software engineering principles, graph algorithms, and philosophical foundations of computer science and computer programming. In [3], various aspects of Dijkstra’s life are discussed, including sections about his scientific career, scientific contributions, working style, opinions, lifestyle, and legacy.

2.9 SELF REVIEW

Questions:

1. As pointed out in Section 2.1 (page 9), a correct solution must satisfy the following two requirements: (1) only one person buys a loaf of bread, when there is no bread, and (2) someone always buys a loaf of bread, when there is no bread.

(a) Does the first attempt solution in Section 2.3 (page 10) satisfy any of these requirements?

(b) Does the second attempt solution in Section 2.4 (page 11) satisfy any of these requirements?

(c) Does the third attempt solution in Section 2.5 (page 12) satisfy any of these requirements?

2. In the correct solution (page 13), Alice and Bob first send the acquire1message, and only then check what is the current configuration and take proper action. Is the order of those two actions significant? That is, if the order of those two actions is replaced, would the algorithm still be correct?

3. In the correct solution (page 13), Bob waits as long as the following two conditions hold: (1) A1 is present and (2) either A2 or B2 are present (but not both). Why can Bob not simply check these two conditions only once, and if both hold, conclude that Alice will buy a loaf of bread and go to sleep?

Answers:

1. (a) It satisfies requirement #2, but does not satisfy requirement #1. (b) It satisfies requirement #1, but does not satisfy requirement #2. (c) It satisfies requirement #1, but does not satisfy requirement #2.

2. No. In such a case, it is possible that both Alice and Bob will buy bread at the same time. To see why this claim is valid, assume that the order of those two actions is replaced (that is, line 1 appears after line 3), and consider the following scenario: initially, no message is sent. Alice arrives home, checks and sees that there are no messages from Bob. Then, before she manages to send a message, Bob arrives. Bob also notices that there are no messages from Alice, and so he sends the messages acquire2 and acquire1. He checks again, and since there are no messages from Alice, he goes and buys bread. Alice continues. She sends the message acquire1 and then checks and finds that B2 is present and A2 is not, she also goes and buys bread.

3. Because Alice might be in the middle of executing Step 1, after sending the message acquire1. If at that point Bob checks the two conditions and goes to sleep, Alice will complete Step 1, gives priority to Bob in buying bread, and will get stuck in Step 2.