Herlihy / Shavit The Art of Multiprocessor Programming, Revised Reprint

1. Auflage 2012
ISBN: 978-0-12-397795-3
Verlag: Elsevier Science & Techn.
Format: EPUB
Kopierschutz: 6 - ePub Watermark

E-Book, Englisch, 536 Seiten

Revised and updated with improvements conceived in parallel programming courses, The Art of Multiprocessor Programming is an authoritative guide to multicore programming. It introduces a higher level set of software development skills than that needed for efficient single-core programming. This book provides comprehensive coverage of the new principles, algorithms, and tools necessary for effective multiprocessor programming. Students and professionals alike will benefit from thorough coverage of key multiprocessor programming issues. - This revised edition incorporates much-demanded updates throughout the book, based on feedback and corrections reported from classrooms since 2008 - Learn the fundamentals of programming multiple threads accessing shared memory - Explore mainstream concurrent data structures and the key elements of their design, as well as synchronization techniques from simple locks to transactional memory systems - Visit the companion site and download source code, example Java programs, and materials to support and enhance the learning experience

Maurice Herlihy received an A.B. in Mathematics from Harvard University, and a Ph.D. in Computer Science from M.I.T. He has served on the faculty of Carnegie Mellon University, on the staff of DEC Cambridge Research Lab, and is currently a Professor in the Computer Science Department at Brown University. Dr. Herlihy is an ACM Fellow, and is the recipient of the 2003 Dijkstra Prize in Distributed Computing. He shared the 2004 G”del Prize with Nir Shavit, with whom he also shared the 2012 Edsger W. Dijkstra Prize In Distributed Computing.

Autoren/Hrsg.

Herlihy, Maurice

Shavit, Nir

Leseproben

2

Mutual Exclusion

Mutual exclusion is perhaps the most prevalent form of coordination in multiprocessor programming. This chapter covers classical mutual exclusion algorithms that work by reading and writing shared memory. Although these algorithms are not used in practice, we study them because they provide an ideal introduction to the kinds of algorithmic and correctness issues that arise in every area of synchronization. The chapter also provides an impossibility proof. This proof teaches us the limitations of solutions to mutual exclusion that work by reading and writing shared memory, and will help to motivate the real-world mutual exclusion algorithms that appear in later chapters. This chapter is one of the few that contains proofs of algorithms. Though the reader should feel free to skip these proofs, it is very helpful to understand the kind of reasoning they present, because we can use the same approach to reason about the practical algorithms considered in later chapters.

2.1 Time

Reasoning about concurrent computation is mostly reasoning about time. Sometimes we want things to happen simultaneously, and sometimes we want them to happen at different times. We need to reason about complicated conditions involving how multiple time intervals can overlap, or, sometimes, how they cannot. We need a simple but unambiguous language to talk about events and durations in time. Everyday English is too ambiguous and imprecise. Instead, we introduce a simple vocabulary and notation to describe how concurrent threads behave in time.

In 1689, Isaac Newton stated “absolute, true and mathematical time, of itself and from its own nature, flows equably without relation to anything external.” We endorse his notion of time, if not his prose style. Threads share a common time (though not necessarily a common clock). A thread is a , and its state transitions are called .

Events are : they occur at a single instant of time. It is convenient to require that events are never simultaneous: distinct events occur at distinct times. (As a practical matter, if we are unsure about the order of two events that happen very close in time, then any order will do.) A thread produces a sequence of events 0, 1, … Threads typically contain loops, so a single program statement can produce many events. We denote the -th occurrence of an event by . One event another event , written ? , if occurs at an earlier time. The relation “?” is a total order on events.

Let 0 and 1 be events such that 0 ? 1. An (0, 1) is the duration between 0 and 1. Interval = (0, 1) = (0, 1), written ? , if 1 ? 0 (that is, if the final event of precedes the starting event of ). More succinctly, the ? relation is a partial order on intervals. Intervals that are unrelated by ? are said to be . By analogy with events, we denote the -th execution of interval by .

2.2 Critical Sections

In an earlier chapter, we discussed the Counter class implementation shown in Fig. 2.1. We observed that this implementation is correct in a single-thread system, but misbehaves when used by two or more threads. The problem occurs if both threads read the value field at the line marked “start of danger zone,” and then both update that field at the line marked “end of danger zone.”

Figure 2.1 The Counter class.

We can avoid this problem if we transform these two lines into a : a block of code that can be executed by only one thread at a time. We call this property . The standard way to approach mutual exclusion is through a Lock object satisfying the interface shown in Fig. 2.2.

Figure 2.2 The Lock interface.

For brevity, we say a thread (alternately ) a lock when it executes a lock() method call, and (alternately ) the lock when it executes an unlock() method call. Fig. 2.3 shows how to use a Lock field to add mutual exclusion to a shared counter implementation. Threads using the lock() and unlock() methods must follow a specific format. A thread is if:

1. each critical section is associated with a unique Lock object,

2. the thread calls that object’s lock() method when it is trying to enter the critical section, and

3. the thread calls the unlock() method when it leaves the critical section.

Figure 2.3 Using a lock object.

Pragma 2.2.1

In Java, these methods should be used in the following structured way.

1 mutex.lock();

2 try {

3 … //

4 } finally {

5 mutex.unlock();

6 }

This idiom ensures that the lock is acquired before entering the try block, and that the lock is released when control leaves the block, even if some statement in the block throws an unexpected exception.

We now formalize the properties that a good Lock algorithm should satisfy. Let be the interval during which executes the critical section for the -th time. Let us assume, for simplicity, that each thread repeatedly acquires and releases the lock, with other work taking place in the meantime.

Mutual Exclusion Critical sections of different threads do not overlap. For threads and , and integers and , either or .

Freedom from Deadlock If some thread attempts to acquire the lock, then some thread will succeed in acquiring the lock. If thread calls lock() but never acquires the lock, then other threads must be completing an infinite number of critical sections.

Freedom from Starvation Every thread that attempts to acquire the lock eventually succeeds. Every call to lock() eventually returns. This property is sometimes called .

Note that starvation freedom implies deadlock freedom.

The mutual exclusion property is clearly essential. Without this property, we cannot guarantee that a computation’s results are correct. In the terminology of Chapter 1, mutual exclusion is a safety property. The deadlock-freedom property is important. It implies that the system never “freezes.” Individual threads may be stuck forever (called ), but some thread makes progress. In the terminology of Chapter 1, deadlock-freedom is a liveness property. Note that a program can still deadlock even if each of the locks it uses satisfies the deadlock-freedom property. For example, consider threads and that share locks 0 and 1. First, acquires 0 and acquires 1. Next, tries to acquire 1 and tries to acquire 0. The threads deadlock because each one waits for the other to release its lock.

The starvation-freedom property, while clearly desirable, is the least compelling of the three. Later on, we will see practical mutual exclusion algorithms that fail to be starvation-free. These algorithms are typically deployed in circumstances where starvation is a theoretical possibility, but is unlikely to occur in practice. Nevertheless, the ability to reason about starvation is essential for understanding whether it is a realistic threat.

The starvation-freedom property is also weak in the sense that there is no guarantee for how long a thread waits before it enters the critical section. Later on, we will look at algorithms that place bounds on how long a thread can wait.

2.3 2-Thread Solutions

We begin with two inadequate but interesting Lock algorithms.

2.3.1 The LockOne Class

Fig. 2.4 shows the LockOne algorithm. Our 2-thread lock algorithms follow the following conventions: the threads have ids 0 and 1, the calling thread has , and the other = 1 - . Each thread acquires its index by calling Thread ID.get().

Figure 2.4 The LockOne algorithm.

Pragma 2.3.1

In practice, the Boolean flag variables in Fig. 2.4, as well as the victim and label variables in later algorithms must all be declared volatile to work properly. We explain the reasons in Chapter 1 and Appendix B. We will begin declaring the appropriate variables as volatile in Chapter 7.

We use write () to denote the event in which assigns value to field , and read (...