Chapter 11: Concurrent Stacks and Elimination

11.1 Introduction

The Stack class is a collection of items (of type T) that provides push() and pop() methods satisfying the last-in-first-out (LIFO) property: the last item pushed is the first popped. This chapter considers how to implement concurrent stacks. At first glance, stacks seem to provide little opportunity for concurrency, because push() and pop() calls seem to need to synchronize at the top of the stack. Surprisingly, perhaps, stacks are not inherently sequential. In this chapter, we show how to implement concurrent stacks that can achieve a high degree of parallelism. As a first step, we consider how to build a lock-free stack in which pushes and pops synchronize at a single location.

11.2 An Unbounded Lock-Free Stack

Fig. 11.1 shows a concurrent LockFreeStack class, whose code appears in Figs. 11.2, 11.3 and 11.4. The lock-free stack is a linked list, where the top field points to the first node (or null if the stack is empty.) For simplicity, we usually assume it is illegal to add a null value to a stack.

Figure 11.1: A Lock-free stack. In Part (a) a thread pushes value a into the stack by applying a compareAndSet() to the top field. In Part (b) a thread pops value a from the stack by applying a compareAndSet() to the top field.

  1  <b class="bold">public class</b> LockFreeStack {  2    AtomicReference top = ...

< Previous Excerpt Next Excerpt >

Purchase This Book

The Art of Multiprocessor Programming

TABLE OF CONTENTS

Chapter 11: Concurrent Stacks and Elimination

11.1 Introduction

11.2 An Unbounded Lock-Free Stack

Contact Preferences

This is embarrasing...

Customize Your GlobalSpec Experience

Select Your Free Newsletters

Industry Newsletters

Select Your Free Product Alerts

This is embarrasing...