可重復使用地并行數(shù)據(jù)結(jié)構(gòu)和算法

1、WORD格式9 種可重復使用的并行數(shù)據(jù)構(gòu)造和算法目錄倒計數(shù)鎖存(Countdown Latch)可重用旋轉(zhuǎn)等待(Spin Wait)屏障(Barrier)阻塞隊列受限緩沖區(qū)(Bounded Buffer)Thin 事件無鎖定LIFO堆棧循環(huán)分塊并行分拆總結(jié)本專欄并未涉及很多公共語言運行庫(CLR)功能的機制問題，而是更多介紹了如何有效使用您手頭所具有的工具。 身為一名程序員，必須做出很多決策， 而選擇正確的 數(shù)據(jù)構(gòu)造和算法 無疑是最常見的， 也是最重要的決策之一。錯誤的選擇可能導致程序無法運行，而大多數(shù)情況下， 那么決定了性能的好壞。 鑒于并行編程通常旨在改進性能，并且要難于串行編程，因此所作

2、的選擇對您程序的成功就更為重要。在本專欄中， 我們將介紹九種可重復使用的數(shù)據(jù)構(gòu)造和算法，這些構(gòu)造和算法是許多并行程序所常用的，您應該能夠輕松將它們應用到自己的.NET 軟件中。專欄中每個例如隨附的代碼都是可用的，但尚未經(jīng)過完全定型、測試和優(yōu)化。這里列舉的模式雖然并不詳盡，但卻代表了一些較為常見的模式。如您所見，很多例如都是互為補充的。在開場前，我想還是先介紹一些相關(guān)內(nèi)容。Microsoft" .NET Framework提供了幾個現(xiàn)有的并發(fā)基元。 雖然我要為您講解如何構(gòu)建自己的基元，但實際上現(xiàn)有基元是足以應付大多數(shù)情況的。 我只是想說某些可選的方案有時也是有參考價值的。此外，了解這些

3、技巧如何應用于實際操作也有助于加深您對并行編程的整體理解。在開場講解前， 我假定您對現(xiàn)有基元已經(jīng)有了一個根本的了解。您也可以參閱"MSDN"雜志" 2005年 8 月版的文章關(guān)于多線程應用程序：每個開發(fā)人員都應了解的內(nèi)容，以全面了解其概念。一、倒計數(shù)鎖存(Countdown Latch)專業(yè)資料整理WORD格式Semaphore 之所以成為并發(fā)編程中一種較為知名的數(shù)據(jù)構(gòu)造，只是因為它在計算機科學領(lǐng)域有著悠久的歷史可以追溯到19原因是多方面的， 而并不世紀 60 年代的操作系統(tǒng)設(shè)專業(yè)資料整理WORD格式計。Semaphore只是一種帶有一個計數(shù)字段的數(shù)據(jù)構(gòu)造，它只支

4、持兩種操作：放置和取走專業(yè)資料整理WORD格式通常分別稱為P 和V 。一次放置操作會增加一個semaphore計數(shù)，而一次取走操作專業(yè)資料整理WORD格式會減少一個 semaphore 計數(shù)。當 semaphore 計數(shù)為零時，除非執(zhí)行一項 并發(fā)的放置操作使計數(shù)變?yōu)榉橇阒?，否那么任何后續(xù)的取走嘗試都將阻塞等待。這兩種操作均為不可再分(atomic)操作，并發(fā)時不會產(chǎn)生錯誤，能夠確保并發(fā)的放置和取走操作有序地進展。Windows專業(yè)資料整理WORD格式具有根底內(nèi)核和對semaphore對象的Win32支持請參閱CreateSemaphore和相關(guān)API ，專業(yè)資料整理WORD格式并且在.NET

5、 Framework中這些對象可以通過System.Threading.Semaphore類公開到上專業(yè)資料整理WORD格式層。 Mutex和Monitor所支持的臨界區(qū)，通常被認為是一種特殊的semaphore，其計數(shù)會專業(yè)資料整理WORD格式在 0 和1 之間來回切換，換句話說，是一個二進制的semaphore。專業(yè)資料整理WORD格式另外還有一種反向semaphore也是非常有用。也就是說，有時您需要數(shù)據(jù)構(gòu)造能夠等待數(shù)據(jù)構(gòu)造計數(shù)歸零。Fork/join式并行模式在數(shù)據(jù)并行編程中是極為常見的，其中由單個主線程控制執(zhí)行假設(shè)干輔助 線程并等待線程執(zhí)行完畢。在這類情況下，使用反向semaphor

6、e 會很有幫助。大多數(shù)時候，您其實并不想喚醒線程來修改計數(shù)。因此在這種情況專業(yè)資料整理WORD格式下，我們將構(gòu)造稱為倒計數(shù)鎖存 ，用來表示計數(shù)的減少，同時還說明一旦設(shè)置為Signaled專業(yè)資料整理WORD格式狀態(tài)， 鎖存將保持signaled這是一個與鎖存相關(guān)的屬性。遺憾的是，Windows和.NET專業(yè)資料整理WORD格式Framework 均不支持這種數(shù)據(jù)構(gòu)造。但令人欣慰的是，構(gòu)建這種數(shù)據(jù)閉鎖并不難。專業(yè)資料整理WORD格式要構(gòu)建倒計數(shù)鎖存，只需將其計數(shù)器初始值設(shè)為n，并讓每項輔助任務在完成時不可再專業(yè)資料整理WORD格式分地將n 減掉一個計數(shù)，這可以通過為減量操作加上鎖或調(diào)用Inter

7、locked.Decrement來專業(yè)資料整理WORD格式實現(xiàn)。 接下來， 線程可以不執(zhí)行取走操作，而是減少計數(shù)并等待計數(shù)器歸零；而當線程被喚專業(yè)資料整理WORD格式醒時，它就可以得知已經(jīng)有n 個信號向鎖存注冊。在while (count != 0)循環(huán)中，讓等待的專業(yè)資料整理WORD格式線程阻塞通常是不錯的選擇這種情況下，您稍后將不得不使用事件，而不是使用旋轉(zhuǎn)。public class CountdownLatch private int m_remain;private EventWaitHandle m_event;public CountdownLatch(int count) m_r

8、emain = count;m_event = new ManualResetEvent(false);public void Signal()/ The last thread to signal also sets the event. if (Interlocked.Decrement(ref m_remain) = 0)m_event.Set();專業(yè)資料整理WORD格式public void Wait() m_event.WaitOne();這看上去極為簡單，但要正確運用還需要技巧。稍后我們將通過一些例如來講解如何使用這種數(shù)據(jù)構(gòu)造。請注意，此處所示根本實現(xiàn)還有很多可以改進地方，例如：

9、在事件上調(diào)用WaitOne 之前添加某種程度的旋轉(zhuǎn)等待、緩慢分配事件而不是在構(gòu)造器中進展分配以防足夠的旋轉(zhuǎn)會防止出現(xiàn)阻塞，如本專欄稍后介紹的ThinEvent演示的那樣、添加重置功能以及提供Dispose 方法以便在不再需要內(nèi)部事件對象時將對象關(guān)閉。二、可重用旋轉(zhuǎn)等待(Spin Wait)雖然忙碌等待(busy waiting)更容易實現(xiàn)阻塞，但在某些情況下，您也許確實想在退回到真正的等待狀態(tài)前先旋轉(zhuǎn)(spin) 一段時間。我們很難理解為何這樣做會有幫助，而大多數(shù)人之所以一開場就防止旋轉(zhuǎn)等待，是因為旋轉(zhuǎn)看上去像是在做無用功；如果上下文切換 每當線程等待內(nèi)核事件時都會發(fā)生需要幾千個周期在Wind

10、ows上確實是這樣，我們稱之為c，并且線程所等待的條件出現(xiàn)的時間少于2c 周期時間 1c 用于等待自身，1c 用于喚醒 ，那么旋轉(zhuǎn)可以降低等待所造成的系統(tǒng)開銷和滯后時間，從而提升算法的整體吞吐量和可伸縮性。如果您決定使用旋轉(zhuǎn)等待，就必須慎重行事。因為如果這樣做，您可能需要注意很多問題，比方：要確保在旋轉(zhuǎn)循環(huán)內(nèi)調(diào)用Thread.SpinWait ，以提高Intel 超線程技術(shù)的計算機上硬件對其他硬件線程的可用性；偶爾使用參數(shù)1 而非0 來調(diào)用Thread.Sleep，以防止優(yōu)先級反向問題；通過輕微的回退(back-off)來引入隨機選擇，從而改善訪問的局部性假定調(diào)用方持續(xù)重讀共享狀態(tài)并可能防止活

11、鎖；當然， 在單CPU 的計算機最好不要采用這種方法因為在這種環(huán)境下旋轉(zhuǎn)是非常浪費資源的。SpinWait類需要被定義為值類型，以便分配起來更加節(jié)省資源?，F(xiàn)在，我們可以使用此算法來防止前述CountdownLatch算法中出現(xiàn)的阻塞。public struct SpinWait private int m_count;private static readonly bool s_isSingleProc =(Environment.ProcessorCount = 1);private const int s_yieldFrequency = 4000;private const int s_

12、yieldOneFrequency = 3*s_yieldFrequency;專業(yè)資料整理WORD格式public int Spin() 專業(yè)資料整理WORD格式int oldCount = m_count;/ On a single-CPU machine, we ensure our counter is always/ a multiple of "s_yieldFrequency , so we yield every time./ Else, we just increment by one.m_count += (s_isSingleProc " s_yield

13、Frequency : 1);/ If not a multiple of "s_yieldFrequency spin (w/ backoff).int countModFrequency = m_count % s_yieldFrequency;if (countModFrequency > 0)Thread.SpinWait(int)(1 + (countModFrequency * 0.05f);elseThread.Sleep(m_count <= s_yieldOneFrequency " 0 : 1);return oldCount;private

14、 void Yield()Thread.Sleep(m_count < s_yieldOneFrequency " 0 : 1);private const int s_spinCount = 4000;public void Wait()SpinWait s = new SpinWait();while (m_remain > 0)if (s.Spin() >= s_spinCount) m_event.WaitOne();專業(yè)資料整理WORD格式不可否認，選擇頻率和旋轉(zhuǎn)計數(shù)是不確定的。與Win32臨界區(qū)旋轉(zhuǎn)計數(shù)類似，我們應專業(yè)資料整理WORD格式該根據(jù)測試和實驗

15、的結(jié)果來選擇合理的數(shù)值，而且即使合理的數(shù)值在不同系統(tǒng)中也會發(fā)生變專業(yè)資料整理WORD格式化。例如，根據(jù)Microsoft Media Center和Windows kernel團隊的經(jīng)歷，MSDN文檔建議專業(yè)資料整理WORD格式臨界區(qū)旋轉(zhuǎn)計數(shù)為4,000 ，但您的選擇可以有所不同。理想的計數(shù)取決于多種因素，包括專業(yè)資料整理WORD格式在給定時間等待事件的線程數(shù)和事件出現(xiàn)的頻率等。大多數(shù)情況下， 您會希望通過等待事件來消除顯式讓出時間，如鎖存的例如中所示。您甚至可以選擇動態(tài)調(diào)整計數(shù)：例如，從中等數(shù)量的旋轉(zhuǎn)開場，每次旋轉(zhuǎn)失敗就增加計數(shù)。一旦計數(shù)到達預定的最大值，就完全停頓旋轉(zhuǎn)并立即發(fā)出WaitOn

16、e 。邏輯如下所示：您希望立即增加到達預定的最大周期數(shù)，但卻無法超過最大周期數(shù)。如果您發(fā)現(xiàn)此最大值缺乏以阻止上下文切換， 那么立即執(zhí)行上下文切換總的算來占用的資源更少。慢慢您就會希望旋轉(zhuǎn)計數(shù)能夠到達一個穩(wěn)定的值。三、屏障(Barrier)屏障， 又稱集合點，是一種并發(fā)性基元，它無需另一 主 線程控制即可實現(xiàn)各線程之間專業(yè)資料整理WORD格式簡單的互相協(xié)調(diào)。每個線程在到達屏障時都會不可再分地發(fā)出信號并等待。僅當所有n 都專業(yè)資料整理WORD格式到達屏障時，才允許所有線程繼續(xù)。這種方法可用于協(xié)調(diào)算法(cooperative algorithms)，該專業(yè)資料整理WORD格式算法廣泛應用于科學、數(shù)學

17、和圖形領(lǐng)域。 很多計算中都適合使用屏障，實際上，甚至CLR 的垃圾收集器都在使用它們。屏障只是將較大的計算分割為假設(shè)干較小的協(xié)作階段(cooperativephase)，例如：const int P = .;Barrier barrier = new Barrier(P);Data partitions = new DataP;/ Runn ing on "P separate threads in parallel: public void Body(int myIndex) FillMyPartition(partitionsmyIndex);barrier.Await();Re

18、adOtherPartition(partitionsP myIndex - 1); barrier.Await();/ .您會很快發(fā)現(xiàn)在這種情況下是可以使用倒計數(shù)鎖存的。每個線程都可以在調(diào)用Signal后立即調(diào)用Wait ，而不是調(diào)用Await ；在到達屏障后，所有線程都會被釋放。但這里存在專業(yè)資料整理WORD格式一個問題： 前面所講的鎖存并不支持屢次重復使用同一對象，而這卻是所有屏障都支持的一專業(yè)資料整理WORD格式個常用屬性。 實際上， 上述例如就需要使用此屬性。您可以通過單獨的屏障對象來實現(xiàn)這一專業(yè)資料整理WORD格式點，但這樣做非常浪費資源；而由于所有線程每次只出現(xiàn)在一個階段，因此根

19、本無需多個屏專業(yè)資料整理WORD格式障對象。專業(yè)資料整理WORD格式要解決這個問題， 您可以使用一樣的根底倒計數(shù)鎖存算法來處理減少計數(shù)器計數(shù)、發(fā)信號指示事件、等待等方面的問題，從而將其擴展為可重復使用。要實現(xiàn)這一點，您需要使用所謂的感應反向屏障(sense reversing barrier)，該屏障需要在偶數(shù) 和 奇數(shù) 階段之間交替。 在交替階段需要使用單獨的事件。using System;using System.Threading;public class Barrier private volatile int m_count;private int m_originalCount;p

20、rivate EventWaitHandle m_oddEvent;private EventWaitHandle m_evenEvent;private volatile bool m_sense = false; / false=even, true=odd.public Barrier(int count) m_count = count;m_originalCount = count;m_oddEvent = new ManualResetEvent(false);m_evenEvent = new ManualResetEvent(false);public void Await()

21、 bool sense = m_sense;/ The last thread to signal also sets the event.if (m_count = 1 | Interlocked.Decrement(ref m_count) = 0) m_count = m_originalCount;m_sense = !sense; / Reverse the sense.if (sense = true) / oddm_evenEvent.Reset();m_oddEvent.Set(); else / evenm_oddEvent.Reset();m_evenEvent.Set()

22、;專業(yè)資料整理WORD格式專業(yè)資料整理WORD格式 else if (sense = true) m_oddEvent.WaitOne();elsem_evenEvent.WaitOne();為何需要兩個事件，其原因很難講清楚。一種方法是在Await中先執(zhí)行Set 隨后立即執(zhí)行Reset，但這很危險，并會導致死鎖。原因有二：第一，另一線程的m_count 可能已減少，但在依次快速調(diào)用Set 和 Reset 時，計數(shù)的值還缺乏以到達可在事件上調(diào)用WaitOne 。第二，雖然等待的線程可能已經(jīng)能夠調(diào)用WaitOne ，但可報警等待如CLR一貫使用的那些 可以中斷等待， 從而暫時從等待隊列中刪除等待

23、的線程，以便運行異步過程調(diào)用(APC) 。等待的線程將始終看不到事件處于設(shè)置(set) 狀態(tài)。兩種情況均會導致事件丟失，并可能導致死鎖。針對奇數(shù)階段和偶數(shù)階段使用單獨的事件即可防止這種情況。您可能想繼續(xù)像CountdownLatch中那樣將旋轉(zhuǎn)添加到Barrier 。但如果您嘗試這樣做，可能會遇到一個問題：一般情況下，旋轉(zhuǎn)線程會開場旋轉(zhuǎn)直到m_count 歸零。但通過上述實現(xiàn)， m_count 的值實際上永遠不會為零，除非最后一個線程將其重置為m_originalCount 。這種想當然的方法將導致一個或多個線程進展旋轉(zhuǎn)永遠地 ，而其他線程那么會在下一階段阻塞也是永遠地。解決方法很簡單。您旋轉(zhuǎn)

24、，等待感應發(fā)生變化public void Await() bool sense = m_sense;/ The last thread to signal also sets the event.if (m_count = 1 | Interlocked.Decrement(ref m_count) = 0) m_count = m_originalCount;m_sense = !sense; / Reverse the sense.if (sense = true) / oddm_evenEvent.Set();m_oddEvent.Reset(); else / evenm_oddEve

25、nt.Set();m_evenEvent.Reset(); else 專業(yè)資料整理WORD格式SpinWait s = new SpinWait();while (sense = m_sense) if (s.Spin() >= s_spinCount) if (sense = true) m_oddEvent.WaitOne();elsem_evenEvent.WaitOne();由于所有線程都必須離開前一階段的 Await 才可以完成下一階段，因此可以確定，所有線程要么會觀察到感應發(fā)生變化，要么最終等待事件并被喚醒。阻塞隊列在共享內(nèi)存的體系構(gòu)造中，兩項或多項任務間唯一的同步點通常是一

26、個位于中樞的共享集合的數(shù)據(jù)構(gòu)造。通常，一項或多項任務會負責為其他一項或多項任務生成要執(zhí)行的工作 ，我們稱之為生產(chǎn)者 /使用者關(guān)系 (producer/consumer) 。這類數(shù)據(jù)構(gòu)造的簡單同步通常是非常簡單的使用 Monitor 或 ReaderWriterLock 即可解決，但當緩沖區(qū)為空時，任務間的協(xié)調(diào)就會變得比較困難。要解決這個問題，通常需要使用阻塞隊列。實際上，阻塞隊列有幾種稍微不同的變體，包括簡單變體和復雜變體。在簡單變量中， 使用者僅在隊列為空時才會阻塞，而在復雜變量中，每個生產(chǎn)者都正好配有 一個使用者， 也就是說， 在使用者到達并開場處理排隊工程之前，生產(chǎn)者會被阻塞，同理，在生

27、產(chǎn)者交付工程前，所有使用者也會被阻塞。這時通常使用FIFO 先進先出排序，但我們并不總是有必要這么做。 我們也可以對緩沖區(qū)進展限制，這一點稍后會為大家介紹。 由于稍后將要介紹的受限緩沖區(qū)包含更為簡單的為空時阻塞 (blocking-when-empty)行為，因此我們這里僅對配對變量做一了解。要實現(xiàn)這個目的，我們只需封裝一個簡單的Queue<T> ，上方保持同步。那么到底需要何種同步？每當線程對元素進展排隊時，在返回前都會等待使用者取消元素排隊。當線程取消元素排隊時，如果發(fā)現(xiàn)緩沖區(qū)為空，那么必須等待新元素的進入。當然，取消排隊后，使用者必須通知生產(chǎn)者已取到其工程請參見圖 5。Fig

28、ure 5 阻塞隊列復制代碼class Cell<T> internal T m_obj;internal Cell(T obj) m_obj = obj; 專業(yè)資料整理WORD格式public class BlockingQueue<T> private Queue<Cell<T>> m_queue = new Queue<Cell<T>>(); public void Enqueue(T obj) Cell<T> c = new Cell<T>(obj);lock (m_queue) m_que

29、ue.Enqueue(c);Monitor.Pulse(m_queue);Monitor.Wait(m_queue);public T Dequeue() Cell<T> c;lock (m_queue) while (m_queue.Count = 0)Monitor.Wait(m_queue);c = m_queue.Dequeue();Monitor.Pulse(m_queue);return c.m_obj;專業(yè)資料整理WORD格式請注意，我們可以在Enqueue方法中依次調(diào)用Pulse和Wait ，類似地，在Dequeue方法專業(yè)資料整理WORD格式中依次調(diào)用Wait和

30、Pulse。只有在釋放監(jiān)視器之后，才會對內(nèi)部事件進展設(shè)置，而由于監(jiān)專業(yè)資料整理WORD格式視器的這種實現(xiàn)方法，會導致某個線程調(diào)度ping-pong 。我們可能會想，也許可以使用Win32專業(yè)資料整理WORD格式事件來構(gòu)建一個更加優(yōu)化的通知機制。但是，使用這類完善的Win32事件會帶來巨大開銷，專業(yè)資料整理WORD格式尤其是使用它們時所進展的本錢分配和內(nèi)核跳轉(zhuǎn)(kernel transitions)，因此還是考慮其他選專業(yè)資料整理WORD格式擇吧。您可以像CLR 的 ReaderWriterLock那樣將這些時間集中到池中，也可以像ThinEvent類型稍后介紹一樣緩慢分配它們。這種實現(xiàn)方法也是

31、有弊端的，即要為每個新元素分配對象，備選方法可能也會將這些對象參加到池中，但同樣會帶來其他麻煩。受限緩沖區(qū)(Bounded Buffer)某些類別的隊列中會出現(xiàn)資源使用問題。 如果生產(chǎn)者任務創(chuàng)立工程的速度快于使用者處理工程的速度，那么系統(tǒng)的內(nèi)存使用將不受限制。專業(yè)資料整理WORD格式為了說明這個問題， 我們假設(shè)一個系統(tǒng)，單個生產(chǎn)者每秒鐘可將50個工程排入隊列， 而使用者每秒鐘只能使用10 個工程。 首先， 這樣會打亂系統(tǒng)的平衡性，而且對于一對一的生產(chǎn)者 使用者配置無法進展很好的調(diào)整。只需一分鐘，就會有2,400 個工程堆積在緩沖區(qū)中。假設(shè)這些工程中每個工程使用10KB內(nèi)存，那將意味著緩沖區(qū)本身

32、就會占用24MB 內(nèi)存。一小時后， 這個數(shù)字將飆升至1GB以上。解決這一問題的一個方法是調(diào)整生產(chǎn)者線程與使用者線程的比例，在上述情況中， 要將比例調(diào)整為一個生產(chǎn)者對應五個使用者。但是到達速度通常是不穩(wěn)定的， 這會導致系統(tǒng)周期性的不穩(wěn)定，并帶來一些明顯的問題，簡單的固定比例是無法解決這個問題的。效勞器上的程序通常是長時間運行的，人們希望程序能夠長期保持良好的運行狀態(tài)，但如果內(nèi)存使用不受限，就會造成不可防止的混亂，還可能導致必須定期回收效勞器進程的情況。受限緩沖區(qū)允許您對生產(chǎn)者強制阻塞前緩沖區(qū)可能到達的大小進展限制。阻塞生產(chǎn)者可讓使用者有時機 趕上 通過允許其線程接收調(diào)度時間片，同時還能夠解決內(nèi)存

33、使用量增加的問題。我們的方法還是僅封裝Queue<T>，同時添加兩個等待條件和兩個事件通知條件：生產(chǎn)者在隊列滿時等待，直至隊列變?yōu)榉菨M，而使用者在隊列空時等待，直至變?yōu)榉强眨?生產(chǎn)者在生產(chǎn)出工程后通知等待的使用者，而使用者也會在取走工程后通知生產(chǎn)者，如圖 6 中所示。Figure 6 受限緩沖區(qū)(Bounded Buffer)復制代碼public class BoundedBuffer<T> private Queue<T> m_queue = new Queue<T>();private int m_consumersWaiting;priva

34、te int m_producersWaiting;private const int s_maxBufferSize = 128;public void Enqueue(T obj) lock (m_queue) while (m_queue.Count = (s_maxBufferSize - 1) m_producersWaiting+;Monitor.Wait(m_queue);m_producersWaiting-;m_queue.Enqueue(obj);if (m_consumersWaiting > 0)Monitor.PulseAll(m_queue);專業(yè)資料整理WO

35、RD格式public T Dequeue() T e;lock (m_queue) while (m_queue.Count = 0) m_consumersWaiting+;Monitor.Wait(m_queue);m_consumersWaiting-;e = m_queue.Dequeue();if (m_producersWaiting > 0)Monitor.PulseAll(m_queue);return e;這里我們再一次使用了一種比較天真的方法。但是我們確實優(yōu)化了對PulseAll的調(diào)用因為它們消耗的資源很多，方法是使用m_consumersWaiting 和 m_pr

36、oducersWaiting這兩個計數(shù)器并僅就計數(shù)器值是否為零發(fā)出信號。除此以外， 我們還可以再做進一步的改進。例如，共享與此類似的單個事件可能會喚醒過多線程：如果使用者將隊列大小降為0，并且生產(chǎn)者和使用者同時處于等待狀態(tài)，顯然您只希望喚醒生產(chǎn)者至少開場時要這么做。此實現(xiàn)將以先進先出的規(guī)那么處理所有等待者，這意味著您可能需要在任一生產(chǎn)者運行前喚醒使用者，這樣做僅僅是為了讓使用者發(fā)現(xiàn)隊列為空，然后再次等待。令人欣慰的是，最終出現(xiàn)生產(chǎn)者和使用者同時等待的情況是很少見的，但其出現(xiàn)也是有規(guī)律的，而且受限區(qū)域較小。Thin 事件與 Monitor.Wait 、 Pulse 和 PulseAll相比， W

37、in32事件有一個很大的優(yōu)勢：它們是粘滯的(sticky)。也就是說，一旦有事件收到信號，任何后續(xù)等待都將立即取消阻止，即使線程在信號發(fā)出前尚未開場等待。如果沒有這個功能，您就需要經(jīng)常編寫一些代碼將所有等待和信號通知嚴格地限制在臨界區(qū)域內(nèi)，由于Windows方案程序總是會提升已喚醒線程的優(yōu)先級，因此這些代碼的效率很低；如果不采取這種方法，您就必須使用某種技巧型很強、容易出現(xiàn)競態(tài)條件的代碼。專業(yè)資料整理WORD格式作為替代方法， 您可以使用thin 事件，這是一種可重用數(shù)據(jù)構(gòu)造，可在阻塞前短暫地旋轉(zhuǎn)，專業(yè)資料整理WORD格式僅在必要時才緩慢分配Win32事件，否那么允許您執(zhí)行類似手動重置事件的行

38、為。換句話說，專業(yè)資料整理WORD格式它可以對那些復雜的容易導致競態(tài)條件的代碼進展封裝，這樣您就不必在整個根本代碼內(nèi)散專業(yè)資料整理WORD格式播它。此例如依賴于Vance Morrison的文章中描述的一些內(nèi)存模型保證，使用的時候要多專業(yè)資料整理WORD格式加小心請參見圖7。專業(yè)資料整理WORD格式Figure 7 Thin事件復制代碼public struct ThinEvent private int m_state; / 0 means unset, 1 means set.private EventWaitHandle m_eventObj;private const int s_sp

39、inCount = 4000;public void Set() m_state = 1;Thread.MemoryBarrier(); / required.if (m_eventObj != null)m_eventObj.Set();public void Reset() m_state = 0;if (m_eventObj != null)m_eventObj.Reset();public void Wait() SpinWait s = new SpinWait();while (m_state = 0) if (s.Spin() >= s_spinCount) if (m_e

40、ventObj = null) ManualResetEvent newEvent =new ManualResetEvent(m_state = 1);if (InterlockedpareExchange<EventWaitHandle>(ref m_eventObj, newEvent, null) = null) 專業(yè)資料整理WORD格式/ If someone set the flag before seeing the new/ event obj, we must ensure it s been set.if (m_state = 1)m_eventObj.Set(

41、); else / Lost the race w/ another thread. Just use/ its event.newEvent.Close();m_eventObj.WaitOne();這根本上反映了 m_state 變量中的事件狀態(tài)，其中值為0 表示未設(shè)置，值為1 表示已設(shè)置?，F(xiàn)在，等待一個已設(shè)置事件消耗資源是很低的；如果m_state 在 Wait例程的入口處值為 1，我們會立即返回， 無需任何內(nèi)核跳轉(zhuǎn)。 但如果線程在事件設(shè)置完畢之前進入等待狀態(tài)，處理上就需要很多技巧。 要等待的首個線程必須分配一個新的事件對象，并對其進展比較后交換至m_eventObj 字段中； 如果 C

42、AS 失敗，那么意味著其他等待者對事件進展了初始化，所以我們只可重復使用它；否那么就必須重新檢查自上次看到m_state 后其值是否發(fā)生更改。不然的話， m_state 的值也許會為1，那么 m_eventObj 就無法收到信號通知，這將導致在調(diào)用WaitOne 時出現(xiàn)死鎖。調(diào)用Set 的線程必須首先設(shè)置m_state，隨后如果發(fā)現(xiàn)值為非空的m_eventObj ，就會調(diào)用其上的 Set。這里需要兩個內(nèi)存屏障：需要注意的是切不可提前移動m_state 的第二次讀取，我們會使用InterlockedpareExchange 設(shè)置m_eventObj來保證這點；在寫入m_eventObj 之前，不

43、可移動Set 中的對 m_eventObj的讀取這是一種在某些Intel 和 AMD 處理器以及CLR 2.0內(nèi)存模型上出現(xiàn)的奇怪的合法轉(zhuǎn)換，并未顯式調(diào)用Thread.MemoryBarrier 。并行重置事件通常是不平安的，因此調(diào)用方需要進展額外的同步化?，F(xiàn)在您可以輕松在其他地方使用它，例如在上述的CountdownLatch例如和隊列例如中，而且通常這樣做可以大幅度提升性能，尤其是當您可以巧妙地運用旋轉(zhuǎn)時。我們上面介紹了一個技巧性很強的實現(xiàn)方式。請注意， 您可以使用單個標志和監(jiān)視器來實現(xiàn)自動和手動重置類型，這遠比本例如簡單但效率方面有時會不及本例。專業(yè)資料整理WORD格式無鎖定LIFO堆棧

44、專業(yè)資料整理WORD格式使用鎖定構(gòu)建線程平安的集合是相當直接明了的，即使限制和阻塞方面會有些復雜如上面看到的。但是，當所有協(xié)調(diào)均通過簡單的后進先出(LIFO)堆棧數(shù)據(jù)構(gòu)造實現(xiàn)時，使用鎖定的開銷會比實際所需的高。線程的臨界區(qū)即保持鎖定的時間有開場點和完畢點， 其持續(xù)時間可能會跨越許多指令的有效期。保持鎖定可阻止其他線程同時進展讀取和寫入操作。這樣做可以實現(xiàn)序列化， 這當然是我們所想要的結(jié)果，但嚴格地講， 這種序列化要比我們所需的序列化強很多。 我們的目的是要在堆棧上推入和彈出元素，而這兩項操作只需通過常規(guī)讀取和單一的比較交換寫入即可實現(xiàn)。我們可以利用這點來構(gòu)建伸縮性更強的無鎖定堆棧，從而不會強制

45、線程進展沒必要的等待。我們的算法工作方式如下。 使用有的列表代表堆棧，其標頭代表堆棧的頂端，并存儲在m_head 字段中。在將一個新項推入堆棧時，要構(gòu)造一個新節(jié)點，其值等于您要推入堆棧的值，然后從本地讀取m_head 字段，并將其存儲至新節(jié)點的m_next 字段，隨后執(zhí)行不可再分的 InterlockedpareExchange 來替換堆棧當前的頭部。如果頂端自首次讀取后在序列中的任何點發(fā)生更改， CompareExchange都會失敗，并且線程必須返回循環(huán)并再次嘗試整個序列。彈出同樣是比較直截了當?shù)摹Ｗx取m_head 并嘗試將其與 m_next 引用的本地副本交換；如果失敗，您只需一直嘗試，

46、如圖 8 中所示。Win32提供了一種名為SList 的類比數(shù)據(jù)構(gòu)造，其構(gòu)建方法采用了類似的算法。Figure 8 無鎖定堆棧復制代碼public class LockFreeStack<T> private volatile StackNode<T> m_head;public void Push(T item) StackNode<T> node = new StackNode<T>(item);StackNode<T> head;do head = m_head;node.m_next = head; while (m_head

47、 != head | InterlockedpareExchange( ref m_head, node, head) != head);public T Pop() StackNode<T> head;SpinWait s = new SpinWait();專業(yè)資料整理WORD格式while (true) StackNode<T> next;do head = m_head;if (head = null) goto emptySpin;next = head.m_next; while (m_head != head | InterlockedpareExchang

48、e( ref m_head, next, head) != head);break;emptySpin:s.Spin();return head.m_value;class StackNode<T> internal T m_value;internal StackNode<T> m_next;internal StackNode(T val) m_value = val; 請注意， 這是理想的并發(fā)控制的一種形式：無需阻止其他線程存取數(shù)據(jù)，只需抱著會在爭用中勝出 的信念繼續(xù)即可。如果事實證明無法勝出 ，您將會遇到一些變化不定的問題，例如活鎖。這種設(shè)計方案還說明您無法確保能夠?qū)崿F(xiàn)FIFO 調(diào)度。根據(jù)概率統(tǒng)計，系統(tǒng)中所有線程都將向前推進。 而實際上從整體來看，系統(tǒng)進度總是向前推進的，因為其中一個線程的失敗總是意味著至少有一個其他線程是推進的這是調(diào)用該無鎖定 的一個條件