단일 프로세서에 인터럽트가 존재하기 때문에 일련의 명령을 원자적으로 실행하지 못하고 동시성에 문제가 있었다. 이를 해결하기 위해 원자적으로 실행하고 싶은 주변에 Lock을 두어 그 부분이 하나의 원자적 명령처럼 실행되도록 보장한다.
Lock의 기본적 아이디어
Lock(락)은 단지 변수일 뿐이고, 사용하려면 락 변수를 선언해야한다. 이 락은 어떤 순간에든 락의 상태를 보유한다. 락이 사용가능하면, 아무 스레드도 락을 보유하지 않았으므로 획득가능하고, 락이 사용중이면, 한 스레드가 락을 보유하고 아마 critical section 에 있다는 뜻이다. 그리고 락 사용자로부터 다른 정보(누가 락을 보유중인지 등)도 데이터 형식에 저장할 수 있다.
lock()을 실행하면, 락을 획득하려고 시도하여 누군가 락을 보유하고 있지 않으면 락을 획득하고 critical section에 들어간다. 이때 다른 스레드가 lock()을 실행해도 락을 반환하지 않아 critical section에 들어가는 것을 방지한다. 락의 소유자가 unlock()을 호출하면 락은 다시 사용가능한 상태가 된다.
코드 일부를 락으로 감싸면 해당 코드 내에서 하나의 스레드만 활성화 되므로 OS스케줄링의 모호함을 줄일 수 있다.
Pthread Locks
POSIX 라이브러리에서 락에 사용하는 이름은 mutex(뮤텍스)이다.
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
Pthread_mutex_lock(&lock); // wrapper; exits on failure
balance = balance + 1;
Pthread_mutex_unlock(&lock);lock,unlock에 락 변수를 전달하면, 서로 다른 변수를 보호하기 위해 다른 락을 사용할 수 있다.
하나의 큰 락(coarse-grained)대신, 한 번에 더 많은 스레드를 락에 있을 수 있게 한다.(fine-grained)
Lock 구축, 평가
효율적인 락은 낮은 비용으로 mutual exclusive(상호 배제)를 제공한다. 락을 구축하기 위해서는 하드웨어와 OS의 지원이 필요하다.
락을 구축할 때의 목표
-
첫 번째는 , 락이 기본 작업을 수행하는지 여부이다.
-
두 번째는 , 공정성(fairness)이다. 락을 경합하는 각 스레드가 락을 획득할 수 있는 공정한 기회를 얻는지 여부이다. 어떤 스레드가 락을 획득하지 못하고 기아(starve)상태에 빠지는 경우가 있는지를 확인해야한다.
-
세 번째는, 성능이다. 락을 추가적으로 사용하니 시간 오버헤드가 증가했을 것이다. 락 경합이 없는 경우 , 경합을 하는 여러 스레드가 있는 경우, CPU와 스레드가 여러개일 경우 등의 시나리오를 비교하며 락의 성능을 체크해야한다.
아래에서 다양한 방법으로 Lock을 구현한 것을 볼 수 있으며, 각 방법들이 목표를 이루고 있는지 판단해보자
Controlling Interrupts
lock을 활용하여 mutual exclusive를 제공하려면 interrupt 를 control 할 수 있어야 한다.
1 void lock() {
2 DisableInterrupts();
3 }
4 void unlock() {
5 EnableInterrupts();
6 }lock과 unlock에서 interrupt를 비활성,활성 시키고 있다. 이 방법은 간단하지만 단점이 많다.
-
첫 번째로, 스레드가 interrupt를 조작하는 특권적인 작업을 함으로써 남용에 대한 위험이 증가한다. 임의의 스레드가 lock을 반환하지 않으면 가져올 수 없다는 위험이다.
-
두 번째, 다중 프로세서에서는 동작하지 않는다. 여러 스레드가 서로 다른 CPU에서 실행되고 각각이 같은 critical section에 진입하려한다면 interrupt의 활성 여부는 무시될 수 있다.
-
세 번째, interrupt를 장시간 비활성화 시 , interrupt가 손실될 수 있고 심각한 문제를 야기할 수 있다.
이런 이유들 때문에 interrupt를 끄는 것은 제한적인 상황에서만 사용될 수 있다. 예를 들어 OS자체가 자체 데이터 구조에 엑세스 할 때는 신뢰문제가 생기지 않는다.
loads/store 사용해보기
interrupt를 사용하지 않고 락을 구현하기 위해서 단순히 단일 변수나 load/store 를 사용해보자
1 typedef struct __lock_t { int flag; } lock_t;
2
3 void init(lock_t *mutex) {
4 // 0 -> lock is available, 1 -> held
5 mutex->flag = 0;
6 }
7
8 void lock(lock_t *mutex) {
9 while (mutex->flag == 1) // TEST the flag
10 ; // spin-wait (do nothing)
11 mutex->flag = 1; // now SET it!
12 }
13
14 void unlock(lock_t *mutex) {
15 mutex->flag = 0;
16 }위의 코드에서는 어떤 스레드가 락을 가지고 있는지를 나타내기 위해서 변수(flag)를 사용한다. 스레드가 critical section에 들어가기 위해 lock()을 호출하여 flag가 1인지 확인한 뒤 0이라면, flag를 1로 설정후 critical section으로 들어간다. flag가 1이어서 들어갈 수 없다면 무한대기(spin-wait)한다.
하지만 여기서 만약 flag가 0인걸 확인한 직후에 인터럽트가 걸려 다른 스레드가 진행한다면, 서로 다른 두 스레드가 flag가 0이라고 판단해서 모두 critical section에 들어가게 된다.
또, 정상작동 한다고 하여도 flag를 기다리기 위해 spin-wait 해야하므로 성능상 큰 문제이다.
Test-And-Set을 사용한 Spin Lock 구축
락을 구현하기 위해 하드웨어적 지원을 받아보자
이해하기 쉬운 하드웨어 지원 기능은 Test-And-Set(원자적 교환) 명령어이다.
int TestAndSet(int *old_ptr, int new) {
int old = *old_ptr; // old_ptr에서 이전 값을 가져옴
*old_ptr = new; // 'new' 값을 old_ptr에 저장
return old; // 이전 값을 반환
}이 명령어가 하는 일은 old_ptr이 가리키는 값을 반환하고 그 값을 new로 업데이트한다. 이 작업이 원자적으로 수행된다는 것이 중요하다. test-and-set이라고 불리는 이유는 이전 값을 테스트하며 메모리 위치를 새 값으로 설정하기 때문이다.
1 typedef struct __lock_t {
2 int flag;
3 } lock_t;
4
5 void init(lock_t *lock) {
6 // 0: lock is available, 1: lock is held
7 lock->flag = 0;
8 }
9
10 void lock(lock_t *lock) {
11 while (TestAndSet(&lock->flag, 1) == 1)
12 ; // spin-wait (do nothing)
13 }
14
15 void unlock(lock_t *lock) {
16 lock->flag = 0;
17 }전의 코드에서는 flag의 값이 1인지 확인하는 것과 1로 설정하는 것이 나뉘어져 있어서 문제가 발생했었다.
이제는 test-and-set을 사용하여 그 작업을 원자적으로 수행한다. 그렇기 때문에 이전에 언급한 두 스레드가 모두 critical section으로 들어가는 문제는 일어나지 않는다.
스핀 락 평가
기본적인 스핀 락이 얼마나 효과적인지 평가해보자.
-
정확성 : 한 번에 하나의 스레드만 critical section에 들어갈 수 있으므로 mutual exclusive를 제공한다.
-
공정성 : 대기 중인 스레드는 영원히 스핀할 수도 있다. 공정하지 않으며 starvation을 만들 수 있다.
-
성능 : 단일 CPU의 경우 각 스레드는 타임슬라이스동안 스핀만 하기때문에 CPU의 낭비가 일어난다. 하지만 CPU가 여러개라면 스핀 락이 잘 작동한다. 스레드 수가 CPU수와 거의 같은 상황에서는 다른 스레드에서 스핀하고 있으면 곧 락이 사용가능해지기 때문이다.
Compare-And-Swap
Compare-And-Swap명령어를 사용하여 하드웨어 지원을 받을 수 있다.
기본 아이디어는 Compare-And-Swap이 지정된 ptr 주소의 값이 expected와 같은지 테스트 하고 만약 그렇다면 ptr이 가리키는 메모리 위치를 새로운 값으로 업데이트한다.
나머지 코드는 test-and-set과 동일하고 lock()만 바꾸면 된다.
int CompareAndSwap(int *ptr, int expected, int new) {
int original = *ptr;
if (original == expected) *ptr = new;
return original;
}
void lock(lock_t *lock) {
while (CompareAndSwap(&lock->flag, 0, 1) == 1)
; // spin
}이 코드는 flag가 0인지 확인하고, 그렇다면 1로 바꾼뒤 락을 획득한다. 이것은 원자적으로 실행된다.
Load-Linked and Store-Conditional
MIPS 아키텍처에서는 load-linked 와 store-conditional 명령어를 함께 사용하여 락과 동시성 구조를 구축할 수 있다.
1 int LoadLinked(int *ptr) {
2 return *ptr;
3 }
4
5 int StoreConditional(int *ptr, int value) {
6 if (no update to *ptr since LL to this addr) {
7 *ptr = value;
8 return 1; // success!
9 } else {
10 return 0; // failed to update
11 }
12 }load-linked 는 일반적인 로드 명령어처럼, 단순히 메모리에서 값을 가져와 레지스터에 저장한다.
하지만, store-conditional은 일반적인 스토어 명렁어와 차이가 있다. store-conditional은 해당 주소에 저장된 값이 변경되지 않았을 경우에만 주소에 값을 업데이트한다. 성공시 1을 반환하고 ptr의 값을 value로 업데이트한다. 실패시 ptr은 업데이트 되지 않고 0을 반환한다.
이제 이 명령어들을 사용하여 lock을 구축해보자
1 void lock(lock_t *lock) {
2 while (1) {
3 while (LoadLinked(&lock->flag) == 1)
4 ; // spin until it’s zero
5 if (StoreConditional(&lock->flag, 1) == 1)
6 return; // if set-to-1 was success: done
7 // otherwise: try again
8 }
9 }
10
11 void unlock(lock_t *lock) {
12 lock->flag = 0;
13 }아래는 더 간단하게 만든 코드이다.
1 void lock(lock_t *lock) {
2 while (LoadLinked(&lock->flag) ||!StoreConditional(&lock->flag, 1)); // spin
3 }Fetch-And-Add
이 명령어는 특정 주소의 값을 원자적으로 증가시키면서 그 주소에 있던 이전 값을 반환한다.
int FetchAndAdd(int *ptr) {
int old = *ptr;
*ptr = old + 1;
return old;
}이 명령어를 사용하여 티켓 락(아래 코드)을 구현할 수 있다.
1 typedef struct __lock_t {
2 int ticket;
3 int turn;
4 } lock_t;
5
6 void lock_init(lock_t *lock) {
7 lock->ticket = 0;
8 lock->turn = 0;
9 }
10
11 void lock(lock_t *lock) {
12 int myturn = FetchAndAdd(&lock->ticket);
13 while (lock->turn != myturn)
14 ; // spin
15 }
16
17 void unlock(lock_t *lock) {
18 lock->turn = lock->turn + 1;
19 }이 방법은 단일 값 대신 티켓과 턴 변수를 조합하여 락을 구축한다.
spin 대신 양보하기
스레드가 락을 얻기 위해 무한히 스핀하는 상황을 해결하기 위해 스핀하는 대신 CPU를 양보할 수 있다. 스레드는 running, ready, blocked 상태중 하나에 있을 수 있다. yield()는 호출자를 running 에서 ready 상태로 이동시킨다.
두 스레드가 하나의 CPU에 있다면, lock을 얻지 못했을 때 yield()를 호출하여 CPU를 양보하여 다른 스레드가 실행할 수 있게 할 수 있다.
하지만 스레드가 많은 상황에서 yield()호출도 많아진다면, context switching 비용이 크기 때문에 성능에 낭비가 있을 것이다. 그리고 양보하는 방식은 starvation 문제를 해결하지 않는다. 무한 스핀이 아니라 무한 양보를 할 수 있기 때문이다.
spin 대신 sleeping : Queue 사용
이전의 방식들은 락을 갖기 위해 스핀하든, 양보하든 스레드가 CPU에서 동작할 기회를 놓치고 starvation 문제를 해결할 수 없었다. 이 문제를 해결하기 위해 queue를 사용해서 락을 얻을 스레드를 sleep 시킨 후 lock을 해제한 스레드가 다음 스레드에 명시적인 제어를 가해줄 수 있다.
Solaris 운영체제에서 사용하는 호출을 살펴보자
park()는 호출한 스레드를 sleep상태로 전환하고, unpark(threadID)는 threadID로 지정된 특정 스레드를 깨운다. 이 두 루틴을 함께 사용하여 호출자가 락을 얻으려고 할 때 sleep 상태로 전환되고, 락이 해제될때 다음 스레드를 깨울 수 있다.
1 typedef struct __lock_t {
2 int flag;
3 int guard;
4 queue_t *q;
5 } lock_t;
6
7 void lock_init(lock_t *m) {
8 m->flag = 0;
9 m->guard = 0;
10 queue_init(m->q);
11 }
12
13 void lock(lock_t *m) {
14 while (TestAndSet(&m->guard, 1) == 1)
15 ; //acquire guard lock by spinning
16 if (m->flag == 0) {
17 m->flag = 1; // lock is acquired
18 m->guard = 0;
19 } else {
20 queue_add(m->q, gettid());
21 m->guard = 0;
22 park();
23 }
24 }
25
26 void unlock(lock_t *m) {
27 while (TestAndSet(&m->guard, 1) == 1)
28 ; //acquire guard lock by spinning
29 if (queue_empty(m->q))
30 m->flag = 0; // let go of lock; no one wants it
31 else
32 unpark(queue_remove(m->q)); // hold lock
33 // (for next thread!)
34 m->guard = 0;
35 }이 예시에서는 test-and-set을 queue와 결합하여 효율적인 lock을 구현한다.
이 접근방식에서는 spin-waiting을 완전히 피하지 않는다. fleg와 queue는 모든 스레드가 사용하는 공용자원인데 이를 보호하기 위해 guard변수가 추가되었으며, fleg와 queue 조작이 일어날 때 이를 보호하기위해 spin-waiting 을 한다.
그리고, 다음 스레드가 깨어날 때 fleg를 0으로 설정하지 않고 다음 스레드로 lock을 직접 전달한다. 스레드가 깨어날 때는 park()에서 반환되는 것처럼 보이는데 그 때 guard,fleg를 바꿀 수 없기 때문이다.
락을 획득하지 못한 스레드는 guard=0 , park() 작업을 수행하는데, 이 순서가 바뀐다면 어떻게 될까? 그렇다면, park()에서 나온 스레드는 guard가 1이라고 판단해 fleg를 수정할 수 없다. 따라서 락을 획득할 수 있어도 불가능하다고 생각해서 다른 스레드에게 CPU를 양보한다.
스레드가 sleep상태로 들어갈 때, 큐에 스레드를 넣은 후 park()를 실행한다. 하지만, park()실행 전에 unpark()가 실행된다면, 스레드는 큐에 존재하지 않는데 park()가 실행되어 영원히 sleep상태에 빠질 수 있다. 이런 문제를 wakeup/waiting race 문제라고 한다. Solaris는 이 문제를 해결하기 위해 setpark()를 추가했다. 이 호출은 스레드가 park하기 직전임을 나타낼 수 있어서 park가 호출되기 전에 unpark되면, park는 즉시 반환된다.
//lock()의 코드수정
1 queue_add(m->q, gettid());
2 setpark(); // 새 코드
3 m->guard = 0;Linux Lock - futex
리눅스는 Solaris 와 유사하지만 커널 내 기능이 더 많은 futex(퓨텍스)를 제공한다.
futex wait(address,expected)호출은 address와 expected가 같을 때 호출하는 스레드를 잠들게 한다. 값이 같지 않으면 호출이 즉시 반환된다.
futex wake(address)호출은 queue의 스레드 하나를 깨운다.
1 void mutex_lock (int *mutex) {//mutex는 공유변수
2 int v; //스레드 지역 변수
3 // 정수의 특정 비트-31번이 0이면 1로 바꾸고 뮤텍스를 획득한다
4 if (atomic_bit_test_set (mutex, 31) == 0)//락 시도
5 return;// 락 성공 > 반환
6 atomic_increment (mutex); // 락 실패 락을 시도하는 스레드 수 1 증가
7 while (1) { //될때까지 시도
8 if (atomic_bit_test_set (mutex, 31) == 0) {//다시 락 시도
9 atomic_decrement (mutex); //락 성공 증가시킨 스레드 수 감소
10 return;
11 }
12 // futex 값이 음수(잠김)인 것을 확인하기 위해 대기해야 합니다.
13 // 우리가 모니터링하는 futex 값이 음수인지 확인해야 합니다.
14 v = *mutex; //이건 load 명령어라 atomic함
15 if (v >= 0) //이걸 실행하면서 인터럽트가 걸릴 수도 있어서 v에 복사하여 비교
16 continue; //mutex가 음수면 잠들기 아니면 다시 락 시도
17 futex_wait (mutex, v); //잠들기
18 }
19 }
20
21 void mutex_unlock (int *mutex) {
22 // 16진수 0x80000000 = 2진수 1000 0000 ... 0000 so 뮤텍스 앞자리 바꾸는 것
23 // 다른 관심 있는 스레드가 없다면 0이 됩니다.
24 if (atomic_add_zero (mutex, 0x80000000))//값을 더한게 0인지 체크
25 return;
26
27 // 이 뮤텍스를 기다리는 다른 스레드들 중 하나를 깨웁니다.
28 futex_wake (mutex);
29 }mutex 라는 단일 정수를 사용해서 락의 여부와 락 대기자 수를 알 수 있다. 정수의 최상위 비트가 음수이면 락이 걸린 것이고, 나머지 비트가 대기자 수를 나타낸다.
예를 들어서 counter = counter + 1 과 같은 작업을 할 때는 어셈블리어로
mutex_lock(&mutex); // C1
100: mov 0x8049a1c, %eax // C2
105: add $0x1, %eax // C3
108: mov %eax, 0x8049a1c // C4
mutex_unlock(&unlock); // C5 과 같이 쓸 수 있다. C2에서 counter에 있는 값을 가져와서 C3에서 1을 더하고 C4에서 다시 counter에 저장한다. 그리고 C1과 C5에서 이 구역을 락으로 감쌌다. 따라서 C1에서 futex lock을 얻으려고 시도하고, C5에서 unlock을 한다.
