<style>
H2{color:#BF0060 !important;}
H3{color:#009393 !important;}
p{color:Black !important;}
li strong {color:#4682b4 !important;}
</style>

# Thread Lock
## **Spin lock**
### **implement**
* **Test-and-Set**
* `while (TestAndSet(&lock->flag, 1) == 1) : 恆設為1，old為1時spin`
* **Compare-and-Swap**
* `while (CompareAndSwap(&lock->flag, exp=0, 1) == 1) : 為0時設成1，old為1時spin`
* **Fetch-and-Add**
* 和 Compare-and-Swap 不同，可以 ensure progress
* void lock(lock_t *lock) {
`int myturn = FetchAndAdd(&lock->ticket}`
`while (lock->turn != myturn);`
}
* void unlock(lock_t *lock) {
`lock->turn = lock->turn + 1;`
}

### **Avoid spining**
* **Yield**
* `while (TestAndSet(&flag, 1) == 1) yield()`
* `defect : too many context switches`
* **Queue and sleeping**
* `implement`
* <img src="https://i.imgur.com/nMrVZJ0.png" width = "200"/></img>
* Queue : keep track of the threads waiting，guard 用來保護 flag(鎖) 和 queue
* park() : put a calling thread to sleep (blocked state)
* unpark(threadID) : wake it up.
* `Lock`
* <img src="https://i.imgur.com/ivdtmgq.png" width = "500"/></img>
* `Unlock`
* <img src="https://i.imgur.com/pzs6z6H.png" width = "500"/></img>
* `Wakeup/Waiting Race`
* <img src="https://i.imgur.com/DkKY9kw.png" width = "500"/></img>
* `Resolving Wakeup/Waiting Race`
* Calling ==setpark()== before park()
* If another thread calls unpark(), the subsequent park() returns immediately (instead of sleeping)
* <img src="https://i.imgur.com/q6n24Ed.png" width = "300"/></img>
* **OS support in Linux**
* `System call: futex_wait(address, expected)`
* If (*addr == expected) : the thread sleeps.
* Else : return immediately
* `System call: futex_wake(address)`
* 從 queue 叫醒一個
* `lock`
* <img src="https://i.imgur.com/ZpCVfCd.png" width = "500"/></img>

* `unlock`
* <img src="https://i.imgur.com/kfEA3Vd.png" width = "390"/></img>
## **Lock usage in POSIX**
### **Mutex 範例**
* <img src="https://i.imgur.com/6q69Ura.png" width = "390"/></img>
* `Calling non-reentrant function 也可以用 mutex 包起來`
* Pthread_mutex_lock(&mutex);
str = malloc(...)
Pthread_mutex_unlock(&mutex);
### **Condition varable**
* **pthread_cond_wait**`(pthread_cond_t *cond,pthread_mutex_t *mutex)`
* Need Atomic lock :
* put the thread to sleep (blocked) and releases the lock (mutex)
* then wait for signaled
* <img src="https://i.imgur.com/bvqExJf.png" width = "500"/></img>
* **pthread_cond_signal**`(pthread_cond_t *cond)`
* <img src="https://i.imgur.com/XRJiIMf.png" width = "500"/></img>
## **producer/consumer problem**
### **Ver 1 :single cond**
* `producer should not procees when count =1`
* <img src="https://i.imgur.com/bbcFcJJ.png" width = "400"/></img>
* <img src="https://i.imgur.com/jSIg44V.png" width = "330"/></img><img src="https://i.imgur.com/WRrUo5y.png" width = "330"/></img>
* **缺點**
* `Ｃ1 ready 但 C2 偷跑進來搶走`
* <img src="https://i.imgur.com/0S4rBEJ.png" width = "500"/></img>
### **Ver 2 : 改用 while**
* **cond 要配合 while**
* `把 if(count...) 改成 while(count...)`

* <img src="https://i.imgur.com/72hDipi.png" width = "500"/></img>
* **缺點**
* `P1 和 C1,C2 時，C1 signal 到 C2 而非 P1`

* <img src="https://i.imgur.com/9bkLJ4o.png" width = "500"/></img>
### **Ver 3 : C, P 有各自的 cond**
* `&cond 改成 &fill 和 &empty`
* <img src="https://i.imgur.com/w4qC4SQ.png" width = "300"/></img><img src="https://i.imgur.com/5XpizKL.png" width = "300"/></img>

###### tags: `OS`