建站
咨詢
售后
建站咨詢
新聞中心
在討論本文的正題前，不得不先說一些閑話，嫌哆嗦者可以跳過“前言”部分不讀。
創(chuàng)新互聯(lián)公司是一家集網(wǎng)站建設(shè),正安企業(yè)網(wǎng)站建設(shè),正安品牌網(wǎng)站建設(shè),網(wǎng)站定制,正安網(wǎng)站建設(shè)報價,網(wǎng)絡(luò)營銷,網(wǎng)絡(luò)優(yōu)化,正安網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強企業(yè)競爭力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時我們時刻保持專業(yè)、時尚、前沿，時刻以成就客戶成長自我，堅持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實用型網(wǎng)站。
1.前言
在發(fā)表了“老子是偉大的多核計算科學(xué)家” （鏈接：http://blog.csdn.net/drzhouweiming/archive/2008/11/07/3246254.aspx，為敘述方便，后面將這篇文章簡稱為“老子”）一文后，褒揚者有許多，但是也引來了許多板磚。當然大部分板磚都只是泛泛的批評，沒有任何內(nèi)容。不過有些人覺得似乎有些牽強附會，倒是引起了我的注意，確實這類文章可能確實容易給人牽強附會的感覺。
需要說明的是，本人并沒有覺得它是牽強附會的。首先申明一下，我并不是研究哲學(xué)的，也沒有詳細研究過老子的《道德經(jīng)》，但是我在設(shè)計多核算法時，確實受到了《道德經(jīng)》中的思想啟發(fā)。舉兩個例子如下：
第一個例子是在設(shè)計多核查找算法（鏈接：http://blog.csdn.net/drzhouweiming/archive/2008/10/27/3159501.aspx）時，最初我是用AVL樹作為多級查找結(jié)構(gòu)的子查找結(jié)構(gòu)的，當時覺得AVL樹肯定會比數(shù)組更好，因為對稍微大一點的數(shù)組進行插入刪除的效率非常低，只能用在很少數(shù)據(jù)的表上，不能對大量數(shù)據(jù)的表進行管理。記得有一天看電視時，湊巧看到在講老子的小國寡民思想，談到了結(jié)繩而治的問題，受此啟發(fā)，對AVL樹比數(shù)組更好的想法產(chǎn)生了懷疑，于是試著將查找子結(jié)構(gòu)改為用最原始的數(shù)組來實現(xiàn)，結(jié)果發(fā)現(xiàn)即使對上百萬個規(guī)模的數(shù)據(jù)的表進行處理，綜合性能也比用AVL樹更好。
第 二個例子是在設(shè)計多核分布式內(nèi)存管理算法時，采用了“搶”的方法，使得分配和釋放內(nèi)存不需要使用鎖。這也是受《道德經(jīng)》中的“無為”及“大道自然”的思想 影響，因為之前已經(jīng)發(fā)現(xiàn)“貪心”、“自私”、“偷”這幾種人性的本能在算法中得到廣泛使用，既然連“偷”都在多核算法中得到使用，那么它的孿生兄弟“搶” 應(yīng)該也可以在多核算法中得到使用，本著此思想，后來終于發(fā)現(xiàn)可以將“搶”的思想用在多核分布式內(nèi)存管理算法中，大大提高共享內(nèi)存分配和釋放的效率。
對老子《道德經(jīng)》的解釋，歷來有各種不同的解釋。既然有些人只是在理論層面都可以進行解釋，我現(xiàn)在把它的部分思想用到了具體的多核算法中，變成了在計算機里可以實際運行的程序，對它解釋一下就變成了牽強附會的話，那么這種牽強附會我想越多越好。
閑話少敘，言歸正傳，下面就來談一個使用“偷”與“自私”的方法實現(xiàn)的多核分布式隊列的詳細實例，以看看如何將看似泛泛而談的思想變成可以運行的程序的。
2.分布式隊列的基本概念
在“多核編程中的條件同步模式”（鏈接： http://softwareblogs-zho.intel.com/2009/01/14/845/）這篇文章中，講到了如何減少共享隊列中的鎖的使用次數(shù)的具體方法，在它的基礎(chǔ)上，可以構(gòu)造出一個高效的隊列池。
如果采用線程分組競爭模式（參見“多核編程中的線程分組競爭模式，鏈接：http://blog.csdn.net/drzhouweiming/archive/2007/07/10/1684753.aspx）來實現(xiàn)隊列池，那么每組線程對應(yīng)于隊列池中的一個子隊列，當某個線程在操作自己所屬的子隊列時，如果子隊列為空卻進行出隊操作，那么此時可以從其他組線程所屬的子隊列中進行出隊操作，這也就是“老子”一文中所說的“偷”的方法的使用。
有沒有更好的方法進一步減少同步或者鎖的使用呢？答案是有的。偷別人的東西總不如掏自己口袋里的東西來得方便，之所以需要“偷”，乃是因為自己口袋里空空。如果大家都富裕了，口袋都鼓鼓的了，自然不需要去“偷”別人的了。
當然在計算機中，“富?！钡霓k法就是給每個線程賦予一個私有隊列，這樣每個線程可以大部分時間都操作自己私有隊列，不需要同步操作，大大提高效率，這也就是“老子”一文中所說的“自私”方法的使用。
基于“偷”和“自私”兩種方法，就可以設(shè)計出一個適應(yīng)多核環(huán)境的分布式隊列。在分布式隊列中，每個操作隊列的線程都有一個私有隊列，另外為了解決私有隊列間的負載均衡問題，還需要一個隊列池來維護數(shù)據(jù)的負載均衡。
分布式隊列的數(shù)據(jù)結(jié)構(gòu)示意圖如下：
圖1：分布式隊列數(shù)據(jù)結(jié)構(gòu)示意圖
有了上面的數(shù)據(jù)結(jié)構(gòu)圖，具體來實現(xiàn)就可以分為兩個步驟：
1、 實現(xiàn)一個隊列池
2、 給每個線程賦予一個私有隊列
隊列池的實現(xiàn)可以采用前面講過方法實現(xiàn)，這里就不詳述了，下面主要談?wù)勅绾谓o每個線程賦予一個私有隊列（也稱作本地化隊列）的詳細實現(xiàn)方法。
3.本地化隊列的實現(xiàn)思路
要給線程指定一個本地化隊列，通常的做法是先將創(chuàng)建好的隊列放入一個數(shù)組中，然后給線程編號，從0開始進行編號，編號為0的線程對應(yīng)于數(shù)組下標為0位置上存放的隊列，編號為1的線程對應(yīng)于數(shù)組下標為1位置上存放的隊列，…。
每個線程要獲取自己的本地化隊列時，只需要先獲取線程編號，然后就可以通過線程編號去訪問對應(yīng)的隊列，由于每個線程的編號都不相同，因此每個線程訪問的隊列都不相同，即每個隊列只有一個線程訪問它，這樣就可以實現(xiàn)每個線程的本地化隊列。
那么如何給線程編號從0開始編號呢，操作系統(tǒng)并沒有直接提供這種功能。即使操作系統(tǒng)提供了線程從0開始編號的功能也沒有用，因為并不一定所有的線程都會訪問分布式隊列。例如有8個線程，其中編號為0，3，5，7的線程會訪問分布式隊列，那么在創(chuàng)建分布式隊列時，就需要創(chuàng)建8個本地隊列，否則線程編號將無法和存放隊列的數(shù)組下標對應(yīng)起來。
看到這里，目標已經(jīng)很明確了，那就是要給所有訪問分布式隊列的線程從0開始依次編號。比如有N個線程要訪問分布式隊列，那么需要給這N個線程依次編號為0，1，…N-1。下面就來討論如何給線程編號的問題。
#p#
4.給線程編號的方法
在操作系統(tǒng)中，通常提供了線程本地存儲的API，通過API可以給每個線程設(shè)定一個數(shù)據(jù)（可以是指針，也可以是一個整數(shù)），同時也可以通過API來取出當前線程設(shè)置的那個數(shù)據(jù)。比如給一個線程A設(shè)定一個整數(shù)0，那么線程A執(zhí)行的任何地方都可以調(diào)用相應(yīng)的API獲取到整數(shù)0，這樣就可以在程序的任何地獲取到線程A的編號為0。
在Windows系列操作系統(tǒng)中，提供了Tls_Alloc()，Tls_SetValue()，Tls_GetValue()，Tls_Free()這幾個函數(shù)來實現(xiàn)線程本地存儲操作。
pthread中，可以通過pthread_key_create(), pthread_setspecific(), pthread_getspecific()等函數(shù)來實現(xiàn)線程本地存儲操作，其中pthread_create_key()和Tls_Alloc()功能相同，只是參數(shù)有所不同，Tls_SetValue()和pthread_setspecific()功能等價，Tls_GetValue()和pthread_getspecific()功能等價。
下面演示一下TlsAlloc()，Tls_SetValue()，Tls_GetValue()，Tls_Free()這幾個函數(shù)的基本用法。
- DWORD g_dwTlsIndex;
- LONG volatile g_dwThreadId = 0;
- int GetId()
- {
- //獲取當前執(zhí)行線程的由TlsSetValue()設(shè)置的值
- int nId = (int)TlsGetValue(g_dwTlsIndex);
- return (nId-1);
- }
- void ThreadFunc(void *args)
- {
- LONG Id = AtomicIncrement (&g_dwThreadId); //對g_dwThreadId進行原子加1操作
- TlsSetValue(g_dwTlsIndex, (void *)Id); //給當前執(zhí)行的線程設(shè)置一個值
- printf("ThreadFunc2: Thread Id = %ld/n", GetId());
- }
- int main(int argc, char* argv[])
- {
- g_dwTlsIndex = TlsAlloc(); //分配一個線程本地存儲索引，需要在創(chuàng)建線程前執(zhí)行
- _beginthread(ThreadFunc, 0, NULL);
- _beginthread(ThreadFunc, 0, NULL);
- Sleep(100); //延時等待上面兩個線程執(zhí)行完
- TlsFree(g_dwTlsIndex);
- return 0;
- }
要說明一下，在ThreadFunc()函數(shù)中，使用了一個AtomicIncrement()函數(shù)，這個函數(shù)對應(yīng)于Windows操作系統(tǒng)中的InterlockedIncrement()函數(shù)。在Widnows系統(tǒng)中，可以使用以下宏定義來實現(xiàn)AtomicIncrement()函數(shù)：
#define AtomicIncrement(x) InterlockedIncrement(x)
上面程序在運行后，會打印出以下結(jié)果：
ThreadFunc: Thread Id = 0
ThreadFunc: Thread Id = 1
從上面代碼和執(zhí)行結(jié)果可以看出，雖然GetValue()在ThreadFunc()函數(shù)中執(zhí)行，但是兩個線程執(zhí)行GetValue()得到的值是不同的，一個線程得到的是0，另外一個線程得到的是1。這主要是因為兩個線程調(diào)用TlsSetValue()設(shè)置的值并不相同，一個為1，另一個為2。
需要注意的是，TlsGetValue()的返回值為0表示失敗，所以使用TlsSetValue()函數(shù)時，應(yīng)該從1開始設(shè)置，然后在GetId()函數(shù)中，返回的是TlsGetValue()的返回值減1。
采用上面的方法，就可以設(shè)計出分布式隊列中的線程Id自動編號和獲取功能了。下面是詳細的實現(xiàn)代碼：
- class CDistributedQueue {
- private:
- DWORD m_dwTlsIndex;
- LONG volatile m_lThreadIdIndex;
- public:
- CDistributedQueue();
- virtual ~CDistributedQueue();
- LONG ThreadIdGet();
- //可以添加其他成員函數(shù)在下面
- };
- CDistributedQueue::CDistributedQueue()
- {
- m_dwTlsIndex = TlsAlloc();
- m_lThreadIdIndex = 0;
- }
- CDistributedQueue::~CDistributedQueue()
- {
- TlsFree(m_dwTlsIndex);
- }
- LONG CDistributedQueue::ThreadIdGet()
- {
- LONG Id = (LONG )TlsGetValue(m_dwTlsIndex);
- if ( Id == 0 )
- {
- Id = AtomicIncrement(&m_lThreadIdIndex);
- TlsSetValue(Id);
- }
- return (Id - 1);
- }
上面的代碼中，設(shè)置或獲取線程編號都在ThreadIdGet()一個成員函數(shù)內(nèi)完成，先判斷獲取的Id是否為0，如果為0，表明線程還沒有被設(shè)置Id，因此將m_lThreadIdIndex原子加1，然后再設(shè)置給對應(yīng)的線程。每調(diào)用一次TlsSetValue()函數(shù)，其設(shè)置的Id值依次加1，這樣就可以得到一個1，2，3，…序列。每個線程調(diào)用了TlsSetValue()函數(shù)后，下一個調(diào)用TlsGetValue()函數(shù)時，獲得的值一定大于0，因此每個線程最多只能執(zhí)行TlsSetValue()函數(shù)一次。
采用上面的方法來獲取線程編號，必須保證創(chuàng)建的本地隊列數(shù)量大于等于訪問隊列的線程數(shù)量，否則隊列數(shù)量不足，將會造成沒有足夠的本地隊列供線程使用，程序中可能會造成越界等不可預(yù)測的異常。常用的解決辦法是將本地隊列的數(shù)量擴大一倍。
上面這種線程編號方法，非常方便，任何訪問分布式隊列的線程都可以被自動編號，調(diào)用分布式隊列的線程不需要為編號操心。
有了給線程自動編號的方法后，就可以實現(xiàn)分布式隊列的各個具體操作如進隊、出隊等。當然在實現(xiàn)具體的操作代碼前，有必要了解一下分布式隊列中是如何進行進隊和出隊操作的。
#p#
5. 進隊出隊操作
分布式隊列的進隊出隊操作根據(jù)不同應(yīng)用類型具有不同的操作策略，但是不論何種類型的操作，其基本思想必須以本地隊列操作最大化作為前提條件。下面給出分布式隊列中常用的進隊出隊操作類型。
1) 出隊操作
出隊操作比較簡單，通常都是先從本地隊列中獲取數(shù)據(jù)，如果本地隊列為空，那么再從共享隊列池中獲取數(shù)據(jù)。
由于先從本地隊列中獲取數(shù)據(jù)，因此有助于實現(xiàn)本地隊列操作的最大化。
出隊操作的流程圖如下：
圖2：分布式隊列的出隊操作流程圖
2:進隊操作
進隊操作相比于出隊操作要復(fù)雜一些，常用的操作策略有以下兩種：
策略1：先判斷本地隊列是否為空，如果為空則將數(shù)據(jù)放入本地隊列中；然后判斷共享隊列池中是否滿，如果滿則將數(shù)據(jù)放入本地隊列中，否則放入共享隊列中。
在這種策略的進隊操作中，首先考慮的是本地隊列的操作問題，本地隊列至少要有一個數(shù)據(jù)，然后考慮的問題是負載平衡問題，共享隊列池中的數(shù)據(jù)主要用于各線程間數(shù)據(jù)的負載均衡。共享隊列池的大小必須做出限制，否則數(shù)據(jù)全部都進到共享隊列池中去了，本地隊列未得到有效使用。
共享隊列池到底設(shè)定多大，才能使得本地隊列操作最大化與負載平衡問題之間取得一個好的均衡，是在實際情況中需要考慮的問題，最好通過測試程序性能去獲取一個合適的值。
進隊操作策略1的操作流程圖如下：
圖3：分布式隊列的進隊操作策略1的流程圖
策略2：當有多個數(shù)據(jù)需要進隊時，先放入一些數(shù)據(jù)到本地隊列中，然后剩下的數(shù)據(jù)再放入共享隊列池中，如果隊列池滿的話，則仍然放入本地隊列中。
本策略中，通常是進隊的線程馬上自己要從隊列中獲取數(shù)據(jù)，因此要先放入一些數(shù)據(jù)到自己的本地隊列中，保證下次從隊列中取數(shù)據(jù)一定是從本地隊列中獲取，可以大大提高本地化隊列操作的頻率，有效降低共享隊列池的操作，大大減少了同步操作。
進隊操作策略2的操作流程圖如下：
圖4：分布式隊列的進隊操作策略2的流程圖
有了進隊操作和出隊操作的詳細流程后，實現(xiàn)分布式隊列的具體代碼就容易多了。
CDistributedQueue類的各個操作的詳細源代碼參見CAPI開源項目中的CDistributedQueue.h。
當前題目：多核分布式隊列的實現(xiàn)：“偷”與“自私”的運用
文章起源：http://www.dlmjj.cn/article/cohopch.html
