Arpan Sen, 技術(shù)負責(zé)人, Synapti Computer Aided Design Pvt Ltd
簡介： 代碼的性能優(yōu)化是一項非常重要的工作。經(jīng)常可以看到，采用 C 或 C++ 編寫的、功能正確的軟件
在執(zhí)行時耗費大量的內(nèi)存、時間、或者在最糟的情況下既耗內(nèi)存又費時間。作為一名開發(fā)人員，可以使用
C/C++ 提供的功能強大的工具來改進處理時間，并且防止內(nèi)存破壞，這些工具其中之一是控制如何在代碼
中分配或者釋放內(nèi)存。通過介紹如何針對特定的情況創(chuàng)建自己的內(nèi)存管理器，本教程對內(nèi)存管理的相關(guān)
概念進行了揭秘。
開始之前
了解本教程中包含的內(nèi)容以及如何最好地利用本教程。
關(guān)于本教程
本教程采用了一種基本方法為任何應(yīng)用程序構(gòu)建內(nèi)存管理器。本教程解釋了為什么需要內(nèi)存管理器，并提供
了為應(yīng)用程序編寫自定義的內(nèi)存管理器（以滿足特定的需求）的方法。
目標
在本教程中，您將了解在設(shè)計內(nèi)存管理器之前需要考慮的一些注意事項、可用于創(chuàng)建這種內(nèi)存管理器的一些
特定技術(shù)，并在文章的最后了解創(chuàng)建內(nèi)存管理器的方法。您還將了解各種類型內(nèi)存管理器設(shè)計的優(yōu)點和不足
之處。
先決條件
本教程面向那些入門級到中級水平的 Linux® 或 UNIX® 程序員。您應(yīng)該對使用 UNIX 命令行 Shell，
以及 C/C++ 語言的應(yīng)用知識有基本的了解。此外，還需要了解 malloc、calloc、free、memcpy 和
memset 等系統(tǒng)調(diào)用（即處理內(nèi)存分配、釋放和內(nèi)容修改的例程）的內(nèi)部工作方式。
系統(tǒng)要求
要運行本教程中的示例，您需要具備安裝了 g++ 編譯器工具鏈的 Linux 或者 UNIX 系統(tǒng)。還需要具有
足夠大的 RAM（大約 256 MB）。
為什么要創(chuàng)建自定義的內(nèi)存管理器呢？
要理解內(nèi)存分配控制如何幫助提高代碼的運行速度，首先需要回憶一下 C/C++ 中內(nèi)存管理的基礎(chǔ)知識。
C 中的標準庫函數(shù)malloc、free、calloc 和 realloc，以及 C++ 中的 new、new [ ]、delete 和 delete
[ ] 操作符，是這兩種語言中內(nèi)存管理的關(guān)鍵之處。在了解了這一點之后，有幾個內(nèi)容值得注意。
如 malloc 和 new 函數(shù)是通用的內(nèi)存分配器。您的代碼可能是單線程的，但它所鏈接的 malloc 函數(shù)同樣
可以處理多線程的范例。正是由于這個額外功能，使得這些例程的性能有所降低。
在執(zhí)行時，malloc 和 new 將向操作系統(tǒng)內(nèi)核請求內(nèi)存，而 free 和 delete 則請求釋放內(nèi)存。這意味著，
操作系統(tǒng)必須在每次提出內(nèi)存請求時在用戶空間代碼和內(nèi)核代碼之間進行切換。反復(fù)調(diào)用 malloc 或者
new 的程序，最終將由于不斷地進行上下文切換而導(dǎo)致運行緩慢。
對于在程序中分配的、并且以后不再需要使用的內(nèi)存，常常會忘記對其進行刪除，并且 C/C++ 并沒有
提供自動的垃圾收集。這將導(dǎo)致程序的內(nèi)存空間占用進一步增長。在實際的大型程序中，性能將受到顯著
的影響，因為可用內(nèi)存變得越來越少，并且硬盤訪問是非常耗時的。
設(shè)計目標
您的內(nèi)存管理器應(yīng)該滿足下面的設(shè)計目標：
速度
與編譯器提供的分配器相比，內(nèi)存管理器的速度必須更快一些。重復(fù)的分配和釋放不應(yīng)該降低代碼的執(zhí)行
速度。如果可能的話，應(yīng)該對內(nèi)存管理器進行優(yōu)化，以便處理代碼中頻繁出現(xiàn)的某些分配模式。
健壯性
在程序終止之前，內(nèi)存管理器必須歸還它向系統(tǒng)請求的所有內(nèi)存。也就是說，不應(yīng)該存在內(nèi)存泄漏。它還
應(yīng)該能夠處理錯誤的情況（例如，請求過大的內(nèi)存），并且很好地解決這些問題。
用戶使用便利性
在將內(nèi)存管理器集成到他們的代碼中時，用戶應(yīng)該只需要更改很少的代碼。
可移植性
應(yīng)該可以很容易地將內(nèi)存管理器移植到其它的系統(tǒng)，并且不應(yīng)該使用與平臺相關(guān)的內(nèi)存管理特性。
創(chuàng)建內(nèi)存管理器的實用策略
在創(chuàng)建內(nèi)存管理器時，下面的這些策略是很實用的：
- 請求較大的內(nèi)存塊。
- 對常見的請求大小進行優(yōu)化。
- 在容器中收集刪除的內(nèi)存。
請求較大的內(nèi)存塊
最常見的內(nèi)存管理策略之一是，在程序啟動期間請求一些較大的內(nèi)存塊，然后在代碼執(zhí)行期間反復(fù)地
使用它們。可以從這些內(nèi)存塊劃出部分內(nèi)存，以滿足各種數(shù)據(jù)結(jié)構(gòu)的內(nèi)存分配請求。這將極大地減少
系統(tǒng)調(diào)用的次數(shù)，并提高執(zhí)行性能。
對常見的請求大小進行優(yōu)化
在任何程序中，某些特定的請求大小將比其它大小的請求更加常見。如果對您的內(nèi)存管理器進行優(yōu)化
以便更好地處理這些請求，那么它將工作得更加出色。
在容器中收集刪除的內(nèi)存
應(yīng)該將程序執(zhí)行期間刪除的內(nèi)存收集到容器中。然后，應(yīng)該使用這些容器來滿足進一步的內(nèi)存請求。
如果某個請求失敗，那么應(yīng)該將內(nèi)存訪問委托給程序啟動期間分配的某個較大的內(nèi)存塊。雖然內(nèi)存
管理最初用于加速程序的執(zhí)行和防止內(nèi)存泄漏，但這種技術(shù)可能會潛在地導(dǎo)致程序的較低內(nèi)存空間
占用，這是因為它可以重用刪除的內(nèi)存。這是編寫您自己的內(nèi)存分配器的另一個原因！
分析 C++ new/delete 操作符的執(zhí)行時間
我們將從一個簡單示例開始。假定您的代碼使用了一個稱為 Complex 的類（該類用于表示復(fù)數(shù)），
并且它使用了 new 和 delete 操作符所提供的機制，如清單 1 中所示。
class Complex
{
public:
Complex (double a, double b): r (a), c (b) {}
private:
double r; // Real Part
double c; // Complex Part
};
int main(int argc, char* argv[])
{
Complex* array[1000];
for (int i = 0;i < 5000; i++) {
for (int j = 0; j < 1000; j++) {
array[j] = new Complex (i, j);
}
for (int j = 0; j < 1000; j++) {
delete array[j];
}
}
return 0;
}
清單 1. Complex 類的 C++ 代碼
外層循環(huán)的每次迭代都會導(dǎo)致 1000 次分配和釋放。5000 次這樣的迭代將導(dǎo)致 10 百萬次用戶和
內(nèi)核代碼之間的切換。在 Solaris 10 計算機中使用 gcc-3.4.6 進行編譯之后，執(zhí)行這個測試程序
平均需要花費 3.5 秒。這是編譯器提供的全局 new 和 delete 操作符實現(xiàn)的基準性能度量。要為
Complex 類創(chuàng)建自定義的內(nèi)存管理器以改進編譯器的實現(xiàn)，您需要重寫 Complex 類特定的 new 和
delete操作符。
New/Delete：深入研究
在 C++ 中，對內(nèi)存管理進行組織實際上就是重載 new 或者 delete 操作符。代碼中不同的類可能
需要使用不同的內(nèi)存分配策略，這意味著每個類需要特定的 new。否則，必須重寫 new 或者 delete
全局操作符。可以采用這兩種形式中的任何一種來實現(xiàn)操作符重載，如清單 2 中所示。
清單 2. 重載 new 或者 delete 操作符void* operator new(size_t size);
void operator delete(void* pointerToDelete);
-OR-
void* operator new(size_t size, MemoryManager& memMgr);
void operator delete(void* pointerToDelete, MemoryManager& memMgr);
經(jīng)過重寫的 new 操作符負責(zé)分配第一個參數(shù)中指定大小的原始內(nèi)存，而 delete 操作符則負責(zé)釋放這
個內(nèi)存。請注意，這些例程只用于分配或者釋放內(nèi)存；它們并不會分別調(diào)用構(gòu)造函數(shù)或析構(gòu)函數(shù)。對
于由 new 操作符分配的內(nèi)存，將調(diào)用構(gòu)造函數(shù)，而只有在調(diào)用了對象的析構(gòu)函數(shù)后才調(diào)用 delete 操
作符。
new 的第二種變體是 placement new 操作符，它接受一個 MemoryManager 參數(shù)，該參數(shù)基本上是為某
個對象分配原始內(nèi)存的數(shù)據(jù)結(jié)構(gòu),最后將調(diào)用這個對象的構(gòu)造函數(shù)。對于本教程，我們建議使用 new 或
者 delete 的第一種變體，因為后一種變體將導(dǎo)致用戶代碼中 MemoryManager& 參數(shù)的大量增加，違反
了用戶使用便利性的設(shè)計目標。
我們使用 MemoryManager 類，以便將 new 和 delete 操作符例程作為下面的 MemoryManager 例程的包裝，
從而進行實際的內(nèi)存分配或者釋放，如清單 3 中所示： MemoryManager gMemoryManager;
// Memory Manager, global variable。
清單 3. 作為包裝的 new、new[ ]、delete 和 delete[ ] 操作符MemoryManager gMemoryManager; // Memory Manager, global variable
void* operator new (size_t size)
{
return gMemoryManager.allocate(size);
}
void* operator new[ ] (size_t size)
{
return gMemoryManager.allocate(size);
}
void operator delete (void* pointerToDelete)
{
gMemoryManager.free(pointerToDelete);
}
void operator delete[ ] (void* arrayToDelete)
{
gMemoryManager.free(arrayToDelete);
}
注意：
- 傳遞給
new[ ] 操作符的 size 是數(shù)組每個元素的大小與數(shù)組元素個數(shù)相乘后所得的大小。 - 這個指針并不是在任何類特定的
new、delete、new[ ] 或者 delete[ ] 操作符中都可以
使用。實際上，這四個例程都用作靜態(tài)方法。您必須在設(shè)計過程中始終牢記這一點。 - 除了使用全局變量來聲明內(nèi)存管理器之外，您當然還可以使用一個單例。
根據(jù)到目前為止的介紹，清單 4 顯示了內(nèi)存管理器類的基本接口。
清單 4. 內(nèi)存管理器接口
class IMemoryManager
{
public:
virtual void* allocate(size_t) = 0;
virtual void free(void*) = 0;
};
class MemoryManager : public IMemoryManager
{
public:
MemoryManager( );
virtual ~MemoryManager( );
virtual void* allocate(size_t);
virtual void free(void*);
};
allocate 和 free 例程作為內(nèi)聯(lián)例程，以便實現(xiàn)更快的分派。
單線程環(huán)境中 Complex 類型的第一個內(nèi)存管理器
我們設(shè)計了本教程的第一個內(nèi)存管理器，并始終牢記到目前為止已經(jīng)介紹的那些原則。出于
簡單的考慮，這個自定義的內(nèi)存管理器專門用于 Complex 類型的對象，并且只能在單線程
環(huán)境中工作。其基本思想是，在可用的內(nèi)存管理器中保存 Complex 對象池，并通過這個池來
完成以后的分配工作。如果需要創(chuàng)建的 Complex 對象的數(shù)目超過了該池中對象的數(shù)目，那么
將對該池進行擴展。刪除的對象將歸還到這個池中。圖 1 很好地說明了所發(fā)生的事件。
圖 1. 創(chuàng)建 Complex 對象的池
該池中的每個塊具有兩個用途：
- 它存儲了一個
Complex 對象。 - 它必須能夠?qū)⑵渥陨磉B接到池中的下一個塊。
沒有選擇在 Complex 數(shù)據(jù)結(jié)構(gòu)中存儲一個指針，因為這將增加設(shè)計的整體內(nèi)存空間占用。相
比較而言，更好的方法是將 Complex 數(shù)據(jù)結(jié)構(gòu)的私有變量包裝到一個結(jié)構(gòu)中，并將其與 Complex
指針一起創(chuàng)建一個聯(lián)合。當用作池中的一部分時，這個指針用于指向該池中的下一個空閑元素。
當用作獨立 Complex 對象時，可以利用該結(jié)構(gòu)來保存實數(shù)和復(fù)數(shù)部分。清單 5 顯示了經(jīng)過修改的
數(shù)據(jù)結(jié)構(gòu)。
清單 5. 經(jīng)過修改的數(shù)據(jù)結(jié)構(gòu)，可以在不產(chǎn)生額外開銷的情況下存儲 Complex*
class Complex
{
public:
Complex (double a, double b): r (a), c (b) {}
private:
union {
struct {
double r; // Real Part
double c; // Complex Part
};
Complex* next;
};
};
然而，這個策略違反了用戶使用便利性的設(shè)計目標，因為在集成內(nèi)存管理器的時候，我們希望在
原始數(shù)據(jù)結(jié)構(gòu)中進行最小限度的更改。為了對此進行改進，我們設(shè)計了一個新的 FreeStore 數(shù)據(jù)
結(jié)構(gòu)，它是一個包裝數(shù)據(jù)結(jié)構(gòu)，在保存為池中的一部分時用作指針，否則用作 Complex 對象。
清單 6 顯示了 FreeStore 對象的數(shù)據(jù)結(jié)構(gòu)。
清單 6. FreeStore 對象的數(shù)據(jù)結(jié)構(gòu)
struct FreeStore
{
FreeStore* next;
};
然后，該池成為 FreeStore 對象的鏈表，其中每一個都可以指向該池中的下一個元素，并且可以
用作一個 Complex 對象。MemoryManager 類必須保存一個指針，以指向這個空閑池第一個元素的頭。
它應(yīng)該提供一些用于在需要時擴展池大小的私有方法，以及在程序終止時清空內(nèi)存的方法。清單 7
包含了經(jīng)過修改的 Complex 類的數(shù)據(jù)結(jié)構(gòu)，從而提供 FreeStore 功能。
清單 7. 經(jīng)過修改的 Complex 類數(shù)據(jù)結(jié)構(gòu)，其中提供了 FreeStore 功能
#include <sys/types.h>
class MemoryManager: public IMemoryManager
{
struct FreeStore
{
FreeStore *next;
};
void expandPoolSize ();
void cleanUp ();
FreeStore* freeStoreHead;
public:
MemoryManager () {
freeStoreHead = 0;
expandPoolSize ();
}
virtual ~MemoryManager () {
cleanUp ();
}
virtual void* allocate(size_t);
virtual void free(void*);
};
MemoryManager gMemoryManager;
class Complex
{
public:
Complex (double a, double b): r (a), c (b) {}
inline void* operator new(size_t);
inline void operator delete(void*);
private:
double r; // Real Part
double c; // Complex Part
};
下面是用于內(nèi)存分配的偽代碼：
- 如果還沒有創(chuàng)建空閑存儲，那么創(chuàng)建空閑存儲，然后跳轉(zhuǎn)到步驟 3。
- 如果空閑存儲已經(jīng)耗盡，則創(chuàng)建一個新的空閑存儲。
- 返回空閑存儲的第一個元素，并且將空閑存儲的下一個元素標記為空閑存儲的頭。
下面是用于內(nèi)存刪除的偽代碼：
- 讓刪除指針中的 next 域指向當前空閑存儲的頭。
- 將刪除指針標記為空閑存儲的頭。
清單 8 包含了 Complex 類的 new 和 delete 操作符的源代碼。清單 9 顯示了空閑存儲的擴展和清理方法。
問題仍然存在。您能發(fā)現(xiàn)具體的問題嗎？
清單 8. 用于 Complex 類的自定義內(nèi)存分配或者釋放
inline void* MemoryManager::allocate(size_t size)
{
if (0 == freeStoreHead)
expandPoolSize ();
FreeStore* head = freeStoreHead;
freeStoreHead = head->next;
return head;
}
inline void MemoryManager::free(void* deleted)
{
FreeStore* head = static_cast <FreeStore*> (deleted);
head->next = freeStoreHead;
freeStoreHead = head;
}
void* Complex::operator new (size_t size)
{
return gMemoryManager.allocate(size);
}
void Complex::operator delete (void* pointerToDelete)
{
gMemoryManager.free(pointerToDelete);
}
空閑存儲的創(chuàng)建并不是那么簡單。關(guān)鍵在于理解相同的 FreeStore* 指針還可以用來表示 Complex 對象。
因此，單個 FreeStore指針所需的大小必須是 FreeStore* 或者 Complex 中較大的一個，如清單 9 中所示。
#define POOLSIZE 32
void MemoryManager::expandPoolSize ()
{
size_t size = (sizeof(Complex) > sizeof(FreeStore*)) ?
sizeof(Complex) : sizeof(FreeStore*);
FreeStore* head = reinterpret_cast <FreeStore*> (new char[size]);
freeStoreHead = head;
for (int i = 0; i < POOLSIZE; i++) {
head->next = reinterpret_cast <FreeStore*> (new char [size]);
head = head->next;
}
head->next = 0;
}
void MemoryManager::cleanUp()
{
FreeStore* nextPtr = freeStoreHead;
for (; nextPtr; nextPtr = freeStoreHead) {
freeStoreHead = freeStoreHead->next;
delete [] nextPtr; // remember this was a char array
}
}
大功告成！您已經(jīng)為 Complex 類創(chuàng)建了自定義的內(nèi)存管理器。記得基準測試花費了 3.5 秒。編譯并
運行相同測試（不需要在主例程中對客戶端代碼進行任何更改），現(xiàn)在顯示執(zhí)行該程序只需要花費
0.67 秒！為什么存在這樣顯著的性能改進呢？主要有兩個原因：
- 在用戶和內(nèi)核代碼之間的切換數(shù)目明顯減少，因為它通過將刪除的內(nèi)存收集回空閑存儲來重用這些內(nèi)存。
- 這個內(nèi)存管理器是一個適合單線程執(zhí)行的分配器。我們并不打算在多線程環(huán)境中運行這些代碼。
之前，我們曾問您是否發(fā)現(xiàn)了設(shè)計中的問題。這個問題就是，如果沒有刪除使用 new 創(chuàng)建的 Complex 對象，
那么在這種設(shè)計中就沒有辦法回收丟失的內(nèi)存。如果開發(fā)人員使用編譯器提供的 new 和 delete 全局操作符，
那么情況也是相同的。然而，內(nèi)存管理器不僅僅涉及性能改進，它還應(yīng)該能夠在設(shè)計中避免內(nèi)存泄漏。對于
使用 new 創(chuàng)建的 Complex 對象進行顯式刪除的情況，cleanUp 例程僅僅將內(nèi)存返回給操作系統(tǒng)。這個問題只
能通過從操作系統(tǒng)中請求更大的內(nèi)存塊（在程序初始化期間）、并對它們進行存儲來加以解決。使用 Complex
的 new 操作符從這些塊中劃出部分內(nèi)存來響應(yīng)內(nèi)存的請求。cleanUp 例程在釋放這些塊時應(yīng)該將其作為一個整
體，而不是從這些內(nèi)存塊中創(chuàng)建的單個對象。
有趣的說明
仍然使用全局 new 和 delete 操作符創(chuàng)建空閑存儲的元素。然而，您也可以使用 malloc 和 free 的組合。在這
兩種情況下，執(zhí)行的平均時間基本相同。
位圖內(nèi)存管理器
可以在最初的固定大小內(nèi)存分配方案基礎(chǔ)上進行有趣的改進，即位圖內(nèi)存管理器。在這個方案中，向操作系統(tǒng)較
大的塊進行內(nèi)存請求，并且通過從這些塊劃出部分內(nèi)存來實現(xiàn)內(nèi)存的分配。通過將整個塊作為一個整體來完成釋
放操作，因而避免了任何潛在的泄漏。這種方法的另一個優(yōu)點是，它可以支持 new 和 delete 操作的數(shù)組版本。
在這種方法中，內(nèi)存管理器將請求較大的內(nèi)存塊。然后進一步將這個塊劃分為較小的、且大小固定的內(nèi)存塊。在
這種情況下，每個內(nèi)存塊的大小都與 Complex 對象的大小相等。根據(jù)這些塊中內(nèi)存塊的數(shù)目，單獨地維護一個位
圖，以顯示每個塊的狀態(tài)（空閑、或者已分配），并且位的數(shù)目與內(nèi)存塊的數(shù)目相等。當程序請求一個新的
Complex 對象時，內(nèi)存管理器將根據(jù)位圖來獲得一個空閑塊。對于所有的空閑塊，將其對應(yīng)的位設(shè)置為 1。對于
已使用的塊，則將它們對應(yīng)的位設(shè)置為 0。要提供 new[ ] 和 delete[ ] 操作符，您需要維護一個輔助的數(shù)據(jù)結(jié)構(gòu)，
以便在創(chuàng)建或者銷毀 Complex 數(shù)組對象時幫助跟蹤位圖中有多少位需要設(shè)置為 1 或者 0。
創(chuàng)建一個位圖內(nèi)存管理器
內(nèi)存管理器從操作系統(tǒng)中請求足夠大的內(nèi)存塊。從這個塊中劃分出部分內(nèi)存以進行稍后的內(nèi)存分配。如果請求失敗，
那么內(nèi)存管理器將解決這個問題，并將合適的消息傳遞給用戶，表示它已經(jīng)退出。在這個階段中，位圖中的所有條
目都設(shè)置為 1。
如果內(nèi)存管理器耗盡了空閑的內(nèi)存塊，那么它將向操作系統(tǒng)進一步請求較大的內(nèi)存塊。MemoryManager 數(shù)據(jù)結(jié)構(gòu)中的
每個位圖都可以用于增大對應(yīng)的內(nèi)存塊。然而，在調(diào)用刪除操作之后，用戶可以使用對應(yīng)的塊。因此，非連續(xù)的刪除
調(diào)用將導(dǎo)致所謂的分段的內(nèi)存，并且可以從這個內(nèi)存中提供適當大小的塊。
清單 10 中給出了 MemoryManager 類的基本結(jié)構(gòu)。它包含 MemoryPoolList，后者保存了從操作系統(tǒng)中請求的內(nèi)存塊的
起始地址。對于每個塊，在 BitMapEntryList 中都存在一個相應(yīng)的條目。FreeMapEntries 是一種數(shù)據(jù)結(jié)構(gòu)，可以用來
為 new 調(diào)用的非數(shù)組版本提高下一個可用空閑塊的搜索速度。
清單 10. MemoryManager 類的定義class MemoryManager : public IMemoryManager
{
std::vector<void*> MemoryPoolList;
std::vector<BitMapEntry> BitMapEntryList;
//the above two lists will maintain one-to-one correspondence and hence
//should be of same size.
std::set<BitMapEntry*> FreeMapEntries;
std::map<void*, ArrayMemoryInfo> ArrayMemoryList;
private:
void* AllocateArrayMemory(size_t size);
void* AllocateChunkAndInitBitMap();
void SetBlockBit(void* object, bool flag);
void SetMultipleBlockBits(ArrayMemoryInfo* info, bool flag);
public:
MemoryManager( ) {}
~MemoryManager( ) {}
void* allocate(size_t);
void free(void*);
std::vector<void*> GetMemoryPoolList();
}; ArrayMemoryList 保存了為 Complex 對象數(shù)組所分配的內(nèi)存的相關(guān)信息。實際上，它是數(shù)組的起始地址到結(jié)構(gòu)的映射，
以便維護MemPoolListIndex、位圖中數(shù)組的 StartPosition 和數(shù)組的大小，如清單 11 中所示。
清單 11. ArrayInfo 結(jié)構(gòu)定義
typedef struct ArrayInfo
{
int MemPoolListIndex;
int StartPosition;
int Size;
}
ArrayMemoryInfo;
清單 12. BitMapEntry 類定義
typedef struct BitMapEntry
{ int Index;
int BlocksAvailable;
int BitMap[BIT_MAP_SIZE];
public:
BitMapEntry():BlocksAvailable(BIT_MAP_SIZE)
{ memset(BitMap,0xff,BIT_MAP_SIZE / sizeof(char));
// initially all blocks are free and bit value 1 in the map denotes
// available block
}
void SetBit(int position, bool flag);
void SetMultipleBits(int position, bool flag, int count);
void SetRangeOfInt(int* element, int msb, int lsb, bool flag);
Complex* FirstFreeBlock(size_t size);
Complex* ComplexObjectAddress(int pos);
void* Head();
}
BitMapEntry;
內(nèi)存管理器將初始化一個“n”位的數(shù)組（作為位圖），這樣一來，這個數(shù)組中的每個位對應(yīng)于所請求的內(nèi)存的一個
塊。將所有的條目都設(shè)置為 1。這項工作在 BitMapEntry 的構(gòu)造函數(shù)中完成。
在對 Complex 類的 new 或者 malloc 的非數(shù)組版本進行調(diào)用的過程中，內(nèi)存管理器將檢查 FreeMapEntries 數(shù)據(jù)結(jié)構(gòu)
中是否存在可用的塊。如果在其中找到了可用的塊，則返回這個塊，否則從操作系統(tǒng)中請求一個新的內(nèi)存塊，并設(shè)
置其對應(yīng)的 BitMapEntry。從這個塊中劃出部分內(nèi)存塊返回給用戶，將其可用位設(shè)置為 0 以表示它不再空閑，并且
將指針返回給用戶，清單 13 中顯示了相關(guān)的代碼。
清單 13. MemoryManager::allocate 定義
void* MemoryManager::allocate(size_t size)
{
if(size == sizeof(Complex)) // mon-array version
{
std::set<BitMapEntry*>::iterator freeMapI = FreeMapEntries.begin();
if(freeMapI != FreeMapEntries.end())
{
BitMapEntry* mapEntry = *freeMapI;
return mapEntry->FirstFreeBlock(size);
}
else
{
AllocateChunkAndInitBitMap();
FreeMapEntries.insert(&(BitMapEntryList[BitMapEntryList.size() - 1]));
return BitMapEntryList[BitMapEntryList.size() - 1].FirstFreeBlock(size);
}
}
else // array version
{
if(ArrayMemoryList.empty())
{
return AllocateArrayMemory(size);
}
else
{
std::map<void*, ArrayMemoryInfo>::iterator infoI =ArrayMemoryList.begin();
std::map<void*, ArrayMemoryInfo>::iterator infoEndI =
ArrayMemoryList.end();
while(infoI != infoEndI)
{
ArrayMemoryInfo info = (*infoI).second;
if(info.StartPosition != 0) // search only in those mem blocks
continue; // where allocation is done from first byte
else
{
BitMapEntry* entry = &BitMapEntryList[info.MemPoolListIndex];
if(entry->BlocksAvailable < (size / sizeof(Complex)))
return AllocateArrayMemory(size);
else
{
info.StartPosition = BIT_MAP_SIZE - entry->BlocksAvailable;
info.Size = size / sizeof(Complex);
Complex* baseAddress = static_cast<Complex*>(
MemoryPoolList[info.MemPoolListIndex]) + info.StartPosition;
ArrayMemoryList[baseAddress] = info;
SetMultipleBlockBits(&info, false);
return baseAddress;
}
}
}
}
}
}
清單 14 中給出了為單個塊設(shè)置或重置位的代碼。
清單 14. MemoryManager::SetBlockBit 定義
void MemoryManager::SetBlockBit(void* object, bool flag)
{
int i = BitMapEntryList.size() - 1;
for (; i >= 0 ; i--)
{
BitMapEntry* bitMap = &BitMapEntryList[i];
if((bitMap->Head <= object )&&
(&(static_cast<Complex*>(bitMap->Head))[BIT_MAP_SIZE-1] >= object))
{
int position = static_cast<Complex*>(object) -
static_cast<Complex*>(bitMap->Head);
bitMap->SetBit(position, flag);
flag ? bitMap->BlocksAvailable++ : bitMap->BlocksAvailable--;
}
}
}
清單 15 中給出了為多個塊設(shè)置或重置位的代碼。
清單 15. MemoryManager::SetMultipleBlockBit 定義
void MemoryManager::SetMultipleBlockBits(ArrayMemoryInfo* info, bool flag)
{ BitMapEntry* mapEntry = &BitMapEntryList[info->MemPoolListIndex];
mapEntry->SetMultipleBits(info->StartPosition, flag, info->Size);
}
對于數(shù)組版本而言，處理方式有一點不同。用于數(shù)組的內(nèi)存塊與那些用于單個對象內(nèi)存分配的
內(nèi)存塊分配自不同的內(nèi)存塊。這減少了在調(diào)用兩種類型的 new 時搜索下一個空閑可用內(nèi)存的開銷。
內(nèi)存管理器將查找 ArrayMemoryList 數(shù)據(jù)結(jié)構(gòu)，以獲取為數(shù)組提供內(nèi)存的塊的有關(guān)信息。當找到
時，它將獲得這個塊中的適當部分，將其地址提供給用戶，并將相應(yīng)的位設(shè)置為 0。如果出于某
種原因而導(dǎo)致操作失敗，那么將從操作系統(tǒng)中請求一個新的塊，并從中劃分出部分內(nèi)存。兩種
new 調(diào)用的內(nèi)存塊作為 MemPoolList 的一部分存儲在 MemoryManager 類中。
在調(diào)用 Complex 類型對象的指針的 delete、或者 free 的非數(shù)組版本的過程中，首先確定包含這
個指針的內(nèi)存塊（請參見清單 16）。然后，根據(jù)這個塊的 BitMapEntry 將對應(yīng)的位重置為 1，
從而使其成為可用的塊。整個操作將花費 O(1) 時間。對于 delete []，從 ArrayMemoryList 中
檢索相關(guān)信息，并且在已知起始位置和位圖大小的情況下，將這些位標記為可用。
清單 16. MemoryManager::free 定義
void MemoryManager::free(void* object)
{ if(ArrayMemoryList.find(object) == ArrayMemoryList.end())
SetBlockBit(object, true); // simple block deletion
else
{//memory block deletion ArrayMemoryInfo *info = &ArrayMemoryList[object];
SetMultipleBlockBits(info, true);
}
}
下載部分中提供了位圖內(nèi)存管理器代碼的完整清單。它是這部分討論的內(nèi)存管理器的一個
工作示例，并且包括了我們在這個部分中討論的所有清單。
繼承帶來的問題
派生類的大小很可能會與其基類有很大的不同。例如，可以考慮 Complex 類的一個派生變體，
稱為 ComplexT，它用于跟蹤復(fù)數(shù)的值隨時間變化的情況，其中包含一個附加的 unsigned long 用來存儲時間。先前重寫的 new 或者 delete 操作符現(xiàn)在將無法工作，除非我們專門針對這個
派生變體再次定義它們。對于這個問題，有三種可能的解決方案：
使用 MemoryManager 為這兩個不同的類維護兩個不同的池。實際上，這意味著分配/釋
放例程的兩個變體，以及用來存儲這兩個池的頭的兩個指針。這種方式可能奏效，但
可伸縮性受到限制。
根據(jù)最大的派生類大小維護一個池。allocate 例程始終返回最大派生類的大小，無論
是基類、派生類層次中的哪個對象在請求內(nèi)存。這樣可以很好地解決問題，但它并不是
一個非常有價值的方法，因為程序的內(nèi)存空間占用將會增加。
為可變大小的分配創(chuàng)建通用的內(nèi)存管理器。
基于空閑列表的內(nèi)存管理器
在一個典型的程序中，內(nèi)存塊的大多數(shù)請求都是特定大小的。這個內(nèi)存管理器將充分利用這個
特點。要實現(xiàn)這一點，您需要維護一些列表，其中包含這種大小的空閑塊的地址。在技術(shù)行話
中，我們稱這些列表為空閑列表。例如，可以考慮某個程序，它將提出 8、16、24、32、48
和 64 字節(jié)的內(nèi)存請求。出于這個目的，內(nèi)存管理器中包含六個不同的空閑列表，并請求從對
應(yīng)的列表提供特定大小的內(nèi)存。與位圖內(nèi)存管理器類似，在啟動時從操作系統(tǒng)中請求內(nèi)存，并
且內(nèi)存管理器在內(nèi)部將從操作系統(tǒng)請求的塊劃分到各個列表中。在用戶為某個對象請求內(nèi)存時，
比如“m”個字節(jié)，那么會將對象的大小轉(zhuǎn)換為最接近的塊大小“n”，并且存在一個空閑列表用來
存儲大小為“n”的塊。
有關(guān)保護字節(jié)（guard bytes）的簡單介紹
“n”字節(jié)的塊不僅存儲了對象，還存儲了一些元數(shù)據(jù)信息。每個塊的末尾附近都包含四個額外的
字節(jié)，其中包含在堆內(nèi)存操作范例中稱為保護字節(jié) 的內(nèi)容。通常，memcpy 和 memset 函數(shù)可以
訪問所分配內(nèi)存的界限之外的內(nèi)存字節(jié)。這將導(dǎo)致堆內(nèi)存的破壞。許多編譯器都為所分配的 mem
塊添加了一些特殊字符，以充當該塊的哨兵（或者保護字節(jié)）。對于所分配內(nèi)存的這些塊所進行
的任何訪問，都將檢查所分配的塊附近的特殊字符。如果找不到這些字符，那么將認為在程序執(zhí)
行期間以非法的方式更改了它們的值，這暗示堆內(nèi)存不再處于有序的狀態(tài)，并且因此受到了破壞。
通過這種機制，程序員可以捕獲一些所了解的內(nèi)存錯誤。在下面的示例中，這四個字節(jié)中的其中
兩個充當了保護字節(jié)，第三個字節(jié)用于存儲這個對象的大小，最后一個字節(jié)存儲了一個標志，表
示這個對象是否可用、或者已經(jīng)被占用。
創(chuàng)建一個空閑列表內(nèi)存管理器
如前所述，內(nèi)存管理器維護了一些指針的列表，這些指針指向可變大小的塊。它還對從操作系統(tǒng)
請求而來的內(nèi)存塊進行維護，并作為memoryPool。在 MemoryManager 調(diào)用其析構(gòu)函數(shù)時，這個池
可以用于釋放整個內(nèi)存塊。清單 17 顯示了該數(shù)據(jù)結(jié)構(gòu)。
清單 17. 基于空閑列表實現(xiàn)的 MemoryManager 類定義
class MemoryManager : public IMemoryManager
{ private:
VoidPtrList Byte8PtrList;
VoidPtrList Byte16PtrList;
VoidPtrList Byte24PtrList;
VoidPtrList Byte32PtrList;
VoidPtrList Byte40PtrList;
std::vector<void*> MemoryPoolList;
. . . . . . . . . //helper routines may go in here
public:
MemoryManager( ) {} ~MemoryManager( ) {} void* allocate(size_t);
void free(void*);
};
我們的示例使用了大小為 16、28 和 32 字節(jié)的三個類，因而需要大小為 24、32和40
個字節(jié)的塊來保存它們的保護字節(jié)。因此，Byte24PtrList、Byte32PtrList 和
Byte40PtrList 的使用最為頻繁，并且代碼也主要是和它們相關(guān)的。然而，設(shè)計相當
靈活，也可以用于添加您所希望的其他大小的列表。
為這些類重載了操作符 new 和 delete，它們將調(diào)用委派給負責(zé)內(nèi)存分配和釋放的
allocate 和 free 例程。下面將詳細地介紹這些例程。我們使用了大小為 1024 的
塊作為對象的初始計數(shù)。另外，將示例中使用的每個類的大小作為預(yù)定義的常數(shù)進
行了存儲，如清單 18 中所示。
清單 18. 這個實現(xiàn)中所使用的預(yù)定義常數(shù)
const int JOB_SCHEDULER_SIZE = sizeof(JobScheduler);
const int COMPLEX_SIZE = sizeof(Complex);
const int COORDINATE_SIZE = sizeof(Coordinate);
const int POOL_SIZE = 1024; //number of elements in a single pool
//can be chosen based on application requirements
const int MAX_BLOCK_SIZE = 36; //depending on the application it may change
//In above case it came as 36
在 allocate 和 free 例程中使用了這些常數(shù)。
allocate 例程
對于給定大小的塊，allocate 例程將確定使用內(nèi)存管理器中的哪個列表。它將查找
必需的列表，以查看是否存在可用的塊。請注意，這個列表僅存儲了指向該塊的指
針，而不是塊本身（該塊是 MemoryPoolList 的一部分）。
如果空閑列表是空的，那么將從操作系統(tǒng)中請求附加的內(nèi)存塊，并由
InitialiseByte24List、InitialiseByte32List 和InitialiseByte40List
例程將其組織為分區(qū)塊。
當存在某個空閑塊地址可供使用時，將對應(yīng)的塊標記為不可使用，設(shè)置其保護字節(jié)，
并且返回該塊的地址。可以考慮如清單 19 中所示的實現(xiàn)。
清單 19. MemoryManager::allocate 定義
void* MemoryManager::allocate(size_t size)
{
void* base = 0;
switch(size)
{ case JOB_SCHEDULER_SIZE :
{ if(Byte32PtrList.empty())
{ base = new char [32 * POOL_SIZE];
MemoryPoolList.push_back(base);
InitialiseByte32List(base);
}
void* blockPtr = Byte32PtrList.front();
*((static_cast<char*>(blockPtr)) + 30) = 32; //size of block set
*((static_cast<char*>(blockPtr)) + 31) = 0; //block is no longer free
Byte32PtrList.pop_front();
return blockPtr;
}
case COORDINATE_SIZE :
{ if(Byte40PtrList.empty())
{ base = new char [40 * POOL_SIZE];
MemoryPoolList.push_back(base);
InitialiseByte40List(base);
}
void* blockPtr = Byte40PtrList.front();
*((static_cast<char*>(blockPtr)) + 38) = 40; //size of block set
*((static_cast<char*>(blockPtr)) + 39) = 0; //block is no longer free
Byte40PtrList.pop_front();
return blockPtr;
}
case COMPLEX_SIZE :
{ if(Byte24PtrList.empty())
{ base = new char [24 * POOL_SIZE];
MemoryPoolList.push_back(base);
InitialiseByte24List(base);
}
void* blockPtr = Byte24PtrList.front();
*((static_cast<char*>(blockPtr)) + 22) = 24; //size of block set
*((static_cast<char*>(blockPtr)) + 23) = 0; //block is no longer free
Byte24PtrList.pop_front();
return blockPtr;
}
default : break;
}
return 0;
}
free 例程
free 例程接收塊的地址，并搜索位于塊末尾的、包含大小信息的字節(jié)（在保護字節(jié)中）。它是
塊中的倒數(shù)第二個字節(jié)。在獲得這個大小之后，將對象標記為可用（將最后一個字節(jié)設(shè)置為 1），
并獲取對應(yīng)的列表。然后，將該對象加入空閑 列表中，這也標志著完成了刪除操作。可以考慮
清單 20 中的實現(xiàn)。
清單 20. MemoryManager::free 定義
void MemoryManager::free(void* object)
{ char* init = static_cast<char*>(object);
while(1)
{ int count = 0;
while(*init != static_cast<char>(0xde))
//this loop shall never iterate more than
{ // MAX_BLOCK_SIZE times and hence is O(1) init++;
if(count > MAX_BLOCK_SIZE)
{ printf ("runtime heap memory corruption near %d", object); exit(1);
}
count++;
}
if(*(++init) == static_cast<char>(0xad)) // we have hit the guard bytes
break; // from the outer while
}
init++;
int blockSize = static_cast<int>(*init);
switch(blockSize)
{ case 24: Byte24PtrList.push_front(object); break;
case 32: Byte32PtrList.push_front(object); break;
case 40: Byte40PtrList.push_front(object); break;
default: break;
}
init++;
*init = 1; // set free/available byte
}
下載部分中提供了空閑列表內(nèi)存管理器代碼的完整清單。它是空閑列表內(nèi)存管理器實現(xiàn)的一個
工作示例，并且包括我們在這個部分中討論的所有清單。
優(yōu)點和不足之處
這個設(shè)計有下面幾個優(yōu)點：
雖然這個設(shè)計可以顯著地改善性能，但它仍然存在不足之處，即它需要大量的內(nèi)存。
多線程內(nèi)存管理器
到目前為止，我們所創(chuàng)建的內(nèi)存管理器并沒有考慮到并發(fā)的環(huán)境。在多線程環(huán)境中，
可能會有多個線程同時嘗試進行內(nèi)存的分配和釋放。這意味著，我們必須確保在內(nèi)
存管理器中進行的分配和釋放操作都是具有原子性的。也就是說，在兩個線程同時
嘗試這些操作時，我們必須在這兩個線程之間提供一種互斥的機制。要確保分配和
釋放操作具有原子性，標準的方法是使用一種基于鎖的機制。當一個線程調(diào)用這兩
種方法其中之一時，在它實際獲得對內(nèi)存的訪問或者釋放內(nèi)存之前，必須獲得一個
獨占鎖。如果該鎖由另一個線程所擁有，那么將阻塞當前線程，直到它擁有這個鎖
為止。清單 21 說明了用作鎖定機制的函數(shù)簽名。
清單 21. pthread mutex 方法
#include <pthread.h>
int pthread_mutex_init(pthread_mutex_t *mutex,
const pthread_mutexattr_t *attr);
int pthread_mutex_destroy(pthread_mutex_t *mutex);
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_trylock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);
就本文而言，我們使用了標準 Header pthread.h 中定義的 pthread mutexes，GNU
編譯器在安裝時就提供了這個 Header，以便模擬鎖定或者解鎖機制。allocation 和
free 例程中的代碼位于 pthread_mutex_lock 和 pthread_mutex_unlock 方法之間。
如果某個線程正在訪問內(nèi)存池時，又有另一個線程調(diào)用了這些例程其中之一，那么它
必須等待，直到該鎖可用為止。清單 22 是該方法的經(jīng)過修改的代碼片段。
清單 22. 分配和釋放方法的并發(fā)版本
void* MemoryManager::allocate(size_t size)
{ pthread_mutex_lock (&lock);
... // usual memory allocation code
pthread_mutex_unlock (&lock);
}
void* MemoryManager::free(size_t size)
{ pthread_mutex_lock (&lock);
... // usual memory deallocation code
pthread_mutex_unlock (&lock);
}
現(xiàn)在，內(nèi)存管理器類需要包括一個 pthread_mutex_lock 對象。需要修改類構(gòu)造函數(shù)，
以便調(diào)用 pthread_mutex_init 初始化鎖，并且類析構(gòu)函數(shù)必須調(diào)用 pthread_mutex_destroy
以銷毀 mutex 對象。清單 23 是 MemoryManager 類的修改之后的代碼。
清單 23. 經(jīng)過修改的 MemoryManager 類，以處理多線程的分配和釋放
class MemoryManager : public IMemoryManager
{ pthread_mutex_t lock;
... // usual MemoryManager code follows
};
MemoryManager::MemoryManager ()
{ pthread_mutex_init (&lock, NULL);
... // usual constructor code
}
MemoryManager:: ~MemoryManager ()
{ ... // usual destructor code
pthread_mutex_destroy (&lock);
}
現(xiàn)在，運行內(nèi)存管理器的多線程版本。在我們的測試中，與單線程版本相比，它的運行要慢
得多，這說明了為什么需要提供專用的、自定義的內(nèi)存管理器。
總結(jié)
本教程解釋了下面的幾個概念：
- 在用戶代碼中使用內(nèi)存管理器的需求。
- 內(nèi)存管理器的設(shè)計需求。
- 如何創(chuàng)建固定大小的分配器或者內(nèi)存管理器。
- 如何創(chuàng)建可變大小的分配器。
- 多線程環(huán)境中的內(nèi)存分配。
有關(guān)這個主題的更多信息，請參見參考資料部分。
下載
| 描述 | 名字 | 大小 | 下載方法 |
|---|
| Source files for bitmapped memory manager | bitmapped_memory_manager.zip | 4KB | HTTP |
| Source files for free-lists based memory manager | free_list_mem_mgr.zip | 3KB | HTTP |
參考資料
學(xué)習(xí)
from:
http://www.ibm.com/developerworks/cn/education/aix/au-memorymanager/index.html
posted on 2012-05-26 22:41
chatler 閱讀(2565)
評論(0) 編輯 收藏 引用 所屬分類:
OS