多核分布式隊列的實現："偷"與"自私"的運用

在討論本文的正題前，不得不先說一些閑話，嫌哆嗦者可以跳過"前言"部分不讀。

• 1. 前言

在發表了"老子是偉大的多核計算科學家" （鏈接：[url]http://blog.csdn.net/drzhouweiming/archive/2008/11/07/3246254.aspx[/url]，為敘述方便，后面將這篇文章簡稱為"老子"）一文后，褒揚者有許多，但是也引來了許多板磚。當然大部分板磚都只是泛泛的批評，沒有任何內容。不過有些人覺得似乎有些牽強附會，倒是引起了我的注意，確實這類文章可能確實容易給人牽強附會的感覺。 需要說明的是，本人并沒有覺得它是牽強附會的。首先申明一下，我并不是研究哲學的，也沒有詳細研究過老子的《道德經》，但是我在設計多核算法時，確實受到了《道德經》中的思想啟發。舉兩個例子如下： 第一個例子是在設計多核查找算法（鏈接：[url]http://blog.csdn.net/drzhouweiming/archive/2008/10/27/3159501.aspx[/url]） 時，最初我是用AVL樹作為多級查找結構的子查找結構的，當時覺得AVL樹肯定會比數組更好，因為對稍微大一點的數組進行插入刪除的效率非常低，只能用在 很少數據的表上，不能對大量數據的表進行管理。記得有一天看電視時，湊巧看到在講老子的小國寡民思想，談到了結繩而治的問題，受此啟發，對AVL樹比數組 更好的想法產生了懷疑，于是試著將查找子結構改為用最原始的數組來實現，結果發現即使對上百萬個規模的數據的表進行處理，綜合性能也比用AVL樹更好。 第二個例子是在設計多核分布式內存管理算法時，采用了"搶"的方法，使得分配和釋放內存不需要使用鎖。這也是受《道德經》中的"無為"及"大道自 然"的思想影響，因為之前已經發現"貪心"、"自私"、"偷"這幾種人性的本能在算法中得到廣泛使用，既然連"偷"都在多核算法中得到使用，那么它的孿生 兄弟"搶"應該也可以在多核算法中得到使用，本著此思想，后來終于發現可以將"搶"的思想用在多核分布式內存管理算法中，大大提高共享內存分配和釋放的效 率。 對老子《道德經》的解釋，歷來有各種不同的解釋。既然有些人只是在理論層面都可以進行解釋，我現在把它的部分思想用到了具體的多核算法中，變成了在計算機里可以實際運行的程序，對它解釋一下就變成了牽強附會的話，那么這種牽強附會我想越多越好。 閑話少敘，言歸正傳，下面就來談一個使用"偷"與"自私"的方法實現的多核分布式隊列的詳細實例，以看看如何將看似泛泛而談的思想變成可以運行的程序的。

• 2. 分布式隊列的基本概念

在"多核編程中的條件同步模式"（鏈接： [url]http://softwareblogs-zho.intel.com/2009/01/14/845/[/url]）這篇文章中，講到了如何減少共享隊列中的鎖的使用次數的具體方法，在它的基礎上，可以構造出一個高效的隊列池。 如果采用線程分組競爭模式（參見"多核編程中的線程分組競爭模式，鏈接：[url]http://blog.csdn.net/drzhouweiming/archive/2007/07/10/1684753.aspx[/url]）來實現隊列池，那么每組線程對應于隊列池中的一個子隊列，當某個線程在操作自己所屬的子隊列時，如果子隊列為空卻進行出隊操作，那么此時可以從其他組線程所屬的子隊列中進行出隊操作，這也就是"老子"一文中所說的"偷"的方法的使用。 有沒有更好的方法進一步減少同步或者鎖的使用呢？答案是有的。偷別人的東西總不如掏自己口袋里的東西來得方便，之所以需要"偷"，乃是因為自己口袋里空空。如果大家都富裕了，口袋都鼓鼓的了，自然不需要去"偷"別人的了。 當然在計算機中，"富裕"的辦法就是給每個線程賦予一個私有隊列，這樣每個線程可以大部分時間都操作自己私有隊列，不需要同步操作，大大提高效率，這也就是"老子"一文中所說的"自私"方法的使用。 基于"偷"和"自私"兩種方法，就可以設計出一個適應多核環境的分布式隊列。在分布式隊列中，每個操作隊列的線程都有一個私有隊列，另外為了解決私有隊列間的負載均衡問題，還需要一個隊列池來維護數據的負載均衡。 分布式隊列的數據結構示意圖如下： 圖1：分布式隊列數據結構示意圖 有了上面的數據結構圖，具體來實現就可以分為兩個步驟：

• 1、 實現一個隊列池
• 2、 給每個線程賦予一個私有隊列

隊列池的實現可以采用前面講過方法實現，這里就不詳述了，下面主要談談如何給每個線程賦予一個私有隊列（也稱作本地化隊列）的詳細實現方法。

轉載于:https://blog.51cto.com/intelisn/130443

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的多核分布式队列的实现：“偷”与“自私”的运用（1）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。