241
並行編程之條件變量（posix condition variables）
在整理Java LockSupport.park()的東東，看到了個"Spurious wakeup"，重新梳理下。
首先來個《UNIX環境高級編程》裏的例子：
#include <pthread.h>
struct msg {
struct msg *m_next;
/* ... more stuff here ... */
};
struct msg *workq;
pthread_cond_t qready = PTHREAD_COND_INITIALIZER;
pthread_mutex_t qlock = PTHREAD_MUTEX_INITIALIZER;
void process_msg(void) {
struct msg *mp;
for (;;) {
pthread_mutex_lock(&qlock);
while (workq == NULL)
pthread_cond_wait(&qready, &qlock);
mp = workq;
workq = mp->m_next;
pthread_mutex_unlock(&qlock);
/* now process the message mp */
}
}
void enqueue_msg(struct msg *mp) {
pthread_mutex_lock(&qlock);
mp->m_next = workq;
workq = mp;
pthread_mutex_unlock(&qlock);
pthread_cond_signal(&qready);
}
一個簡單的消息生產者和消費者的代碼。它們之間用condition同步。
這個代碼最容易讓人搞混的是process_msg函數裏的pthread_mutex_lock 和 pthread_mutex_unlock 是一對函數調用，前麵加鎖，後麵解鎖。的確，是加鎖解鎖，但是它們兩不是一對的。它們的另一半在pthread_cond_wait函數裏。
pthread_cond_wait函數可以認為它做了三件事：
- 把自身線程放到condition的等待隊列裏，把mutex解鎖；
- 等待被喚醒（當其它線程調用pthread_cond_signal或者pthread_cond_broadcast時）；
- 被喚醒之後，對metex加鎖，再返回。
mutex和condition實際上是綁定在一起的，一個condition隻能對應一個mutex。在Java的代碼裏，Condition對象隻能通過lock.newCondition()的函數來獲取。
Spurious wakeup
所謂的spurious wakeup，指的是一個線程調用pthread_cond_signal()，卻有可能不止一個線程被喚醒。為什麼會出現這種情況？wiki和其它的一些文檔都隻是說在多核的情況下，簡化實現允許出現這種spurious wakeup。。
在man文檔裏給出了一個可能的實現，然後解析為什麼會出現。
假定有三個線程，線程A正在執行pthread_cond_wait，線程B正在執行pthread_cond_signal，線程C正準備執行pthread_cond_wait函數。
pthread_cond_wait(mutex, cond):
value = cond->value; /* 1 */
pthread_mutex_unlock(mutex); /* 2 */
pthread_mutex_lock(cond->mutex); /* 10 */
if (value == cond->value) { /* 11 */
me->next_cond = cond->waiter;
cond->waiter = me;
pthread_mutex_unlock(cond->mutex);
unable_to_run(me);
} else
pthread_mutex_unlock(cond->mutex); /* 12 */
pthread_mutex_lock(mutex); /* 13 */
pthread_cond_signal(cond):
pthread_mutex_lock(cond->mutex); /* 3 */
cond->value++; /* 4 */
if (cond->waiter) { /* 5 */
sleeper = cond->waiter; /* 6 */
cond->waiter = sleeper->next_cond; /* 7 */
able_to_run(sleeper); /* 8 */
}
pthread_mutex_unlock(cond->mutex); /* 9 */
線程A執行了第1,2步，這時它釋放了mutex，然後線程B拿到了這個mutext，並且pthread_cond_signal函數時執行並返回了。於是線程B就是一個所謂的“spurious wakeup”。
為什麼pthread_cond_wait函數裏一進入，就釋放了mutex？沒有找到什麼解析。。
查看了glibc的源代碼，大概可以看出上麵的一些影子，但是太複雜了，也沒有搞明白為什麼。。
/build/buildd/eglibc-2.19/nptl/pthread_cond_wait.c
/build/buildd/eglibc-2.19/nptl/pthread_cond_signal.c
不過從上麵的解析，可以發現《UNIX高級編程》裏的說明是錯誤的（可能是因為太久了）。
The caller passes it locked to the function, which then atomically places the calling thread on the list of threads waiting for the condition and unlocks the mutex.
上麵的偽代碼，一進入pthread_cond_wait函數就釋放了mutex，明顯和書裏的不一樣。
wait morphing優化
在《UNIX環境高級編程》的示例代碼裏，是先調用pthread_mutex_unlock，再調用pthread_cond_signal。
void enqueue_msg(struct msg *mp) {
pthread_mutex_lock(&qlock);
mp->m_next = workq;
workq = mp;
pthread_mutex_unlock(&qlock);
pthread_cond_signal(&qready);
}有的地方給出的是先調用pthread_cond_signal，再調用pthread_mutex_unlock：
void enqueue_msg(struct msg *mp) {
pthread_mutex_lock(&qlock);
mp->m_next = workq;
workq = mp;
pthread_cond_signal(&qready);
pthread_mutex_unlock(&qlock);
}先unlock再signal，這有個好處，就是調用enqueue_msg的線程可以再次參與mutex的競爭中，這樣意味著可以連續放入多個消息，這個可能會提高效率。類似Java裏ReentrantLock的非公平模式。
網上有些文章說，先singal再unlock，有可能會出現一種情況是被singal喚醒的線程會因為不能馬上拿到mutex（還沒被釋放），從而會再次休眠，這樣影響了效率。從而會有一個叫“wait morphing”優化，就是如果線程被喚醒但是不能獲取到mutex,則線程被轉移(morphing)到mutex的等待隊列裏。
但是我查看了下glibc的源代碼，貌似沒有發現有這種“wait morphing”優化。
man文檔裏提到：
The pthread_cond_broadcast() or pthread_cond_signal() functions may be called by a thread whether or not it currently owns the mutex that threads calling pthread_cond_wait() or pthread_cond_timedwait() have associated with the condition variable during their waits; however, if predictable scheduling behavior is required, then that mutex shall be locked by the thread calling pthread_cond_broadcast() or pthread_cond_signal().
可見在調用singal之前，可以不持有mutex，除非是“predictable scheduling”，可預測的調度行為。這種可能是實時係統才有這種嚴格的要求。
為什麼要用while循環來判斷條件是否成立？
while (workq == NULL) pthread_cond_wait(&qready, &qlock);
而不用if來判斷？
if (workq == NULL) pthread_cond_wait(&qready, &qlock);
一個原因是spurious wakeup，但即使沒有spurious wakeup，也是要用While來判斷的。
比如線程A，線程B在pthread_cond_wait函數中等待，然後線程C把消息放到隊列裏，再調用pthread_cond_broadcast，然後線程A先獲取到mutex，處理完消息完後，這時workq就變成NULL了。這時線程B才獲取到mutex，那麼這時實際上是沒有資源供線程B使用的。所以從pthread_cond_wait函數返回之後，還是要判斷條件是否成功，如果成立，再進行處理。
pthread_cond_signal和pthread_cond_broadcast
在這篇文章裏，https://www.cppblog.com/Solstice/archive/2013/09/09/203094.html
給出的示例代碼7裏，認為調用pthread_cond_broadcast來喚醒所有的線程是比較好的寫法。但是我認為pthread_cond_signal和pthread_cond_broadcast是兩個不同東東，不能簡單合並在同一個函數調用。隻喚醒一個效率和喚醒全部等待線程的效率顯然不能等同。典型的condition是用CLH或者MCS來實現的，要通知所有的線程，則要曆遍鏈表，顯然效率降低。另外，C++11裏的condition_variable也提供了notify_one函數。
https://en.cppreference.com/w/cpp/thread/condition_variable/notify_one
mutex，condition是不是公平(fair)的？
這個在參考文檔裏沒有說明，在網上找了些資料，也沒有什麼明確的答案。
我寫了個代碼測試，發現mutex是公平的。condition的測試結果也是差不多。
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
volatile int mutexCount = 0;
void mutexFairTest(){
int localCount = 0;
while(1){
pthread_mutex_lock(&lock);
__sync_fetch_and_add(&mutexCount, 1);
localCount += 1;
if(mutexCount > 100000000){
break;
}
pthread_mutex_unlock(&lock);
}
pthread_mutex_unlock(&lock);
printf("localCount:%d\n", localCount);
}
int main() {
pthread_mutex_lock(&lock);
pthread_create(new pthread_t, NULL, (void * (*)(void *))&mutexFairTest, NULL);
pthread_create(new pthread_t, NULL, (void * (*)(void *))&mutexFairTest, NULL);
pthread_create(new pthread_t, NULL, (void * (*)(void *))&mutexFairTest, NULL);
pthread_create(new pthread_t, NULL, (void * (*)(void *))&mutexFairTest, NULL);
pthread_create(new pthread_t, NULL, (void * (*)(void *))&mutexFairTest, NULL);
pthread_create(new pthread_t, NULL, (void * (*)(void *))&mutexFairTest, NULL);
pthread_mutex_unlock(&lock);
sleep(100);
}輸出結果是：
localCount:16930422 localCount:16525616 localCount:16850294 localCount:16129844 localCount:17329693 localCount:16234137
還特意在一個單CPU的虛擬機上測試了下。輸出的結果差不多。操作係統是ububtu14.04。
連續調用pthread_cond_signal，會喚醒多少次/多少個線程？
比如線程a,b 在調用pthread_cond_wait之後等待，然後線程c, d同時調用pthread_cond_signal，那麼a, b線程是否都能被喚醒？
會不會出現c, d, a 這種調用順序，然後b一直在等待，然後死鎖了？
根據文檔：
The pthread_cond_signal() function shall unblock at least one of the threads that are blocked on the specified condition variable cond (if any threads are blocked on cond).
因此，如果有線程已經在調用pthread_cond_wait等待的情況下，pthread_cond_signal調用至少會喚醒等待中的一個線程。
所以不會出現上麵的線程b一直等待的情況。
但是，我們再仔細考慮下：
如何確認線程a, b 調用pthread_cond_wait完成了？還是隻是剛切換到內核態？顯然是沒有辦法知道的。
所以，我們平時編程肯定不會寫這樣的代碼，應該是共享變量，在獲取到鎖之後，再修改變量。這樣子來做同步。參考上麵《UNIX環境高級編程》的例子。
不過，這個問題也是挺有意思的。
參考：
https://en.wikipedia.org/wiki/Spurious_wakeup
https://siwind.iteye.com/blog/1469216
https://www.cppblog.com/Solstice/archive/2013/09/09/203094.html
https://www.cs.cmu.edu/afs/cs/academic/class/15492-f07/www/pthreads.html
最後更新：2017-04-03 08:26:21