天天看點

《多核與GPU程式設計:工具、方法及實踐》---- 3.7 經典問題中的monitor

本節書摘來自華章出版社《多核與gpu程式設計:工具、方法及實踐》一書中的第3章,第3.7節, 作 者 multicore and gpu programming: an integrated approach[阿聯酋]傑拉西莫斯·巴拉斯(gerassimos barlas) 著,張雲泉 賈海鵬 李士剛 袁良 等譯, 更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。

生産者–消費者問題中緩沖區的管理通常是輕量級的。然而,為了完整性,需要考慮基于monitor的解決方案,并考慮前面介紹的不同的設計方法。

在這種情況下,monitor僅需要為生産者和消費者公開put和get函數。特别是将之與信号量進行比較時,代碼清單3-20所展示的解決方案可以清楚地顯示monitor架構的表達能力顯得更為簡潔。

《多核與GPU程式設計:工具、方法及實踐》---- 3.7 經典問題中的monitor
《多核與GPU程式設計:工具、方法及實踐》---- 3.7 經典問題中的monitor
《多核與GPU程式設計:工具、方法及實踐》---- 3.7 經典問題中的monitor

生産者和消費者代碼簡化為最短(第67~72行以及第98~102行),但是緩沖區管理的所有複雜細節都包含在monitor的<code>put</code>(第20~29行)和<code>get</code>(第32~43行)方法内部。代碼清單3-20與代碼清單3-10在生産者和消費者終止(亦即給定需要處理的資源的總數)上有許多相同的特征,模闆類的使用也使得其可以支援各種特殊情況。

與代碼清單3-10中的代碼不同,這裡的生産者和消費者并不了解共享緩沖區的内部工作機制,也不通過信号量進行互相通知。所有的通信都在monitor類内部隐式實作。

monitor類使用兩種等待條件——<code>full</code>和<code>empty</code>,當隊列滿時(第23、24行)阻塞生産者線程,當隊列空時(第35~36行)阻塞消費者線程。注意,monitor類使用大量變量,而這些變量在代碼清單3-10的線程間共享并用于避免競争條件。現在在兩類線程間的唯一共享變量是monitor執行個體,并通過<code>initclass</code>方法使得兩類線程獲得這一共享變量。

如果在共享緩沖區中添加或者移除資源需要花費一定的時間(例如需要拷貝對象而不僅是引用),則使用第二種設計方法可以有效提高性能。從monitor中擷取和釋放一個<code>permit</code>意味着<code>run</code>方法将會花費較之上一設計中更長的時間。

這種思路是,生産者和消費者将會使用一對函數,首先獲得緩沖區位置的互斥通路,然後釋放給monitor繼續使用。

《多核與GPU程式設計:工具、方法及實踐》---- 3.7 經典問題中的monitor
《多核與GPU程式設計:工具、方法及實踐》---- 3.7 經典問題中的monitor

代碼清單3-21中的解決方案的關鍵之處如下。

<code>monitor</code>類提供以下兩對方法。

<code>pdroducer</code>線程使用<code>canput和doneputting</code>方法

<code>consumer</code>線程使用<code>canget和donegetting</code>方法

這些方法的主體主要包括代碼清單3-20中<code>put</code>和<code>get</code>方法的兩部分(平分)。

<code>canput</code>函數和<code>canget</code>函數傳回指向緩沖區位置的指針,該位置可以用來存儲資源的索引。通過<code>in</code>和<code>out</code>指針而不是<code>count</code>計數器的加一,實際上防止傳回的位置被monitor進一步修改。

在<code>canput</code>和<code>canget</code>函數傳回之後,<code>producer</code>和<code>consumer</code>線程可以充分利用時間來存儲或者提取一個資源。<code>monitor</code>此時可以繼續服務于其他線程。

一旦調用<code>doneputting</code>或<code>donegetting</code>方法,計數器加一或者減一,并且一個等待的<code>producer</code>或者<code>consumer</code>線程通過<code>empty</code>或者<code>full</code>等待條件通知。

基于monitor的解決方案也可以移植到讀者–寫者問題。應用monitor而不是信号量,為一個線程或者其他類型的一個線程配置設定優先級變得十分簡單。問題的特征使得必須使用第二種設計方法,亦即每個線程都将獲得通路資源的允許,并且在完成任務後釋放這一允許。

線程無須考慮優先級,或者不用考慮其他位于關鍵區的線程的存在性。這一功能嵌入在monitor的方法中。

在下一節将要介紹的三種解決方案中,<code>reader</code>和<code>writer</code>線程執行固定數目的操作,如下所示:

《多核與GPU程式設計:工具、方法及實踐》---- 3.7 經典問題中的monitor

下幾節中将要分析monitor實作的具體細節。

為了賦予讀者線程優先級,必須維護等待的讀者線程<code>readerwaiting</code>,并且在<code>readerwaiting</code>大于零時阻止一個寫者進入關鍵區。

《多核與GPU程式設計:工具、方法及實踐》---- 3.7 經典問題中的monitor
《多核與GPU程式設計:工具、方法及實踐》---- 3.7 經典問題中的monitor

代碼清單3-22所展示的解決方案的重要之處如下。

monitor維護兩個等待條件:用于喚醒等待寫者的wq和用于喚醒等待讀者的rq。

在讀者線程内部關鍵區中維護一個計數器,在第29行加一,而一旦讀者線程離開時将在第44行減一。如果計數器為0,信号将會被發送給所有等待的寫者線程(第46行)。

如果有讀者線程位于其關鍵區内,則寫者線程會阻塞,否則寫者線程将進入關鍵區(第35行)。

最後一部分實作優先級到讀者線程的轉移,并在<code>finishedwriting</code>方法中管理等待條件隊列:隻在沒有等待的讀者線程時才喚醒一個寫者(第53~56行)。

為了賦予寫者線程優先級,必須維護等待寫者隊列<code>writerswaiting</code>,并且當<code>writerswaiting</code>

大于零時,阻止讀者線程進入其關鍵區。

代碼清單3-22和代碼清單3-23中的兩個類是近似等價的。其差別僅在于控制關鍵區的入口和退出關鍵區的隊列管理上。在前一解決方案中,如果有寫者線程等待在其關鍵區入口,第22行将強制讀者阻塞。将優先級轉交給寫者線程在代碼清單3-23中的第52~55行實作,一個寫者離開其關鍵區時将會喚醒一個等待的寫者線程(前提是有一個寫者程序的優先級高于幾個讀者程序)。但是如果沒有等待的寫者線程,所有的讀者線程都将被喚醒(第55行)。

《多核與GPU程式設計:工具、方法及實踐》---- 3.7 經典問題中的monitor
《多核與GPU程式設計:工具、方法及實踐》---- 3.7 經典問題中的monitor

為讀者–寫者問題設計一個公平的解決方案是一項具有挑戰性的任務。盡管這還未在之前的章節中考慮過,為了滿足在關鍵區入口的請求,從一個等待條件隊列中釋放線程的順序是實作一個先入先出順序的關鍵。

qt文檔中有關<code>wakeone</code>和<code>wakeall</code>的方法寫道:“線程被喚醒的順序依賴于作業系統的具體排程政策,不能預先控制或者預測。”

值得注意的是,這并不是qt實作的錯誤。一旦一組線程重新就緒,其執行的順序就是作業系統的職責,不能直接控制。一個等價的問題會對任意monitor實作帶來困難。

qt文檔提供了一個關于如何處理這一問題的啟示:“如果想喚醒指定線程,典型的解決方案是使用一個不同的等待條件,并使不同的線程等待不同的條件。”

代碼清單3-24展示的解決方案恰好展示了這一特征:被強制阻塞的線程等待不同的條件,允許顯式精确控制喚醒哪一個線程以及按照何種順序喚醒。一個固定的等待條件數組按照循環隊列模式配置設定和管理(<code>in和out</code>索引以及一個用于記錄使用數目的<code>counter</code>)。附加一個布爾型數組(<code>writeflag</code>)允許區分何種類型的線程被阻塞在每種等待條件上。如果所有的等待條件都被使用,線程将會被強制移出并加入到一個通用的等待條件(<code>quefull</code>)。這其實是與完全公平的解決方案唯一的不同之處(由于線程離開隊列時不按先入先出隊列),但這是一個微妙的折中。

《多核與GPU程式設計:工具、方法及實踐》---- 3.7 經典問題中的monitor
《多核與GPU程式設計:工具、方法及實踐》---- 3.7 經典問題中的monitor
《多核與GPU程式設計:工具、方法及實踐》---- 3.7 經典問題中的monitor

代碼清單3-24中代碼的其他一些關鍵點如下。

所有請求進入關鍵區的線程首先檢查等待條件隊列的狀态,以及在其關鍵區執行的線程的種類。

隻要沒有寫者線程在隊列中并且等待條件隊列為空,讀者線程就允許執行<code>canread(counter==0)</code>。如果後一種情況為假(第30行),這意味着在服務順序中至少有一個寫者位于這一讀者之前。

如果等待條件隊列為空并且沒有其他寫者或者讀者線程位于關鍵區内,寫者線程就允許執行<code>canwrite</code>(第48行)。

如果第30行和第48行的條件為真,使用c數組中的一個元素阻塞線程,<code>writeflag</code>中的對應元素被設定/重置,以表示有一個讀者/寫者線程被阻塞。

當調用<code>finishwriting</code>,并且等待條件隊列為非空(<code>counter&gt;0</code>)時,位于隊列頭的線程類型(out指針指向)被檢測(第80行)。如果第一個元素是讀者,隊列中的所有讀者線程或者直到遇到一個寫者線程之前的讀者線程被喚醒(第82~86行)。否則,第一個寫者線程被喚醒(第91~93行)。

以這種細粒度方法管理嘗試進入關鍵區的線程能力,可能導緻多種可能性,它們超過這種簡單的讀者–寫者場景。例如,可以用任意目标函數判斷将要執行哪一個線程(例如,基于優先級、資金因素等)。一個恰當的例子是滿足客戶請求的多線程dbms系統。這可能通過客戶的級别、請求的優先級或者任意其他标準集進行排序。

繼續閱讀