reference: https://pages.cs.wisc.edu/~remzi/OSTEP/
for Mutual Exclusion
"오직 하나의 쓰레드만을 임계 구역에 허용한다."
=> 원자성 보장
관련 테크닉: mutex API, lock 변수(pthread_mutex_t 구조체)
1) 임계영역을 파악한다.
2) mutex 구조체 또는 클래스 객체(락 변수, lock)를 선언하고, 이를 초기화 한다(pthread_mutex_init(&lock)).
3) 쓰레드의 임계영역 전 객체(락 변수)를 인자로 전달하여 락을 건다(pthread_mutex_lock(&lock)).
4) 임계영역의 처리를 마친 후 락을 푼다(pthread_mutex_unlock(&lock)).
for Synchronization
"하나의 쓰레드는 다른 쓰레드가 작업을 끝낼 때까지 기다려야 한다."
=> 순서 관계 보장, 쓰레드1 -> 쓰레드2
관련 테크닉: cond API, 조건 변수(conditional variable)(pthread_cont_t 구조체)
1) T1: accquire lock => check ready valiable => wait on Condition Valiable
=> sleep mode (implicitly release the lock!)
2) T2: accquire lock => ready = 1 => signal on Condition Valiable
=> (implicitly) release lock
3) T1: wake up from condition variable(implicitly accquire the lock) => check ready variable => wait again or release the lock
==> C -> B : 순서 보장, 동기화(synchronization)
Lock
임계영역(critical section) 예시
balance = balance + 1;
변수뿐 아니라 공유 자료구조를 업데이트 하는 것도 임계영역 존재 ex) 연결리스트에 노드를 더하는 작업 등
Mutual exclusion using Lock
lock/unlock을 임계영역 전후에 적절히 사용
- ex) pthread_mutex_lock(), pthread_mutex_unlock()
Lock 구현 방식
- Controlling interrupt
- 인터럽트 제어
- SW approach: S/W적 방법
- test-and-set(원자적 x)
- HW approach: 원자적 연산 사용 (using atomic operations)
- test-and-set(원자적), compare-and-swap, load-linked and store-conditional, fetch-and-add
How to build the lock()/unlock() APIs?
=> collaboration between HW and OS
How to evaluate a lock()/unlock()? => three properties
1) correctness(정확도): does is gurantee mutual exclusion??
2) fairness(형평성): does any thread strave?
3) performance(성능): overhead added by using lock
one issue: lock size
1. Coarse-grained lock
- bit critical section with smaller number of locks
- (+) simple, (-) parallelism(병렬성이 떨어짐)
2. Fine-grained lock
- small critical section with larger number of locks
- (+) parallelism, (-) not simple
How to build the lock()/unlock() APIs?
1. Disable interrupt
스케줄링은 보통 타이머 장치 인터럽트에 의해 발생한다. 따라서 이 인터럽트를 disable하는 방식으로 쓰레드 수행의 원자성을 보장할 수 있다.
원리: No 인터럽트 -> No 문맥교환 -> No 임계구역 내 간섭
pros(+)
- simple
cons(-)
- 긴 시간 동안 인터럽트를 막는것은 시스템에 문제를 야기할 수 있다.
- 이 방식의 남용과 오용은 독접과 무한루프를 이끌 수 있다. 예를 들어 한 사용자가 intterupt disable 방식으로 CPU 자원을 독점할 수 있다는 것이다.
- 싱글 프로세서에서만 제대로 동작한다. 하나의 코어 단위에서 발생하는 문맥 교환 뿐 아니라 멀티 코어 위의 멀티 쓰레드 수행에 있어서도 공유자원의 문제가 발생할 수 있기 때문이다.
- used inside the OS (or trusy world): OS 내부적으로 trusty한 상태(not misuse)와 한 코어에서만의 동작이 보장될 때 사용하는 방식이다.
2. S/W only approach 방식
T1: Test -> (test 통과 후) Set flag = 1
T2: flag가 풀릴 때 까지flag == 0 루프안에서 계속 기다린다.
SW적 락 구현 방식은 이 외에도 여러 방법이 있다.
There were many SW-only approach: Such as Dekker's algorithm, Peterson's algorithm, ..
pros(+)
- SW solition
cons(-)
- mutex가 완전치 않다. Test와 Set이 원자적으로 이루지지 않을 수 있다.
-> both thread can enter the critical section
-> correctness가 떨어진다.
- spinnig (spin-wait) 방식(루프에서 계속 기다림) -> 성능이 떨어진다.
-> CPU busy, but doing useless work(플래그 체크만을 하는 의미없는 작업)
=> S/W only approach는 요즘은 거의 사용하지 않는다. (incorrect in modern systems)
3. HW approach 방식
방식1. test-and-set
위 3개의 statement => 하나의 기계명령어(xchg) in Intel
-> 원자적으로 처리되기에 Mutex가 보장된다.
only SW적 방식에서는 test과정과 set과정이 (원자적으로)떨어져있었다. 즉 원자적으로 수행되지 않았다는 것이다.
반면 HW적 방식에서는 원자성이 보장된다. (하나의 기계 명령어로써 한 명령어 사이클로 수행된다.)
(평가)
- 1) correctness
- Mutex를 보장하는 가? => Yes
- 임계역역 내 하나의 쓰레드 수행만을 보장
- 2) Fairness
- Can it guarantee that a waiting thread will enter the critical section? => unfortunately no😢
ex) 10개의 높은 순위의 쓰레드와 1개의 낮은 순위 쓰레드가 있다면 후자의 쓰레드는 계속해서 spin을 돌 것이며, 결국 starvation..- ticket lock 기법 등으로 이를 해결할 수 있다.
- 3) Performance
- spin 방식으로 인해 성능이 떨어진다. <-> SLEEP LOCK (참고로 SPIN 방식과 반대되는 방식의 lock 기법이 있다.)
- Single CPU의 경우 오버헤드는 상당히 painful
- Multiple CPUs의 경우
- 임계구역이 작다면 Spin이 차라리 나을 수도 있다. (trade-off with Context-Switching) -> do not waste another CPU cycles that much
- 따라서 임계영역이 짧은 곳에선 자주 spin lock 기법을 사용한다.
방식2. Compare-and-Swap => 마찬가지로 cmpxchg 라는 기계명령어를 사용해 원자성 보장
test-and-set 방식과의 차이점은 비교 구문 여부.
(real implementation)
방식3. load-linked and store-conditional => RISC CPU 명령어 사용
방식4. Fetch-and-Add: Fairness도 보장!
lock을 얻으려 함 -> call FetchAndAdd() with ticket => if(myturn == lock->turn) 임계구역 진입 => unlock with turn++
- 이 방식은 모든 쓰레드가 임계영역 내 수행을 보장한다. => Fairness 보장!
Lock mechanisms
1. Spin Lock
- busy waiting (endless check while using CPU)
- 간단하지만 비효율적인 방식, 특히 임계구역이 큰 경우는 더욱 비효율적이다.
2. Sleep Lock (supported by OS)
- lock을 얻지 못하면 선점(preempt)되어 wait state로 들어간다.
- lock이 풀리면 wakeup 된다.
- 1) CPU를 더 유용한 작업에 사용할 수 있다. (단순한 waiting x)
- 2) 하지만 임계구역이 짧은 경우는 차라리 그냥 spinning을 하는 것이 더 나을 수 있다. 문맥교환의 비용이 있기 때문이다.
- Need OS supports
- Sleep
단순한 spin보다 좋다. lock을 소유하고 있는 쓰레드에게 스케줄 기회 양보한다. - Issues
where to sleep => Using Queue (sleep 상태의 쓰레드들이 메달리는 큐)
How to wake up> => OS support (문맥교환)
lock을 얻지 못한다면 sleep queue에 들어가고, OS가 제공하는 API(ex, park()(by 솔라리스))를 사용해 해당 쓰레드는 sleep 상태에 들어간다.
