Chapter 06, Designing lock based concurrent data structures

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

Designing lock-based concurrent data structures

제가 여기에 정리를 너무 개판으로 해서 새로 정리하고 있습니다. https://github.com/HIPERCUBE/Designing-lock-based-concurrent-data-structure.git

이번 챕터에서 다루는 내용

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

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.

6.3 더 복잡한 Lock 기반 자료구조 설계하기

Designing more complex lock-based data structures

Stack과 Queue는 쉽다 : 인터페이스가 매우 제한적이며 특정 목적에만 집중하기 때문이다. 모든 자료구조가 간단한 것은 아니다; 대부분의 자료구조는 다양한 기능을 지원해줘야한다. 이러한 원칙을 따르면 Concurrency에 대한 더 많은 기회로 이어지게 된다. 하지만 이는 데이터를 보호하는 데에 있어 더 어려워진다. 왜냐하면 다중 접근 패턴이 생각되어져야 하기 때문이다. 실행될 수 있는 다양한 기능에 대한 정확한 특성은 동시 실행 접근을 위한 자료구조를 설계 하는데에 있어 중요하다. 이에 관련된 며가지 문제점을 보기 위해 Lookup 테이블 설계를 보도록 하자.

Stacks and queues are simple: the interface is exceedingly limited, and they’re very tightly focused on a specific purpose. Not all data structures are that simple; most data structures support a variety of operations. In principle, this can then lead to greater opportunities for concurrency, but it also makes the task of protecting the data that much harder because the multiple access patterns need to be taken into account. The precise nature of the various operations that can be performed is important when designing such data structures for concurrent access. To see some of the issues involved, let’s look at the design of a lookup table.

6.3.1 Lock을 이용하여 Thread-safe한 Look Up 테이블 만들기

Writing a thread-safe lookup table using locks

Look Up 테이블 또는 Dictionary는 한가지 타입(Key타입)의 값이 동일 타입 또는 다른 타입(Mapping된 타입)에 연결되도록 한다. 일반적으로 이러한 구조에 대한 의도는 코드가 주어진 Key값에 대해 연결된 값을 Query해 올 수 있도록 하기 위해서이다. C++ 표준 라이브러리에서는 이러한 기능은 이와 같은 컨테이너에서 지원된다: std::map<>, std::multimap<>, std::unordered_map<>,and std::unordered_multimap<>.

A lookup table or dictionary associates values of one type (the key type) with values of either the same or a different type (the mapped type). In general, the intention behind such a structure is to allow code to query the data associated with a given key. In the C++ Standard Library, this facility is provided by the associative containers: std::map<>, std::multimap<>, std::unordered_map<>, and std::unordered_multimap<>.

Lookup 테이블은 Stack 또는 Queue와 다른 사용 패턴을 가지고 있다. Stack 또는 Queue에 대한 대부분의 연산은 해당 자료구조를 어떤 형태로는 변화를 하게 된다; 요소를 추가하거나 제어 한다. Lookup 테이블은 아주 가끔 변하게 된다. 3.13에 있는 DNS 캐시는 std::map<>에 비해서 매우 축소된 언터페이스를 가진 시나리오 중 하나이다. Stack과 Queue에서 본것과 같이 표준 컨테이너의 인터페이스는 다중 Thread에서 동시적으로 접근하는 자료구조로서는 적합하지 않다. 왜냐하면 인터페이스 디자인에서 내재된 Race Conditions가 존재하기 때문이다. 그러므로 이러한 자료구조는 축소되고 변경되어야 한다.

A lookup table has a different usage pattern than a stack or a queue. Whereas almost every operation on a stack or a queue modifies it in some way, either to add an element or remove one, a lookup table might be modified rarely. The simple DNS cache in listing 3.13 is one example of such a scenario, which features a greatly reduced interface compared to std::map<>. As you saw with the stack and queue, the interfaces of the standard containers aren’t suitable when the data structure is to be accessed from multiple threads concurrently, because there are inherent race conditions in the interface design, so they need to be cut down and revised.

concurrency 입장에서 std::map<>의 큰 문제는 반복자이다. 다른 Thread들이 컨테이너를 접근/변경을 할 수 있는 상황에서 반복자가 컨테이너에 대해 안전한 접근을 할 수 있게 해주어도, 이는 매우 애매한 제안이다. 반복자를 응용하는 것은 반복자가 참조하는 요소를 다른 Thread가 제거하는 것과 같은 문제점을 해결해야 한다. Thread-safe한 Lookup 테이블 인터페이스에 대해 알아보기 위해 우리는 반복자에 대해서는 건너뛸 것이다. std::map<>에 대해 인터페이스(그리고 표준 라이브러리의 다른 관련 컨테이너)가 반복자에 매우 의존한다면, 이를 제쳐놓고 밑에서 부터 인터페이스를 설계해 보도록 하자.

The biggest problem with the std::map<> interface from a concurrency perspective is the iterators. Although it’s possible to have an iterator that provides safe access into a container even when other threads can access (and modify) the container, this is a tricky proposition. Correctly handling iterators requires you to deal with issues such as another thread deleting the element that the iterator is referring to, which can get rather involved. For the first cut at a thread-safe lookup table interface, you’ll skip the iterators. Given that the interface to std::map<> (and the other associative containers in the standard library) is so heavily iterator-based, it’s probably worth setting them aside and designing the interface from the ground up.

Lookup 테이블에 대해 몇가지의 기본 기능을 보도록 하자:

• 새로운 Key/value 추가 하는것.
• 주어진 Key에 해당하는 값을 바꾸는 것.
• Key와 관련된 변수 제거하는 것.
• 주어진 Key에 대해 관련된 값 구하는 것. 컨테이너가 비어 있는지 확인하는 것, Key에 대한 모든 리스트를 가져오는것, Key/value 쌍에 대한 모든 집합을 가져오는 것과 같은 기능은 반복자 기반이지만 우용한 기능들이다.

There are only a few basic operations on a lookup table:

• Add a new key/value pair.
• Change the value associated with a given key.
• Remove a key and its associated value.
• Obtain the value associated with a given key if any. There are also a few container-wide operations that might be useful, such as a check on whether the container is empty, a snapshot of the complete list of keys, or a snapshot of the complete set of key/value pairs.

레퍼런스를 반환하지 않는것, 전체 멤버 함수에 대해 Mutex Lock을 거는 것과 같이 Thread-safe한 가이드 라인들을 고수한다면, 모든 점에서 안전할 것이다; 이들은 다른 Thread로 부터 오는 변화에 대해 먼저 처리되거나 후에 처리될 것이다. Race Condition이 발생할 수 있는 제일 큰 가능성은 새로운 Key/value 쌍이 추가될때 이다; 만약 2개의 Thread가 새로운 값을 추가하게 되면, 첫번째 접근되는 요소만 추가되고, 두번째로 추가되는 요소는 추가되지 못할 것이다. 가능한 방법중 하나는 Listing3.13에서 했던 DNS캐시에 했던 것과 같이 단일 멤버 함수로 추가/합병 시키는 것이다. 인터페이스 관점에서 다른 흥미로운 점은 관련된 값을 구할때 "만약에 있다면" 점에 대한 요소이다. 하나의 옵션은 Key가 존재하지 않을때 사용자에게 "Default" 결과값을 반환하도록 하게 하는 것이다: mapped_type get_value(key_type const& key, mapped_type default_value); 이러한 경우에는 mapped_type의 기본-생성된 인스턴스는 default_value가 명확히 제공되지 않았을 때 사용될 수 있다. 이는 mapped_type의 인스턴스 대신에 std::pair<mapped_type, bool>을 반환하도록 확장될 수 있다. 여기에서 bool은 변수 존재하는지 여부를 보여준다. 또 다른 옵션은 이 값을 지칭하는 스마트 포인터를 반환하는 것이다; 만약 포인터 값이 NULL이라면 반환할 값이 없는 것이다.

If you stick to the simple thread-safety guidelines such as not returning references and put a simple mutex lock around the entirety of each member function, all of these are safe; they either come before some modification from another thread or come after it. The biggest potential for a race condition is when a new key/value pair is being added; if two threads add a new value, only one will be first, and the second will therefore fail. One possibility is to combine add and change into a single member function, as you did for the DNS cache in listing 3.13. The only other interesting point from an interface perspective is the if any part of obtaining an associated value. One option is to allow the user to provide a “default” result that’s returned in the case when the key isn’t present: mapped_type get_value(key_type const& key, mapped_type default_value); In this case, a default-constructed instance of mapped_type could be used if the default_value wasn’t explicitly provided. This could also be extended to return a std::pair<mapped_type,bool> instead of just an instance of mapped_type, where the bool indicates whether the value was present. Another option is to return a smart pointer referring to the value; if the pointer value is NULL, there was no value to return.

이미 언급했듯이 인터페이스가 정해지면,(인터페이스에 대한 Race condition)이 없다고 가정하면) Thread 안전도는 단일 Mutex을 사용하는 것과 기반이 되는 자료구조를 보호하기 위해 모든 멤버 함수에 대해 Look을 거는 것을 통해 보장이 될 수 있다. 하지만 이는 자료구조를 읽고 변경하기 위한 각각의 함수에서 제공되는 Concurrency에 대한 가능성을 낭비하게 된다. 이에 대한 하나의 옵션은 다중 읽기 Thread 또는 단일 쓰기 Thread를 지원해주는 Mutex를 사용하는 것이다. 예를 들면 Listing 3.13에서 사용된 boost::shared_mutex가 있다.

As already mentioned, once the interface has been decided, then (assuming no interface race conditions) the thread safety could be guaranteed by using a single mutex and a simple lock around every member function to protect the underlying data structure. However, this would squander the possibilities for concurrency provided by the separate functions for reading the data structure and modifying it. One option is to use a mutex that supports multiple reader threads or a single writer thread, such as the boost::shared_mutex used in listing 3.13. Although this would indeed improve the possibilities for concurrent access, only one thread could modify the data structure at a time. Ideally, you’d like to do better than that.

Find-Grained Locking을 위한 Map 자료구조 설계하기

DESIGNING A MAP DATA STRUCTURE FOR FINE-GRAINED LOCKING

6.2.3장에서 이야한 Queue에서 Find-Grained Locking을 허용하기 위해서는 이미 존재하는 std::map<>에 대해 wrapping을 하기 보다는 자료구조의 디테일을 자세히 봐야 한다. 여러분의 Lookup 테이블과 같은 관련 컨테이너를 적용하는 데에 3가지 방법이 있다:

• Red-Black 트리와 같은 이진트리
• Sorted Array(정렬된 배열)
• Hash 테이블

As with the queue discussed in section 6.2.3, in order to permit fine-grained locking you need to look carefully at the details of the data structure rather than just wrapping a preexisting container such as std::map<>. There are three common ways of implementing an associative container like your lookup table:

• A binary tree, such as a red-black tree
• A sorted array
• A hash table

이진 트리는 concurrency에 대해 많은 확장 가능성을 제공하지 않는다; 모든 loockup 또는 변경은 루트 노드를 접근함으로서 시작되며, 이는 Lock이 되어야 한다. 그럼에도 불구하고 이 Lock은 접근 Thread가 트리를 내려가면서 해제된다. 이는 전체 자료구조에 걸쳐 단일 Lock보다 못하다.

A binary tree doesn’t provide much scope for extending the opportunities for concurrency; every lookup or modification has to start by accessing the root node, which therefore has to be locked. Although this lock can be released as the accessing thread moves down the tree, this isn’t much better than a single lock across the whole data structure.

Sorted Array은 더 심각하다. 왜냐하면 주어진 데이터가 어디에 배치될 지 알수 없기 때문이다. 그러므로 전체 배열에 대해 단일 Lock이 필요하다. 선택할 수 있는 것은 hash 테이블만 남게 된다. 고정된 수의 Bucket을 사용한다고 가정할 때, 어느 Bucket에 Key가 속하는지는 Key와 Hash 함수의 성질에 달려 있다. 이는 각각의 Bucket에 대해 별개의 Lock을 안전하게 가질 수 있다는 것이다. 다중 읽기 또는 단일 쓰기를 지원하는 Mutex를 사용하게 된다면, Bucket 수인 N배에 비례하여 Concurrency에 대해 가능성을 높일 수 있다. C++ 표준라이브러리는 std::hash<> 템플릿을 제공하며, 이를 위해 우리는 이 템플릿을 사용할 수 있다. 이 템플릿은 이미 int와 같은 근본적인 타입과 std::string과 같은 공통 라이브러리 타입에 대해서는 이미 특화가 되어 있다. 그리고 사용자는 쉽게 다른 Key 타입에 대해 특화 시킬 수 있다. 표준 비정렬 컨테이너에 대한 단서를 따르고, Hashing 하는 것과 템플릿 매개 변수를 위해 함수 객체를 사용한다면, 사용자는 std::hash<>를 Key 타입에 대해서 특화던가 별개의 Hash함수를 제공할 수 있다.

A sorted array is even worse, because you can’t tell in advance where in the array a given data value is going to be, so you need a single lock for the whole array. That leaves the hash table. Assuming a fixed number of buckets, which bucket a key belongs to is purely a property of the key and its hash function. This means you can safely have a separate lock per bucket. If you again use a mutex that supports multiple readers or a single writer, you increase the opportunities for concurrency N-fold, where N is the number of buckets. The downside is that you need a good hash function for the key. The C++ Standard Library provides the std::hash<> template, which you can use for this purpose. It’s already specialized for the fundamental types such as int and common library types such as std::string, and the user can easily specialize it for other key types. If you follow the lead of the standard unordered containers and take the type of the function object to use for doing the hashing as a template parameter, the user can choose whether to specialize std::hash<> for their key type or provide a separate hash function.

이제 코드를 보도록 하자. Thread에 안전한 Lookup테이블은 어떻게 생겼을까? 그중 하나가 여기에 보여지고 있다.

So, let’s look at some code. What might the implementation of a thread-safe lookup table look like? One possibility is shown here.