reference: https://pages.cs.wisc.edu/~remzi/OSTEP/
"오직 하나의 쓰레드만을 임계 구역에 허용한다."
=> 원자성 보장
1) 임계영역을 파악한다.
2) mutex 구조체 또는 클래스 객체(락 변수, lock)를 선언하고, 이를 초기화 한다(pthread_mutex_init(&lock)).
3) 쓰레드의 임계영역 전 객체(락 변수)를 인자로 전달하여 락을 건다(pthread_mutex_lock(&lock)).
4) 임계영역의 처리를 마친 후 락을 푼다(pthread_mutex_unlock(&lock)).
"하나의 쓰레드는 다른 쓰레드가 작업을 끝낼 때까지 기다려야 한다."
=> 순서 관계 보장, 쓰레드1 -> 쓰레드2
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)
balance = balance + 1;
변수뿐 아니라 공유 자료구조를 업데이트 하는 것도 임계영역 존재 ex) 연결리스트에 노드를 더하는 작업 등
lock/unlock을 임계영역 전후에 적절히 사용
=> collaboration between HW and OS
1) correctness(정확도): does is gurantee mutual exclusion??
2) fairness(형평성): does any thread strave?
3) performance(성능): overhead added by using lock
1. Coarse-grained lock
2. Fine-grained lock
1. Disable interrupt
스케줄링은 보통 타이머 장치 인터럽트에 의해 발생한다. 따라서 이 인터럽트를 disable하는 방식으로 쓰레드 수행의 원자성을 보장할 수 있다.
원리: No 인터럽트 -> No 문맥교환 -> No 임계구역 내 간섭
pros(+)
cons(-)
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(+)
cons(-)
=> 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++