Arpan Sen, 技術負責人, Synapti Computer Aided Design Pvt Ltd
簡介： 代碼的性能優化是一項非常重要的工作。經?？梢钥吹?，采用 C 或 C++ 編寫的、功能正確的軟件
在執行時耗費大量的內存、時間、或者在最糟的情況下既耗內存又費時間。作為一名開發人員，可以使用
C/C++ 提供的功能強大的工具來改進處理時間，并且防止內存破壞，這些工具其中之一是控制如何在代碼
中分配或者釋放內存。通過介紹如何針對特定的情況創建自己的內存管理器，本教程對內存管理的相關
概念進行了揭秘。
開始之前
了解本教程中包含的內容以及如何最好地利用本教程。
關于本教程
本教程采用了一種基本方法為任何應用程序構建內存管理器。本教程解釋了為什么需要內存管理器，并提供
了為應用程序編寫自定義的內存管理器（以滿足特定的需求）的方法。
目標
在本教程中，您將了解在設計內存管理器之前需要考慮的一些注意事項、可用于創建這種內存管理器的一些
特定技術，并在文章的最后了解創建內存管理器的方法。您還將了解各種類型內存管理器設計的優點和不足
之處。
先決條件
本教程面向那些入門級到中級水平的 Linux® 或 UNIX® 程序員。您應該對使用 UNIX 命令行 Shell，
以及 C/C++ 語言的應用知識有基本的了解。此外，還需要了解 malloc、calloc、free、memcpy 和
memset 等系統調用（即處理內存分配、釋放和內容修改的例程）的內部工作方式。
系統要求
要運行本教程中的示例，您需要具備安裝了 g++ 編譯器工具鏈的 Linux 或者 UNIX 系統。還需要具有
足夠大的 RAM（大約 256 MB）。
為什么要創建自定義的內存管理器呢？
要理解內存分配控制如何幫助提高代碼的運行速度，首先需要回憶一下 C/C++ 中內存管理的基礎知識。
C 中的標準庫函數malloc、free、calloc 和 realloc，以及 C++ 中的 new、new [ ]、delete 和 delete
[ ] 操作符，是這兩種語言中內存管理的關鍵之處。在了解了這一點之后，有幾個內容值得注意。
如 malloc 和 new 函數是通用的內存分配器。您的代碼可能是單線程的，但它所鏈接的 malloc 函數同樣
可以處理多線程的范例。正是由于這個額外功能，使得這些例程的性能有所降低。
在執行時，malloc 和 new 將向操作系統內核請求內存，而 free 和 delete 則請求釋放內存。這意味著，
操作系統必須在每次提出內存請求時在用戶空間代碼和內核代碼之間進行切換。反復調用 malloc 或者
new 的程序，最終將由于不斷地進行上下文切換而導致運行緩慢。
對于在程序中分配的、并且以后不再需要使用的內存，常常會忘記對其進行刪除，并且 C/C++ 并沒有
提供自動的垃圾收集。這將導致程序的內存空間占用進一步增長。在實際的大型程序中，性能將受到顯著
的影響，因為可用內存變得越來越少，并且硬盤訪問是非常耗時的。
設計目標
您的內存管理器應該滿足下面的設計目標：
速度
與編譯器提供的分配器相比，內存管理器的速度必須更快一些。重復的分配和釋放不應該降低代碼的執行
速度。如果可能的話，應該對內存管理器進行優化，以便處理代碼中頻繁出現的某些分配模式。
健壯性
在程序終止之前，內存管理器必須歸還它向系統請求的所有內存。也就是說，不應該存在內存泄漏。它還
應該能夠處理錯誤的情況（例如，請求過大的內存），并且很好地解決這些問題。
用戶使用便利性
在將內存管理器集成到他們的代碼中時，用戶應該只需要更改很少的代碼。
可移植性
應該可以很容易地將內存管理器移植到其它的系統，并且不應該使用與平臺相關的內存管理特性。
創建內存管理器的實用策略
在創建內存管理器時，下面的這些策略是很實用的：
- 請求較大的內存塊。
- 對常見的請求大小進行優化。
- 在容器中收集刪除的內存。
請求較大的內存塊
最常見的內存管理策略之一是，在程序啟動期間請求一些較大的內存塊，然后在代碼執行期間反復地
使用它們?？梢詮倪@些內存塊劃出部分內存，以滿足各種數據結構的內存分配請求。這將極大地減少
系統調用的次數，并提高執行性能。
對常見的請求大小進行優化
在任何程序中，某些特定的請求大小將比其它大小的請求更加常見。如果對您的內存管理器進行優化
以便更好地處理這些請求，那么它將工作得更加出色。
在容器中收集刪除的內存
應該將程序執行期間刪除的內存收集到容器中。然后，應該使用這些容器來滿足進一步的內存請求。
如果某個請求失敗，那么應該將內存訪問委托給程序啟動期間分配的某個較大的內存塊。雖然內存
管理最初用于加速程序的執行和防止內存泄漏，但這種技術可能會潛在地導致程序的較低內存空間
占用，這是因為它可以重用刪除的內存。這是編寫您自己的內存分配器的另一個原因！
分析 C++ new/delete 操作符的執行時間
我們將從一個簡單示例開始。假定您的代碼使用了一個稱為 Complex 的類（該類用于表示復數），
并且它使用了 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++ 代碼
外層循環的每次迭代都會導致 1000 次分配和釋放。5000 次這樣的迭代將導致 10 百萬次用戶和
內核代碼之間的切換。在 Solaris 10 計算機中使用 gcc-3.4.6 進行編譯之后，執行這個測試程序
平均需要花費 3.5 秒。這是編譯器提供的全局 new 和 delete 操作符實現的基準性能度量。要為
Complex 類創建自定義的內存管理器以改進編譯器的實現，您需要重寫 Complex 類特定的 new 和
delete操作符。
New/Delete：深入研究
在 C++ 中，對內存管理進行組織實際上就是重載 new 或者 delete 操作符。代碼中不同的類可能
需要使用不同的內存分配策略，這意味著每個類需要特定的 new。否則，必須重寫 new 或者 delete
全局操作符?？梢圆捎眠@兩種形式中的任何一種來實現操作符重載，如清單 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);
經過重寫的 new 操作符負責分配第一個參數中指定大小的原始內存，而 delete 操作符則負責釋放這
個內存。請注意，這些例程只用于分配或者釋放內存；它們并不會分別調用構造函數或析構函數。對
于由 new 操作符分配的內存，將調用構造函數，而只有在調用了對象的析構函數后才調用 delete 操
作符。
new 的第二種變體是 placement new 操作符，它接受一個 MemoryManager 參數，該參數基本上是為某
個對象分配原始內存的數據結構,最后將調用這個對象的構造函數。對于本教程，我們建議使用 new 或
者 delete 的第一種變體，因為后一種變體將導致用戶代碼中 MemoryManager& 參數的大量增加，違反
了用戶使用便利性的設計目標。
我們使用 MemoryManager 類，以便將 new 和 delete 操作符例程作為下面的 MemoryManager 例程的包裝，
從而進行實際的內存分配或者釋放，如清單 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 是數組每個元素的大小與數組元素個數相乘后所得的大小。 - 這個指針并不是在任何類特定的
new、delete、new[ ] 或者 delete[ ] 操作符中都可以
使用。實際上，這四個例程都用作靜態方法。您必須在設計過程中始終牢記這一點。 - 除了使用全局變量來聲明內存管理器之外，您當然還可以使用一個單例。
根據到目前為止的介紹，清單 4 顯示了內存管理器類的基本接口。
清單 4. 內存管理器接口
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 例程作為內聯例程，以便實現更快的分派。
單線程環境中 Complex 類型的第一個內存管理器
我們設計了本教程的第一個內存管理器，并始終牢記到目前為止已經介紹的那些原則。出于
簡單的考慮，這個自定義的內存管理器專門用于 Complex 類型的對象，并且只能在單線程
環境中工作。其基本思想是，在可用的內存管理器中保存 Complex 對象池，并通過這個池來
完成以后的分配工作。如果需要創建的 Complex 對象的數目超過了該池中對象的數目，那么
將對該池進行擴展。刪除的對象將歸還到這個池中。圖 1 很好地說明了所發生的事件。
圖 1. 創建 Complex 對象的池
該池中的每個塊具有兩個用途：
- 它存儲了一個
Complex 對象。 - 它必須能夠將其自身連接到池中的下一個塊。
沒有選擇在 Complex 數據結構中存儲一個指針，因為這將增加設計的整體內存空間占用。相
比較而言，更好的方法是將 Complex 數據結構的私有變量包裝到一個結構中，并將其與 Complex
指針一起創建一個聯合。當用作池中的一部分時，這個指針用于指向該池中的下一個空閑元素。
當用作獨立 Complex 對象時，可以利用該結構來保存實數和復數部分。清單 5 顯示了經過修改的
數據結構。
清單 5. 經過修改的數據結構，可以在不產生額外開銷的情況下存儲 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;
};
};
然而，這個策略違反了用戶使用便利性的設計目標，因為在集成內存管理器的時候，我們希望在
原始數據結構中進行最小限度的更改。為了對此進行改進，我們設計了一個新的 FreeStore 數據
結構，它是一個包裝數據結構，在保存為池中的一部分時用作指針，否則用作 Complex 對象。
清單 6 顯示了 FreeStore 對象的數據結構。
清單 6. FreeStore 對象的數據結構
struct FreeStore
{
FreeStore* next;
};
然后，該池成為 FreeStore 對象的鏈表，其中每一個都可以指向該池中的下一個元素，并且可以
用作一個 Complex 對象。MemoryManager 類必須保存一個指針，以指向這個空閑池第一個元素的頭。
它應該提供一些用于在需要時擴展池大小的私有方法，以及在程序終止時清空內存的方法。清單 7
包含了經過修改的 Complex 類的數據結構，從而提供 FreeStore 功能。
清單 7. 經過修改的 Complex 類數據結構，其中提供了 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
};
下面是用于內存分配的偽代碼：
- 如果還沒有創建空閑存儲，那么創建空閑存儲，然后跳轉到步驟 3。
- 如果空閑存儲已經耗盡，則創建一個新的空閑存儲。
- 返回空閑存儲的第一個元素，并且將空閑存儲的下一個元素標記為空閑存儲的頭。
下面是用于內存刪除的偽代碼：
- 讓刪除指針中的 next 域指向當前空閑存儲的頭。
- 將刪除指針標記為空閑存儲的頭。
清單 8 包含了 Complex 類的 new 和 delete 操作符的源代碼。清單 9 顯示了空閑存儲的擴展和清理方法。
問題仍然存在。您能發現具體的問題嗎？
清單 8. 用于 Complex 類的自定義內存分配或者釋放
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);
}
空閑存儲的創建并不是那么簡單。關鍵在于理解相同的 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
}
}
大功告成！您已經為 Complex 類創建了自定義的內存管理器。記得基準測試花費了 3.5 秒。編譯并
運行相同測試（不需要在主例程中對客戶端代碼進行任何更改），現在顯示執行該程序只需要花費
0.67 秒！為什么存在這樣顯著的性能改進呢？主要有兩個原因：
- 在用戶和內核代碼之間的切換數目明顯減少，因為它通過將刪除的內存收集回空閑存儲來重用這些內存。
- 這個內存管理器是一個適合單線程執行的分配器。我們并不打算在多線程環境中運行這些代碼。
之前，我們曾問您是否發現了設計中的問題。這個問題就是，如果沒有刪除使用 new 創建的 Complex 對象，
那么在這種設計中就沒有辦法回收丟失的內存。如果開發人員使用編譯器提供的 new 和 delete 全局操作符，
那么情況也是相同的。然而，內存管理器不僅僅涉及性能改進，它還應該能夠在設計中避免內存泄漏。對于
使用 new 創建的 Complex 對象進行顯式刪除的情況，cleanUp 例程僅僅將內存返回給操作系統。這個問題只
能通過從操作系統中請求更大的內存塊（在程序初始化期間）、并對它們進行存儲來加以解決。使用 Complex
的 new 操作符從這些塊中劃出部分內存來響應內存的請求。cleanUp 例程在釋放這些塊時應該將其作為一個整
體，而不是從這些內存塊中創建的單個對象。
有趣的說明
仍然使用全局 new 和 delete 操作符創建空閑存儲的元素。然而，您也可以使用 malloc 和 free 的組合。在這
兩種情況下，執行的平均時間基本相同。
位圖內存管理器
可以在最初的固定大小內存分配方案基礎上進行有趣的改進，即位圖內存管理器。在這個方案中，向操作系統較
大的塊進行內存請求，并且通過從這些塊劃出部分內存來實現內存的分配。通過將整個塊作為一個整體來完成釋
放操作，因而避免了任何潛在的泄漏。這種方法的另一個優點是，它可以支持 new 和 delete 操作的數組版本。
在這種方法中，內存管理器將請求較大的內存塊。然后進一步將這個塊劃分為較小的、且大小固定的內存塊。在
這種情況下，每個內存塊的大小都與 Complex 對象的大小相等。根據這些塊中內存塊的數目，單獨地維護一個位
圖，以顯示每個塊的狀態（空閑、或者已分配），并且位的數目與內存塊的數目相等。當程序請求一個新的
Complex 對象時，內存管理器將根據位圖來獲得一個空閑塊。對于所有的空閑塊，將其對應的位設置為 1。對于
已使用的塊，則將它們對應的位設置為 0。要提供 new[ ] 和 delete[ ] 操作符，您需要維護一個輔助的數據結構，
以便在創建或者銷毀 Complex 數組對象時幫助跟蹤位圖中有多少位需要設置為 1 或者 0。
創建一個位圖內存管理器
內存管理器從操作系統中請求足夠大的內存塊。從這個塊中劃分出部分內存以進行稍后的內存分配。如果請求失敗，
那么內存管理器將解決這個問題，并將合適的消息傳遞給用戶，表示它已經退出。在這個階段中，位圖中的所有條
目都設置為 1。
如果內存管理器耗盡了空閑的內存塊，那么它將向操作系統進一步請求較大的內存塊。MemoryManager 數據結構中的
每個位圖都可以用于增大對應的內存塊。然而，在調用刪除操作之后，用戶可以使用對應的塊。因此，非連續的刪除
調用將導致所謂的分段的內存，并且可以從這個內存中提供適當大小的塊。
清單 10 中給出了 MemoryManager 類的基本結構。它包含 MemoryPoolList，后者保存了從操作系統中請求的內存塊的
起始地址。對于每個塊，在 BitMapEntryList 中都存在一個相應的條目。FreeMapEntries 是一種數據結構，可以用來
為 new 調用的非數組版本提高下一個可用空閑塊的搜索速度。
清單 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 對象數組所分配的內存的相關信息。實際上，它是數組的起始地址到結構的映射，
以便維護MemPoolListIndex、位圖中數組的 StartPosition 和數組的大小，如清單 11 中所示。
清單 11. ArrayInfo 結構定義
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”位的數組（作為位圖），這樣一來，這個數組中的每個位對應于所請求的內存的一個
塊。將所有的條目都設置為 1。這項工作在 BitMapEntry 的構造函數中完成。
在對 Complex 類的 new 或者 malloc 的非數組版本進行調用的過程中，內存管理器將檢查 FreeMapEntries 數據結構
中是否存在可用的塊。如果在其中找到了可用的塊，則返回這個塊，否則從操作系統中請求一個新的內存塊，并設
置其對應的 BitMapEntry。從這個塊中劃出部分內存塊返回給用戶，將其可用位設置為 0 以表示它不再空閑，并且
將指針返回給用戶，清單 13 中顯示了相關的代碼。
清單 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 中給出了為單個塊設置或重置位的代碼。
清單 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 中給出了為多個塊設置或重置位的代碼。
清單 15. MemoryManager::SetMultipleBlockBit 定義
void MemoryManager::SetMultipleBlockBits(ArrayMemoryInfo* info, bool flag)
{ BitMapEntry* mapEntry = &BitMapEntryList[info->MemPoolListIndex];
mapEntry->SetMultipleBits(info->StartPosition, flag, info->Size);
}
對于數組版本而言，處理方式有一點不同。用于數組的內存塊與那些用于單個對象內存分配的
內存塊分配自不同的內存塊。這減少了在調用兩種類型的 new 時搜索下一個空閑可用內存的開銷。
內存管理器將查找 ArrayMemoryList 數據結構，以獲取為數組提供內存的塊的有關信息。當找到
時，它將獲得這個塊中的適當部分，將其地址提供給用戶，并將相應的位設置為 0。如果出于某
種原因而導致操作失敗，那么將從操作系統中請求一個新的塊，并從中劃分出部分內存。兩種
new 調用的內存塊作為 MemPoolList 的一部分存儲在 MemoryManager 類中。
在調用 Complex 類型對象的指針的 delete、或者 free 的非數組版本的過程中，首先確定包含這
個指針的內存塊（請參見清單 16）。然后，根據這個塊的 BitMapEntry 將對應的位重置為 1，
從而使其成為可用的塊。整個操作將花費 O(1) 時間。對于 delete []，從 ArrayMemoryList 中
檢索相關信息，并且在已知起始位置和位圖大小的情況下，將這些位標記為可用。
清單 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);
}
}
下載部分中提供了位圖內存管理器代碼的完整清單。它是這部分討論的內存管理器的一個
工作示例，并且包括了我們在這個部分中討論的所有清單。
繼承帶來的問題
派生類的大小很可能會與其基類有很大的不同。例如，可以考慮 Complex 類的一個派生變體，
稱為 ComplexT，它用于跟蹤復數的值隨時間變化的情況，其中包含一個附加的 unsigned long 用來存儲時間。先前重寫的 new 或者 delete 操作符現在將無法工作，除非我們專門針對這個
派生變體再次定義它們。對于這個問題，有三種可能的解決方案：
基于空閑列表的內存管理器
在一個典型的程序中，內存塊的大多數請求都是特定大小的。這個內存管理器將充分利用這個
特點。要實現這一點，您需要維護一些列表，其中包含這種大小的空閑塊的地址。在技術行話
中，我們稱這些列表為空閑列表。例如，可以考慮某個程序，它將提出 8、16、24、32、48
和 64 字節的內存請求。出于這個目的，內存管理器中包含六個不同的空閑列表，并請求從對
應的列表提供特定大小的內存。與位圖內存管理器類似，在啟動時從操作系統中請求內存，并
且內存管理器在內部將從操作系統請求的塊劃分到各個列表中。在用戶為某個對象請求內存時，
比如“m”個字節，那么會將對象的大小轉換為最接近的塊大小“n”，并且存在一個空閑列表用來
存儲大小為“n”的塊。
有關保護字節（guard bytes）的簡單介紹
“n”字節的塊不僅存儲了對象，還存儲了一些元數據信息。每個塊的末尾附近都包含四個額外的
字節，其中包含在堆內存操作范例中稱為保護字節 的內容。通常，memcpy 和 memset 函數可以
訪問所分配內存的界限之外的內存字節。這將導致堆內存的破壞。許多編譯器都為所分配的 mem
塊添加了一些特殊字符，以充當該塊的哨兵（或者保護字節）。對于所分配內存的這些塊所進行
的任何訪問，都將檢查所分配的塊附近的特殊字符。如果找不到這些字符，那么將認為在程序執
行期間以非法的方式更改了它們的值，這暗示堆內存不再處于有序的狀態，并且因此受到了破壞。
通過這種機制，程序員可以捕獲一些所了解的內存錯誤。在下面的示例中，這四個字節中的其中
兩個充當了保護字節，第三個字節用于存儲這個對象的大小，最后一個字節存儲了一個標志，表
示這個對象是否可用、或者已經被占用。
創建一個空閑列表內存管理器
如前所述，內存管理器維護了一些指針的列表，這些指針指向可變大小的塊。它還對從操作系統
請求而來的內存塊進行維護，并作為memoryPool。在 MemoryManager 調用其析構函數時，這個池
可以用于釋放整個內存塊。清單 17 顯示了該數據結構。
清單 17. 基于空閑列表實現的 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 字節的三個類，因而需要大小為 24、32和40
個字節的塊來保存它們的保護字節。因此，Byte24PtrList、Byte32PtrList 和
Byte40PtrList 的使用最為頻繁，并且代碼也主要是和它們相關的。然而，設計相當
靈活，也可以用于添加您所希望的其他大小的列表。
為這些類重載了操作符 new 和 delete，它們將調用委派給負責內存分配和釋放的
allocate 和 free 例程。下面將詳細地介紹這些例程。我們使用了大小為 1024 的
塊作為對象的初始計數。另外，將示例中使用的每個類的大小作為預定義的常數進
行了存儲，如清單 18 中所示。
清單 18. 這個實現中所使用的預定義常數
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 例程中使用了這些常數。
allocate 例程
對于給定大小的塊，allocate 例程將確定使用內存管理器中的哪個列表。它將查找
必需的列表，以查看是否存在可用的塊。請注意，這個列表僅存儲了指向該塊的指
針，而不是塊本身（該塊是 MemoryPoolList 的一部分）。
如果空閑列表是空的，那么將從操作系統中請求附加的內存塊，并由
InitialiseByte24List、InitialiseByte32List 和InitialiseByte40List
例程將其組織為分區塊。
當存在某個空閑塊地址可供使用時，將對應的塊標記為不可使用，設置其保護字節，
并且返回該塊的地址?？梢钥紤]如清單 19 中所示的實現。
清單 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 例程接收塊的地址，并搜索位于塊末尾的、包含大小信息的字節（在保護字節中）。它是
塊中的倒數第二個字節。在獲得這個大小之后，將對象標記為可用（將最后一個字節設置為 1），
并獲取對應的列表。然后，將該對象加入空閑 列表中，這也標志著完成了刪除操作。可以考慮
清單 20 中的實現。
清單 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
}
下載部分中提供了空閑列表內存管理器代碼的完整清單。它是空閑列表內存管理器實現的一個
工作示例，并且包括我們在這個部分中討論的所有清單。
優點和不足之處
這個設計有下面幾個優點：
雖然這個設計可以顯著地改善性能，但它仍然存在不足之處，即它需要大量的內存。
多線程內存管理器
到目前為止，我們所創建的內存管理器并沒有考慮到并發的環境。在多線程環境中，
可能會有多個線程同時嘗試進行內存的分配和釋放。這意味著，我們必須確保在內
存管理器中進行的分配和釋放操作都是具有原子性的。也就是說，在兩個線程同時
嘗試這些操作時，我們必須在這兩個線程之間提供一種互斥的機制。要確保分配和
釋放操作具有原子性，標準的方法是使用一種基于鎖的機制。當一個線程調用這兩
種方法其中之一時，在它實際獲得對內存的訪問或者釋放內存之前，必須獲得一個
獨占鎖。如果該鎖由另一個線程所擁有，那么將阻塞當前線程，直到它擁有這個鎖
為止。清單 21 說明了用作鎖定機制的函數簽名。
清單 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 方法之間。
如果某個線程正在訪問內存池時，又有另一個線程調用了這些例程其中之一，那么它
必須等待，直到該鎖可用為止。清單 22 是該方法的經過修改的代碼片段。
清單 22. 分配和釋放方法的并發版本
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);
}
現在，內存管理器類需要包括一個 pthread_mutex_lock 對象。需要修改類構造函數，
以便調用 pthread_mutex_init 初始化鎖，并且類析構函數必須調用 pthread_mutex_destroy
以銷毀 mutex 對象。清單 23 是 MemoryManager 類的修改之后的代碼。
清單 23. 經過修改的 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);
}
現在，運行內存管理器的多線程版本。在我們的測試中，與單線程版本相比，它的運行要慢
得多，這說明了為什么需要提供專用的、自定義的內存管理器。
總結
本教程解釋了下面的幾個概念：
- 在用戶代碼中使用內存管理器的需求。
- 內存管理器的設計需求。
- 如何創建固定大小的分配器或者內存管理器。
- 如何創建可變大小的分配器。
- 多線程環境中的內存分配。
有關這個主題的更多信息，請參見參考資料部分。
下載
| 描述 | 名字 | 大小 | 下載方法 |
|---|
| 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 |
參考資料
學習
from:
http://www.ibm.com/developerworks/cn/education/aix/au-memorymanager/index.html
posted on 2012-05-26 22:41
chatler 閱讀(2541)
評論(0) 編輯 收藏 引用 所屬分類:
OS