Chapter 06, Designing lock based concurrent data structures

잠금 기반의 동시 데이터 구조 디자인

Designing lock-based concurrent data structures

이번 챕터에서 다루는 내용

• 동시성을 위한 데이터구조 디자인은 무엇인가?
• 이렇게 하기 위한 가이드라인(지침)
• 동시성 디자인이 적용된 데이터구조 구현 예시

This chapter covers

• What it means to design data structures for concurrency
• Guidelines for doing so
• Example implementations of data structures designed for concurrency

지난 챕터에서 우리는 원자조작(atomic operation)과 메모리 모델과 같이 저수준의 자세한 것들을 공부했다. 이번 챕터에서 우리는 저수준의 자세한 것들은 쉬고(7장도 마친가지) 데이터 구조에 대해 생각해보자.

In the last chapter we looked at the low-level details of atomic operations and the memory model. In this chapter we’ll take a break from the low-level details (although we’ll need them for chapter 7) and think about data structures.

프로그래밍 문제해결하기 위해 사용하는 데이터 구조의 선택은 솔루션 전체의 중요한 부분이 될 수 있고, 병렬 프로그래밍 문제가 예외 발생하지 않게 해준다. 만약 데이터 구조가 여러 쓰레드로부터 접근이 가능해야하고, 완전히 불변이어서 데이터가 절대 변하지 않고, 동기화가 필요하지 않으려면 프로그램이 스레드간에 변경사항의 완벽한 동기화를 보장도록 설계되어야한다. 한 방법은 챕터 3,4에서 보았던 기술들을 이용하여, 데이터를 보호하기 위해 별도의 외부 뮤텍스 잠금을 사용하는 것이고, 다른 방법은 동시 접근을 위해 데이터 구조 자체를 설계하는것이다.

The choice of data structure to use for a programming problem can be a key part of the overall solution, and parallel programming problems are no exception. If a data structure is to be accessed from multiple threads, either it must be completely immutable so the data never changes and no synchronization is necessary, or the program must be designed to ensure that changes are correctly synchronized between threads. One option is to use a separate mutex and external locking to protect the data, using the techniques we looked at in chapters 3 and 4, and another is to design the data structure itself for concurrent access.

동시성 데이터 구조를 설계 할 때, 당신은 뮤텍스와 상태변수(condition variable) 같은 이전 챕터의 멀티 쓰레드 기반 응용프로그램의 기본 빌딩 블럭(build-ing blocks)을 사용할 수 있습니다. 대신에 당신은 이미 이런 빌딩 블럭들(building blocks)을 데이터 구조들이 다중 쓰레드들의 동시접근으로부터 안전하게 쓰도록 합치는 방법을 몇개 보았을것이다.

When designing a data structure for concurrency, you can use the basic building blocks of multithreaded applications from earlier chapters, such as mutexes and condition variables. Indeed, you’ve already seen a couple of examples showing how to combine these building blocks to write data structures that are safe for concurrent access from multiple threads.

이번 챕터에서 우리는 동시성 데이터 구조 설계의 일반적인 가이드라인을 보면서 배워나갈 것이다. 우리는 상태변수(condition variable)들의 기본적인 빌딩 블럭(building blocks)들을 공부한 후, 복잡한 데이터 구조들을 공부하기전에, 이러한 기본적인 데이터 구조들의 설계를 되짚어 볼 것이다. 챕터 7에서 우리는 기본으로 돌아가서(go right back to basics), 어떻게 챕터 5에서 설명한 잠금없는 데이터 구조들을 구축하는 원자 연산(atomic operation)을 사용하는지 볼 것이다.

In this chapter we’ll start by looking at some general guidelines for designing data structures for concurrency. We’ll then take the basic building blocks of locks and condition variables and revisit the design of those basic data structures before moving on to more complex data structures. In chapter 7 we’ll look at how to go right back to basics and use the atomic operations described in chapter 5 to build data structures without locks.

그래서 속히 동시성을 위한 데이터 구조 설계에는 무엇이 있는지 알아보자

So, without further ado, let’s look at what’s involved in designing a data structure for concurrency.

6.1 동시성을 위한 설계는 무엇인가?

What does it mean to design for concurrency?

기본적인 수준에서, 동시성 데이터 구조를 설계하는것은 다중 쓰레드가 동시에 데이터 구조에 접근할 수 있거나, 같거나 다른 연산을 수행하고, 각각의 쓰레드가 데이터 구조의 일관성있는 시각으로 볼 것이다. 어떤 데이터는 손실되거나 손상되고, 모든 불변값(invariants)은 확정될것이고, 문제의 경쟁 상태(problematic race conditions)도 없을것이다. 이러한 데이터 구조는 쓰레드 세이프(thread-safe)하다고 불린다. 일반적으로, 데이터 구조는 각각의 동시 접근의 타입(types)에 안전할 것이다. 동시성 데이터 구조는 하나의 동작 유형을 수행하는 다중 스레드를 가지는것이 가능한 반면, 어떤 동작은 단일 쓰레드에 의해 단독 접근을 필요로한다. 만약 그들이 서로 다른 작업들을 수행하더라도, 다중 쓰레드들이 같은 작업을 수행하는것이 문제가 될 때, 동시성 데이터 구조에 접근하는 다중 쓰레드들은 안전할 것이다.

At the basic level, designing a data structure for concurrency means that multiple threads can access the data structure concurrently, either performing the same or distinct operations, and each thread will see a self-consistent view of the data structure. No data will be lost or corrupted, all invariants will be upheld, and there’ll be no problematic race conditions. Such a data structure is said to be thread-safe. In general, a data structure will be safe only for particular types of concurrent access. It may be possible to have multiple threads performing one type of operation on the data structure concurrently, whereas another operation requires exclusive access by a single thread. Alternatively, it may be safe for multiple threads to access a data structure concurrently if they’re performing different actions, whereas multiple threads performing the same action would be problematic.

진정한 동시성을 설계하기 위해서는 쓰레드들이 데이터 구조에 접근하도록 하는 동시성을 위한 기회를 제공해야한다. 본질적으로, 뮤텍스(mutex)는 상호 배제(mutual exclusion)을 제공한다. : 한번에 오직 한 쓰레드가 뮤텍스(mutex)의 자물쇠(lock)를 얻을 수 있다. 뮤텍스(mutex)는 보호하는 데이터에 대한 접근을 명시적으로 막음으로써 데이터 구조를 보호할 수 있다.

Truly designing for concurrency means more than that, though: it means providing the opportunity for concurrency to threads accessing the data structure. By its very nature, a mutex provides mutual exclusion: only one thread can acquire a lock on the mutex at a time. A mutex protects a data structure by explicitly preventing true concurrent access to the data it protects.

이것을 직렬화(serialization)라고 부른다 : 쓰레드들은 뮤텍스(mutex)로부터 보호받는 데이터에 번갈아 가며 접근한다. 쓰레드들은 데이터에 접근할때 동시에 접근하지 말고, 순차적으로(serially) 접근해야한다. 따라서 당신은 동시 접근을 허용하는 데이터 구조를 설계할때 조심해야한다. 몇몇 데이터 구조들은 다른것들보다 동시성의 범위가 더 넓지만, 모든 경우의 방법(idea)는 같다 : 보호할 영역이 작고, 연산이 적은것들은 직렬화(serialized)하고, 이것들은 동시성의 가능성이 더 크다.

This is called serialization: threads take turns accessing the data protected by the mutex; they must access it serially rather than concurrently. Consequently, you must put careful thought into the design of the data structure to enable true concurrent access. Some data structures have more scope for true concurrency than others, but in all cases the idea is the same: the smaller the protected region, the fewer operations are serialized, and the greater the potential for concurrency.

몇몇 데이터 구조 설계들을 보기 전에, 언제 동시성을 디자인해야하는지 설명된 가벼운 가이드라인들을 살펴보도록 하자.

Before we look at some data structure designs, let’s have a quick look at some simple guidelines for what to consider when designing for concurrency.

6.1.1 동시성 데이터 구조 설계 가이드라인

Guidelines for designing data structures for concurrency

언급했듯이, 동시 접근이 가능한 데이터 구조를 설계할때 2개의 관점에서 고려해야한다. : 접근들이 안전하고, 완전한 동시 접근이 가능하도록 보장한다. 나는 어떻게 데이터 구조를 쓰레드-세이프(thread-safe)하게 만드는지에 대한 기초를 챕터 3에서 다루었다 :

• 어떠한 쓰레드도 다른 쓰레드의 행동에의해 부셔져버린 데이터 구조가 어디에 있는지 invariants 상태를 볼 수 없도록 보장한다.
• 완전한 작업보다는 오히려 작업단계에 대한 기능을 제공함으로써 데이터 구조에 대한 인터페이스에 들어있는 race conditions을 피하기 위해 주의해야한다.
• 데이터 구조는 invariants가 broken되는것을 막기 위해 존재하는 예외들이 어떻게 동작하는지 주의를 기울여야 한다.
• 데이터 구조를 사용할때 잠금의 범위와 중첩 잠금 가능한 경우를 방지함으로써 교착상태(deadlock)에대한 기회를 최소화해야한다.

As I just mentioned, you have two aspects to consider when designing data structures for concurrent access: ensuring that the accesses are safe and enabling genuine concurrent access. I covered the basics of how to make the data structure thread-safe back in chapter 3:

• Ensure that no thread can see a state where the invariants of the data structure have been broken by the actions of another thread.
• Take care to avoid race conditions inherent in the interface to the data structure by providing functions for complete operations rather than for operation steps.
• Pay attention to how the data structure behaves in the presence of exceptions to ensure that the invariants are not broken.
• Minimize the opportunities for deadlock when using the data structure by restricting the scope of locks and avoiding nested locks where possible.

이러한 세부사항들을 생각하기 전에, 데이터구조의 user에 넣을때 어떤 제약조간이 있는지에 대해 생각하는것은 중요하다. 만약 한 쓰레드가 다른 쓰레드에게 불려도 안전한 특정한 함수를 통해 데이터 구조에 접근할때

Before you think about any of these details, it’s also important to think about what constraints you wish to put on the users of the data structure; if one thread is accessing the data structure through a particular function, which functions are safe to call from other threads

이것은 실제로 고민해야할 중요한 문제이다. 일반적으로 생성자들과 소멸자들은 데이터 구조로 독립적인 접근을 필요로 하지만, 이것은 구성이 완료되거나 파괴가 시작도니 후에 전에 액세스하지 않을 것을 보장하기 위해 사용자에 달려있다. 데이터 구조는 할당, swap() 또는 복사 생성(copy construction)을 지원한다면, 데이터 구조 설계자로서, 이러한 작업에도 불구 독림적(배타적) 액세스를 보장하기 위해 다른 작업으로 또는 사용자가 필요한지 여부 동시에 안전하게 호출인지 여부를 결정해야 데이터 구조를 조작하기 위한 기능의 대부분은 동시에 문제없이 여러 스레드에서 호출 할 수 있다(?? 해석 많이 이상할듯...)

This is actually quite a crucial question to consider. Generally constructors and destructors require exclusive access to the data structure, but it’s up to the user to ensure that they’re not accessed before construction is complete or after destruction has started. If the data structure supports assignment, swap(), or copy construction, then as the designer of the data structure, you need to decide whether these operations are safe to call concurrently with other operations or whether they require the user to ensure exclusive access even though the majority of functions for manipulating the data structure may be called from multiple threads concurrently without problem.

고려해야할 두 번재 측면은 진정한 동시 접근을 가능하게 하는것이다. 여기서 가이드라인의 방법을 많이 설명할 수 없다. 그 대신, 데이터 구조 설계자로서 스스로에게 물어봐야할 질문들 리스트이다

• 잠금(자물쇠)들의 범위을 연산의 일부가 잠금 밖에 수행되도록 제한할 수 있는가?
• 다른 데이터 구조의 부분(part)이 다른 뮤텍스로 부터 보호받을 수 있는가?
• 모든 연산들이 같은 수준의 보호를 받을 수 있는가?
• 데이터 구조의 간단한 변경이 연산 Semantic에 영향을 주지 않으면서 동시성을 위한 기회를 개선할 수 있는가?

The second aspect to consider is that of enabling genuine concurrent access. I can’t offer much in the way of guidelines here; instead, here’s a list of questions to ask yourself as the data structure designer:

• Can the scope of locks be restricted to allow some parts of an operation to be performed outside the lock?
• Can different parts of the data structure be protected with different mutexes?
• Do all operations require the same level of protection?
• Can a simple change to the data structure improve the opportunities for concurrency without affecting the operational semantics?

모든 이런 질문들은 하나의 생각에 의해 인도된다(guided) : 어떻게 반드시 발생하는 직렬화(serialization) 양을 최소화 하는지 그리고, 진정한 동시성의 양을 최대화 시켰는가? 데이터 구조가 데이터 구조를 읽기만하는 다중 쓰레드로 부터의 동시 접근을 허용하는 경우는 드물지 않은(It's not uncommon)반면 데이터이 구조를 수정할 수 있는 쓰레드는 독립적인 접근을 가져야 한다. boost::shared_mutex같은 구조를 사용하면 지원된다. 반면에, 곧 보겠지만, 데이터 구조가 같은 연산을 수행하는 쓰레드를 직렬화(serializing)하는 동안 다른 연산을 수행하는 쓰레드들로 부터 동시 접근을 지원하는것은 아주 흔하다.

All these questions are guided by a single idea: how can you minimize the amount of serialization that must occur and enable the greatest amount of true concurrency? It’s not uncommon for data structures to allow concurrent access from multiple threads that merely read the data structure, whereas a thread that can modify the data structure must have exclusive access. This is supported by using constructs like boost:: shared_mutex. Likewise, as you’ll see shortly, it’s quite common for a data structure to support concurrent access from threads performing different operations while serializing threads that try to perform the same operation.

간단한 쓰레드 세이프한 데이터 구조들은 일반적으로 뮤텍스와 데이터를 보호하기 위한 자물쇠(locks)를 사용한다. 비록 이것은 이슈가 있지만, 챕터 3에서 봤듯이, 한번에 오직 한 쓰레드가 데이터 구조에 접근할 수 있도록 보장하는것은 상대적으로 쉽다. 쓰레드 세이프한 데이터 구조의 설계로 용이or완화(ease)하려면, 이번장에 있는 잠금기반 데이터 구조를 지켜보는것에 충실하고, 챕터7에서 다루는 자물쇠(locks)없이 동시성 데이터 구조를 설계하지 말아야 한다.

The simplest thread-safe data structures typically use mutexes and locks to protect the data. Although there are issues with this, as you saw in chapter 3, it’s relatively easy to ensure that only one thread is accessing the data structure at a time. To ease you into the design of thread-safe data structures, we’ll stick to looking at such lock-based data structures in this chapter and leave the design of concurrent data structures without locks for chapter 7.

6.2 잠금기반 동시성 데이터 구조

6.2 Lock-based concurrent data structures

잠금기반 동시성 데이터 구조 설계는 데이터에 접근하려고 하려고할때 오른쪽 뮤텍스(right mutex)가 잠기고, 잠금은 최소한의 시간동안 유지되도록 보장하는 것이다. 한 뮤텍스가 한 데이터 구조를 보호할때는 hard(단단->안전? or 어렵다)하다. 데이터가 3장에서 봤듯이 인터페이스 내부에 경쟁상태가 없는 뮤텍스 잠금 보호 밖에서 접근하지 못하도록 보장해야한다. 만약 데이터 구조의 각 부분을 보호하기위해 분리된 뮤텍스를 사용할때, 문제는 악화된다, 그리고 데이터 구조의 연산이 잠긴 뮤텍스를 하나 이상 필요로 할때, deadlock의 가능성이 있다. 그러므로 단일 뮤덱스로 사용하는 데이터구조의 설계보다 다중 뮤텍스로 사용하는 데이터 구조의 설계를 더 고려할 필요가 있다.

The design of lock-based concurrent data structures is all about ensuring that the right mutex is locked when accessing the data and ensuring that the lock is held for a minimum amount of time. This is hard enough when there’s just one mutex protecting a data structure. You need to ensure that data can’t be accessed outside the protection of the mutex lock and that there are no race conditions inherent in the interface, as you saw in chapter 3. If you use separate mutexes to protect separate parts of the data structure, these issues are compounded, and there’s now also the possibility of deadlock if the operations on the data structure require more than one mutex to be locked. You therefore need to consider the design of a data structure with multiple mutexes even more carefully than the design of a data structure with a single mutex.

이번 세션에서 뮤텍스와 데이터를 보호하기 위한 자물쇠(lock)을 사용하면서 몇몇 간단한 데이터 구조를 설계해보면서 세션 6.1.1의 가이드 라인을 적용할 것이다. 각각의 케이스에서 데이터구조가 쓰레드세이프하면서 더 나은 동시성이 가능하게하는 기회를 찾아내야한다.

In this section you’ll apply the guidelines from section 6.1.1 to the design of several simple data structures, using mutexes and locks to protect the data. In each case you’ll seek out the opportunities for enabling greater concurrency while ensuring that the data structure remains thread-safe.

3장의 스택구현을 보면서 시작하자. 이것은 주위의 간단한 데이터 구조들 중 하나이고, 오직 단일 뮤텍스를 사용한다. 정말 쓰레드 세이프 할까? 어떻게하면 진정한 동시성 달성의 관점에서 fare할 수 있을까?

Let’s start by looking at the stack implementation from chapter 3; it’s one of the simplest data structures around, and it uses only a single mutex. Is it really thread- safe? How does it fare from the point of view of achieving true concurrency?

6.2.1 자물쇠(lock)을 사용한 쓰레드 세이프한 스택(Stack)

A thread-safe stack using locks

3장의 쓰레드 세이프 스택을 재현하였다. 항목을 스택에 넣고 뺄수 있는 std::stack와 유사한 쓰레드 세이프한 데이터 구조를 작성한것입니다.

The thread-safe stack from chapter 3 is reproduced in the following listing. The intent is to write a thread-safe data structure akin to std::stack<>, which supports pushing data items onto the stack and popping them off again.

#include <exception>

struct empty_stack: std::exception {
    const char *what() const throw();
};

template<typename T>
class threadsafe_stack {
private:
    std::stack <T> data;
    mutable std::mutex m;
public:
    threadsafe_stack() { }
    threadsafe_stack(const threadsafe_stack &other)
    {
        std::lock_guard <std::mutex> lock(other.m);
        data = other.data;
    }
    threadsafe_stack &operator=(const threadsafe_stack &) = delete;
    void push(T new_value)
    {
        std::lock_guard <std::mutex> lock(m);
        data.push(std::move(new_value));							<= A
    }
    std::shared_ptr <T> pop()
    {
        std::lock_guard <std::mutex> lock(m);
        if (data.empty()) throw empty_stack();						<= B
        std::shared_ptr < T > const res(
           std::make_shared<T>(std::move(data.top())));		      <= C
        data.pop();													<= D
        return res;
    }
    void pop(T &value) 
    {
        std::lock_guard <std::mutex> lock(m);
        if (data.empty()) throw empty_stack();
        value = std::move(data.top());								<= E
        data.pop();													<= F
    }
    bool empty() const
    {
        std::lock_guard <std::mutex> lock(m);
        return data.empty();
    }
};

각각의 가이드라인을 차례대로 보고, 어떻게 적용했는지 확인하자.

Let’s look at each of the guidelines in turn, and see how they apply here.

먼저, 알 수 있듯이, 기본적인 쓰레드 세이프티는 뮤텍스를 가진 자물쇠를 가진 각각의 멤버함수를 보호함으로써 얻을 수 있다. 오직 한 쓰레드가 데이터에 언제든지 접근하는것을 보장해서, 각각의 멤버 함수가 invariants을 유지하는것이다. 어떠한 쓰레드도 부셔진 invariant을 볼 수 없다.

First, as you can see, the basic thread safety is provided by protecting each member function with a lock on the mutex, m. This ensures that only one thread is actually accessing the data at any one time, so provided each member function maintains the invariants, no thread can see a broken invariant.

두번째로, empty()랑 pop() 함수들은 경쟁상태(race condition)을 유발한 가능성이 있지만, 코드가 명시적으로 pop()이 잠겨있는동안 스택이 비어 있는지 확인하기 때문에, 이 경쟁상태(race condition)은 문제가 되지 않는다. pop()호출로 직접 꺼낸(poped) 데이터를 반환함으로써, std::stack<>같이 top()과 pop()에 존재하는 잠재적인 경쟁상태(race condition)을 피할 수 있다.

Second, there’s a potential for a race condition between empty() and either of the pop() functions, but because the code explicitly checks for the contained stack being empty while holding the lock in pop(), this race condition isn’t problematic. By returning the popped data item directly as part of the call to pop(), you avoid a potential race condition that would be present with separate top() and pop() member functions such as those in std::stack<>.

다음으로, 몇몇 잠재적인 Exception의 원인이 있다. (뮤텍스 또는 시스템 리소스 부족 문제가 있음을 나타내기 때문에)매우 드물지만, 각 멤버 함수의 첫번째 연산에서, 뮤텍스를 잠그면 exception을 던질것이다. 어떠한 데이터도 수정되지 않기 때문에 안전하다. 뮤텍스를 잠금 해제(unlocking)하면 뮤텍스는 무조건 안전하고, std::lock_guard<>의 사용은 뮤텍스가 잠긴채로 남겨지지 않도록 보장한다.

Next, there are a few potential sources of exceptions. Locking a mutex may throw an exception, but not only is this likely to be exceedingly rare (because it indicates a problem with the mutex or a lack of system resources), it’s also the first operation in each member function. Because no data has been modified, this is safe. Unlocking a mutex can’t fail, so that’s always safe, and the use of std::lock_guard<> ensures that the mutex is never left locked.

A의 data.push()호출은 데이터 값을 복사/이동 작업이 예외를 던지거나 데이터 구조를 확장하기에 충분한 메모리가 할당되지 않았을때 예외를 던질것이다. 어느 쪽이든 std::stack<>은 안전하고 문제가 발생하지 않도록 보장한다.

The call to data.push() A may throw an exception if either copying/moving the data value throws an exception or not enough memory can be allocated to extend the underlying data structure. Either way, std::stack<> guarantees it will be safe, so that’s not a problem either.

B에서 처음 pop()을 오버로드할때, 코드는 스스로 empty_stack exception을 던지지만, 수정된건 없고 안전하다. C에서 res 생성은 다음 이유들로 인해 exception을 던진다. : std::make_shared 호출은 새로운 객체의 메모리를 할당할수 없고, 내부 데이터가 레퍼런스 카운팅(reference counting)을 필요로 하기 때문에 예외를 던지거나 반환될 데이터의 복자 생성자 또는 이동 생성자가 새로 할당된 메모리에 복사/이동할때 예외를 던지기 때문이다. 이 2경우 모두, C++ 런타임과 표준 라이브러리(Standard Library)는 메모리 누수 또는 새 객체가 파괴되지 않도록 보장한다. 아래의 스택을 아직 수정하지 않았기 때문에 안전하다. D에서의 data.pop() 호출은 결과 봔환으로 예외를 던지지 않도록 보장하고, 오버로딩한 pop()이 Exception-Safe하도록 한다.

In the first overload of pop(), the code itself might throw an empty_stack exception B, but nothing has been modified, so that’s safe. The creation of res C might throw an exception though for a couple of reasons: the call to std::make_shared might throw because it can’t allocate memory for the new object and the internal data required for reference counting, or the copy constructor or move constructor of the data item to be returned might throw when copying/moving into the freshly allocated memory. In both cases, the C++ runtime and Standard Library ensure that there are no memory leaks and the new object (if any) is correctly destroyed. Because you still haven’t modified the underlying stack, you’re still OK. The call to data.pop() D is guaranteed not to throw, as is the return of the result, so this overload of pop() is exception-safe.

pop()의 두번째 오버로딩도 비슷하다. 이번 exception은 새로운 객체의 생성과 std::shared_ptr** 인스턴스보다는 **E**의 복사 할당 또는 이동 할당 연산자에서 던지는 것이다. 다시말해, 데이터 구조를 **F**에서 예외를 던지지 않도록 보장하는 data.pop()`을 호출하기 전까지 변경하면 안된다. 그러면 이 오버로딩도 Exception-safe 할 것이다.

The second overload of pop() is similar, except this time it’s the copy assignment or move assignment operator that can throw E rather than the construction of a new object and a std::shared_ptr instance. Again, you don’t actually modify the data structure until the call to data.pop() F, which is still guaranteed not to throw, so this overload is exception-safe too.

마침내, empty()는 어떤 데이터도 수정하지 않고, Exception-Safe하다.

Finally, empty() doesn’t modify any data, so that’s exception-safe.

There are a couple of opportunities for deadlock here, because you call user code while holding a lock: the copy constructor or move constructor A, C and copy assignment or move assignment operator E on the contained data items, as well as potentially a user-defined operator new. If these functions either call member func- tions on the stack that the item is being inserted into or removed from or require a lock of any kind and another lock was held when the stack member function was invoked, there’s the possibility of deadlock. However, it’s sensible to require that users of the stack be responsible for ensuring this; you can’t reasonably expect to add an item onto a stack or remove it from a stack without copying it or allocating memory for it.

Because all the member functions use a std::lock_guard<> to protect the data, it’s safe for any number of threads to call the stack member functions. The only member functions that aren’t safe are the constructors and destructors, but this isn’t a particular problem; the object can be constructed only once and destroyed only once. Calling member functions on an incompletely constructed object or a partially destructed object is never a good idea whether done concurrently or not. As a conse- quence, the user must ensure that other threads aren’t able to access the stack until it’s fully constructed and must ensure that all threads have ceased accessing the stack before it’s destroyed.

Although it’s safe for multiple threads to call the member functions concurrently, because of the use of locks, only one thread is ever actually doing any work in the stack data structure at a time. This serialization of threads can potentially limit the performance of an application where there’s significant contention on the stack: while a thread is waiting for the lock, it isn’t doing any useful work. Also, the stack doesn’t provide any means for waiting for an item to be added, so if a thread needs to wait, it must periodically call empty() or just call pop() and catch the empty_stack excep- tions. This makes this stack implementation a poor choice if such a scenario is required, because a waiting thread must either consume precious resources checking for data or the user must write external wait and notification code (for example, using condition variables), which might render the internal locking unnecessary and there- fore wasteful. The queue from chapter 4 shows a way of incorporating such waiting into the data structure itself using a condition variable inside the data structure, so let’s look at that next.