Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

  • Create BookmarkCreate Bookmark
  • Create Note or TagCreate Note or Tag
  • PrintPrint
Share this Page URL
Help

Chapter 7. Designing lock-free concurren... > Examples of lock-free data structure...

7.2. Examples of lock-free data structures

In order to demonstrate some of the techniques used in designing lock-free data structures, we’ll look at the lock-free implementation of a series of simple data structures. Not only will each example describe the implementation of a useful data structure, but I’ll use the examples to highlight particular aspects of lock-free data structure design.

As already mentioned, lock-free data structures rely on the use of atomic operations and the associated memory-ordering guarantees in order to ensure that data becomes visible to other threads in the correct order. Initially, we’ll use the default memory_order_seq_cst memory ordering for all atomic operations, because that’s the easiest to reason about (remember that all memory_order_seq_cst operations form a total order). But for later examples we’ll look at reducing some of the ordering constraints to memory_order_acquire, memory_order_release, or even memory_order_relaxed. Although none of these examples use mutex locks directly, it’s worth bearing in mind that only std::atomic_flag is guaranteed not to use locks in the implementation. On some platforms what appears to be lock-free code might actually be using locks internal to the C++ Standard Library implementation (see chapter 5 for more details). On these platforms, a simple lock-based data structure might actually be more appropriate, but there’s more to it than that; before choosing an implementation, you must identify your requirements and profile the various options that meet those requirements.


  

You are currently reading a PREVIEW of this book.

                                                                                                                    

Get instant access to over $1 million worth of books and videos.

  

Start a Free 10-Day Trial


  
  • Safari Books Online
  • Create BookmarkCreate Bookmark
  • Create Note or TagCreate Note or Tag
  • PrintPrint