Too Much Spining
spin을 사용하는 정책의 고질적인 문제가 있다.
Bad Performance
한 스레드가 lock 상태에서 spin을 돌면 다른 스레드는 lock을 얻기 힘들어진다.
priority inversion
spin의 또 다른 문제점은 priority inversion이다. 이는 우선순위가 낮은 job이 먼저 스케줄 되는 상황을 말한다.
우선순위가 있는 스케줄링이라고 가정하자.
Priority inversion
이런 문제를 해결하는 방법 중 하나는 priority inheritance다.
A Simple Approach: Just Yield
이런 spin의 문제를 해결하기 위해 lock을 얻지 못하면 바로 Yield하는 방식을 사용할 수 있다.
- Lock With Test-and-set And Yield
void init() {
flag = 0;
}
void lock() {
while (TestAndSet(&flag, 1) == 1)
yield(); // give up the CPU
}
void unlock() {
flag = 0;
}yield를 하면 running에서 ready로 상태가 변한다. 즉 yield는 자기 스스로 deschedule하는 것이다.
- Lock With Queues, Test-and-set, Yield, And Wakeup
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)
; //acquire guard lock by spinning
if (m->flag == 0) {
m->flag = 1; //
m->guard = 0; }else{
queue_add(m->q,
m->guard = 0;
park();
}
}
void unlock(lock_t *m) {
while (TestAndSet(&m->guard, 1) == 1)
; //acquire guard lock by spinning
if (queue_empty(m->q))
m->flag = 0; // let go of lock; no one wants it
else
lock is acquired
gettid());
unpark(queue_remove(m->q)); // hold lock (for next thread!)
m->guard = 0;
}- Spin vs Yield
하지만 yield는 context switcing을 하기 때문에 cost가 많이 들고, starvation 문제를 해결하지 못한다.
Using Queues: Sleeping
Spin 하는 대신 wait Q에서 sleep 하면서 기다린다.
Solaris는 park()로 스레드를 sleep시키고, unpark()로 스레드를 wake up 시킨다.
- Lock With Queues, Test-and-set, Yield, And Wakeup (with guard)
typedef struct __lock_t {
int flag;
int guard;
queue_t *q; // waiting queue!
} lock_t;
void lock_init(lock_t *m) {
m->flag = 0;
m->guard = 0;
queue_init(m->q);
}
void lock(lock_t *m) {
// ---------------- guard lock -------------------------
while (TestAndSet(&m->guard, 1) == 1)
; //acquire guard lock by spinning
if (m->flag == 0) { // flag=0이면 1로
m->flag = 1; // lock is acquired
// guard unlcok
m->guard = 0; // Test & Set 역할을 하는 작은 lock
} else { // flag=1이면 Q에서 기다린다.
queue_add(m->q, gettid());
m->guard = 0; // guard 풀기
// ---------------- guard unlock -----------------------
// 여기서 다른 스레드가 unlock()을 해서 unpark()까지 하면 이 스레드를 다시는 못깨움
park(); // sleep (Blocked)
}
}
void unlock(lock_t *m) {
// ---------------- guard lock -------------------------
while (TestAndSet(&m->guard, 1) == 1)
; //acquire guard lock by spinning
if (queue_empty(m->q))
m->flag = 0; // let go of lock; no one wants it
else
unpark(queue_remove(m->q)); // hold lock(for next thread)
// 큐에서 대기(blocked)하던 스레드를 wake up(ready로 변화)
// 위에서 flag는 풀었지만 아직 guard를 안풀었음.
// 만약 여기서 다른 스레드의 lock()과 경쟁하면
// 그 스레드는 guard에 의해 lock을 얻지 못함.
m->guard = 0;
// ---------------- guard unlock -----------------------
}user-defined여서 크기를 알 수 없는 lock()과 unlock() 사이의 critical section을 spin 하는 대신 함수 내부에서 짧은 spin을 한다.
lock()을 하면 guard를 0으로 바꾸고 CPU를 yield 한다. while()에서 예상 가능한 시간만큼 spin한다.
race condition 가능성이 남아있다.
솔라리스는 setpark()을 사용하는데, setpark() 이후 unpark()이 실행되었는지 체크한다.
setpark() 이후 unpark()이 있으면 아래서 park를 안하고, unpark()이 없으면 나중에 park()한다.
- setpark()
queue_add(m->q, gettid());
setpark(); // new code
m->guard = 0;
// 사용 예시
setpark()
unlock(guard)
// 여기에 inturrpt가 들어와서 다른 스레드가 unpark()할 수도 있음.
park() // <- unpark()이 있었으면 얘는 실행안함.
// unpark()이 없었으면 얘는 park()함.
Different OS, Different Support (Futex)
리눅스는 futex를 사용한다.
- Linux-based Futex Locks
/*
* mutex의 비트열에 대한 의미
* 최상위 비트: lock을 가지고 있는지 나타낸다.
* 나머지 : lock이 몇 개 걸렸는 지를 가지고 있다.
*/
void mutex_lock(int *mutex){
int v;
// 0->1: lock / 1->1: lock 획득 실패
if(atomic_bit_test_set(mutex, 31) == 0) // 최상위비트 test & set
return;
// 락 대기열에 하나가 더 들어갔음을 표기.
atomic_increment(mutex);
while(1) { // 최상위 비트가 0이 될 때까지 반복
// 0이면 1로 바꿈
// 최상위 비트를 0->1로 바꾸었으면 if state
// 원래 0이어서 0->0이면 else
if(atomic_bit_test_set(mutex, 31) == 0){
atomic_decrement(mutex);
return;
}
// v는 최상위 비트를 점검하여 락 상태를 확인.
// 최상위 비트가 1인 경우(v는 음수) lock이 걸렸음.
v = *mutex;
if(v >= 0)
continue;
// goto sleep if (*mutex == v)
futex_wait(mutex, v); // sleep
}
}
void mutex_unlock(int *mutex){
// 최상위 비트를 0으로 만들어서 unlock.
// 최상위 비트에 +1해서 mutex가 0인지 확인
if(atomic_add_zero(mutex, 0x80000000))
return;
futex_wake(mutex);
}Spin vs Sleep
CPU 1개
T2가 spin 하는 동안 T1이 스케줄 되지 않는다. 따라서 time out까지 기다려야 한다.
만약 sleep을 한다면 context switch 정도의 시간 지연 후에 T1이 스케줄 될 수 있다.
CPU 2개
critical section이 context switching보다 긴 경우 sleep해서 다른 스레드에게 줄 수 있어서 유리하다.
critical section이 작은 경우 바로 스케줄되어서 실행할 수 있는 spin이 유리하다.
Two-Phase Locks
Two-Phase Lock은 spin과 sleep을 모두 사용하는 방식이다.
처음 phase에서는 먼저 lock을 얻기 위해 spin을 한다.
만약 처음 phase에서 lock을 얻지 못하면 sleep 한다.
Uploaded by Notion2Tistory v1.1.0