Introduction
concurrency에서 instruction이 atomic하지 않아서 문제가 발생한다. 이를 해결하기 위해 critial section을 lock으로 감싸서 atomic하게 만든다.
Locks: The Basic Idea
lock_t mutex; // some globally-allocated lock ’mutex’
...
lock(&mutex);
balance = balance + 1;
unlock(&mutex);위처럼 lock variable을 이용해 mutex를 선언한다.
lock()을 호출해서 lock 획득을 시도할 수 있다. 만약 다른 스레드가 lock이 아니면 lock을 획득하고 critical section에 접근할 수 있다.
Pthread Locks
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
Pthread_mutex_lock(&lock); // wrapper for pthread_mutex_lock()
balance = balance + 1;
Pthread_mutex_unlock(&lock);Evaluating Locks
lock 구현의 평가 요소
- Correctness: mutual exclusive한가
- Mutual exclusion: critical section에 하나만 들어가도록 (가장 중요)
- Progress: DeadLock에 걸리면 안 됨.(설계 오류) → 최소 스레드 하나는 스케줄 되어야 함.
- Bounded wait: 굶으면 안된다.(fair와도 관련 있음) 계속 기다리면 안 됨
- Fairness:기다리는 시간이 공평한가
- Performance: 효율적인가
Controlling Interrupts
- Lock with interrupts
void lock() {
DisableInterrupts();
}
void unlock() {
EnableInterrupts();
}lock을 걸면 다른 스레드가 interrupt를 걸 수 없도록 해서 atomic하게 구현할 수 있음.
장점: 단순하다.
단점:
- 모든 스레드가 권한이 있어야 한다.
독점 가능, 타임아웃도 못 건다.
만약 무한 loop을 돈다면 lock을 해제할 수 없다.
- 멀티 프로세서에서 동작하지 않는다.
CPU가 여러 개인 경우 T1이 CPU1에서 락을 걸어도 T2가 CPU2에서 실행될 수 있다. CPU1의 인터럽트를 제어해도, CPU2에서 인터럽트를 걸 수 있다.
- 인터럽트를 오래 끄면 여러 문제가 발생할 수 있다.
(오류 등을 알려주는 인터럽트를 무시하면) 아주 중요한 장치의 인터럽트를 놓칠 수 있음.
- 인터럽트 관련 명령은 느리다.
A Failed Attempt: Just Using Loads/Stores
- First Attempt: A Simple Flag
typedef struct __lock_t { int flag; } lock_t;
void init(lock_t *mutex) {
// 0 -> lock is available, 1 -> held
mutex->flag = 0;
}
void lock(lock_t *mutex) {
// LD
while (mutex->flag == 1) // TEST the flag
; // spin-wait (do nothing)
// race condition
mutex->flag = 1; // ST
}
// now SET it!
void unlock(lock_t *mutex) {
mutex->flag = 0;
}Trace: Load/Store (정상적인 경우)
T1의 critical section이 분리 되었지만 T2가 중가에 들어올 수 없다.
하지만 race condition이 발생할 수 있다.
- Trace: Load/Store (race condition)
LD해서 flag가 0임을 확인하고 1로 ST하려는 사이에 인터럽트가 걸릴 수 있다.)
Building A Working Spin Lock(with Test-And-Set)
Test-And-Set: LD와 ST를 동시에 수행
while() loop에서 spin을 돌면서 lock을 시도한다.
flag를 1로 계속 바꾸는데 만약 0에서 1로 바뀐 경우 lock을 얻는다.
- A Simple Spin Lock Using Test-and-set
// HW가 수행(xchange로 동시에 수행함)
// (기계어)
int TestAndSet(int *old_ptr, int new) {
int old = *old_ptr; // fetch old value at old_ptr
*old_ptr = new; // store ’new’ into old_ptr
return old; // return the old value
}typedef struct __lock_t {
int flag;
} lock_t;
void init(lock_t *lock) {
// 0 indicates that lock is available, 1 that it is held
lock->flag = 0;
}
void lock(lock_t *lock) {
// TestAndSet() 0->1 이면 return 1 (while loop)
// TestAndSet() 1->1 이면 return 0 (break -> get lock)
while (TestAndSet(&lock->flag, 1) == 1)
; // spin-wait (do nothing)
}
void unlock(lock_t *lock) {
lock->flag = 0;
}A는 계속 동작하고 B는 CPU를 못 얻음(starve + unfair) → spin lock의 문제
- Spin Lock - Starvation
B에게 unfair하다.
B가 spin 하면서 효율이 떨어진다.
단점: spin, unfair
Compare-And-Swap
Compare-And-Swap: flag가 기대하는 값인지 확인(Test)하고 맞으면 Set.
- Compare and Swap
// (assembly)
int CompareAndSwap(int *ptr, int expected, int new) {
int actual = *ptr;
// 가져온 값이 expected이면 값을 바꿈
if (actual == expected)
*ptr = new;
return actual;
}
void lock(lock_t *lock) {
// flag가 0이면 1로 세팅 -> break
// flag가 1이면 do nothing -> while loop
while (CompareAndSwap(&lock->flag, 0, 1) == 1)
; // spin
}- 실제 assembly code
char CompareAndSwap(int *ptr, int old, int new) {
unsigned char ret;
// Note that sete sets a ’byte’ not the word
__asm__ __volatile__ (
" lock\n"
" cmpxchgl %2,%1\n"
" sete %0\n"
: "=q" (ret), "=m" (*ptr)
: "r" (new), "m" (*ptr), "a" (old)
: "memory");
return ret; }단점: spin, unfair
Load-Linked and Store-Conditional
Test(Load-Linked) 이후 처음 쓰는 경우 Set(Store-Conditional)
- Load-Linked and Store-Conditional
// (기계어)
LoadLinked(int *ptr) {
// LD해서 주소만 기억함
return *ptr;
}
// (기계어)
StoreConditional(int *ptr, int value) {
// LD한 이후에 그 주소에 내가 처음으로 ST하는 경우
if (no one has updated *ptr since the LoadLinked to this address) {
*ptr = value;
return 1; // success!
}
else {
// 내가 처음이 아니면 ST 안함
return 0; // failed to update
}
}
void lock(lock_t *lock) {
while (1) {
// flag 0이면 break
// flag 1이면 while loop (누가 lock이라는 의미)
while (LoadLinked(&lock->flag) == 1)
; // spin until it’s zero
// flag = 0이었으면 1로 세팅 시도 (단 내가 처음으로 ST인 경우만 성공)
// if문 위아래로 interrupt 발생 가능
if (StoreConditional(&lock->flag, 1) == 1)
return; // if set-it-to-1 was a success: all done
// otherwise: try it all over again
}
}
void unlock(lock_t *lock) {
lock->flag = 0;
}단점: spin, unfair
spin lock을 사용하는 세 방법 이 unfair함
- Working Spin Lock with Test-And-Set
- Compare-And-Swap
- Load-Linked and Store-Conditional
Fetch-And-Add (번호표)
- fetch-and-add
// (기계어)
int FetchAndAdd(int *ptr) {
int old = *ptr;
// 번호표 부여
*ptr = old + 1;
return old;
}
// (기계어) atomic한 구현이 내장 되어있음
Implementation:
__sync_fetch_and_add(ptr, 1)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) {
// ticket을 받아옴
int myturn = FetchAndAdd(&lock->ticket);
// 내 차례까지 기다림
while (lock->turn != myturn)
; // spin
}
// turn을 1 증가시켜서 다음 번호가 기회를 잡음
void unlock(lock_t *lock) {
lock->turn = lock->turn + 1;
}Example: fetch-and add example
Evaluation: fetch-and-add
Correctness를 모두 충족하고 fair하다.
하지만 lock()에 spin이 있어서 비효율적이다.
Uploaded by Notion2Tistory v1.1.0