as “Moore’s Law,” went on to become a self-fulfilling prophecy. Moore’s Law has become actual fact, with the doubling of transistor density every 18 months, as well as exponential growth in clock rates. However, due to inherent limitations imposed by the laws of physics, this exponential growth of the computing power of uniprocessors has to decline. The constraints of heat dissipation due to high-power consumption by fast uniprocessors have forced chip manufacturers to develop multicore architectures, where increases in throughput are achieved by packaging multiple cores embedded on the same chip which resides inside a single multiprocessor computer.
1Multicore means multiple processors embedded on the same chip (i.e., on the same piece of semiconducting material).
2In mid-2007, IBM unveiled Blue Gene/P, the second generation of one of the most powerful supercomputers in the world. The Blue Gene/P supercomputer configuration is a 294,912-processor, 72-rack system harnessed to a high-speed, optical network. It is used for executing applications like hydrodynamics, quantum chemistry, molecular dynamics, climate modeling, and financial modeling.
3The multicore era for mainstream computers began in spring 2005 when Intel and AMD (followed the lead of IBM and Sun Microsystems) announced that their microprocessors would rely on multiple processors or cores, and introduced computers with two processors each (dual-core processors) which enable the execution of two programs in parallel.
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
