多核編程中的條件同步模式
在多線程編程中，當對共享資源進行操作時，需要使用同步（通常是鎖或原子操作）來進行保護，以避免數據競爭問題。不幸的是，同步操作的開銷非常大，比如對一個整數變量進行加法操作，那么同步操作的開銷是加法操作的上百倍以上。
有沒有辦法可以減少這種同步操作的開銷呢？如果能設計出更快的鎖或更快的原子操作來，那么這種開銷自然就減少了。以目前的技術來看，最快速的原子操作耗時也是普通加法操作的上百倍，所以從這方面著手是非常困難的。
那么能不能從軟件算法的角度來減少同步操作的開銷呢？答案是當然可以，基本思想是減少使用同步的次數，比如原來要使用同步1000次，現在改為在滿足一定條件下才使用同步，只需要10次，那么同步的開銷平攤下來就被減少了100倍，效率大大提高了。下面先來看一個共享隊列例子。
一個普通的共享隊列通常都是使用鎖來實現，當然也有用CAS原子操作來實現的，這里只討論用鎖來實現的共享隊列。
在有鎖保護的共享隊列中，在隊列的進隊和出隊操作時，通常都是使用鎖來進行保護的，一個典型的使用鎖保護的出隊操作偽代碼如下：
- template class <T>
- Locked_DeQueue(T &data)
- {
- Lock();
- DeQueue(data); //調用串行的出隊操作
- Unlock();
- }
在使用上面的Locked_DeQueue()函數時，每調用一次，就會發生一次鎖操作。事實上，并不是每次都需要加鎖操作的，比如隊列為空時，這時實際上是不需要進行出隊操作的，完全可以采取的一定的方法避免鎖操作，但是采用上面的Locked_DeQueue()函數無法避免鎖操作，這就需要對上面的函數進行改進。
一種最容易想到的方面就是先判斷隊列是否為空，如果不為空才使用鎖保護進行出隊操作。代碼如下：
- template class <T>
- Locked_DeQueue_a(T &data)
- {
- If ( !IsEmpty() )
- {
- Lock();
- DeQueue(data); //調用串行的出隊操作
- Unlock();
- }
- }
上面的Locked_DeQueue_a()函數的一個關鍵之處是IsEmpty()函數必須不能使用鎖操作，否則不僅沒有減少同步開銷，反而將同步開銷增大了近一倍。
如何來使得IsEmtpy()函數不用鎖操作呢，以數組實現的環行隊列為例，在判斷隊列是否為空時，其基本方法是判斷隊首指針是否等于隊尾指針。偽代碼如下：
- INT IsEmpty()
- {
- Lock()
- if ( 隊首指針 == 隊尾指針 )
- {
- Unlock();
- return 1; //為空
- }
- else
- {
- Unlock();
- return 0; //非空
- }
- }
由于隊首指針和隊尾指針在進隊或出隊操作時會發生改變，因此在上面的IsEmpty()函數中，需要使用鎖保護，那么如何去掉這層鎖保護呢？
基本的方法是設一個標志變量EmptyFlag，在進隊和出隊操作中，當隊列為空時，標志變量的值置為1，隊列非空時，標志變量的值置為0。這樣判斷隊列是否為空就可以通過EmptyFlag單個變量來進行，而單個變量的讀寫可以使用原子操作來實現，使得讀操作和普通操作一樣不存在同步操作。
下面是使用EmptyFlag變量實現的出隊操作。
- template class <T>
- Locked_DeQueue_b(T &data)
- {
- if ( EmptyFlag )
- {
- return;
- }
- Lock();
- if ( !EmptyFlag ) //Lock()前, 其他線程可能修改了標志
- {
- DeQueue(data); //調用串行的出隊操作
- if ( 隊首指針 == 隊尾指針 )
- {
- //出隊后，隊列變空，使用原子操作將EmptyFlag置為1
- AtomicIncrement(&EmptyFlag);
- }
- }
- Unlock();
- }
隊列的是否為空函數可以使用下面的完全不需要同步的實現。
- INT IsEmpty()
- {
- return EmptyFlag;
- }
從Locked_DeQueue_b()函數的實現可以看出，如果隊列本來為空的情況下，它只判斷一個EmptyFlag就返回了，不會調用鎖操作，減少了同步使用的次數，并且在IsEmpty()函數中，根本不需要使用同步，這對于那些需要頻繁判斷隊列是否為空的使用場景，有很好的效果。
比 如對于動態任務調度，假設使用普通的有鎖的共享隊列。當一個線程私有隊列為空時，需要去偷取其他線程的共享隊列中的任務，如果偷取的隊列為空則發生了一次 鎖操作，此時需要再偷另外一個隊列的任務，如果這個隊列仍然為空則又要一次鎖操作，一次獲取任務的操作中將可能出現多次加鎖解鎖的情況。通過上面講的條件 同步方法就可以在偷取取一個任務時，只要一次鎖操作就可以實現。
上面講的條件同步模式非常適應于具有狀態機性質的場合，只有在發生狀態切換（例如隊列中空或非空的狀態的切換）時才使用同步，通過對狀態變量（例如EmptyFlag）的操作來替代其他非狀態變量(例如隊首指針和隊尾指針)的操作，減少同步的使用。
原文鏈接：http://blog.csdn.net/drzhouweiming/article/details/4006899
