[Lecture 8] 멀티쓰레딩 II - Basic Locking / Managing Shared State

#Introduction

• 멀티스레드 프로그램은 가상 주소 공간을 공유하기 때문에 주소 공간에 할당된 모든 개체(글로벌 변수, 힙 개체 등)에 직접 액세스할 수 있다
• Preemptive scheduling  체제에 의해 도입된 non-determinism 및/또는 여러 프로세서 또는 코어에 대한 동시 실행은 이러한 공유를 어렵게 만든다. (예: counter++)

Typical Shared Memory Multicore Architecture

#Data Races

데이터 레이스란 멀티 쓰레드 환경에서 여러 쓰레드가 공유자원에 동시에 접근할 때 유발되는 문제이다.

 

두 개 이상의 스레드가 공유 변수에 액세스하고, 적어도 하나의 액세스는 쓰기 액세스이며, 최종 결과는 스레드의 실행 순서, 특히 메모리 액세스 순서에 따라 달라진다

 

• 이러한 데이터 레이스는 동시성(concurrency) 관련 버그(일명 "race condition")의 한 형태이다.
• 간헐적이고 찾기 어려울 수 있다("Heisenbugs")
• 기타 사항: ordering violations (주문 위반), atomicity violations (원자성 위반)
• 이러한 사항들을 막기 위해 다음과 같은 전략이 있다
  • 복제 및 파티셔닝을 통한 방지
  • 잠금장치(lock)와 같은 상호배제장치 사용
  • 원자 명령어(atomic instruciton)의 사용

#Avoiding Sharing

• 데이터가 공유되지 않는 계산 부분에서는 데이터 레이스가 발생할 수 없다.
• 문제를 재구성하는 전략은 다음과 같다:
  • 복제: 스레드가 독립적으로 수정할 수 있는 데이터 구조의 개별 복사본 제공 
  • 파티셔닝: 데이터를 여러 스레드에 의해 개별적으로 작동하는 분리된 부분으로 분리

• 데이터 구조를 재설계하여 공유를 방지하거나 축소함으로써 많은 확장성이 보장되었다, 예를들어
  • 스레드별 카운터
  • CPU별 ready 큐
  • 지역 기반 메모리 할당자
• 그러나 이러한 전략에는 관리 복잡성의 측면에서 비용이 발생할 수 있으며 추가 공간이 필요하다

#Sequential Consistency

• 각 스레드의 프로그램을 일련의 "단계"로 생각한다
• 순차적으로 일관된 실행은 이러한 단계들의 일부 인터리빙(interleaving)의 결과이다(각 스레드의 순서를 변경하지 않고, 즉시 다른 스레드로 업데이트를 전파함)
• 기본적으로 프로그래밍 언어는 이러한 실행을 보장하지 않는다. 왜냐하면 컴파일러는 논리적으로 서로 의존하지 않는 문을 정렬할 수 있고 프로세서는 마찬가지로 로드/저장 명령을 정렬할 수 있기 때문이다

C, C++와 같은 현대 언어들은 데이터 레이스가 없는 프로그램들에 대해서만 순차적으로 일관된 실행을 보장한다. 데이터 경쟁으로부터 자유로워지려면 동기화가 필요하며, 특히 중요한 섹션(상호 배제, 잠금)을 적절하게 사용해야 한다.

#Mutual Exclusion / 상호배제

한 번에 하나의 프로세스/스레드만 critical section 에서 실행할 수 있다는 의미이다. Mutual exclusion은 "critical section"문제로도 알려져있다. 여기서 critical section이란 여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 블록이다.

• 스레드는 중요 섹션을 입력한 후에만 공유 데이터를 업데이트한다
• 한 번에 하나의 나사산만 중요 섹션 내에 있을 수 있다
• 한 번에 하나의 thread만 중요 섹션 내에 있을 수 있다
• 공유 데이터에 액세스할 때만 스레드가 중요 섹션으로 들어간다.
• 따라서 임계 구간 내에서 수행되는 모든 작업(읽기 및 쓰기)은 하나의 원자(분리된) 단위로 나타난다.
• 일반적으로 "잠금(lock)"이라고 하는 mutex에 의해 제공된다
  • 입력 작업이 잠금을 "획득"하거나 잠군다
  • 그런 다음 스레드가 잠금을 "유지"한다.
  • 종료 작업(exit operation)은 잠금을 "release"하거나 잠금 해제한다.

#Understanding Locks

Lock은 여러 스레드 간에 자원을 접근하는 매커니즘을 제공한다. 일반적으로 위에도 언급했던 상호 배제 정책(mutual exclusion)을 통해, 하나의 스레드가 특정 자원에 접근중인 경우에는 다른 스레드가 접근하지 못하도록 제한한다. 락이 없다면 두 개 이상의 스레드가 동시에 자원에 접근할 수 있으므로, 데이터의 무결성이 보장되지 않는다.

• lock은 코드를 보호하지 않는다. 그 대신 데이터를 보호한다.
• 공유 데이터의 각 부분에는 이를 보호하는 잠금 장치가 있어야 한다
  • struct list task_queue; // protected by task_queue_lock
    pthread_mutex_t task_queue_lock; // protects task_queue
• 잠금 기능은 데이터를 자동으로 보호하지 않는다. 대신, 스레드 간 협력 프로토콜을 통해 공유되는 데이터의 데이터 경합을 방지한다
• 코드 내 어디에서 데이터에 액세스하든 관련 잠금을 유지해야 한다
• 동일한 lock을 통해 다른 데이터 조각을 보호할 수도 있다

#Lock을 사용할 때 주의할점/하지 말아야 할 점

• 동일한 데이터에 액세스할 때 코드의 다른 섹션에 다른 잠금을 사용하면 안된다
• 이미 보유하고 있는 lock을 획득하려고 하면 안된다
• 일부 경로의 lock 해제를 잊으면 안된다
  • 위의 실수를 방지하는 가장 좋은 방법은 function level에서 불변성 (invariant)을 보장하는 것이다.
• 일부 이벤트(절전, I/O, ...)를 차단하는 동안 잠금을 유지하면 안된다
  • 위 행위는 동일한 잠금이 필요한 스레드가 동일한 이벤트를 기다리게 만든다

#Lock을 사용할 때 하면 좋은 점

race condition 감지 도구를 사용하면 lock을 사용할때 좋다 (예: Helgrind, DRD, Intel Thread Checker, TSAN).

적절한 잠금 규칙을 사용하는 경우 변수 x에 대한 모든 액세스 쌍 간에 "happens-before" 관계가 설정된다.

예: 동일한 스레드에 의해 수행되므로 a1(x) → U1(m1)이다. (L2(m1) → a2(x) → U2(m1) 및 L3(m1) → a3(x)관계 와 같다).

U1(m1) → L2(m2) 및 U2(m1) → L3(m1) 관계는 뮤텍스의 잠금 해제가 다음 잠금 작업 전에 발생하기 때문에 유지된다.

ak (x) || aj(x) iff neither ak (x) → aj(x) nor aj(x) → ak (x).

#Thread-Safety

여러 스레드에서 호출될 때 올바른 결과를 산출하는 함수의 속성이다, 즉 thread-safe란 멀티 스레드 프로그래밍에서 일반적으로 어떤 함수나 변수, 혹은 객체가 여러 스레드로부터 동시에 접근이 이루어져도 프로그램의 실행에 문제가 없음을 뜻한다

 

• Thread-safety는 라이브러리의 API 설명서의 일부로 문서화해야 하는 속성이다.
  • 일부 전통적인 C 함수는 스레드 세이프가 아니다(strtok)
• 다음 아래 상황들이 일어난다면 함수는 thread-safe가 아니다
  • 공유 변수 보호 실패
  • 호출 전반에 걸쳐 지속적 상태 의존*
  • 정적 변수에 포인터 반환
  • 스레드 세이프가 아닌 다른 함수 호출

*호출 전반에 걸쳐 지속적 상태 의존

• 호출 전반에 걸쳐 지속적 상태 (persistent state)에 의존 하는 함수는 공유 상태를 보호하지 못할 뿐만 아니라 의사 난수(pseudo-random numbers)가 생성되는 결정론적 순서를 유지하지 못한다
• fix: state를 function에 pass하면 된다(예: rand_r()).
• 멀티스레드 지원의 도입으로 C 라이브러리는 스레드 세이프인 몇 가지 r() 함수를 지원하도록 업데이트되었다.
• 여기서 'r'은 reentrant(재진입)를 의미하는데, 이는 스레드 세이프보다 더 강한 특성이다.
• 재진입 함수는 호출이 진행되는 동안 안전하게 다시 입력할 수 있다(예: 재귀 함수)

#예제: rand()

static unsigned int next = 1;
/* rand -return pseudo-random integer in 0..32767 */
int rand(void) {
	next = next * 1103515245 + 12345;
	return (unsigned int)(next/65536) % 32768;
}
/* srand-set seed for rand() */
	void srand(unsigned intseed) {
	next = seed;
}

#Fix: rand_r()

int rand_r(unsigned int *seedp);