락 (Lock)
병행 프로그램의 근본적인 문제
여러 개의 명령어들을 원자적으로 실행하고 싶지만, 단일 프로세서의 인터럽트로 인해 불가능
이 장에서는 앞서 다룬 락(Lock)을 이용하여 임계 영역을 하나의 원자 단위 명령어인 것처럼 실행되도록 해볼 것이다.
1. 락: 기본 개념
락을 사용하여 임계 영역(balance = balance+1)을 감쌀 수 있다.
lock_t mutex; // 글로벌 변수로 선언된 락
...
lock(&mutex);
balance = balance + 1;
unlock(&mutex);락 변수: 락의 상태를 나타내는 변수
- 락은 하나의 변수이므로 먼저 선언을 해야한다.
(lock_t mutex;) - 락의 상태
- 사용 가능(available), 해제(unlocked, free) 상태
- 사용 중(acquired), 락을 획득한 상태
- 락 사용자는 락 자료구조 속의 정보에 대해 알 수 없다.
lock/unlock 루틴
lock(): 락 획득을 시도한다.- 만약 어떠한 쓰레드도 락을 갖고 있지 않으면, 락 획득을 시도한 쓰레드가 락 소유자(owner)가 된다.
- 다른 쓰레드가 락을 이미 사용 중인 경우에는 lock 함수가 리턴을 하지 않는다.
unlock(): 락 소유자가 unlock을 호출하면 락은 이제 다시 사용 가능한 상태가 된다.
- 락은 프로그래머에게 스케줄링에 대한 최소한의 제어권을 제공한다.
- 락으로 코드를 감싸서 프로그래머는 그 코드 내에서는 하나의 쓰레드만 동작하도록 보장한다.
2. Pthread Lock
POSIX 라이브러리는 락을 mutex라고 부른다.
(상호 배제, mutual exclusion)
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
Pthread_mutex_lock(&lock); // pthread_mutex_lock()을 위한 래퍼
balance = balance + 1;
Pthread_mutex_unlock(&lock);- 락에 변수 명을 지정하여 락/언락 함수에 전달한다.
다른 변수를 보호하기 위해 다른 락을 사용할 수도 있기 때문이다. - 즉, 서로 다른 데이터와 자료구조를 보호하기 위해 여러 락을 사용한다.
- 세밀한(fine-grained) 락 사용 전략: 서로 다른 락으로 보호된 코드 내에 각자가 진입이 가능한 락 사용 전략
3. 락 구현
핵심 질문: 락은 어떻게 만들까
- 효율적인 락은 낮은 비용으로 상호 배제 기법을 제공하고, 하드웨어 및 운영체제 지원이 필요하다. 그렇다면...
- 효율적인 락은 어떻게 만들어야 하는가?
- 어떤 하드웨어 지원 필요?
- 어떤 운영체제 지원 필요?
정교한 락 라이브러리를 제작하는 데 있어 운영체제가 관여하는 것은 무엇인지 알아보자.
4. 락의 평가
락의 효율을 어떻게 평가해야 할까?
- 상호 배제
- 락이 제대로 잘 동작하여 상호 배제를 지원하는가?
- 임계 영역 내로 한 쓰레드만 진입할 수 있는지 검사
- 공정성(fairness)
- 쓰레드들이 락 획득에 대한 공정한 기회가 주어지는가?
- 락을 전혀 얻지 못해 굶주리는(starve) 경우가 발생하는가?
- 성능(performance)
- 락 사용 시 시간적 오버헤드를 평가해야 한다.
- 경쟁이 전혀 없는 경우의 성능
(한 쓰레드가 실행 중에 락을 획득하고 해제하는 과정에서 발행사는 부하의 정도 평가) - 여러 쓰레드가 단일 CPU 상에서 락을 획들하려고 경쟁할 때의 성능
- 멀티 CPU 상황에서 락 경쟁 시의 성능
5. 인터럽트 제어
초창기 단일 프로세스 시스템에서는 상호 배제 지원을 위해 임계 영역 내에서는 인터럽트를 비활성화하는 방법을 사용했다.
void lock() {
DisableInterrupts();
}
void unlock() {
EnableInterrupts();
}- 임게 영역에 진입하기 전에 인터럽트를 막으면, 임계 영역 내의 코드에서는 인터럽트가 발생할 수 없기 때문에 원자적으로 실행될 수 있다.
- 장점: 단순하다. (인터럽트가 없으면 다른 쓰레드가 끼어들지 못함)
- 단점
- 인터럽트 활성/비활성화를 위해 특권(privileged) 연산의 실행을 허가해야 한다.
- 이러한 특권 연산을 다른 악의적인 목적으로 사용하지 않음을 신뢰해야만 한다.
- 멀티프로세서에서는 적용할 수 없다. 특정 프로세서의 인터럽트 비활성화는 다른 프로세서에 영향을 주지 못하기 때문이다.
- 장시간 동안 인터럽트를 중지시키는 것은 중요한 인터럽트의 시점을 놓칠 수 있다.
- 인터럽트를 비활성화시키는 코드들은 최신의 CPU들에서는 느리게
실행되어 비효율적이다.
- 인터럽트 활성/비활성화를 위해 특권(privileged) 연산의 실행을 허가해야 한다.
따라서 상호 배제를 위해 인터럽트를 비활성화하는 것은 제한된 범위에서만 사용되어야 한다.
6. Test-And-Set (Atomic Exchange)
Test-And-Set 기법 (원자적 교체, atomic exchange)
- 락 지원을 위한 하드웨어 기법이다.
typedef struct __lock_t {
int flag;
} lock_t;
void init(lock_t *mutex) {
// 0 −> 락이 사용 가능함, 1 −> 락 사용 중
mutex−>flag = 0;
}
void lock(lock_t *mutex) {
while (mutex−>flag == 1) // flag 변수를 검사(TEST) 함
; // spin−wait (do nothing)
mutex−>flag = 1; // 이제 설정(SET) 한다!
}
void unlock(lock_t *mutex) {
mutex−>flag = 0;
}- 만약 flag가 0이면 사용이 가능하고, 1이면 다른 쓰레드에서 락을 사용하고 있는 것이다.
lock()이 호출되었을 때, 다른 쓰레드에서 락을 사용하고 있으면(mutex의 flag가 1이면) 락을 소유한 쓰레드의unlock()기다린다. (spin-wait)- 락을 소유했던 쓰레드가
unlock()을 호출하면, 이제 해당 쓰레드가 락을 가지게 된다. - 정확성 문제
- 쓰레드 1의 while문을 탈출하는 순간에 인터럽트가 발생하면, 두 쓰레드 모두
flag=1이 될 수도 있다.
- 쓰레드 1의 while문을 탈출하는 순간에 인터럽트가 발생하면, 두 쓰레드 모두
- 성능 문제: 다른 쓰레드가 락을 해제할 때까지 시간을 낭비한다.
7. 제대로 돌아가는 스핀 락의 구현
int TestAndSet(int *old_ptr, int new) {
int old = *old_ptr; // old_ptr 의 이전 값을 가져옴
*old_ptr = new; // old_ptr 에 new' 의 값을 저장함
return old; // old의 값을 반환함
}- 검사(test)와 동시에 메모리에 새로운 값을 설정(set)한다.
- 동작들이 원자적으로 수행된다.
typedef struct __lock_t {
int flag;
} lock_t;
void init(lock_t *lock) {
// 0 은 락이 획득 가능한 상태를 표시, 1 은 락을 획득했음을 표시
lock−>flag = 0;
}
void lock(lock_t *lock) {
while (TestAndSet(&lock−>flag, 1) == 1)
; // 스핀(아무 일도 하지 않음)
}
void unlock(lock_t *lock) {
lock−>flag = 0;
}- 만약 flag가 0이면,
TestAndSet()은 0을 반환하고 flag는 1이 되어 락을 획득한다. - 만약 flag가 1이면,
TestAndSet()은 1을 반환하므로 while문을 계속해서 스핀한다. - 단일 프로세서에서 이 방식을 제대로 사용하려면 선점형 스케줄러(preemptive scheduler)를 사용해야 한다.
- 선점형 스케줄러는 필요에 따라 다른 쓰레드가 실행될 수 있도록 타이머를 통해 쓰레드에 인터럽트를 발생시킬 수 있다.
(프로세스 완료 전에 끊고 전환 가능) - 선점형이 아니면, 단일 CPU에서 스핀 락의 사용은 불가능하다. 왜냐하면 while 문을 회전하며 대기하는 쓰레드가 CPU를 영원히 독점하기 때문이다.
- 선점형 스케줄러는 필요에 따라 다른 쓰레드가 실행될 수 있도록 타이머를 통해 쓰레드에 인터럽트를 발생시킬 수 있다.
8. 스핀 락 평가
- 상호 배제의 정확성
- 락이 제대로 잘 동작하여 상호 배제를 지원하는가?
- 임계 영역 내로 한 쓰레드만 진입할 수 있는지 검사
스핀 락은 임의의 시간에 단 하나의 쓰레드만이 임계 영역에 진입할 수 있도록 한다. 👍
- 공정성(fairness)
- 쓰레드들이 락 획득에 대한 공정한 기회가 주어지는가?
- 락을 전혀 얻지 못해 굶주리는(starve) 경우가 발생하는가?
스핀 락은 어떠한 공정성도 보장해 줄 수 없다. 👎
(while 문을 회전 중인 쓰레드는 경쟁에 밀려서 계속 그 상태에 남아 있을 수 있다.)
- 성능(performance)
- 단일 쓰레드의 경우: 성능 오버헤드는 상당히 클 수 있다.
- 임계 영역 내에서 락을 밖고 있던 쓰레드가 선점된 경우를 생각해 보자.
- N −1개의 다른 쓰레드가 있다고 가정할 때 스케줄러가 락을 획득하려고 시도하는 나머지 쓰레드들을 하나씩 깨울 수도 있다.
- 이런 경우, 쓰레드는 할당받은 기간 동안 CPU 사이클을 낭비하면서 락을 획득하기 위해 대기한다.
- CPU가 여러 개인 경우: 스핀 락은 꽤 합리적으로 동작한다.
- 쓰레드의 개수가 CPU의 개수와 대충 같다고 가정하자.
- 쓰레드 A(CPU 1), 쓰레드 B(CPU 2)가 락 획득을 위해 경쟁중이다.
- 쓰레드 A가 락을 획득한 후에 쓰레드 B가 획득하려고 시도했다고 하면, B는 CPU 2에서 기다린다.
- 임계 영역의 구간이 매우 짧다고 하면 락은 곧 획득 가능한 상태가 될 것이고 쓰레드 B는 락을 획득하게 된다.
- 다른 프로세서에서 락을 획득하기 위해 while 문을 회전하면서 대기하는 것은 그렇게 많은 사이클을 낭비하지 않기 때문에 효율적일 수 있다.
- 단일 쓰레드의 경우: 성능 오버헤드는 상당히 클 수 있다.
9. Compare-And-Swap
Compare-And-Swap 기법
- 락 지원을 위한 하드웨어 기법이다.
int CompareAndSwap(int *ptr, int expected, int new) {
int actual = *ptr;
if (actual == expected)
*ptr = new;
return actual;
}ptr이 가리키고 있는 주소의 값이expected변수와 일치하는지 검사하는 것이다.- 만약 일치한다면,
ptr을 새 값으로 변경하고, 그렇지 않다면 아무 것도 하지 않는다. - Test-And-Set 기법과 똑같은 방식으로 락을 만들 수 있다.
void lock(lock_t *lock) { while (CompareAndSwap(&lock−>flag, 0, 1) == 1) ; // 스핀(아무 일도 하지 않음) } - Test-And-Set보다 강력하고, 대기 없는 동기화(wait-free synchronization)를 다룰 때 더 좋다.
10. Load-Linked 그리고 Store-Conditional
MIPS 구조에서는 load-linked와 store-conditional 명령어를 앞뒤로 사용하여 락이나 기타 병행 연산을 위한 자료 구조를 만들 수 있다.
int LoadLinked(int *ptr) {
return *ptr;
}
int StoreConditional(int *ptr, int value) {
if (LoadLinked 후 ptr이 갱신되지 않은 경우) {
*ptr = value;
return 1; // 성공!
} else {
return 0; // 갱신을 실패함
}
}LoadLinked(): 일반 로드 명령어와 같이 메모리 값을 레지스터에 저장한다.StoreConditional(): ptr 갱신이 없는 경우에만 저장을 성공하고, 성공 시 load-linked가 탑재했던 값을 갱신한다.
void lock(lock_t *lock) {
while (1) {
while (LoadLinked(&lock−>flag) == 1)
; // 0이 될 때까지 스핀
if (StoreConditional(&lock−>flag, 1) == 1)
return; // 1로 변경하는 것이 성공하였다면: 완료
// 아니라면: 처음부터 다시 시도
}
}
void unlock(lock_t *lock) {
lock−>flag = 0;
}- 안쪽 while문을 돌며 flag가 0이 되기를 기다린다.
- flag가 0이 되면 (락이 해제되면)
StoreConditional()을 호출하여 락 획득을 시도하고, 성공 시 flag를 1이 되고 임계 영역 내로 진입한다. StoreConditional()에 실패하는 경우- 쓰레드가
lock()을 호출하여LoadLinked()를 실행, 이후 락이 사용 가능한 상태가 되어 0을 반환한다. - 이때
StoreConditional()을 실행하기 직전에 인터럽드에 걸렸고, 다른 쓰레드가lock()코드를 호출하여 똑같이LoadLinked()의 반환값으로 0을 받았다고 하자. - 이 시점에서 두 쓰레드는 모두
LoadLinked명령어를 실행하였고, 둘 다StoreConditional를 부르려고 하는 상황이다. StoreConditional()은LoadLinked후 ptr이 갱신되지 않은 경우에만 값을 갱신하므로, 오직 하나의 쓰레드만 flag 값을 1로 설정함을 보장한다.- 즉, 두번째로
StoreConditional()를 실행하는 쓰레드는 락 획득에 실패한다.
- 쓰레드가
11. Fetch-And-Add
Fetch-And-Add: 원자적으로 특정 주소의 예전 값을 반환하면서 값을 증가시키는 하드웨어 기법
- 하나의 변수만을 사용하는 대신, 티켓(ticket)과 차례(turn)의 조합으로 티켓 락을 사용한다.
int FetchAndAdd(int *ptr) {
int old = *ptr;
*ptr = old + 1;
return old;
}
// 티켓 락
typedef struct __lock_t {
int ticket;
int turn;
} lock_t;
void lock_init(lock_t *lock) {
lock−>ticket = 0;
lock−>turn = 0;
}
void lock(lock_t *lock) {
int myturn = FetchAndAdd(&lock−>ticket);
while (lock−>turn != myturn)
; // 회전
void unlock(lock_t *lock) {
FetchAndAdd(&lock−>turn);
}- 하나의 쓰레드가 락 획득을 원하면, 티켓변수에 원자적 동작인 fetch-and-add 명령어를 실행한다.
- 결과 값은 해당 쓰레드의 "차례"(
myturn)를 나타낸다. - 전역 공유 변수인
lock->turn을 사용하여 어느 쓰레드의 차례인지 판단한다. - 만약 한 쓰레드가 (
myturn == turn) 이라는 조건에 부합하면 그 쓰레드가 임계 영역에 진입할 차례인 것이다. - 언락 동작은 차례 변수의 값을 증가시켜서 대기 중인 다음 쓰레드에게 (만약 있다면) 임계 영역 진입 차례를 넘겨준다.
모든 쓰레드들이 각자의 순서에 따라 진행한다는 것이 특징이다.
즉, 쓰레드가 티켓 값을 할당받았다면, 미래의 어느 때에 실행되는 것이 보장되는 것이다.
12. 요약 : 과도한 스핀
하드웨어 기반 락은 간단하고 잘 동작하지만, 때론 비효율적이기도 하다.
- 예시) 여러 쓰레드를 단일 프로세서 시스템에서 실행하는 경우
- 쓰레드 1이 임계 영역 내에서 락을 보유한 채 인터럽트에 걸렸다고 하자.
- 쓰레드 2,3,...N은 락을 획득하려고 시도하지만, 실패 후 계속 스핀한다.
- 인터럽트가 발생하여 쓰레드 1이 다시 실행되기 전까지 N-1 개의 쓰레드가 낭비된다.
핵심 질문: 회전을 피하는 방법
어떻게 하면 스핀에 CPU 시간을 낭비하지 않는 락을 만들 수 있을까?
이제부터는 운영체제로부터의 지원이 추가로 필요하다.
13. 간단한 접근법 : 무조건 양보!
무조건 양보
-
락이 해제되기를 기다리며 스핀해야 하는 경우, 자신에개 할당된 CPU를 다른 쓰레드에게 양보하는 전략
void init() { flag = 0; } void lock() { while (TestAndSet(&flag, 1) == 1) // 만약 다른 쓰레드가 락 보유하면, yield(); // CPU를 양보함 } void unlock() { flag = 0; }- 이 방법에서는 운영체제에 자신이 할당받은 CPU 시간을 포기하고 다른 쓰레드가 실행될 수 있도록 하는
yield()기법이 있다고 가정한다. - 양보(yield)라는 시스템 콜은 호출 쓰레드 상태를 실행 중 (running) 상태에서 준비(ready) 상태로 변환 하여 다른 쓰레드가 실행 중 상태로 전이하도록 한다.
- 결과적으로 양보 동작은 스케줄 대상에서 자신을 빼는 것 (deschedule) 이나 마찬가지이다.
- 이 방법에서는 운영체제에 자신이 할당받은 CPU 시간을 포기하고 다른 쓰레드가 실행될 수 있도록 하는
그러나 이 방법도 한계가 있다.
- ex) 100개의 쓰레드 중 한 쓰레드가 락을 획득하고 선점한 경우
- 나머지 99개의 쓰레드가
lock()호출하고 CPU 양도 - 만약 라운드로빈 스케줄러를 사용한다면, 쓰레드를 실행하고 양도하는 과정을 99번 반복하게 된다.
- 99번 스핀하며 낭비하는 것보다는 괜찮지만, 여전히 문맥교환 비용이 상당하며 낭비가 많다.
- 나머지 99개의 쓰레드가
- 특정 쓰레드는 무한히 양보만 하며 굶주리게 될 수도 있다.
14. 큐의 사용 : 스핀 대신 잠자기
이전 방법들은 너무 많을 부분을 운에 맡긴다는 문제점이 있었고, 따라서 어떤 쓰레드가 다음으로 락을 획득할지를 명시적으로 제어할 수 있어야 한다.
이를 위해서는 운영체제로부터 적절한 지원과 큐를 이용하여 대기 쓰레드를 관리하는 방법에 대해 알아볼 것이다.
typedef struct __lock_t {
int flag;
int guard;
queue_t *q;
} lock_t;
void lock_init(lock_t *m) {
m−>flag = 0;
m−>guard = 0;
queue_init(m−>q);
}
void lock(lock_t *m) {
while (TestAndSet(&m−>guard, 1) == 1)
; // 회전하면서 guard 락을 획득
if (m−>flag == 0) {
m−>flag = 1; // 락을 획득함
m−>guard = 0;
} else {
queue_add(m−>q, gettid());
m−>guard = 0;
park();
}
}
void unlock(lock_t *m) {
while (TestAndSet(&m−>guard, 1) == 1)
; // 회전하면서 guard 락을 획득
if (queue_empty(m−>q))
m−>flag = 0; // 락을 포기함: 누구도 락을 원치 않음
else
unpark(queue_remove(m−>q)); // 락을 획득함 (다음 쓰레드를 위해!)
m−>guard = 0;
}park(): 호출하는 쓰레드를 잠재우는 함수unpark(threadID): threadID로 명시된 특정 쓰레드를 깨우는 함수- 이 두 루틴은 이미 사용 중인 락을 요청하는 프로세스를 재우고 해당 락이 해제되면 깨우도록 하는 락을 제작하는 데 앞뒤로 사용할 수 있다.
guard:flag와 큐의 삽입/삭제 동작을 스핀 락으로부터 보호하는데 사용- 이 방법은 회전 대기를 완전히 배제하지는 못했다.
- 쓰레드는 락을 획득/해제하는 과정에서 인터럽트에 걸릴 수 있지만, 회전 대기 시간이 짧다.
- 왜냐하면 사용자가 지정한 임계영역에 진입하는 것이 아니라 락과 언락 코드 내의 몇 개의 명령어만 수행하면 되기 때문이다.
- 큐를 사용한 쓰레드 관리
lock()을 호출하여 락 획득을 시도하였는데 다른 쓰레드가 이미 락을 보유한 경우를 가정하자.- 이때 락 소유자(쓰레드)의 큐에 자기 자신의 ID(쓰레드 ID)를 추가한다.
- 이후
guard변수를 0으로 변경하고park()를 호출하여 CPU를 양보한다 (sleep 상태). - 나중에
unlock()이 호출되어 큐에서 나오게 되었을 때 잠자고 있던 쓰레드를 깨운다.
- 깨우기/대기 경쟁(wakeup/waiting race)
park()직전에 경쟁 조건이 발생된다.- 어떤 쓰레드에서 락 획득에 실패하여 park() 문을 수행하려는 상황을 가정하자.
- 만약 그 직전에 락 소유자한테 CPU가 할당되는 경우 문제가 발생할 수 있다.
- 예를 들어 락을 보유한 쓰레드가 해당 락을 해제했다고 하자.
- 처음의 쓰레드가 자기 차례에 park()를 수행하면 (잠재적으로) 깨어날 방법이 없다.
- Solaris는
setspark()라는 코드를 추가하여 해결하였다.queue_add(m−>q, gettid()); setpark();// 추가 m−>guard=0;setspark():park()를 호츌하기 직전이라는 것을 표시- 만약 그때 인터럽트가 수행되고,
park()가 실제로 호출되기 전에 다른 쓰레드가unpark()를 먼저 호출한다면, 추후park()문은 sleep 하지 않고 바로 return이 된다.
15. 다른 운영체제, 다른 지원
Linux: futex 지원
- futex는 특정 물리 메모리 주소와 연결이 되어 있으며. futex마다 커널 내부의 큐를 밖고 있다.
- 호출자는 futex를 호출하여 필요에 따라 잠을 자거나 깨어날 수 있다.
futex_wait(address, expected)- address의 값과 expected의 값이 동일한 경우 쓰레드를 잠재우고, 같지 않다면 즉시 리턴한다.
futex_wake(address, expected)- 큐에서 대기하고 있는 쓰레드 하나를 깨운다.
void mutex_lock (int *mutex) {
int v;
/* 31번째 비트가 이미 초기화되어 있다. mutex를 이미획득했다. 바로 리턴한다. （이것이 빠르게 실행하는 방법이다) */
if (atomic_bit_test_set(mutex, 31) == 0)
return;
atomic_increment(mutex);
while (1) {
if (atomic_bit_test_set(mutex, 31) == 0) {
atomic_decrement(mutex);
return;
}
/* 이제 대기해야 한다. 먼저, 우리가 관찰 중인 futex 값이 실제로 음수 인지 확인해야 한다（잠겨있는 상태인지). */
v = *mutex;
if (v >= 0)
continue;
futex_wait(mutex, v);
}
}
void mutex_unlock (int *mutex) {
/* 필요충분 조건으로 관심 대상의 다른 쓰레드가 없는 경우에 한해서
0x80000000를 카운터에 더하면 0을 얻는다. */
if (atomic_add_zero(mutex, 0x80000000))
return;
/* 이 mutex를 기다리는 다른 쓰레드가 있다면 그 쓰레드들을 깨운다. */
futex_wake(mutex);- 최상위 비트를 사용하여 락의 사용 중 여부를 표현 (1이면 락 사용중)
- 나머지 비트로 대기자 수를 표현
- 경쟁이 없는 일반적인 경우에 대한 최적화 방법을 제시하였다.
- 단 하나의 쓰레드가 락을 획득하고 해제하는 경우라면 아주 약간만 일을 하도록 하였다.
- 원자적으로 비트 단위의 TestAndSet로 락을 획득하고 원자적 덧셈을 하여 락을 해제한다.
16. 2단계 락
2단계 락(two-phase lock)
- 첫 번째 단계에서는 곧 락을 획득할 수 있을 것이라는 기대로 회전하며 기다린다.
- 첫 번째 단계에서 락을 획득하지 못했다면 두 번째 단계로 진입한다.
- 두 번째 단계에서는 호출자는 sleep 상태가 되고, 락이 해제된 후에 호출자가 깨어나도록 한다.
- 2단계 락은 두 개의 좋은 개념을 사용하여 개선된 하나를 만들어 내는 하이브리드 방식의 일종이다.
- 하드웨어 환경, 쓰레드의 개수, 세부 작업량 등에 의존성이 있으므로 항상 좋다고 보기는 어렵다.
코딩연습