一、整體設(shè)計(jì)

1、需求分析

池化技術(shù)是計(jì)算機(jī)中的一種設(shè)計(jì)模式，內(nèi)存池是常見的池化技術(shù)之一，它能夠有效的提高內(nèi)存的申請(qǐng)和釋放效率以及內(nèi)存碎片等問(wèn)題，但是傳統(tǒng)的內(nèi)存池也存在一定的缺陷，高并發(fā)內(nèi)存池相對(duì)于普通的內(nèi)存池它有自己的獨(dú)特之處，解決了傳統(tǒng)內(nèi)存池存在的一些問(wèn)題。

附：實(shí)現(xiàn)一個(gè)內(nèi)存池管理的類方法

1）直接使用new/delete、malloc/free存在的問(wèn)題

new/delete用于c++中動(dòng)態(tài)內(nèi)存管理而malloc/free在c++和c中都可以使用，本質(zhì)上new/delete底層封裝了malloc/free。無(wú)論是上面的那種內(nèi)存管理方式，都存在以下兩個(gè)問(wèn)題：

• 效率問(wèn)題：頻繁的在堆上申請(qǐng)和釋放內(nèi)存必然需要大量時(shí)間，降低了程序的運(yùn)行效率。對(duì)于一個(gè)需要頻繁申請(qǐng)和釋放內(nèi)存的程序來(lái)說(shuō)，頻繁調(diào)用new/malloc申請(qǐng)內(nèi)存,delete/free釋放內(nèi)存都需要花費(fèi)系統(tǒng)時(shí)間，頻繁的調(diào)用必然會(huì)降低程序的運(yùn)行效率。
• 內(nèi)存碎片：經(jīng)常申請(qǐng)小塊內(nèi)存，會(huì)將物理內(nèi)存“切”得很碎，導(dǎo)致內(nèi)存碎片。申請(qǐng)內(nèi)存的順序并不是釋放內(nèi)存的順序，因此頻繁申請(qǐng)小塊內(nèi)存必然會(huì)導(dǎo)致內(nèi)存碎片，造成“有內(nèi)存但是申請(qǐng)不到大塊內(nèi)存”的現(xiàn)象。

2）普通內(nèi)存池的優(yōu)點(diǎn)和缺點(diǎn)

針對(duì)直接使用new/delete、malloc/free存在的問(wèn)題，普通內(nèi)存池的設(shè)計(jì)思路是：預(yù)先開辟一塊大內(nèi)存，程序需要內(nèi)存時(shí)直接從該大塊內(nèi)存中“拿”一塊，提高申請(qǐng)和釋放內(nèi)存的效率，同時(shí)直接分配大塊內(nèi)存還減少了內(nèi)存碎片問(wèn)題。

優(yōu)點(diǎn)：申請(qǐng)和釋放內(nèi)存的效率有所提高；一定程度上解決了內(nèi)存碎片問(wèn)題。

缺點(diǎn)：多線程并發(fā)場(chǎng)景下申請(qǐng)和釋放內(nèi)存存在鎖競(jìng)爭(zhēng)問(wèn)題造成申請(qǐng)和釋放內(nèi)存的效率降低。

3）高并發(fā)內(nèi)存池要解決的問(wèn)題

基于以上原因，設(shè)計(jì)高并發(fā)內(nèi)存池需要解決以下三個(gè)問(wèn)題：

• 效率問(wèn)題
• 內(nèi)存碎片問(wèn)題
• 多線程并發(fā)場(chǎng)景下的內(nèi)存釋放和申請(qǐng)的鎖競(jìng)爭(zhēng)問(wèn)題。

2、總體設(shè)計(jì)思路

高并發(fā)內(nèi)存池整體框架由以下三部分組成，各部分的功能如下：

• 線程緩存（thread cache）：每個(gè)線程獨(dú)有線程緩存，主要解決多線程下高并發(fā)運(yùn)行場(chǎng)景線程之間的鎖競(jìng)爭(zhēng)問(wèn)題。線程緩存模塊可以為線程提供小于64k內(nèi)存的分配，并且多個(gè)線程并發(fā)運(yùn)行不需要加鎖。
• 中心控制緩存（central control cache）：中心控制緩存顧名思義，是高并發(fā)內(nèi)存池的中心結(jié)構(gòu)主要用來(lái)控制內(nèi)存的調(diào)度問(wèn)題。負(fù)責(zé)大塊內(nèi)存切割分配給線程緩存以及回收線程緩存中多余的內(nèi)存進(jìn)行合并歸還給頁(yè)緩存，達(dá)到內(nèi)存分配在多個(gè)線程中更均衡的按需調(diào)度的目的，它在整個(gè)項(xiàng)目中起著承上啟下的作用。（注意：這里需要加鎖，當(dāng)多個(gè)線程同時(shí)向中心控制緩存申請(qǐng)或歸還內(nèi)存時(shí)就存在線程安全問(wèn)題，但是這種情況是極少發(fā)生的，并不會(huì)對(duì)程序的效率產(chǎn)生較大的影響，總體來(lái)說(shuō)利大于弊）
• 頁(yè)緩存（page cache）：以頁(yè)為單位申請(qǐng)內(nèi)存，為中心控制緩存提供大塊內(nèi)存。當(dāng)中心控制緩存中沒有內(nèi)存對(duì)象時(shí)，可以從page cache中以頁(yè)為單位按需獲取大塊內(nèi)存，同時(shí)page cache還會(huì)回收central control cache的內(nèi)存進(jìn)行合并緩解內(nèi)存碎片問(wèn)題。

3、申請(qǐng)內(nèi)存流程圖

二、詳細(xì)設(shè)計(jì)

1、各個(gè)模塊內(nèi)部結(jié)構(gòu)詳細(xì)剖析

1）thread cache

邏輯結(jié)構(gòu)設(shè)計(jì)

thread cache的主要功能就是為每一個(gè)線程提供64K以下大小內(nèi)存的申請(qǐng)。為了方便管理，需要提供一種特定的管理模式，來(lái)保存未分配的內(nèi)存以及被釋放回來(lái)的內(nèi)存，以方便內(nèi)存的二次利用。這里的管理通常采用將不同大小的內(nèi)存映射在哈希表中，鏈接起來(lái)。而內(nèi)存分配的最小單位是字節(jié)，64k = 1024*64Byte如果按照一個(gè)字節(jié)一個(gè)字節(jié)的管理方式進(jìn)行管理，至少也得需要1024*64大小的哈希表對(duì)不同大小的內(nèi)存進(jìn)行映射。為了減少哈希表長(zhǎng)度，這里采用按一定數(shù)字對(duì)齊的方式進(jìn)行內(nèi)存分配，將浪費(fèi)率保持在1%~12%之間。具體結(jié)構(gòu)如下：

具體說(shuō)明如下：

• 使用數(shù)組進(jìn)行哈希映射，每一個(gè)位置存放的是一個(gè)鏈表freelists，該鏈表的作用是將相同大小的內(nèi)存對(duì)象鏈接起來(lái)方便管理。
• 每個(gè)數(shù)組元素鏈接的都是不同大小的內(nèi)存對(duì)象。
• 第一個(gè)元素表示對(duì)齊數(shù)是8，第2個(gè)是16....依次類推。對(duì)齊數(shù)表示在上一個(gè)對(duì)齊數(shù)和這個(gè)對(duì)齊數(shù)之間的大小的內(nèi)存都映射在這個(gè)位置，即要申請(qǐng)1字節(jié)或者7字節(jié)的內(nèi)存都在索引位置為0出找8字節(jié)大小的內(nèi)存，要申請(qǐng)9~16字節(jié)大小的內(nèi)存都在索引為1的位置找16字節(jié)的內(nèi)存對(duì)象。
• 通過(guò)上面的分析，可以看出如果進(jìn)行8字節(jié)對(duì)齊，最多會(huì)浪費(fèi)7字節(jié)的內(nèi)存（實(shí)際申請(qǐng)1字節(jié)內(nèi)存，返回的是8字節(jié)大小的內(nèi)存對(duì)象）,將這種現(xiàn)象稱為內(nèi)存碎片浪費(fèi)。
• 為了將內(nèi)存碎片浪費(fèi)保持在12%以下，也就是說(shuō)最多容忍有12%的內(nèi)存浪費(fèi)，這里使用不同的對(duì)齊數(shù)進(jìn)行對(duì)齊。
• 0~128采用8字節(jié)對(duì)齊，129~1024采用16字節(jié)對(duì)齊，1025~8*1024采用128字節(jié)對(duì)齊，8*1024~64*1024采用1024字節(jié)對(duì)齊；內(nèi)存碎片浪費(fèi)率分別為：1/8，129/136，1025/1032，8102/8199均在12%左右。同時(shí)，8字節(jié)對(duì)齊時(shí)需要[0,15]共16個(gè)哈希映射；16字節(jié)對(duì)齊需要[16,71]共56個(gè)哈希映射；128字節(jié)對(duì)齊需要[72,127]共56個(gè)哈希映射;1024字節(jié)對(duì)齊需要[128,184]共56個(gè)哈希映射。
• 哈希映射的結(jié)構(gòu)如下：

如何保證每個(gè)線程獨(dú)有？

TLS(Thread Local Stirage)

大于64k的內(nèi)存如何申請(qǐng)？

當(dāng)thread cache中申請(qǐng)的內(nèi)存大于64K時(shí)，直接向page cache申請(qǐng)。但是page cache中最大也只能申請(qǐng)128頁(yè)的內(nèi)存，所以當(dāng)thread cache申請(qǐng)的內(nèi)存大于128頁(yè)時(shí)page cache中會(huì)自動(dòng)給thread cache在系統(tǒng)內(nèi)存中申請(qǐng)。

2）central control cache

central control cache作為thread cache和page cache的溝通橋梁，起到承上啟下的作用。它需要向thread cache提供切割好的小塊內(nèi)存，同時(shí)他還需要回收thread cache中的多余內(nèi)存進(jìn)行合并，在分配給其他其他thread cache使用，起到資源調(diào)度的作用。它的結(jié)構(gòu)如下：

具體說(shuō)明如下：

• central control cache的結(jié)構(gòu)依然是一個(gè)數(shù)組，他保存的是span類型的對(duì)象。
• span是用來(lái)管理一塊內(nèi)存的，它里邊包含了一個(gè)freelist鏈表，用于將大塊內(nèi)存切割成指定大小的小塊內(nèi)存鏈接到freelist中，當(dāng)thread cache需要內(nèi)存時(shí)直接將切割好的內(nèi)存給thread cache。
• 開始時(shí)，每個(gè)數(shù)組索引位置都是空的，當(dāng)thread cache申請(qǐng)內(nèi)存時(shí)，spanList數(shù)組會(huì)向page cache申請(qǐng)一大塊內(nèi)存進(jìn)行切割后掛在list中。當(dāng)該快內(nèi)存使用完，會(huì)繼續(xù)申請(qǐng)新的內(nèi)存，因此就存在多個(gè)span鏈接的情況。前邊span存在對(duì)象是因?yàn)橛锌赡芎筮呉呀?jīng)申請(qǐng)好內(nèi)存了前邊的內(nèi)存也釋放回來(lái)了。
• 當(dāng)某一個(gè)span的全部?jī)?nèi)存都還回來(lái)時(shí)，central control cache會(huì)再次將這塊內(nèi)存合并，在歸還到page cache中。
• 當(dāng)central control cache為空時(shí)，向page cache申請(qǐng)內(nèi)存，每次至少申請(qǐng)一頁(yè)，并且必須以頁(yè)為單位進(jìn)行申請(qǐng)（這里的頁(yè)大小由我們自己決定，這里采用4K）。

這里需要注意的是，thread cache可能會(huì)有多個(gè)，但是central control cache只有一個(gè)，要讓多個(gè)thread cache對(duì)象訪問(wèn)一個(gè)central control cache對(duì)象，這里的central control cache需要設(shè)計(jì)成單例模式。

3）page cache

page cache是以頁(yè)為單位進(jìn)行內(nèi)存管理的，它是將不同頁(yè)數(shù)的內(nèi)存利用哈希進(jìn)行映射，最多映射128頁(yè)內(nèi)存，具體結(jié)構(gòu)如下：

page Cache申請(qǐng)和釋放內(nèi)存流程：

• 當(dāng)central control cache向page cache申請(qǐng)內(nèi)存時(shí)，比如要申請(qǐng)8頁(yè)的內(nèi)存，它會(huì)先在span大小為8的位置找，如果沒有就繼續(xù)找9 10...128，那個(gè)有就從那個(gè)中切割8頁(yè)。
• 例如，走到54時(shí)才有內(nèi)存，就從54處切8頁(yè)返回給central control cache，將剩余的54-846頁(yè)掛在46頁(yè)處。
• 當(dāng)page cache中沒有內(nèi)存時(shí)，它直接申請(qǐng)一個(gè)128頁(yè)的內(nèi)存掛在128位置。當(dāng)central control cache申請(qǐng)內(nèi)存時(shí)再?gòu)?28頁(yè)切。

2、設(shè)計(jì)細(xì)節(jié)

1）thread cache

根據(jù)申請(qǐng)內(nèi)存大小計(jì)算對(duì)應(yīng)的_freelists索引

• 1~8都映射在索引為0處，9~16都在索引為2處......
• 因此以8字節(jié)對(duì)齊時(shí)，可以表示為：((size + (2^3 - 1)) >> 3) - 1;
• 如果申請(qǐng)的內(nèi)存為129，索引如何計(jì)算？
• 首先前128字節(jié)是按照8字節(jié)對(duì)齊的，因此：((129-128）+（2^4-1))>>4)-1 + 16
• 上式中16表示索引為0~15的16個(gè)位置以8字節(jié)對(duì)齊。

代碼實(shí)現(xiàn)：

//根據(jù)內(nèi)存大小和對(duì)齊數(shù)計(jì)算對(duì)應(yīng)下標(biāo)
static inline size_t _Intex(size_t size, size_t alignmentShift)
{
	//alignmentShift表示對(duì)齊數(shù)的位數(shù)，例如對(duì)齊數(shù)為8 = 2^3時(shí)，aligmentShift = 3
	//這樣可以將除法轉(zhuǎn)化成>>運(yùn)算，提高運(yùn)算效率
	return ((size + (1 << alignmentShift) - 1) >> alignmentShift) - 1;
}
//根據(jù)內(nèi)存大小，計(jì)算對(duì)應(yīng)的下標(biāo)
static inline size_t Index(size_t size)
{
	assert(size <= THREAD_MAX_SIZE);
 
	//每個(gè)對(duì)齊數(shù)對(duì)應(yīng)的索引個(gè)數(shù)，分別表示8 16 128 1024字節(jié)對(duì)齊
	int groupArray[4] = {16,56,56,56};
 
	if (size <= 128)
	{
		//8字節(jié)對(duì)齊
		return _Intex(size, 3) + groupArray[0];
	}
	else if (size <= 1024)
	{
		//16字節(jié)對(duì)齊
		return _Intex(size, 4) + groupArray[1];
	}
	else if (size <= 8192)
	{
		//128字節(jié)對(duì)齊
		return _Intex(size, 7) + groupArray[2];
	}
	else if (size <= 65536)
	{
		//1024字節(jié)對(duì)齊
		return _Intex(size, 10) + groupArray[3];
	}
 
	assert(false);
	return -1;
}

freelist向中心緩存申請(qǐng)內(nèi)存時(shí)需要對(duì)申請(qǐng)的內(nèi)存大小進(jìn)行對(duì)齊

首先，需要申請(qǐng)的內(nèi)存大小不夠?qū)R數(shù)時(shí)都需要進(jìn)行向上對(duì)齊。即，要申請(qǐng)的內(nèi)存大小為1字節(jié)時(shí)需要對(duì)齊到8字節(jié)。如何對(duì)齊？不進(jìn)行對(duì)齊可以嗎？

首先，不進(jìn)行對(duì)齊也可以計(jì)算出freelist索引，當(dāng)?shù)谝淮紊暾?qǐng)內(nèi)存時(shí)，freelist的索引位置切割后的內(nèi)存大小就是實(shí)際申請(qǐng)的內(nèi)存大小，并沒有進(jìn)行對(duì)齊，造成內(nèi)存管理混亂。對(duì)齊方式如下：

• 對(duì)齊數(shù)分別為8 = 2^3; 16 = 2^4 ; 128 = 2^7 ; 1024 = 2^10,轉(zhuǎn)化成二進(jìn)制后只有1個(gè)1.
• 在對(duì)齊區(qū)間內(nèi)，所有數(shù)+對(duì)齊數(shù)-1后一定是大于等于當(dāng)前區(qū)間的最大值且小于下一個(gè)相鄰區(qū)間的最大值。
• 因此，size + 對(duì)齊數(shù) - 1如果是8字節(jié)對(duì)齊只需將低3位變?yōu)?，如果是16字節(jié)對(duì)齊將低3位變?yōu)?......
• 例如：size = 2時(shí)，對(duì)齊數(shù)為8；則size + 8 - 1 = 9，轉(zhuǎn)為而進(jìn)制位1001，將低三位變?yōu)?后為1000，轉(zhuǎn)為十進(jìn)制就是對(duì)齊數(shù)8.

代碼表示如下：alignment表示對(duì)齊數(shù)

(size + alignment - 1) & ~(alignment - 1);

注意：向這些小函數(shù)，定義成inline可以減少壓棧開銷。 ‘

如何將小塊內(nèi)存對(duì)象“掛在”freelist鏈表中

哈哈，前邊已經(jīng)為這里做好鋪墊了。前邊規(guī)定單個(gè)對(duì)象大小最小為8字節(jié)，32位系統(tǒng)下一個(gè)指針的大小為4字節(jié)，64位機(jī)器下一個(gè)指針的大小為8字節(jié)。前邊我們規(guī)定單個(gè)對(duì)象最小大小為8字節(jié)就是為了無(wú)論是在32位系統(tǒng)下還是在64位系統(tǒng)下，都可以保存一個(gè)指針將小塊對(duì)象鏈接起來(lái)。那么，如何使用一小塊內(nèi)存保存指針？

直接在內(nèi)存的前4/8個(gè)字節(jié)將下一塊內(nèi)存的地址保存，取內(nèi)存時(shí)直接對(duì)該內(nèi)存解引用就可以取出地址。

訪問(wèn)：*(void**)(mem)

每次從freelist中取內(nèi)存或者歸還內(nèi)存時(shí)，直接進(jìn)行頭插或頭刪即可。

從central control cache中申請(qǐng)內(nèi)存，一次申請(qǐng)多少合適呢？

這里的思路是采用“慢啟動(dòng)”的方式申請(qǐng)，即第一次申請(qǐng)申請(qǐng)一個(gè)，第二次申請(qǐng)2個(gè)....當(dāng)達(dá)到一定大小（512個(gè)）時(shí)不再增加。這樣做的好處是，第一次申請(qǐng)給的數(shù)量少可以防止某些線程只需要一個(gè)多給造成浪費(fèi)，后邊給的多可以減少?gòu)腸entral control cache的次數(shù)從而提高效率。

當(dāng)使用慢啟動(dòng)得到的期望內(nèi)存對(duì)象個(gè)數(shù)大于當(dāng)前central control cache中內(nèi)存對(duì)象的個(gè)數(shù)時(shí)，有多少給多少。因?yàn)椋瑢?shí)際上目前只需要一個(gè)，我們多申請(qǐng)了不夠，那就有多少給多少。當(dāng)一個(gè)都沒有的時(shí)候才會(huì)去page cache申請(qǐng)。

什么時(shí)候thread cache將內(nèi)存還給central controlcache？

當(dāng)一個(gè)線程將內(nèi)存還給thread cache時(shí)，會(huì)去判斷對(duì)應(yīng)的_freelist的對(duì)應(yīng)位置是否有太多的內(nèi)存還回來(lái)（thread cache中內(nèi)存對(duì)象的大小大于等于最個(gè)數(shù)的時(shí)候，就向central control cache還）。

2）Central Control Cache

SpanList結(jié)構(gòu)

SpanList在central control cache中最重要的作用就是對(duì)大塊內(nèi)存管理，它存儲(chǔ)的是一個(gè)個(gè)span類的對(duì)象，使用鏈表進(jìn)行管理。結(jié)構(gòu)如下：

也就是說(shuō)，SpanList本質(zhì)上就是一個(gè)span鏈表。這里考慮到后邊歸還內(nèi)存需要找到對(duì)應(yīng)頁(yè)歸還，方便插入，這里將spanlist設(shè)置成雙向帶頭循環(huán)鏈表。

Span結(jié)構(gòu)

Span存儲(chǔ)的是大塊內(nèi)存的信息，陪SpanList共同管理大塊內(nèi)存，它的內(nèi)存單位是頁(yè)（4K）。它的結(jié)構(gòu)實(shí)際上就是一個(gè)個(gè)size大小的對(duì)象鏈接起來(lái)的鏈表。它同時(shí)也作為SpanList的節(jié)點(diǎn)，spanList是雙向循環(huán)鏈表，因此span中還有next和prev指針。

struct Span
{
PageID _pageId = 0; // 頁(yè)號(hào)
size_t _n = 0; // 頁(yè)的數(shù)量

Span* _next = nullptr;
Span* _prev = nullptr;

void* _list = nullptr; // 大塊內(nèi)存切小鏈接起來(lái)，這樣回收回來(lái)的內(nèi)存也方便鏈接
size_t _usecount = 0; // 使用計(jì)數(shù)，==0 說(shuō)明所有對(duì)象都回來(lái)了

size_t _objsize = 0; // 切出來(lái)的單個(gè)對(duì)象的大小
};

當(dāng)spanList中沒有內(nèi)存時(shí)需要向PageCache申請(qǐng)內(nèi)存，一次申請(qǐng)多少合適呢？

根據(jù)申請(qǐng)的對(duì)象的大小分配內(nèi)存，也就是說(shuō)單個(gè)對(duì)象大小越小分配的頁(yè)數(shù)越少，單個(gè)對(duì)象的大小越大分配到的內(nèi)存越多。如何衡量多少？

這里我們是通過(guò)thread cache中從central control cache中獲取的內(nèi)存對(duì)象的個(gè)數(shù)的上限來(lái)確定。也就是說(shuō)，個(gè)數(shù)的上限*內(nèi)存對(duì)象的大小就是我們要申請(qǐng)的內(nèi)存的大小。在右移12位（1頁(yè)）就是需要申請(qǐng)的頁(yè)數(shù)。

//計(jì)算申請(qǐng)多少頁(yè)內(nèi)存
static inline size_t NumMovePage(size_t memSize)
{
	//計(jì)算thread cache最多申請(qǐng)多少個(gè)對(duì)象，這里就給多少個(gè)對(duì)象
	size_t num = NumMoveSize(memSize);
	//此時(shí)的nPage表示的是獲取的內(nèi)存大小
	size_t nPage = num*memSize;
	//當(dāng)npage右移是PAGE_SHIFT時(shí)表示除2的PAGE_SHIFT次方，表示的就是頁(yè)數(shù)
	nPage >>= PAGE_SHIFT;
 
	//最少給一頁(yè)（體現(xiàn)了按頁(yè)申請(qǐng)的原則）
	if (nPage == 0)
		nPage = 1;
 
	return nPage;
}

向central control cache申請(qǐng)一塊內(nèi)存，切割時(shí)如果最后產(chǎn)生一個(gè)碎片（不夠一個(gè)對(duì)象大小的內(nèi)存）如何處理？

一旦產(chǎn)生這種情況，最后的碎片內(nèi)存只能丟棄不使用。但是對(duì)于我們的程序來(lái)說(shuō)是不會(huì)產(chǎn)生的，因?yàn)槲覀兠看紊暾?qǐng)至少一頁(yè)，4096可以整除我們所對(duì)應(yīng)的任何一個(gè)大小的對(duì)象。

central control cache何時(shí)將內(nèi)存還給page cache？

thread cache將多余的內(nèi)存會(huì)還給central control cache中的spanlist對(duì)應(yīng)的span，span中有一個(gè)usecount用來(lái)統(tǒng)計(jì)該span中有多少個(gè)對(duì)象被申請(qǐng)走了，當(dāng)usecount為0時(shí)，表示所有對(duì)象都還回來(lái)了，則將該span還給page cache，合并成更大的span。

3）Page Cache

當(dāng)從一個(gè)大頁(yè)切出一個(gè)小頁(yè)內(nèi)存時(shí)，剩余的內(nèi)存如何掛在對(duì)應(yīng)位置？

在Page cache中的span它是沒有切割的，都是一個(gè)整頁(yè)，也就是說(shuō)這里的Span的list并沒有使用到。這里計(jì)算內(nèi)存的地址都是按照頁(yè)號(hào)計(jì)算的，當(dāng)一個(gè)Span中有多頁(yè)內(nèi)存時(shí)保存的是第一頁(yè)的內(nèi)存，那么就可以計(jì)算出剩余內(nèi)存和切走內(nèi)存的頁(yè)號(hào)，設(shè)置相應(yīng)的頁(yè)號(hào)進(jìn)行映射即可。

從一個(gè)大的Span中切時(shí)，采用頭切還是尾切？

Span中如何通過(guò)頁(yè)號(hào)計(jì)算地址？

每一頁(yè)大小都是固定的，當(dāng)我們從系統(tǒng)申請(qǐng)一塊內(nèi)存會(huì)返回該內(nèi)存的首地址，申請(qǐng)內(nèi)存時(shí)返回的都是一塊連續(xù)的內(nèi)存，所以我們可以使用內(nèi)存首地址/頁(yè)大小的方式計(jì)算出頁(yè)號(hào)，通過(guò)這種方式計(jì)算出來(lái)的一大塊內(nèi)存的多個(gè)頁(yè)的頁(yè)號(hào)都是連續(xù)的。

Page Cache向系統(tǒng)申請(qǐng)內(nèi)存

Page Cache向系統(tǒng)申請(qǐng)內(nèi)存時(shí)，前邊我們說(shuō)過(guò)每次直接申請(qǐng)128頁(yè)的內(nèi)存。這里需要說(shuō)明的是，我們的項(xiàng)目中不能出現(xiàn)任和STL中的數(shù)據(jù)結(jié)構(gòu)和庫(kù)函數(shù)，因此這里申請(qǐng)內(nèi)存直接采用系統(tǒng)調(diào)用VirtualAlloc。下面對(duì)VirtualAlloc詳細(xì)解釋：

VirtualAlloc是一個(gè)Windows API函數(shù)，該函數(shù)的功能是在調(diào)用進(jìn)程的虛地址空間,預(yù)定或者提交一部分頁(yè)。簡(jiǎn)單點(diǎn)的意思就是申請(qǐng)內(nèi)存空間。

函數(shù)聲明如下：

LPVOID VirtualAlloc{
LPVOID lpAddress, // 要分配的內(nèi)存區(qū)域的地址

DWORD dwSize, // 分配的大小

DWORD flAllocationType, // 分配的類型

DWORD flProtect // 該內(nèi)存的初始保護(hù)屬性

};

參數(shù)說(shuō)明：

• LPVOID lpAddress, 分配內(nèi)存區(qū)域的地址。當(dāng)你使用VirtualAlloc來(lái)提交一塊以前保留的內(nèi)存塊的時(shí)候，lpAddress參數(shù)可以用來(lái)識(shí)別以前保留的內(nèi)存塊。如果這個(gè)參數(shù)是NULL，系統(tǒng)將會(huì)決定分配內(nèi)存區(qū)域的位置，并且按64-KB向上取整(roundup)。
• SIZE_T dwSize, 要分配或者保留的區(qū)域的大小。這個(gè)參數(shù)以字節(jié)為單位，而不是頁(yè)，系統(tǒng)會(huì)根據(jù)這個(gè)大小一直分配到下頁(yè)的邊界DWORD
• flAllocationType, 分配類型 ,你可以指定或者合并以下標(biāo)志：MEM_COMMIT，MEM_RESERVE和MEM_TOP_DOWN。
• DWORD flProtect 指定了被分配區(qū)域的訪問(wèn)保護(hù)方式

注：PageCache中有一個(gè)map用來(lái)存儲(chǔ)pageId和Span的映射。在釋放內(nèi)存時(shí)，通過(guò)memSize計(jì)算出pageId，在通過(guò)PageId在map中查找對(duì)應(yīng)的Span從而就可以獲得單個(gè)對(duì)象的大小，在根據(jù)單個(gè)對(duì)象的大小確定是要將內(nèi)存還給page cache還是還給central control cache。

central control cache釋放回來(lái)的內(nèi)存如何合并成大內(nèi)存？

通過(guò)span中的頁(yè)號(hào)查找前一頁(yè)和后一頁(yè)，判斷前一頁(yè)和后一頁(yè)是否空閑（沒有被申請(qǐng)的內(nèi)存），如果空閑就進(jìn)行和并，合并完后重新在map中進(jìn)行映射。

注意：將PageCache和CentralControlCache設(shè)置成單例模式，因?yàn)槎鄠€(gè)線程對(duì)同時(shí)使用一個(gè)page cache和central control cache進(jìn)行內(nèi)存管理。

單例模式簡(jiǎn)單介紹

• 單例模式，顧名思義只能創(chuàng)建一個(gè)實(shí)例。
• 有兩種實(shí)現(xiàn)方式：懶漢實(shí)現(xiàn)和餓漢實(shí)現(xiàn)
• 做法：將構(gòu)造函數(shù)和拷貝構(gòu)造函數(shù)定義成私有且不能默認(rèn)生成，防止在類外構(gòu)造對(duì)象；定義一個(gè)本身類型的成員，在類中構(gòu)造一個(gè)對(duì)象，提供接口供外部調(diào)用。

4）加鎖問(wèn)題

• 在central control cache和page cache中都存在多個(gè)線程訪問(wèn)同一臨界資源的情況，因此需要加鎖。
• 在central control cache中，不同線程只要訪問(wèn)的不是同一個(gè)大小的內(nèi)存對(duì)象，則就不需要加鎖，可以提高程序的運(yùn)行效率（加鎖后就有可能導(dǎo)致線程掛起等待），也就是說(shuō)central control cache中是“桶鎖”。需要改freelist那個(gè)位置的內(nèi)存，就對(duì)那個(gè)加鎖。
• page cache中，需要對(duì)申請(qǐng)和合并內(nèi)存進(jìn)行加鎖。
• 這里我們統(tǒng)一使用互斥鎖。

注意：使用map進(jìn)行映射，雖然說(shuō)我們對(duì)pagecache進(jìn)行了加鎖，不會(huì)早成寫數(shù)據(jù)的沖突，但是我們還向外提供了查找的接口，就有可能導(dǎo)致一個(gè)線程在向map中寫而另一個(gè)線程又查找，出現(xiàn)線程安全問(wèn)題，但是如果給查找位置加鎖，這個(gè)接口會(huì)被頻繁的調(diào)用，造成性能的損失。而在tcmalloc中采用基數(shù)樹來(lái)存儲(chǔ)pageId和span的映射關(guān)系，從而提高效率。

附：基數(shù)樹

三、測(cè)試

1、單元測(cè)試

void func1()
{
	for (size_t i = 0; i < 10; ++i)
	{
		hcAlloc(17);
	}
}
 
void func2()
{
	for (size_t i = 0; i < 20; ++i)
	{
		hcAlloc(5);
	}
}
 
//測(cè)試多線程
void TestThreads()
{
	std::thread t1(func1);
	std::thread t2(func2);
 
 
	t1.join();
	t2.join();
}
 
//計(jì)算索引
void TestSizeClass()
{
	cout << SizeClass::Index(1035) << endl;
	cout << SizeClass::Index(1025) << endl;
	cout << SizeClass::Index(1024) << endl;
}
 
//申請(qǐng)內(nèi)存
void TestConcurrentAlloc()
{
	void* ptr0 = hcAlloc(5);
	void* ptr1 = hcAlloc(8);
	void* ptr2 = hcAlloc(8);
	void* ptr3 = hcAlloc(8);
 
	hcFree(ptr1);
	hcFree(ptr2);
	hcFree(ptr3);
}
 
//大塊內(nèi)存的申請(qǐng)
void TestBigMemory()
{
	void* ptr1 = hcAlloc(65 * 1024);
	hcFree(ptr1);
 
	void* ptr2 = hcAlloc(129 * 4 * 1024);
	hcFree(ptr2);
}
 
//int main()
//{
//	//TestBigMemory();
//
//	//TestObjectPool();
//	//TestThreads();
//	//TestSizeClass();
//	//TestConcurrentAlloc();
//
//	return 0;
//}

2、性能測(cè)試

void BenchmarkMalloc(size_t ntimes, size_t nworks, size_t rounds)
{
	//創(chuàng)建nworks個(gè)線程
	std::vector<std::thread> vthread(nworks);
	size_t malloc_costtime = 0;
	size_t free_costtime = 0;
 
	//每個(gè)線程循環(huán)依次
	for (size_t k = 0; k < nworks; ++k)
	{
		//鋪貨k
		vthread[k] = std::thread([&, k]() {
			std::vector<void*> v;
			v.reserve(ntimes);
 
			//執(zhí)行rounds輪次
			for (size_t j = 0; j < rounds; ++j)
			{
				size_t begin1 = clock();
				//每輪次執(zhí)行ntimes次
				for (size_t i = 0; i < ntimes; i++)
				{
					v.push_back(malloc(16));
				}
				size_t end1 = clock();
 
				size_t begin2 = clock();
				for (size_t i = 0; i < ntimes; i++)
				{
					free(v[i]);
				}
				size_t end2 = clock();
				v.clear();
 
				malloc_costtime += end1 - begin1;
				free_costtime += end2 - begin2;
			}
		});
	}
 
	for (auto& t : vthread)
	{
		t.join();
	}
 
	printf("%u個(gè)線程并發(fā)執(zhí)行%u輪次，每輪次malloc %u次: 花費(fèi)：%u ms\n",
		nworks, rounds, ntimes, malloc_costtime);
 
	printf("%u個(gè)線程并發(fā)執(zhí)行%u輪次，每輪次free %u次: 花費(fèi)：%u ms\n",
		nworks, rounds, ntimes, free_costtime);
 
	printf("%u個(gè)線程并發(fā)malloc&free %u次，總計(jì)花費(fèi)：%u ms\n",
		nworks, nworks*rounds*ntimes, malloc_costtime + free_costtime);
}
 
 
// 單輪次申請(qǐng)釋放次數(shù) 線程數(shù) 輪次
void BenchmarkConcurrentMalloc(size_t ntimes, size_t nworks, size_t rounds)
{
	std::vector<std::thread> vthread(nworks);
	size_t malloc_costtime = 0;
	size_t free_costtime = 0;
 
	for (size_t k = 0; k < nworks; ++k)
	{
		vthread[k] = std::thread([&]() {
			std::vector<void*> v;
			v.reserve(ntimes);
 
			for (size_t j = 0; j < rounds; ++j)
			{
				size_t begin1 = clock();
				for (size_t i = 0; i < ntimes; i++)
				{
					v.push_back(hcAlloc(16));
				}
				size_t end1 = clock();
 
				size_t begin2 = clock();
				for (size_t i = 0; i < ntimes; i++)
				{
					hcFree(v[i]);
				}
				size_t end2 = clock();
				v.clear();
 
				malloc_costtime += end1 - begin1;
				free_costtime += end2 - begin2;
			}
		});
	}
 
	for (auto& t : vthread)
	{
		t.join();
	}
 
	printf("%u個(gè)線程并發(fā)執(zhí)行%u輪次，每輪次concurrent alloc %u次: 花費(fèi)：%u ms\n",
		nworks, rounds, ntimes, malloc_costtime);
 
	printf("%u個(gè)線程并發(fā)執(zhí)行%u輪次，每輪次concurrent dealloc %u次: 花費(fèi)：%u ms\n",
		nworks, rounds, ntimes, free_costtime);
 
	printf("%u個(gè)線程并發(fā)concurrent alloc&dealloc %u次，總計(jì)花費(fèi)：%u ms\n",
		nworks, nworks*rounds*ntimes, malloc_costtime + free_costtime);
}
 
int main()
{
	cout << "==========================================================" << endl;
	BenchmarkMalloc(100000, 4, 10);
	cout << endl << endl;
 
	BenchmarkConcurrentMalloc(100000, 4, 10);
	cout << "==========================================================" << endl;
 
	return 0;
}

結(jié)果比較

附1：完整代碼

到此這篇關(guān)于C++高并發(fā)內(nèi)存池的整體設(shè)計(jì)和實(shí)現(xiàn)思路的文章就介紹到這了,更多相關(guān)C++高并發(fā)內(nèi)存池內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！