亚洲av成人无遮挡网站在线观看,少妇性bbb搡bbb爽爽爽,亚洲av日韩精品久久久久久,兔费看少妇性l交大片免费,无码少妇一区二区三区

<nobr id="szcuc"></nobr>

Chinaunix

標(biāo)題: MemoryPool的LockFree實(shí)現(xiàn) [打印本頁(yè)]

作者: softarts 時(shí)間: 2009-04-09 16:34
標(biāo)題: MemoryPool的LockFree實(shí)現(xiàn)
http://blog.csdn.net/softarts/archive/2009/04/08/4056465.aspx

沒事寫了這篇文章，正好看到Intel在搞多核編程征文，就去參加了，麻煩看到的人給投個(gè)票

投票地址：http://intel.csdn.net/multicoreblog/show.aspx?page=1（倒數(shù)第4頁(yè)，謝謝支持）

MemoryPool的LockFree實(shí)現(xiàn)-2009/04/07

MemoryPool已經(jīng)是一個(gè)非常古老的話題了，關(guān)于此方面的文章比比皆是，在Addison-Wesley 1999年出版的<Efficient C++ Performance Programming Techniques > (下面簡(jiǎn)稱Efficient文)中，兩位富有經(jīng)驗(yàn)的作者Dov Bulka, David Mayhew 詳細(xì)講述了如何編寫一個(gè)Multi-Thread的MemoryPool；而JAVA hotspot VM，Share Source CLI源碼中也可見這方面的實(shí)現(xiàn)。就我看來，他們的實(shí)現(xiàn)都大同小異。本文首先簡(jiǎn)單介紹Efficient文中Memory Pool的實(shí)現(xiàn)，然后在此基礎(chǔ)上研究如何使用Lock-Free的機(jī)制去進(jìn)一步改善性能。

<1>Multi-Thread MemoryPool的實(shí)現(xiàn)

以Dov Bulka版本為例,首先簡(jiǎn)單看看一個(gè)最基本的基于對(duì)象的MemoryPool實(shí)現(xiàn)：

MemoryPool的基本思想是將在delete 的對(duì)象的時(shí)候并不真正delete，而是歸還到Pool中，以某種數(shù)據(jù)形式管理起來，在下一次分配對(duì)象內(nèi)存的時(shí)候，先到Pool中尋找，看看有沒有空余的內(nèi)存，如果沒有，在調(diào)用OS的malloc來分配新的內(nèi)存。

MemoryPool的聲明:

template < class T >

class MemoryPool {

public:

MemoryPool (size_t size = EXPANSION_SIZE);

~MemoryPool ();

// Allocate a T element from the free list.

inline void* alloc (size_t size);

// Return a T element to the free list.

inline void free (void *someElement);

private:

// next element on the free list.

MemoryPool<T> *next;

// If the freeList is empty, expand it by this amount.

enum { EXPANSION_SIZE = 32};

// Add free elements to the free list

void expandTheFreeList(int howMany = EXPANSION_SIZE);

};

看看幾個(gè)關(guān)鍵的函數(shù)

分配內(nèi)存:

template < class T >

inline

void* MemoryPool < T > :: alloc (size_t)

{

if (!next) {

      expandTheFreeList();

}

MemoryPool<T> *head = next;

next = head->next;

return head;

}

釋放內(nèi)存，原理是next 指針指向當(dāng)前Pool的可用對(duì)象內(nèi)存鏈表的頭部，在釋放對(duì)象內(nèi)存的時(shí)候，就更新鏈表頭部時(shí)期指向剛釋放的對(duì)象內(nèi)存塊

template < class T >

inline

void MemoryPool < T > :: free (void *doomed)

{

MemoryPool<T> *head = static_cast <MemoryPool<T> *> doomed;

head->next = next;

next  = head;

}

擴(kuò)充內(nèi)存池, 這個(gè)是把新分配的內(nèi)存依次串接到next所在的linked list中

template < class T >

void MemoryPool < T > :: expandTheFreeList(int howMany)

{

// We must allocate an object large enough to contain the

// next pointer.

size_t size = (sizeof(T) > sizeof(MemoryPool<T> *)) ?

      sizeof(T) : sizeof(MemoryPool<T> *);

MemoryPool<T> *runner = static_cast <MemoryPool<T> *> new char [size];

next =  runner;

for (int i = 0; i < howMany ; i++) {

      runner->next =

         static_cast <MemoryPool<T> *> new char [size];

      runner = runner->next;

}

runner->next = 0;

}

<2>MemoryPool的同步機(jī)制

從上面的代碼可見，分配和釋放都可能需要更新FreeList可用鏈表頭部，因此，多線程環(huán)境下需要使用鎖機(jī)制來保護(hù)對(duì)空閑鏈表頭部的修改，很多Linux/GNU 的Multi-Thread Memory Pool實(shí)現(xiàn)都會(huì)使用pthread_mutex_lock，例如SSCLI和JAVA hotspot VM中的實(shí)現(xiàn)。

除開pthread_mutex函數(shù)族外，還有pthread_spin系列也可用于線程同步。這兩者的主要區(qū)別是，如果沒有獲得鎖資源，pthread_mutex會(huì)使線程睡眠，而pthread_spin 顧名思義，則會(huì)反復(fù)嘗試直到取得鎖資源，這樣會(huì)使CPU空轉(zhuǎn)。

Efficient文中提到pthread_mutex是這樣使用的：

class ABCLock {// Abstract base class

public:

virtual ~ABCLock() {}

virtual void lock() = 0;

virtual void unlock() = 0;

};

class MutexLock : public ABCLock {

public:

MutexLock() {pthread_mutex_init(&lock, NULL);}

~MutexLock() {pthread_mutex_destroy(&lock);}

inline void lock() {pthread_mutex_lock(&lock);}

inline void unlock() {pthread_mutex_unlock(&lock);}

private:

pthread_mutex_t lock;

};

在需要保護(hù)臨界信息的地方使用lock()函數(shù)

template <class M, class L>

inline

void* MTMemoryPool<M,L>::alloc (size_t size)

{

void * mem;

theLock.lock();

mem = stPool.alloc(size);

theLock.unlock();

return mem;

}

pthread_spin的自旋鎖特性導(dǎo)致其比較適用一些輕量級(jí)，極短時(shí)間的多核cpu系統(tǒng)上的鎖保護(hù)，在單核cpu上，pthread_spin實(shí)質(zhì)上會(huì)死循環(huán)直到線程時(shí)間片耗盡，從而性能比pthread_mutex大為縮水，一個(gè)測(cè)試中也證明了這一點(diǎn)。

測(cè)試環(huán)境，2個(gè)線程，1個(gè)用于operator new 分配內(nèi)存(通過alloc調(diào)用)，另一個(gè)用operator delete 釋放內(nèi)存(通過free調(diào)用)

表一，2 core 的測(cè)試結(jié)果：

environment
Intel Core 2 Duo CPU    E6850  @ 3.00GHz

average time
MutexLock
SpinLock



Lock()
0.00045
0.00024



Unlock()
0.000185
0.00009919



Alloc()
0.000857
0.0005728



Free()
0.0007549
0.0005512



表二，在single core上，Spinlock 的性能降低。

Environment
nosmp maxcpus=0 Intel Core 2 Duo CPU    E6850  @ 3.00GHz

Average time
MutexLock
SpinLock



Lock()
0.0005167
0.0014



Unlock()
0.000312
0.000246



Alloc()
0.001176
0.002443



Free()
0.001506
0.00396



從表一中可以看到，Lock ( pthread_mutex_lock或者pthread_spin_lock)占用了Alloc() 一半以上的cpu時(shí)間，Dov Bulka和David Mayhew也覺得pthread_mutex太過overweight了，他作了如下假設(shè)，并且給出了一個(gè)AIX上快速鎖的例子：“我們需要的是一個(gè)輕量級(jí)的鎖，假設(shè)正在加鎖的線程還沒有持有鎖，正在解鎖的線程恰巧好是起初加鎖的那個(gè)線程。”這樣的鎖在Linux上并沒有對(duì)應(yīng)的實(shí)現(xiàn)，我們只能采用pthread_spin_trylock 加上 pthread_spin_lock來模仿這樣的過程。

<3>Lock-Free機(jī)制

pthread_spin 雖然足夠輕量，但仍然是一種鎖機(jī)制，線程的運(yùn)行需要依賴于持有鎖的那個(gè)線程。從上面的測(cè)試結(jié)果可以看到，減去Lock/Unlock消耗的時(shí)間，Alloc()真正的cpu時(shí)間大約在0.00083-0.00045-0.000185=0.00022左右，有沒有一種同步方法可以使Alloc的消耗時(shí)間降低到這個(gè)數(shù)值？

在2004年Maged M. Michael那片開創(chuàng)性的文章“Scalable Lock-Free Dynamic Memory Allocation”，采用了Lock-Free機(jī)制的malloc實(shí)現(xiàn)擊敗了目前所有現(xiàn)存的malloc庫(kù)，包括ptmalloc3,hoard等，Lock-Free一時(shí)間成為主流的研究重點(diǎn)。我們也打算采用這種方法來提高Alloc()的性能，不過由于實(shí)現(xiàn)的復(fù)雜性，本文所要介紹的Lock-Free實(shí)現(xiàn)，主要是用于避免在讀寫空閑鏈表頭部的Lock/Unlock帶來的性能損失，MemoryPool采用的lib_malloc仍然是Linux/GNU環(huán)境下的基于Lock/Unlock的ptmalloc實(shí)現(xiàn)。盡管如此，采用Lock-Free的實(shí)現(xiàn)比mutex/spin lock有明顯的性能提高。

嚴(yán)格講,Lock-Free是一套以原子操作為基礎(chǔ)，采用事務(wù)->提交->提交失敗->重試這樣特定編程手法的機(jī)制，它使得正在訪問共享資源的線程不依賴于任何其它線程的調(diào)度和執(zhí)行，并且能夠在有限的步驟內(nèi)完成。

Lock-Free的實(shí)現(xiàn)往往都是通過CAS-Compare And Swap原子操作完成，聲明如下：

CAS(addr,expval,newval) atomically do

if (*addr == expval) {

*addr = newval;

return true;

} else

return false;

Linux上一種典型的實(shí)現(xiàn)是：

inline int CAS(unsigned long *mem,unsigned long newval,unsigned long oldval)

{

  __typeof (*mem) ret;

  __asm __volatile ("lock; cmpxchgl %2, %1"

                  : "=a" (ret), "=m" (*mem)

                  : "r" (newval), "m" (*mem), "0" (oldval));

return (int) ret;

}

以MemoryPool < T > :: alloc (size_t)為例：

….

//更新next指針的內(nèi)容

do {

oldheader = next;

if (oldheader==NULL)

expandTheFreeList();

else

target=oldheader->next;

}

while (CAS(&next,target,oldheader)!=oldheader)

實(shí)際執(zhí)行中，如果next 的值為oldheader，那么就會(huì)更新next的值為target，并返回oldheader，這一過程是原子操作；如果在執(zhí)行CAS指令的時(shí)候，next的內(nèi)容已經(jīng)發(fā)生變化，那么CAS的返回值就不會(huì)等于oldheader,while中的條件為false，程序會(huì)返回重新執(zhí)行oldheader = next，直到next 的值被成功更新。同時(shí)，expandTheFreeList也要作類似的Lock-Free修改，下面的例子中把原先expandTheFreeList的代碼放置到alloc中。

newbuf_head = NULL //note1

do

{

oldheader =(MemoryPool*) next;          //note2

if (!oldheader)

{

   if (!newbuf_head)

   {

         size_t size = (m_sizeofClass > sizeof(MemoryPool *))?m_sizeofClass:sizeof(MemoryPool*);

         MemoryPool *runner = reinterpret_cast<MemoryPool*>(new char[size]);

         newbuf_head  = runner;

         for (int i = 0 ; i < EXPANSION_SIZE; i++)

         {

            runner->next = reinterpret_cast<MemoryPool *>(new char [size]);

            runner =(MemoryPool*) runner->next;

         }

         runner->next = 0;

         newbuf_tail = runner;

   }

}

if (newbuf_head)  //note3

{

      newbuf_tail->next = (MemoryPool*)next;

      target = newbuf_head;

}

else if (oldheader)

{

      target = oldheader;//note4

}

//note5

}while ( CAS((unsigned long*)&next,/*m_freeheader,*/(unsigned long)target->next,(unsigned long)oldheader) !=(int) oldheader);

如果oldheader 為NULL,那么就會(huì)分配一段新的內(nèi)存，頭部為newbuf_head，尾部為newbuf_tail，并且把原先的FreeList頭部掛接到新內(nèi)存的尾部，以新內(nèi)存的頭部作為新的FreeList的頭部去更新next的值。

如果分配內(nèi)存后，CAS執(zhí)行失敗了，這沒關(guān)系，此時(shí)newbuf_head已被置值，因此并不會(huì)再次分配內(nèi)存，程序仍然試圖執(zhí)行上一次執(zhí)行過的路徑。

考慮一種極端情況，起初next指向一個(gè)有效地址(oldheader也指向一個(gè)有效值)，因此程序跳過了分配新內(nèi)存那段(斜體字)，不幸在執(zhí)行到note3處時(shí)，next卻由于另一個(gè)線程分配了內(nèi)存的關(guān)系置為NULL，此時(shí)怎么辦？

答案，CAS操作時(shí)next的內(nèi)容與oldheader不一致，因此CAS失敗，程序再次返回note2處執(zhí)行。

<4>Lock-Free中的ABA問題

承接上面的那一個(gè)極端問題，

線程A在執(zhí)行note2時(shí)的空閑鏈表狀態(tài)如下: A-B-C-D-E-NULL，在執(zhí)行到note5時(shí)，期間發(fā)生了如下事情：

線程B從FreeList中分配了一個(gè)A和B兩個(gè)內(nèi)存塊，F(xiàn)reeList變?yōu)镃-D-E-NULL，但隨后線程B歸還了內(nèi)存塊A，從而FreeList再次變?yōu)锳-C-D-E-NULL。

線程A在執(zhí)行到note5，進(jìn)入CAS臨界操作時(shí)，next的內(nèi)容仍然和note2時(shí)的一致，均指向A，但CAS的第二個(gè)關(guān)鍵參數(shù),target->next 的卻已不是B了！(在note4時(shí)target被設(shè)置為oldheader即A，從而target->next為B)，如果把next更新為B，那么就會(huì)造成程序錯(cuò)誤。

這個(gè)就是Lock-Free與生俱來的ABA問題，CAS無法判斷目標(biāo)內(nèi)容從A變?yōu)锽，然后又變?yōu)锳這種情況，解決的辦法通常是使用一個(gè)額外的tag來記錄這種情況，并且使用CAS2，來同時(shí)檢查tag和目標(biāo)內(nèi)存兩個(gè)值又沒有發(fā)生變化，聲明如下：

bool CAS2 (volatile void * ptr, uint32_t old1, uint32_t old2, uint32_t new1, uint32_t new2)

{

bool ret;

__asm__ __volatile__ ("lock cmpxchg8b (%1) \n\t sete %%al"

      : "=a"(ret)

      : "D"(ptr), "a"(old1), "d"(old2), "b"(new1), "c"(new2)

      : "memory"

;

return ret;

}

CAS2可以用來檢查一個(gè)64 bit長(zhǎng)度的內(nèi)存指并原子交換他們的內(nèi)容。

在某些情況下也可以采用thread specified Pool這種方案，就是每個(gè)線程有其專用的內(nèi)存池，不會(huì)出現(xiàn)兩個(gè)線程同時(shí)在一個(gè)Pool上分配內(nèi)存的情況，這需要額外的空間在分配的對(duì)象中嵌入線程的信息。

<5>Lock-Free的性能

可見Lock-Free的實(shí)現(xiàn)并不算一件太新鮮復(fù)雜的事情，Windows平臺(tái)上早就有了InterlockedCompareExchange之類的函數(shù)，Windows中提供的Slist也是一個(gè)Lock-Free 的linked-list。那么在何種情況下使用Lock-Free能達(dá)到最理想的效果？

Lock-Free機(jī)制在single core上會(huì)取得明顯的性能優(yōu)勢(shì)。所有的CAS操作實(shí)質(zhì)上在CPU微觀世界里是串行執(zhí)行的，由于沒有別的線程干擾，一個(gè)處于運(yùn)行狀態(tài)的線程永遠(yuǎn)不會(huì)發(fā)生CAS操作失敗。

2 cpu core的情況下,一個(gè)線程alloc對(duì)象另一個(gè)線程free對(duì)象內(nèi)存，可能會(huì)導(dǎo)致一個(gè)線程里有少量的CAS失敗，但是與pthread_spin_lock機(jī)制相比，耗時(shí)仍然非常少。究其原因，pthread_spin_lock會(huì)受到鎖粒度的的影響，假如Alloc需要耗時(shí)0.00023秒的話，那么pthread_spin_lock就可能需要消耗同樣的時(shí)間。而CAS是一種盡力處理的機(jī)制，即使在某個(gè)線程里發(fā)生了一個(gè)CAS失敗，一方面程序會(huì)以一個(gè)很細(xì)的粒度馬上重試，另一方面也表明與此同時(shí)另一個(gè)線程成功執(zhí)行了一次CAS操作。

從下表看出，CAS的耗時(shí)僅僅是pthread_mutex_lock的1/10。而整個(gè)alloc的耗時(shí)比較，Lock-Free也只有pthread_mutex版本的1/4。

如果增加alloc/free的線程以及cpu 的數(shù)量，Lock-Free機(jī)制會(huì)由于CAS操作失敗而不斷重復(fù)執(zhí)行do {}while(CAS) 中的代碼，從而導(dǎo)致一定的性能下降。因此，應(yīng)該盡量讓do{}中的代碼寫得簡(jiǎn)短，以保證較高的CAS成功率，其次是針對(duì)特定場(chǎng)景開發(fā)Lock-Free應(yīng)用，例如在多核程序中進(jìn)行pipeline處理，在同一個(gè)地方分配內(nèi)存，在同一個(gè)地方回收內(nèi)存。

Environment
Intel Core 2 Duo CPU    E6850  @ 3.00GHz

average time
MutexLock
SpinLock
Lock-Free


Lock()
0.00045
0.00024
0.000059(CAS)


Unlock()
0.000185
0.00009919
0


Alloc()
0.000857
0.0005728
0.0002425


Free()
0.0007549
0.0005512
0.0002002


<6>參考資料

[1] Maged M. Michael, Scalable Lock-Free Dynamic Memory Allocation http://researchweb.watson.ibm.com/people/m/michael/pldi-2004.pdf

[2] Dov Bulka, David Mayhew, Efficient C++: Performance Programming Techniques

[3] 搜狗實(shí)驗(yàn)室技術(shù)交流文檔 Vol4:2 C10K與高性能程序續(xù)篇

歡迎光臨 Chinaunix (http://72891.cn/)