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?