Designing Concurrent Data Structures

In the previous chapter, we touched on the basics of concurrency and multithreading in C++. One of the biggest challenges in concurrent code design is properly handling data races. The concepts of thread synchronization and orchestration are not easy to grasp. However, they are essential. While we can use synchronization primitives such as mutexes in all places where data races may occur, that practice has costs and side effects, which must be considered.

A better way of designing concurrent code is to avoid locks at all costs. That would not only increase the performance of the application but also make it much safer than before. Easier said than done – lock-free programming is a challenging topic, which we will introduce in this chapter. In particular, we will go further into the fundamentals of designing lock-free algorithms and data structures. This is a complex topic being continuously researched by many outstanding developers. We...

Technical requirements

The g++ compiler with the -std=c++2a option is used to compile the examples in this chapter. You can find the source files used in this chapter at https://github.com/PacktPublishing/Expert-CPP.

Thread safety

Thread safety is a crucial idea in computer science and programming. In the current world, where applications can run in parallel both locally and remotely, being able to write code that multiple processes can execute simultaneously plays a crucial role in software development.

Imagine a C++ first-person platform game with functions that allow the player to perform actions such as moving and jumping, computer-generated characters that can attack the player, and a user interface that keeps the player updated with the most relevant information about the status of the game (i.e., points, health, etc.). In this context, all those functions must be thread-safe. If the functions are not thread-safe, the game can behave unpredictably. For example, the player could end up interacting with a piece of a computer-generated object that is not in that spot anymore, or they may see a status of their actions that is outdated or incorrect.

This example includes the main concerns...

Lock-based concurrent data structures

Lock-based concurrent data structures are a type of concurrent structure. They are called lock-based because they use synchronization-locking mechanisms such as mutexes to ensure that only one thread can access the underlying data.

A thread-safe singleton pattern

In the previous chapter, we discussed deadlocks and ways to avoid them. The last example we used was implementing a thread-safe singleton pattern. We will expand on that in this section. Imagine that we want to use a class for creating database connections. We will name that class connection_manager.

Here’s a simple pattern implementation that tracks down the connections to the database. Keeping a separate connection whenever we need access to the database is not a good practice. Instead, we will re-use the existing connection to query the database from different parts of the program:

#include <memory>namespace db_utils {
class connection_manager {
private:
 ...

Lock-free concurrent data structures

As mentioned in the previous sections, lock-based data structures have some drawbacks. Among them, the reduction in performance is caused by the need to check the synchronization structures and the possibility of introducing problems such as deadlocking. A possible solution to this problem is to use lock-free concurrent data structures.

Unlike lock-based functions, where one thread can block another, and both might wait for some condition before making progress, a lock-free state ensures progress is made by at least one of the threads. We say that algorithms and data structures using data synchronization primitives are blocking. That is, a thread is suspended until another thread acts. That means the thread can’t progress until the block is removed (typically unlocking a mutex). Our interest lies in data structures and algorithms that don’t use blocking functions. We call some of them lock-free, although we should make a distinction...

Summary

In this chapter, we introduced a simple example of a stack design. There are more complex examples to research and follow. When we discussed designing a concurrent stack, we looked at two versions, one representing a lock-free stack. Unlike lock-based solutions, lock-free data structures and algorithms are the ultimate goals for programmers, as they provide mechanisms to prevent data races without synchronizing the resources.

We also introduced atomic types and operations, which you can use in your projects to ensure instructions are indivisible. If you remember to use atomic types when using multithreading, it is unnecessary to worry about synchronization. We strongly suggest you continue researching the topic and build more robust, complex lock-free data structures. In the next chapter, we will see how to design world-ready applications.

Questions

1. What is the advantage of checking whether the instance is null in the multi-threaded singleton implementation?
2. What is the purpose of using a mutex in implementing a lock-based stack’s copy constructor?
3. What are atomic types, and what are their basic operations?
4. What operations do the load() and store() functions perform in atomic types?
5. What additional operations are supported on std::atomic<int> compared to std::atomic<>?

Further reading

• Concurrent Patterns and Best Practices by Atul Khot, at https://www.packtpub.com/application-development/concurrent-patterns-and-best-practices
• Mastering C++ Multithreading by Maya Posch, at https://www.packtpub.com/application-development/mastering-c-multithreading