nach oben

2013 | Buch

Kapitel lesen Erstes Kapitel lesen

Concurrent Programming: Algorithms, Principles, and Foundations

Algorithms, Principles, and Foundations

verfasst von: Michel Raynal

Verlag: Springer Berlin Heidelberg

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

The advent of new architectures and computing platforms means that synchronization and concurrent computing are among the most important topics in computing science. Concurrent programs are made up of cooperating entities -- processors, processes, agents, peers, sensors -- and synchronization is the set of concepts, rules and mechanisms that allow them to coordinate their local computations in order to realize a common task. This book is devoted to the most difficult part of concurrent programming, namely synchronization concepts, techniques and principles when the cooperating entities are asynchronous, communicate through a shared memory, and may experience failures. Synchronization is no longer a set of tricks but, due to research results in recent decades, it relies today on sane scientific foundations as explained in this book.

In this book the author explains synchronization and the implementation of concurrent objects, presenting in a uniform and comprehensive way the major theoretical and practical results of the past 30 years. Among the key features of the book are a new look at lock-based synchronization (mutual exclusion, semaphores, monitors, path expressions); an introduction to the atomicity consistency criterion and its properties and a specific chapter on transactional memory; an introduction to mutex-freedom and associated progress conditions such as obstruction-freedom and wait-freedom; a presentation of Lamport's hierarchy of safe, regular and atomic registers and associated wait-free constructions; a description of numerous wait-free constructions of concurrent objects (queues, stacks, weak counters, snapshot objects, renaming objects, etc.); a presentation of the computability power of concurrent objects including the notions of universal construction, consensus number and the associated Herlihy's hierarchy; and a survey of failure detector-based constructions of consensus objects.

The book is suitable for advanced undergraduate students and graduate students in computer science or computer engineering, graduate students in mathematics interested in the foundations of process synchronization, and practitioners and engineers who need to produce correct concurrent software. The reader should have a basic knowledge of algorithms and operating systems.

Inhaltsverzeichnis

Frontmatter

Lock-Based Synchronization

Frontmatter

Chapter 1. The Mutual Exclusion Problem

Abstract

This chapter introduces definitions related to process synchronization and focuses then on the mutual exclusion problem, which is one of the most important synchronization problems. It also defines progress conditions associated with mutual exclusion, namely deadlock-freedom and starvation-freedom.

Michel Raynal

Chapter 2. Solving Mutual Exclusion

Abstract

This chapter is on the implementation of mutual exclusion locks. As announced at the end of the previous chapter, it presents three distinct families of algorithms that solve the mutual exclusion problem. The first is the family of algorithms which are based on atomic read/write registers only. The second is the family of algorithms which are based on specialized hardware operations (which are atomic and stronger than atomic read/write operations). The third is the family of algorithms which are based on read/write registers which are weaker than atomic registers. Each algorithm is first explained and then proved correct. Other properties such as time complexity and space complexity of mutual exclusion algorithms are also discussed.

Michel Raynal

Chapter 3. Lock-Based Concurrent Objects

Abstract

After having introduced the notion of a concurrent object, this chapter presents lock-based methodologies to implement such objects. The first one is based on a low-level synchronization object called a semaphore. The other ones are based on linguistic constructs. One of these constructs is based on an imperative approach (monitor construct), while the other one is based on a declarative approach (path expression construct). This chapter closes the first part of the book devoted to lock-based synchronization.

Michel Raynal

On the Foundations Side: the Atomicity Concept

Chapter 4. Atomicity: Formal Definition and Properties

Abstract

Atomicity is a consistency condition, i.e., it allows us to answer the following question: Is this implementation of a concurrent object correct? The atomicity notion for read/write registers was introduced in Chap. 1, where algorithms that solve the mutual exclusion problem (i.e., algorithms which implement lock objects) were presented. Chap. 3 presented semaphore objects and programming language constructs which allow designers of concurrent objects to benefit from lock objects.

Michel Raynal

Mutex-Free Synchronization

Frontmatter

Chapter 5. Mutex-Free Concurrent Objects

Abstract

This chapter is devoted to mutex-free implementations of concurrent objects. Mutex-freedom means that in no way (be it explicit or implicit) is the implementation of a concurrent object allowed to rely on critical sections (locks). The chapter consequently introduces new progress conditions suited to mutex-free object implementations, namely obstruction-freedom, non-blocking, and wait-freedom. It then presents mutex-free implementations of concurrent objects (splitter, queue, stack, etc.) that satisfy these progress conditions. Some of these implementations are based on read/write atomic registers only, while others use also more sophisticated registers that can be accessed by hardware-provided primitive operations such as compare&swap, swap, or fetch&add (which are stronger than base read/write operations). To conclude, this chapter presents an approach based on failure detectors that allows the construction of contention managers that permit a non-blocking or a wait-free implementation of a concurrent object to be obtained from an obstruction-free implementation of that object.

Michel Raynal

Chapter 6. Hybrid Concurrent Objects

Abstract

This chapter focuses on hybrid implementations of concurrent objects. Roughly speaking, “hybrid” means that lock-based code and mutex-free code can be merged in the same implementation. After defining the notion of a hybrid implementation, this chapter presents hybrid implementations of concurrent objects, where each implementation has its own features. The chapter presents also the notion of an abortable object and shows how a starvation-free implementation of a concurrent object can be systematically obtained from an abortable non-blocking version of the same object.

Michel Raynal

Chapter 7. Wait-Free Objects from Read/Write Registers Only

Abstract

The two previous chapters were on the implementation of concurrent atomic objects (such as queues and stacks). More precisely, the aim of Chap. 5 was to introduce and illustrate the notion of a mutex-free implementation and associated progress conditions, namely obstruction-freedom, non-blocking and wait-freedom. The aim of Chap. 6 was to introduce and investigate the notion of a hybrid implementation. In both cases, the internal representation of the high-level object that was constructed was based on atomic read/write registers and more sophisticated registers accessed by stronger hardware-provided operations such as \( \mathsf{{compare \& swap}}()\), \( \mathsf{{fetch \& add}}()\), or \(\mathsf{{swap}}()\).

Michel Raynal

Chapter 8. Snapshot Objects from Read/Write Registers Only

Abstract

This chapter is devoted to snapshot objects. Such an object can be seen as a store-collect object whose two operations are atomic. After having defined the concept of a snapshot object, this chapter presents wait-free implementations of it, which are based on atomic read/write registers only. This chapter introduces also the notion of an immediate snapshot object, which can be seen as the atomic counterpart of the fast store-collect object presented in the previous chapter.

Michel Raynal

Chapter 9. Renaming Objects from Read/Write Registers Only

Abstract

This chapter is devoted to the renaming problem. After having presented the problem, it describes three wait-free implementations of one-shot renaming objects. These implementations, which are all based on read/write registers, differ in their design principles, their cost, and the size of the new name space allowed to the processes. Finally, the chapter presents a long-lived renaming object based on registers stronger than read/write registers, namely test&set registers.

Michel Raynal

The Transactional Memory Approach

Frontmatter

Chapter 10. Transactional Memory

Abstract

This chapter is devoted to software transactional memories (STM). This concept was first proposed by M. Herlihy and J. Moss (1993), and later refined by N. Shavit and D. Touitou (1997). The idea is to provide the designers of multiprocess programs with a language construct (namely, the notion of an atomic procedure called a transaction) that discharges them from the management of synchronization issues. More precisely, a programmer has to concentrate her efforts only on defining which parts of processes have to be executed atomically and not on the way atomicity is realized, this last issue being automatically handled by the underlying STM system.

This chapter, which is mainly on basic principles of algorithms implementing STM systems, assumes that the asynchronous processes are reliable (i.e., they never crash).

Michel Raynal

On the Foundations Side: from Safe Bits to Atomic Registers

Chapter 11. Safe, Regular, and Atomic Read/Write Registers

Abstract

For self-containment, this chapter starts with a short presentation of the notions of safe, regular, and atomic read/write registers (which were introduced in Chap. 2). It then presents simple wait-free implementations of “high-level” registers from “low-level” registers. The notions of “high-level” and “low-level” used here are not related to the computability power but to the abstraction level. This is because, as we will see in the next two chapters, while a regular register is easier to use than a safe register and an atomic register is easier to use than a regular register, they are all computationally equivalent; i.e., any of them can be built wait-free from any other without enriching the underlying system with additional computational power.

The proofs of the theorems stated in this chapter use the definitions and terminology introduced in Chap. 4.

Michel Raynal

Chapter 12. From Safe Bits to Atomic Bits: Lower Bound and Optimal Construction

Abstract

Constructions of higher-abstraction-level read/write registers from lower-abstraction-level read/write registers were presented in the previous chapter. As we have seen, the notion of “abstraction level” that was considered has several dimensions, namely (a) the safety, regularity, or atomicity behavior of the base registers, (b) the number of values they can contain, and (c) the fact that they are SWSR, SWMR, or MWMR registers.

One of these constructions has shown how to build an SWSR atomic register from an SWSR safe register. This construction, which is based on sequence numbers, was particularly simple. Unfortunately, as it uses sequence numbers, it is an unbounded construction. This chapter presents a bounded construction that builds an atomic bit from SWSR safe (or regular) bits. This construction, which is due to J. Tromp (1989), is optimal with respect to the number of safe bits that are used; namely, it requires only three safe bits.

Before presenting this non-trivial construction, this chapter presents a lower bound theorem due to L. Lamport (1986). This theorem states that, in any bounded construction of an SWSR atomic register from SWSR safe (or regular) registers, both the reader and the writer must write the shared memory which means that bidirectional communication is necessary.

Michel Raynal

Chapter 13. Bounded Constructions of Atomic b-Valued Registers

Abstract

The previous chapter has shown how to construct an SWSR atomic bit from a bounded number (three) of safe bits. Moreover, a bounded construction, due to K. Vidyasankar, of a \(b\)-valued atomic register (i.e., a register that can take \(b\) different values) from atomic bits was presented in Chap. 11. It is consequently possible to obtain an SWSR \(b\)-valued atomic register from a bounded number of SWSR safe bits. However, stacking these two constructions requires \(O(b)\) safe bits, i.e., a number of safe bits linear with respect to the size of the value domain of the atomic register we want to construct.

This chapter presents two efficient bounded constructions of an SWSR \(b\)-valued atomic register from a constant number of atomic bits and a constant number of \(b\)-valued safe registers each made up of \(\lceil \log _2 b \rceil \) safe bits. As an atomic bit can be built from three safe bits, these constructions (due to J. Tromp and K. Vidyasankar) require only \(O(\lceil \log _2 b\rceil )\) safe bits and are consequently efficient.

As in the previous chapters, the read and write operations associated with the constructed SWSR atomic \(b\)-valued register \(R\) are denoted \(R.\mathsf{{read}}()\) and \(R.\mathsf{{write}}()\), respectively.

Michel Raynal

On the Foundations Side: the Computability Power of Concurrent Objects (Consensus)

Chapter 14. Universality of Consensus

Abstract

This chapter introduces the notion of a universal object and a universal construction and shows that the consensus object is universal. To that end two consensus-based universal constructions (which rest on different principles) are presented. This chapter shows also that binary consensus is as powerful as multi-valued consensus, hence binary consensus is universal.

Michel Raynal

Chapter 15. The Case of Unreliable Base Objects

Abstract

The previous chapter presented universal constructions that allow one to build implementations of any object defined by a sequential specification (on total operations) that are wait-free, i.e., that tolerate any number of process crashes. As we have seen, these constructions rest on two types of objects: atomic read/write registers and consensus objects. These universal constructions assume that these base objects are reliable; namely, they implicitly consider that their behavior always complies with their specification. As an example, given an atomic register \(R\), it is assumed that an invocation of \(R.\mathsf{{read}}()\) always returns the last value that was written into \(R\) (“last” is with respect to the linearization order). Similarly, given a consensus object \( CONS \), an invocation \( CONS .\mathsf{{propose}}()\) is assumed to always return the single value decided by this consensus object.

This chapter revisits the failure-free object assumption and investigates the case where the base objects are prone to failure. It focuses on the self-implementation of such objects. Self-implementation means that the internal representation of the reliable object \(RO\) that is built relies on a bounded number \(m\) of objects \(O_1,\ldots ,O_m\) of the very same type. Hence, a reliable atomic register is built from a set of atomic registers of which some (not known in advance) can be faulty, and similarly for a consensus object. Moreover, such a self-implementation has to be \(t\)-tolerant. This means that the reliability of the object \(RO\) that is built has to be guaranteed despite the fact that up to \(t\) of the base objects \(O_1,\ldots ,O_m\) which implement \(RO\) can be faulty (Fig. 15.1). Hence, this chapter is devoted to the self-implementation of \(t\)-tolerant atomic read/write registers and consensus objects.

From a terminology point of view, wait-freedom is related to process crashes while \(t\)-tolerance is related to the failure of base objects.

Michel Raynal

Chapter 16. Consensus Numbers and the Consensus Hierarchy

Abstract

An object type characterizes the possible behaviors of a set of objects (namely, the objects of that type). As an example the type consensus defines the behavior of all consensus objects. Similarly, the type atomic register defines the behavior of all atomic registers. This chapter considers concurrent object types defined by a sequential specification on a finite set of operations.

We have seen in Chap. 14 that an object type T is universal if, together with atomic registers, objects of type T allow for the wait-free construction of any type T \( {\prime}\) (defined by a sequential specification on total operations). As consensus objects are universal, a natural and fundamental question that comes to mind is the following:

Which object types allow us to wait-free implement a consensus object?

As an example, do atomic registers alone or atomic registers plus queues allow consensus objects to be wait-free implemented? This chapter addresses this question. To that end it first introduces the notion of a consensus number that can be associated with an atomic object type. (In the following, when there is no confusion, we sometimes use equivalently the words “object” and “object type”.) It then shows that the consensus number notion allows for the ranking of atomic objects with respect to their synchronization power when one is interested in wait-free object implementations.

Michel Raynal

Chapter 17. The Alpha(s) and Omega of Consensus: Failure Detector-Based Consensus

Abstract

Chapter 16 has shown that a base read/write system enriched with objects whose consensus number is at least \(x\) allows consensus objects to be wait-free implemented in a system of at most \(x\) processes. Moreover, thanks to universal constructions (Chap. 14) these objects allow construction of wait-free implementations of any object defined by a sequential specification on total operations.

Hence, the question: is the enrichment of a read/write asynchronous system with stronger operations such as compare&swap the only means to obtain wait-free implementations of consensus objects? This chapter shows that the answer to this question is “no”. To that end it presents another approach which is based on information on failures (the failure detector-based approach). Each process is enriched with a specific module that gives it (possibly unreliable) information on the faulty/correct status of processes.

The chapter presents first a de-construction of compare&swap that allows us to introduce two types of objects whose combination allows consensus to be solved despite asynchrony and any number of process crashes. One is related to the safety of consensus, the other one to its liveness. The chapter presents then the failure detector \(\Omega \) which has been proved to be the one providing the weakest information on failure which allows consensus to be solved. \(\Omega \) is used to ensure the consensus termination property. Several base objects that can be used to guarantee the consensus safety properties are then introduced. Differently from \(\Omega \), these objects can be wait-free built from read/write registers only. The chapter finally investigates additional synchrony assumptions that allow \(\Omega \) to be implemented.

Michel Raynal

Backmatter

Titel: Concurrent Programming: Algorithms, Principles, and Foundations
verfasst von: Michel Raynal
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-32027-9
Print ISBN: 978-3-642-32026-2
DOI: https://doi.org/10.1007/978-3-642-32027-9