線程假喚醒的原因
http://en.wikipedia.org/wiki/Spurious_wakeup
Spurious wakeup
From Wikipedia, the free encyclopedia
This article has an unclear citation style. The references used may be made clearer with a different or consistent style of citation, footnoting, or external linking. (September 2009)
Spurious wakeup describes a complication in the use of condition variables as provided by certain multithreading APIs such as POSIX Threads and the Windows API.
Even after a condition variable appears to have been signaled from a waiting thread's point of view, the condition that was awaited may still be false. One of the reasons for this is a spurious wakeup; that is, a thread might be awoken from its waiting state even though no thread signaled the condition variable. For correctness it is necessary, then, to verify that the condition is indeed true after the thread has finished waiting. Because spurious wakeup can happen repeatedly, this is achieved by waiting inside a loop that terminates when the condition is true, for example:
/* In any waiting thread: */
while(!buf->full)
wait(&buf->cond, &buf->lock);
/* In any other thread: */
if(buf->n >= buf->size){
buf->full = 1;
signal(&buf->cond);
}
In this example it is known that another thread will set buf->full (the actual condition awaited) before signaling buf->cond (the means of synchronizing the two threads). The waiting thread will always verify the truth of the actual condition upon returning from wait, ensuring correct behaviour if spurious wakeup occurs.
According to David R. Butenhof's Programming with POSIX Threads ISBN 0-201-63392-2:
"This means that when you wait on a condition variable, the wait may (occasionally) return when no thread specifically broadcast or signaled that condition variable. Spurious wakeups may sound strange, but on some multiprocessor systems, making condition wakeup completely predictable might substantially slow all condition variable operations. The race conditions that cause spurious wakeups should be considered rare."
Other reasons for verifying the invariant[edit]
Practical reasons exist for checking the invariant after a return from a wait other than spurious wakeups. For example, a woken-up thread may not be scheduled immediately after the wake up, but be at the mercy of the system scheduler. A scheduler may preempt a process abruptly or schedule other threads. It may be the case that, in the meantime, an external entity (another process or hardware) has invalidated the invariant assumption. As with spurious wakeup, wrapping the wait with a loop avoids such cases.
External links
External links[edit]
online references
discussions
Interface without spurious wakeups
Volodya's blog - Spurious wakeups
Posix documentation for pthread_cond_wait, pthread_cond_timedwait functions
Categories:
C POSIX library
http://blog.csdn.net/nhn_devlab/article/details/6117239
對條件變量(condition variable)的討論
2011-01-05 10:06 2043人閱讀 評論(3) 收藏 舉報(bào)
semaphorethreadsignalvariableslinuxjavadoc
目錄(?)[+]
作者：王東
1.1 什么是條件變量和條件等待？
簡單的說：
條件變量(condition variable)是利用線程間共享的全局變量進(jìn)行同步的一種機(jī)制，主要包括兩個(gè)動(dòng)作：一個(gè)線程等待某個(gè)條件為真，而將自己掛起；另一個(gè)線程使的條件成立，并通知等待的線程繼續(xù)。為了防止競爭，條件變量的使用總是和一個(gè)互斥鎖結(jié)合在一起。
Wiki中的定義如下：
Conceptually a condition variable is a queue of threads, associated with a monitor, on which a thread may wait for some condition to become true. Thus each condition variable c is associated with an assertion P. While a thread is waiting on a condition variable, that thread is not considered to occupy the monitor, and so other threads may enter the monitor to change the monitor's state. In most types of monitors, these other threads may signal the condition variable c to indicate that assertion P is true in the current state[1].
條件變量(condition variable)是一種特殊的同步變量，它是與一個(gè)互斥量(monitor)關(guān)聯(lián)的線程隊(duì)列，條件變量都與一個(gè)斷言(assertion) P關(guān)聯(lián)，因?yàn)槠渲械木€程隊(duì)列中有一個(gè)線程在等待這個(gè)斷言P為真。當(dāng)一個(gè)線程處于等待條件變量(condition variable)時(shí)，該線程不再占用互斥量(monitor)，讓其他線程能夠進(jìn)入互斥區(qū)去改變條件狀態(tài)。
在條件變量上有兩種基本操作：
等待（wait）：一個(gè)線程因?yàn)榈却龜嘌?assertion) P為真而處于等待在條件變量上，此時(shí)線程不會占用互斥量(monitor);
通知（signal/notify）：另一個(gè)線程在使得斷言(assertion) P為真的時(shí)候，通知條件變量。
一個(gè)線程發(fā)生signal時(shí)，另一個(gè)線程被激活，那么兩個(gè)線程都占用的互斥量(monitor), 選擇哪個(gè)線程來占用互斥，這就分為了Blocking condition variables（把優(yōu)先級給被通知的線程）和Nonblocking condition variables（把優(yōu)先級給發(fā)出signal通知的線程[1]。
使用條件等待有如下的場景：
多線程訪問一個(gè)互斥區(qū)域內(nèi)的資源，如果獲取資源的條件不夠時(shí)，則線程需要等待，直到其他線程釋放資源后，喚醒等待條件，使得線程得以繼續(xù)。例如：
Thread1：
Lock (mutex)
while (condition is false) {
//為什么要在這里用while而不是if呢?
//參考1.2.1條件變量存在的問題
Cond_wait(cond, mutex, timeout)
}
DoSomething()
Unlock (mutex)
Thread2:
Lock (mutex)
…
condition is true
Cond_signal(cond)
Unlock (mutex)
例如 Thread1從一個(gè)大小為50的鏈接池中獲取一個(gè)鏈接，如果已經(jīng)用的鏈接達(dá)到50時(shí)，那該線程必須等待一個(gè)條件。Thread2 用完一個(gè)鏈接時(shí)，將該鏈接還給鏈接池，然后發(fā)送條件notify，告訴Thread1 可以繼續(xù)了。.
1.1.1 關(guān)于條件變量(condition variable)和信號量（Semaphore）
信號量（Semaphore）是一個(gè)非負(fù)的整數(shù)計(jì)數(shù)器，被用于進(jìn)程或線程間的同步與互斥。
通過信號量可以實(shí)現(xiàn) “PV操作”這種進(jìn)程或線程間的同步機(jī)制。
P操作是獲得資源，將信號量的值減1，如果結(jié)果不為負(fù)則繼續(xù)執(zhí)行，線程獲得資源，否則線程被阻塞，處于睡眠狀態(tài)，直到等待的資源被別的線程釋放；
V操作則是釋放資源，給信號量的值加1，釋放一個(gè)因執(zhí)行P操作而等待的線程。
最簡單的信號燈形式，信號燈的值只能取0或1，類似于mutex。
當(dāng)信號量的值為任意非負(fù)值（大于1），其值就代表可用資源的個(gè)數(shù)。
可以將信號量Semaphore和互斥鎖(mutex)來實(shí)現(xiàn)一個(gè)來實(shí)現(xiàn)對一個(gè)池的同步和保護(hù)。使用mutex來實(shí)現(xiàn)同步，使用semaphore用于實(shí)現(xiàn)對資源記數(shù)。
獲得資源的線程：
sem_wait (semaphore1)
Lock (mutex)
…
Unlock (mutex)
sem_post (semaphore2)
釋放資源的線程:
sem_wait (semaphore2)
Lock (mutex)
…
Unlock (mutex)
sem_post (semaphore1)
這個(gè)模型很像多線程的生產(chǎn)者與消費(fèi)者模型，這里的semaphore2是為了防止過度釋放。
比起信號量來說，條件變量可以實(shí)現(xiàn)更為復(fù)雜的等待條件。當(dāng)然，條件變量和互斥鎖也可以實(shí)現(xiàn)信號量的功能（window下的條件變量只能實(shí)現(xiàn)線程同步不能實(shí)現(xiàn)進(jìn)程同步）。
在Posix.1基本原理一文聲稱，有了互斥鎖和條件變量還提供信號量的原因是：“本標(biāo)準(zhǔn)提供信號量的而主要目的是提供一種進(jìn)程間同步的方式；這些進(jìn)程可能共享也可能不共享內(nèi)存區(qū)。互斥鎖和條件變量是作為線程間的同步機(jī)制說明的；這些線程總是共享(某個(gè))內(nèi)存區(qū)。這兩者都是已廣泛使用了多年的同步方式。每組原語都特別適合于特定的問題”。盡管信號量的意圖在于進(jìn)程間同步，互斥鎖和條件變量的意圖在于線程間同步，但是信號量也可用于線程間，互斥鎖和條件變量也可用于進(jìn)程間。應(yīng)當(dāng)根據(jù)實(shí)際的情況進(jìn)行決定。信號量最有用的場景是用以指明可用資源的數(shù)量[11]。
個(gè)人的感覺是：由于起源不同，導(dǎo)致了兩種理念，一中理念力挺條件變量(condition variable)，覺得信號量沒有什么用（例如POSIX Thread模型中沒有信號量的概念，雖然也提出了Posix Semaphore，但是為什么一開始不把它放在一起呢？）；另一理念恰好相反（例如window剛開始沒有條件變量的概念，只有信號量的概念）。
進(jìn)化到后來，目前的linux和window都同時(shí)具備了這二者。
1.2 Linux中的條件等待函數(shù)是那些？
Linux提供了的條件等待函數(shù)和notify函數(shù)。
pthread_cond_timedwait(cond, mutex, abstime);
pthread_cond_wait(cond, mutex);
pthread_cond_signal(cond); 將至少解鎖一個(gè)線程（阻塞在條件變量上的線程）。
pthread_cond_broadcast(cond) : 將對所有阻塞在條件變量上的線程解鎖。
線程1調(diào)用pthread_cond_wait() 所做的事 三個(gè)部分：
1. 同時(shí)對mutex解鎖，
2. 并等待條件 cond 發(fā)生
3. 獲得通知后，對mutex加鎖；
調(diào)用pthread_cond_wait()后，同時(shí)對mutex解鎖，并等待條件 cond 發(fā)生（要求解鎖并阻塞是一個(gè)原子操作）
現(xiàn)在互斥對象已被解鎖，其它線程可以進(jìn)入互斥區(qū)域,修改條件。
此時(shí)，pthread_cond_wait() 調(diào)用還未返回。等待條件 mycond是一個(gè)阻塞操作，這意味著線程將睡眠，在它蘇醒之前不會消耗 CPU 周期。直到特定條件發(fā)生[3]。
假設(shè)另一個(gè)線程2對mutex加鎖, 并改變條件, 然后調(diào)用函數(shù) pthread_cond_signal() 激活等待條件。這意味著線程1現(xiàn)在將蘇醒。此時(shí)線程1試圖對mutex加鎖，由于線程2還沒有對mutex解鎖，所以線程1只有等待，只有在線程2對mutex解鎖后，線程1優(yōu)先獲得mutex加鎖，然后就能做想做的事情了。
這里是存在問題的：如何讓線程1優(yōu)先獲得mutex加鎖，而不是其他線程，pthread_mutex_lock 的偽代碼[4]中展示了這種實(shí)現(xiàn)的可能性，signal函數(shù)中優(yōu)先激活了wait中的線程。
pthread_cond_wait(mutex, cond):
value = cond->value;
pthread_mutex_unlock(mutex);
pthread_mutex_lock(cond->mutex);
if (value == cond->value) {
me->next_cond = cond->waiter;
cond->waiter = me;
pthread_mutex_unlock(cond->mutex);
unable_to_run(me);
} else
pthread_mutex_unlock(cond->mutex);
pthread_mutex_lock(mutex);
pthread_cond_signal(cond):
pthread_mutex_lock(cond->mutex);
cond->value++;
if (cond->waiter) {
sleeper = cond->waiter;
cond->waiter = sleeper->next_cond;
able_to_run(sleeper);
}
pthread_mutex_unlock(cond->mutex);
下面的例子展示了使用條件變量的示例代碼[2]：
其中一個(gè)或多個(gè)線程負(fù)責(zé)count數(shù)增加（inc_count），另一個(gè)線程負(fù)責(zé)監(jiān)聽count數(shù)，一旦達(dá)到COUNT_LIMIT，就報(bào)告（watch_count）。
void inc_count (void) {
…
pthread_mutex_lock(&count_mutex);
count++;
if (count == COUNT_LIMIT) {
pthread_cond_signal(&count_threshold_cv);
printf("inc_count(): thread %ld, count = %d Threshold reached./n",
my_id, count);
}
printf("inc_count(): thread %ld, count = %d, unlocking mutex/n",
my_id, count);
pthread_mutex_unlock(&count_mutex);
…
}
void watch_count (void) {
…
pthread_mutex_lock(&count_mutex);
while (count<COUNT_LIMIT) {
pthread_cond_wait(&count_threshold_cv, &count_mutex);
printf("watch_count(): thread %ld Condition signal received./n", my_id);
count += 125;
printf("watch_count(): thread %ld count now = %d./n", my_id, count);
}
pthread_mutex_unlock(&count_mutex);
…
}
1.2.1 條件變量中存在的問題：虛假喚醒
Linux中幫助中提到的：
在多核處理器下，pthread_cond_signal可能會激活多于一個(gè)線程（阻塞在條件變量上的線程）。 On a multi-processor, it may be impossible for an implementation of pthread_cond_signal() to avoid the unblocking of more than one thread blocked on a condition variable.
結(jié)果是，當(dāng)一個(gè)線程調(diào)用pthread_cond_signal()后，多個(gè)調(diào)用pthread_cond_wait()或pthread_cond_timedwait()的線程返回。這種效應(yīng)成為”虛假喚醒”(spurious wakeup) [4]
The effect is that more than one thread can return from its call to pthread_cond_wait() or pthread_cond_timedwait() as a result of one call to pthread_cond_signal(). This effect is called "spurious wakeup". Note that the situation is self-correcting in that the number of threads that are so awakened is finite; for example, the next thread to call pthread_cond_wait() after the sequence of events above blocks.
雖然虛假喚醒在pthread_cond_wait函數(shù)中可以解決，為了發(fā)生概率很低的情況而降低邊緣條件（fringe condition）效率是不值得的，糾正這個(gè)問題會降低對所有基于它的所有更高級的同步操作的并發(fā)度。所以pthread_cond_wait的實(shí)現(xiàn)上沒有去解決它。
While this problem could be resolved, the loss of efficiency for a fringe condition that occurs only rarely is unacceptable, especially given that one has to check the predicate associated with a condition variable anyway. Correcting this problem would unnecessarily reduce the degree of concurrency in this basic building block for all higher-level synchronization operations.
所以通常的標(biāo)準(zhǔn)解決辦法是這樣的：
將條件的判斷從if 改為while
pthread_cond_wait中的while()不僅僅在等待條件變量前檢查條件變量，實(shí)際上在等待條件變量后也檢查條件變量。
這樣對condition進(jìn)行多做一次判斷，即可避免“虛假喚醒”.
這就是為什么在pthread_cond_wait()前要加一個(gè)while循環(huán)來判斷條件是否為假的原因。
有意思的是這個(gè)問題也存在幾乎所有地方，包括: linux 條件等待的描述, POSIX Threads的描述, window API(condition variable), java等等。
在linux的幫助中對條件變量的描述是[4]：
添加while檢查的做法被認(rèn)為是增加了程序的健壯性，在IEEE Std 1003.1-2001中認(rèn)為spurious wakeup是允許的。
An added benefit of allowing spurious wakeups is that applications are forced to code a predicate-testing-loop around the condition wait. This also makes the application tolerate superfluous condition broadcasts or signals on the same condition variable that may be coded in some other part of the application. The resulting applications are thus more robust. Therefore, IEEE Std 1003.1-2001 explicitly documents that spurious wakeups may occur.
在POSIX Threads中[5]:
David R. Butenhof 認(rèn)為多核系統(tǒng)中 條件競爭（race condition [8]）導(dǎo)致了虛假喚醒的發(fā)生，并且認(rèn)為完全消除虛假喚醒本質(zhì)上會降低了條件變量的操作性能。
“…, but on some multiprocessor systems, making condition wakeup completely predictable might substantially slow all condition variable operations. The race conditions that cause spurious wakeups should be considered rare”
在window的條件變量中[6]:
MSDN幫助中描述為，spurious wakeups問題依然存在，條件需要重復(fù)check。
Condition variables are subject to spurious wakeups (those not associated with an explicit wake) and stolen wakeups (another thread manages to run before the woken thread). Therefore, you should recheck a predicate (typically in a while loop) after a sleep operation returns.
在Java中 [7]，對等待的寫法如下：
synchronized (obj) {
while (<condition does not hold>)
obj.wait();
... // Perform action appropriate to condition
}
Effective java 曾經(jīng)提到Item 50: Never invoke wait outside a loop.
顯然，虛假喚醒是個(gè)問題,但它也是在JLS的第三版的JDK5的修訂中才得以澄清。在JDK 5的Javadoc進(jìn)行更新
A thread can also wake up without being notified, interrupted, or timing out, a so-called spurious wakeup. While this will rarely occur in practice, applications must guard against it by testing for the condition that should have caused the thread to be awakened, and continuing to wait if the condition is not satisfied. In other words, waits should always occur in loops.
Apparently, the spurious wakeup is an issue (I doubt that it is a well known issue) that intermediate to expert developers know it can happen but it just has been clarified in JLS third edition which has been revised as part of JDK 5 development. The javadoc of wait method in JDK 5 has also been updated
1.3 Window 里面的條件等待函數(shù)是那些？
比較奇怪的是一直到vista和window2008以前，window居然沒有標(biāo)準(zhǔn)的條件變量的概念。
實(shí)現(xiàn)條件變量和條件等待.
Window 采用了一種組合方式的策略來實(shí)現(xiàn)條件等待。
1. 使用 mutex 來實(shí)現(xiàn)互斥鎖
2. 使用 SignalObjectAndWait實(shí)現(xiàn)條件等待；
3. 對autoreset類型的event 使用 PulseEvent實(shí)現(xiàn)signal 條件；
事實(shí)上，window是用 autoreset的event來實(shí)現(xiàn)條件的。
具體的：
Thread1:
WaitForSingleObject(hMutex);
If (condition is false){
SignalObjectAndWait(hMutex, hEvent);
WaitForSingleObject(hMutex);
}
Dosomething();
ReleaseMutex(hMutex);
Thead2:
WaitForSingleObject(hMutex);
PulseEvent (hEvent);
ReleaseMutex(hMutex);
SignalObjectAndWait做的工作和cond_wait不完全一樣。
SignalObjectAndWait只做2件事情：
1. 同時(shí)對mutex解鎖，
2. 并等待條件 cond 發(fā)生
獲得signal通知，直接就往下走了，而不是等待mutex，這一點(diǎn)與Pthread_cond_wait()不同。因此在使用SignalObjectAndWait 后，必須使用lock(mutex)來獲得mutex的鎖，防止兩個(gè)線程同時(shí)進(jìn)入mutex。
這里lock(mutex)是可能存在問題的，因?yàn)闊o法保證這里的lock(mutex)能優(yōu)先獲得進(jìn)入的權(quán)利。事實(shí)上如果在SignalObjectAndWait()和lock(mutex)(WaitForSingleObject)加sleep()， 就會導(dǎo)致其他線程先獲得mutex的lock。因此也應(yīng)該像linux中一樣，使用循環(huán)判斷。
Thread1:
WaitForSingleObject(hMutex);
while (condition is false){
SignalObjectAndWait(hMutex, hEvent);
WaitForSingleObject(hMutex);
}
Dosomething();
ReleaseMutex(hMutex);
1.3.1 PulseEvent在條件等待中存在的問題，如何解決？
實(shí)際上PulseEvent 是不可信賴的，因?yàn)楫?dāng)一個(gè)線程處于等待狀態(tài)時(shí)，會一些瞬間其狀態(tài)并不是等待狀態(tài)，這就導(dǎo)致了PulseEvent()不能激活這些線程。
例如：核心模式的APC調(diào)用，會導(dǎo)致等待的線程瞬間不處于等待狀態(tài)。
A thread waiting on a synchronization object can be momentarily removed from the wait state by a kernel-mode APC, and then returned to the wait state after the APC is complete. If the call to PulseEvent occurs during the time when the thread has been removed from the wait state, the thread will not be released because PulseEvent releases only those threads that are waiting at the moment it is called. Therefore, PulseEvent is unreliable and should not be used by new applications. Instead, use condition variables.
當(dāng)然可以用SetEvent ()來代替PulseEvent()，那將會喚醒所以等待的線程。這樣的喚醒更像是notifyAll,而不是notify.
標(biāo)準(zhǔn)的解決辦法是使用window中condition variables[9].
1.3.2 Window下標(biāo)準(zhǔn)做法
condition variables是微軟從vista和2008以后引入的技術(shù)，xp和2003的系統(tǒng)不支持。
condition variables和臨界區(qū)一樣，是用戶態(tài)調(diào)用，不是系統(tǒng)調(diào)用（意味著是高效的），只支持同一個(gè)進(jìn)程內(nèi)的多線程。
WakeConditionVariable 喚醒一個(gè)等待條件變量的線程
WakeAllConditionVariable 喚醒所有等待條件變量的線程；
SleepConditionVariableCS 釋放臨界區(qū)鎖和等待條件變量作為原子性操作
SleepConditionVariableSRW 釋放SRW鎖和等待條件變量作為原子性操作.
這樣，在window下使用條件變量的方法如下所示：
Thread1：
EnterCriticalSection(&CritSection);
while( TestPredicate() == FALSE ){
SleepConditionVariableCS(&ConditionVar, &CritSection, INFINITE);
}
DoSth();
LeaveCriticalSection(&CritSection);
Thread2：
EnterCriticalSection(&CritSection);
WakeConditionVariable (ConditionVar);
LeaveCriticalSection(&CritSection);
同樣的spurious wakeups問題依然存在，條件需要重復(fù)check。
1.3.3 Window下的其他方法？
Window下面使用condition variable固然好，但是對于不能使用condition variable的xp和2003怎么辦呢。
有兩個(gè)辦法：
1 使用pthread porting到window中的pthread win32方法。使用pthread在window中的運(yùn)行庫。具體可參考：
http://sourceware.org/pthreads-win32/
2 自己寫一個(gè)，或者利用他人寫好的條件變量
可參考：
a) A Fair Monitor (Condition Variables) Implementation for Win32
http://thbecker.net/free_software_utilities/fair_monitor_for_win32/start_page.html
b) Windows下條件變量的實(shí)現(xiàn)
http://blog.csdn.net/leafarmy/archive/2009/03/31/4039548.aspx
1.4 參考：
1．Monitor (synchronization) Condition variable
http://en.wikipedia.org/wiki/Condition_variable
2 POSIX Threads Programming
https://computing.llnl.gov/tutorials/pthreads/#ConditionVariables
3 pthread_cond_wait()太難理解了
http://hi.baidu.com/nkhzj/blog/item/f5480d4f740f7f35aec3ab4b.html
4 pthread_cond_signal(3) - Linux man page
http://linux.die.net/man/3/pthread_cond_signal
5 POSIX Threads-Spurious wakeup
http://en.wikipedia.org/wiki/Spurious_wakeup
6 Condition Variables
http://msdn.microsoft.com/en-us/library/ms682052(v=VS.85).aspx
7 java-的spurious wakeup問題
http://www.devguli.com/blog/eng/spurious-wakeup/
8 Race condition
http://en.wikipedia.org/wiki/Race_condition
9 PulseEvent
http://msdn.microsoft.com/en-us/library/ms684914(VS.85).aspx
10 windows - Condition Variables
http://msdn.microsoft.com/en-us/library/ms682052(v=VS.85).aspx
11 進(jìn)程間的通信（互斥鎖、條件變量、讀寫鎖、文件鎖、信號燈）
http://blog.csdn.net/ccskyer/archive/2010/12/24/6096710.aspx
12 pthread_cond_wait的spurious wakeup問題
http://blog.chinaunix.net/u/12592/showart_2213910.html
