本節書摘來自華章出版社《多核與gpu程式設計：工具、方法及實踐》一書中的第3章，第3.5節， 作 者 multicore and gpu programming: an integrated approach［阿聯酋］傑拉西莫斯·巴拉斯（gerassimos barlas） 著，張雲泉 賈海鵬 李士剛 袁良 等譯， 更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。
下面幾節将介紹一組問題，有兩重目的。
這些問題代表了實際應用中常見的場景。
這些問題引入了日常中常見的一些特殊條件。
生産者–消費者問題是通過一個共享緩沖區對兩類不同程序進行同步的問題，共享緩沖區用來存放生産者線程産生的資源，消費者線程從中擷取資源。一般情況下問題包含n個生産者和m個消費者。
代碼清單3-8中的僞碼展示了兩種類型的線程如何進行互操作。
首先羅列出兩類線程必須滿足的需求，共享緩沖區邊界特征以及安全通路共享變量的需求。
當一個生産者在共享緩沖區中存儲一個資源時，必須對in參數加鎖。表3-2中的相關模式是s1。
當一個消費者在共享緩沖區中移除一個資源時，必須對out參數加鎖。表3-2中的相關模式是s1。
如果共享緩沖區為空，則消費者線程必須等待生産者産生資源。表3-2中的相關模式是s2。
如果共享緩沖區已滿，則生産者線程必須等待消費者移除資源。表3-2中的相關模式是s2。
以上讨論可以歸納為，需要兩個二進制信号量作為in和out參數的加鎖操作，需要兩個計數信号量來訓示線程對共享緩沖區的操作。代碼清單3-9中的解決方案克服了代碼清單3-8中效率低下的缺點，即第13行和第25行的空循環。這是由于信号量可以阻塞調用線程，直到資源可用時才恢複執行，是以while循環可以删除。
比較代碼清單3-8和代碼清單3-9可以引出如下幾個問題。
q：rescount計數器為何删除？這是一個共享變量，但是沒有被互斥量保護，并且被完全删除。
a：删除這一變量是由于使用它的空循環被删除。如果依然在代碼中保留這一計數器，則需要一個互斥量進行保護。
q：是否可以将resavail和slotsavail兩個計數信号量合并為一個計數信号量？這是由于resavail+slotsavail=buffsize。
a：在串行程式中resavail+slotsavail永遠等于buffsize，但是當通路共享緩沖區的每種類型的線程個數多于一個時，可能産生：
另一個不允許合并這些信号量的原因在于其扮演一個信号通知角色，用于喚醒等待一個資源或者一個空位的線程。
q：是否可以替換兩個互斥量為一個？兩個互斥量的作用看上去都是鎖定共享緩沖區。
a：可以，但是這樣會降低程式效率。這會強制一個生産者等待消費者完成資源移除操作以及更新out變量，反之也是如此。但是，當每個類型的線程數目為1時可以消除一個或者兩個互斥量。是以，如果僅存在一個生産者，l1（及其相關邏輯）可以删除，如果隻有一個消費者，l2（及其相關邏輯）可以删除。表3-3總結了這些不同情況。
q：對in和out的鎖的釋放操作位于資源被存儲和移除以前，這是否會導緻資源競争？
a：在resavail和slotsavail信号量被正确更新之前，由in和out（在更新之前）索引的共享緩沖區位置是不會被另一個線程（無論何種類型）通路的。第18行和第33行的臨時指針也保證關鍵區的執行時間以及對并發性的影響程度為最小。
代碼清單3-8中的代碼可以通過将共享緩沖區變為一個合适的類（提供配置互斥量的方法）來進一步優化其簡潔性。這将同步問題交給共享緩沖區本身，使得線程完全不用考慮任何并發問題。3.6節将會進一步讨論該問題。
共享記憶體和分布式應用中的一個重要問題是處理程式終止。經常會出現需要對複雜條件進行判斷以便執行程式終止。這些條件通常在本地進行判斷（例如，在密碼破解程式中查找一個合适的哈希值，或者一個gui線程對于單擊一個exit按鈕的響應），這些條件被傳播給其他線程。本節将會介紹兩種用于适當終止多線程程式的方法。
在這兩種方法中都有兩個需要注意的關鍵之處：
無論何種形式的終止信号都需要到達所有線程。
線程應該可以在合理的時間範圍内檢測到這一信号。
這兩個解決方案在生産者-消費者問題中介紹，但是也可應用到其他情況中。唯一的限制是每個線程都應該周期地檢查終止條件是否已滿足。
利用共享資料狀态終止運作看上去是一個一般的解決方案，但是其實作有許多注意事項。現代cpu都包含多層共享緩存，以便加速記憶體資料通路。這些緩存所依賴的一緻性模型可能并非十分嚴格，即一個共享變量可能在多個共享緩存中存在副本，但其中一個改變時，其他位置的值并不是立即更新。大部分共享緩存一緻性實作遵循弱一緻性模型，即同步變量（例如信号量）有一個全局一緻性狀态，但是普通資料的讀寫操作可以按照不同順序執行。
是以為了恰當地通過一個共享标志來支援程式終止，必須使用原子資料類型（例如qt中的qatomicint或者信号量）或者強制編譯器設定volatile關鍵字來禁止對這些共享标志進行緩存操作。
在生産者–消費者問題中，根據線程執行疊代的次數是固定還是可變的，可以有兩種不同的設計方案。具體情況區分如下：
1.已知疊代次數是先驗知識。
一個計數信号量可以被所有類型的線程通路，并把無限的whlie（1）循環替換為while（sem.tryacquire()）。tryacquire方法是acquire的非阻塞版本，當成功對信号量減一時傳回真，否則傳回假。這一代碼如代碼清單3-10所示，其中包含生産者和消費者線程模闆類的工作代碼。
代碼清單3-10中展示的程式需要生産者數目、消費者數目和疊代次數資訊來執行，具體執行個體如下：
程式的關鍵點包括：
所有producer和consumer類都定義為一般類型（模闆），可以支援任意資源類型。
類不變量，例如信号量、緩沖區引用以及in/out索引都另存為類的靜态變量（第9～14行以及第52～56行），并在initclass靜态方法中初始化。初始化操作在所有線程生成（第112行和第113行）前以及main函數已完成所需資料配置設定後執行。
資源相關部分（即被處理的資源的産生和消費部分）由兩個函數處理。這兩個函數作為參數傳遞給initclass方法。代碼中用到的真實函數僅包含存根（stub）。
avail和buffslots信号量被兩種類同時共享，這也是要在類外面進行聲明的原因，相反，l1和l2互斥量是類私有的，分别在第11行和第54行聲明。
c++中的靜态模闆函數指針文法格式如第89行和第90行所示。如果想要使用其他具體資料類型t，則需要将int說明符替換為t。
2.疊代執行次數在運作時确定。
這種情況下的代碼如下：
但是這導緻了另一個問題：除非能檢查共享的exitflag标志狀态，否則線程無法終止。當檢測到終止狀态時，如何喚醒可能在信号量隊列中被阻塞的線程？喚醒線程需要增加相應的信号量，運作線程重新開始運作。
一種顯而易見的方法是令第一個檢測到執行終止狀态的線程執行該任務。代碼清
單3-11展示了這一實作（出于簡潔性，僅展示了部分代碼），consume函數觸發終止信号，某個consumer線程檢測到這一信号，并将終止标志設為真（第66行）。
代碼清單3-10和代碼清單3-11的其他關鍵不同之處在于：
檢測到程式終止的線程（第62行）確定所有其他類型的線程都能通過适當地增加resavail和slotsavail來終止運作（第67行和第68行）。
由于借助一個consumer線程執行終止，是以在類中要包含consumer和producer兩種類型線程的個數（第86行）。
聲明為volatileexitflag的布爾變量在所有類型的線程間共享，允許通過一個簡單的while（exitflag == false）循環控制語句來完成終止操作（第20行和第50行）。
被喚醒的線程在與共享緩沖區互動（第24行和第53行）之前，首先要立即檢測終止條件，這就防止了某些副作用和開銷。
另一個可以适用于分布式記憶體應用的解決方案是傳遞終止消息。在這種生産者-消費者方案中，可以通過共享緩沖區将交換的資源視為隐式消息。一個特殊的（在程式環境中無效的）資源（例如傳遞給一個隻接受正整數的程式負數值）可以用來表示程式終止。例如，可以假定生産者線程生成并存儲在類的共享緩沖區執行個體中：
一個triangle3d執行個體有兩個相同的頂點時可以被消費者線程看成終止信号。
由于資源流是無向的，是以唯一的限制是終止必須由生産者處理。如果消費者線程用來完成這一目的，則必須使用上一節提到的方法來實作。
為了說明這一概念，代碼清單3-12中展示了一個示例，即一個多線程積分函數。生産者線程在共享緩存中放入計算說明，消費者線程取出并對一個特定的區間進行計算，即包含一個區間範圍以及劃分的子區間個數。這一個程式基本上遵循2.4.4節介紹的map-reduce計算模式。
具體的積分實作利用梯形法則，即整個積分區間[a，b]被劃分為n個等寬的子區間，每個子區間長度為h，如圖3-10所示。位于xi和xi+1間的每個子區間的函數面積通過h[f（xi）+f（xi+1）]/2來近似。[a，b]區間的整個面積是：
這裡x0=a，xn=b，xi=a+i*h，h=（b-a）/n。
上面程式的關鍵之處如下。
第18～34行的integercalc類作為一個消費者，從程式主線程中接收slice結構（第7～11行）作為配置設定的計算任務。
主線程轉變slice結構并設定其可用性，然後依靠生産者執行（第111～116行）。
在initclass方法中初始化的類不變量，也作為參數傳遞進來，指向在主線程和消費者線程間共享的信号量（第94行）。
run方法運作一個無限循環（第47行），當一個slice結構中的div等于零時終止（第61行）。
程式的終止由主線程負責。在所有slice結構都被放入共享緩沖區中後，主線程生成與生成線程數目一樣多的信号結構（第120～125行）。注意，終止循環組織為與生成slice任務同樣的結構，在給定的共享緩沖區結構中隻能這樣處理。
integrcalc線程從slice結構中抽取需要的計算參數并根據梯形法則計算面積。計算的部分結果被累加存入*result中。後者被所有integrcalc線程共享，并在關鍵區中執行累加操作（第78～80行）。
理發師問題是一個線程/程序同步問題，在不同的文獻中都有介紹，其最簡單的情形如下：
假設有一個理發店，隻有一個理發師和一個理發椅，還有一間等待房屋（可容納固定數量的椅子）。每個進入理發店的客戶都必須先坐在等待房間的椅子上，然後等待理發師的邀請才能坐在理發椅上。當理發師服務完一個客戶之後，就将客戶送出理發店并從等待房間中邀請另一名客戶。
基于理發師和客戶的上述行為方式，以及相應數目的線程，這個問題有許多種解決方案。這裡将介紹一個特殊的問題，其中引入了公平性。公平性常常應用于排程算法的評價中，例如，如果一個排程程式是公平的，則所有具有相同優先級且等待運作的程序都将獲得相同的處理器時間。在這種上下文中，公平性意味着發送給某個線程的信号終将到達。
為了描述這一問題，假定理發店中有兩個理發師，每個理發師使用兩個可用的理發椅中的一個為服務客戶。代碼清單3-13展示了解決方案的僞碼實作。
代碼清單3-13中的解決方案能夠正确工作，但是存在一個緻命缺陷。圖3-11中的時序圖說明了一個場景，其中一個理發師将一個客戶的理發信号截斷，導緻另一個理發椅上的客戶起身離開。當兩個理發師線程的運作速度不同時就有可能發生這種情況。一旦cust1增加customerready并從相應隊列中釋放barb1，這兩個線程就已經隐式關聯在一起。barb1如果運作太慢而不能及時完成任務，則barb2增加了barberdone，cust1就會離開理發椅。這顯然不是一個合适的解決方案。
解決這一問題的唯一方法是在客戶和理發師之間建立聯系，有兩種實作方法：
1.客戶獲得将要對其服務的理發師線程的id。
2.理發師獲得其将要服務的客戶的id。
兩種解決方案都要求把原始解決方案中的信号量替換為信号量隊列，數目與需要進行辨別的線程數目一樣多。顯然應用第一種解決方案更為高效，因為隻需要為兩個理發師配置設定兩個元素。
對于一個可以獲得理發師id的客戶而言，必須建立一個存放可用理發師id的緩沖區。這一緩沖區的實作必須利用生産者–消費者模式。具體如何配置需要仔細考慮：如果存放id的緩沖區大小跟id的數目一樣多，理發師（生産者）就無須等待緩存中的可用位置。從理發師視角看，緩沖區大小相當于是無限的，是以相關聯的信号量可以删除。代碼清單3-14展示了這一解決方案的關鍵之處。
代碼清單3-14解決方案的關鍵之處如下。
每個理發師都通過customerready和barberdone兩個信号量隊列與一個元素相聯，分别在第101行、第102行定義。
與本章介紹的上一個解決方案一樣，在兩種類型的線程間共享的資料在main()中配置設定，并作為參數傳遞給對兩個類的資料成員初始化的方法（第98～105行）。
一個緩沖區用于存放可用的理發師id。消費者線程通過生産者–消費者模式抽取id。唯一删除的内容是slotsavail信号量，這是由于緩沖區大小足夠容納所有理發師id，是以總會有一個空閑的可用位置。生産者部分的代碼如第43～47行所示，消費者部分的代碼如第81～84行所示。
customer線程并不執行任何循環，是以程式終止由barber線程負責。為了完成這一功能，customerleft信号量在第32行被初始化為客戶數目，在第42行barber::run方法内進行遞減/測試操作。
最後，第3～7行定義的concurprint函數用于生成非錯誤控制台輸出，限制在關鍵區内使用cout對象。
3.5.4 讀者–寫者問題
讀者–寫者問題發生在多個線程嘗試更新一個共享資源并且多個線程嘗試讀取同一共享資源時。在最簡單的場景中，如下兩個條件控制這整個問題的運作：
每個寫者必須對資源進行互斥更新。所有其他線程（包括所有讀線程）都必須被阻塞。
如果一個讀者通路資源，其他讀者也可以同時通路。顯然，與前一條件一緻，寫者必須等待讀者完成操作後才能通路資源。
這兩個規則可以防止資源進入不一緻狀态，避免競争條件以及錯誤的改變。但是這些條件沒有定義線程通路資源的順序。
是否應該賦予某種類型的線程優先級？優先級的引入可能會導緻餓死情況的發生，但是在某些情況下，優先級是程式所必需的。解決該問題的關鍵是對嘗試通路資源的線程隊列的管理。
這三個不同的可能性（包括線程順序問題）将會在下一節的分析中解決。
優先考慮讀線程意味着，當一個讀線程嘗試通路資源并且該資源目前正在被其他讀線程通路時，無論是否存在等待的寫線程，該讀線程都允許繼續執行。
代碼清單3-15展示了這一解決方案的核心部分僞碼。
這一解決方案的設計十分簡單。
寫線程共享一個互斥量（writerlock），用于控制寫線程進入關鍵區。
讀線程也共享一個互斥量（countlock），用于控制讀線程通路共享計數器（numreaders）。在第8行和第16行中改變這一計數器之前，一個線程必須鎖定這一互斥量。
第一個獲得countlock的讀線程也嘗試獲得writerlock互斥量。如果已經有一個寫線程在關鍵區中執行，該讀線程進行等待（其他進入的讀線程也将會被阻塞在這一等待處）。否則，讀線程将會繼續執行，并阻止其他寫線程進入關鍵區。
在最後一個讀線程退出關鍵區後，寫線程的互斥量将被釋放（第18行）。
這一解決方案優先考慮讀線程，這是因為一旦一個讀線程進入其關鍵區，所有其他嘗試進入的讀線程都将成功進入，并阻塞所有等待中的寫線程。
優先考慮寫線程意味着，在等待隊列中的任意寫線程都将繞過所有讀線程進入關鍵區。盡管看上去更為複雜，但是這一解決方案十分類似前一節介紹的方案。代碼清單3-16展示了這一解決方案的關鍵核心僞碼。
初步看上去，讀線程部分等價于代碼清單3-15中的代碼，僅僅增加了對readerslock看上去無效的
加鎖解鎖對，更多的細節包括：
除了阻止讀線程進入關鍵區外，readerlock鎖并沒有其他作用。這就是讀線程要立即對其進行釋放的原因（第16行）。寫線程在其第一次運作時執行這一控制（第32行）。
第31行中，隻有第一個寫線程阻塞其他讀線程。最後一個寫線程離開時釋放所有讀線程的鎖（第41行和第42行）。
通過numwriters枚舉所有等待的寫線程需要使用互斥量（writercountlock）來避免競争條件。
在第一個寫線程嘗試更新資料之前，讀線程的執行過程與前一節的介紹一緻。
一個公平的方案是對于等待的線程隊列應用一個嚴格先入先出政策。這意味着所有線程将按照其排隊的順序進入關鍵區，也遵循3.5.4節介紹的兩個規則。
公平解決這一問題的一個可用技巧是使用另一個信号量，使得所有線程在執行之前隻通路一次。一旦允許兩種類型的線程進入其關鍵區，二者就應釋放該信号量。隻要利用一個強信号量，其執行順序就是先入先出的，是以沒有餓死的危險。
代碼清單3-17展示了這一公平解決方案的僞碼：
這一公平解決方案的一些關鍵點包括：
讀者線程的代碼與優先考慮讀線程的解決方案一緻。然而，fairlock互斥量的引入強制所有類型的線程進入相同隊列中。
當一個讀者線程獲得fairlock時，它将對numreaders計數器加一，并獲得writerlock鎖。它将在進入其關鍵區之前釋放fairlock，允許其他讀者線程也進入。
如果一個寫者線程跟随一個讀線程進入fairlock線程，将會在第29行阻塞它，并阻止所有其他線程通路fairlock鎖。
qt提供一個友善的qreadwritelock類，以便解決讀者–寫者問題。這一類支援如下方法：
lockforread：這一鎖用于資源的隻讀通路。隻要沒有寫線程在之前進入過等待隊列，其他讀者線程就仍然允許進入。
lockforwrite：這一鎖用于修改資源的通路。所有其他線程都将被阻塞。
unlock：釋放鎖。
同時也支援一類非阻塞的try*類型方法（例如trylockforread）。qreadwritelock的解決方案中優先考慮寫者線程。是以它更适用于寫者線程不如讀者線程頻繁的情形。