malloc関数の実装
8646 ワード
1.malloc()動作メカニズム
malloc関数の本質は、使用可能なメモリブロックを長いリストに接続するいわゆる空きチェーンテーブルにある.malloc関数を呼び出すと、接続テーブルに沿ってユーザー要求を満たすのに十分なメモリブロックを探します.次に、メモリブロックを2つに分割します(1つのブロックのサイズはユーザーが要求したサイズと等しく、もう1つのブロックのサイズは残りのバイトです).次に、ユーザに割り当てられたメモリをユーザに渡し、残りのメモリ(ある場合)を接続テーブルに戻します.free関数を呼び出すと、ユーザが解放したメモリブロックが空きチェーンに接続されます.最後に、空きチェーンは多くの小さなメモリフラグメントに切断されます.この場合、ユーザーが大きなメモリフラグメントを申請すると、空きチェーンにはユーザーの要求を満たすフラグメントがない可能性があります.そこでmalloc関数は遅延を要求し,空きチェーン上で各メモリフラグメントを箱をひっくり返してチェックし始め,それらを整理し,隣接する小さな空きブロックを大きなメモリブロックに統合する.
2.オペレーティングシステムにおけるmalloc()の実装は、Cプログラムにおいて、malloc()およびfree()を複数回使用する.ただし、オペレーティングシステムでどのように実現されているかを考える時間はありません.このセクションでは、mallocとfreeの最も簡略化された実装コードを示し、メモリの管理時にどのようなことが起こったかを説明します.ほとんどのオペレーティングシステムでは、メモリ割り当ては、numbytesサイズのメモリを割り当て、最初のバイトを指すポインタを返すvoid*malloc(long numbytes)の2つの簡単な関数で処理されます.void free(void*firstbyte):以前のmallocから返されたポインタが与えられた場合、関数は割り当てられたスペースをプロセスの「空きスペース」に返します. malloc_Initはメモリ割り当てプログラムを初期化する関数になります.割り当てプログラムを初期化済みとして識別し、システム内の最後の有効なメモリアドレスを見つけ、管理するメモリへのポインタを確立する3つのことを完了します.この3つの変数はすべてグローバル変数です:リスト1.我々の単純な割り当てプログラムのグローバル変数int has_initialized = 0; void *managed_memory_start; void *last_valid_address;前述したように、マッピングされたメモリの境界(最後の有効アドレス)は、システムブレークポイントまたは現在のブレークポイントと呼ばれることが多い.多くのUNIXで?システムでは、現在のシステム中断点を示すために、sbrk(0)関数を使用する必要があります.sbrkは、パラメータに与えられたバイト数に基づいて現在のシステム割り込みポイントを移動し、新しいシステム割り込みポイントを返します.パラメータ0を使用して、現在のブレークポイントを返すだけです.ここではmalloc初期化コードです.現在のブレークポイントを見つけ、変数を初期化します.
リスト2.アサイメントプログラム初期化関数
メモリを完全に管理するには、どのメモリを割り当てて回収するかを追跡する必要があります.メモリブロックをfree呼び出した後、使用されていないとマークするなど、mallocを呼び出すときに使用されていないメモリブロックを特定する必要があります.したがって、mallocが返す各メモリの先頭には、まずこの構造が必要です.
リスト3.メモリ制御ブロック構造定義
プログラムがmallocを呼び出すと、この構造をどのように知っているかという問題が発生すると思います.答えは彼らが知る必要はありません.ポインタを返す前に、この構造に移動した後、隠します.これにより、返されるポインタは、他の用途に使用されていないメモリを指します.このように,呼び出しプログラムの観点から,それらが得たものはすべて空き,オープンメモリである.その後、free()を介してポインタを渡すと、メモリバイトを数バイト後退させるだけで、この構造を再び見つけることができます.メモリの割り当てについて説明する前に、解放について説明します.それは簡単だからです.メモリを解放するために、私たちがしなければならない唯一のことは、私たちが与えたポインタを取得し、sizeof(struct mem_control_block)バイトをロールバックし、使用可能としてマークすることです.対応するコードは次のとおりです.
リスト4.割当て関数の解除
ご覧のように、この割り当てプログラムでは、メモリの解放は非常に簡単なメカニズムを使用して、一定時間でメモリの解放を完了します.メモリの割り当ては少し難しいです.アルゴリズムの概要を以下に示します.
リスト5.プライマリ割当てプログラムの擬似コード
1. If our allocator has not been initialized, initialize it. 2. Add sizeof(struct mem_control_block) to the size requested. 3. start at managed_memory_start. 4. Are we at last_valid address? 5. If we are: A. We didn't find any existing space that was large enough -- ask the operating system for more and return that. 6. Otherwise: A. Is the current space available (check is_available from the mem_control_block)? B. If it is: i) Is it large enough (check "size"from the mem_control_block)? ii) If so: a. Mark it as unavailable b. Move past mem_control_block and return the pointer iii) Otherwise: a. Move forward "size"bytes b. Go back go step 4 C. Otherwise: i) Move forward "size"bytes ii) Go back to step 4
私たちは主に接続されたポインタを使用してメモリを巡り、開いたメモリブロックを探します.コード:
リスト6.しゅぶんぱいルーチン
3.malloc()の他の実装malloc()の実装は多く、これらの実装にはそれぞれ利点と欠点がある.割り当てプログラムを設計する際には、割り当ての速度を含む多くのトレードオフが必要です.回収の速度.スレッドのある環境の動作.メモリがライトされるときの動作.ローカルキャッシュ.ブックマークメモリのオーバーヘッド.仮想メモリ環境での動作.小さいオブジェクトまたは大きいオブジェクト.リアルタイム保証.各実装には、それ自体の長所と短所の集合がある.私たちの簡単な割り当てプログラムでは、割り当てが非常に遅く、回収が非常に速いです.また、仮想メモリシステムの使用が悪いため、大きなオブジェクトを処理するのに最適です.他にも多くの割り当てプログラムが使用できます.Doug Lea Malloc:Doug Lea Mallocは、Doug Leaの元の割当てプログラム、GNU libc割当てプログラム、ptmallocを含む、実際には完全な割当てプログラムのセットです.Doug Leaの配布プログラムは、私たちのバージョンと非常に似た基本構造を持っていますが、インデックスが追加されており、検索速度が速くなり、使用されていない複数のブロックを大きなブロックに組み合わせることができます.また、最近解放されたメモリをより迅速に再使用できるようにキャッシュもサポートされています.ptmallocはDoug Lea Mallocの拡張バージョンで、マルチスレッドをサポートしています.本明細書の後述するリファレンスセクションには、Doug LeaのMalloc実装について説明する文章がある.BSD Malloc:BSD Mallocは4.2 BSD発行に伴う実装であり、FreeBSDに含まれており、この割当プログラムは、予め確実なサイズのオブジェクトからなるプールからオブジェクトを割り当てることができる.オブジェクトサイズに使用されるsizeクラスがいくつかあります.これらのオブジェクトのサイズは2の数乗から定数を減算します.したがって、指定したサイズのオブジェクトを要求すると、それに一致するsizeクラスが簡単に割り当てられます.これにより、高速な実装が可能になりますが、メモリが無駄になる可能性があります.リファレンスセクションには、この実装について説明する文章があります.
Hoard:Hoardを作成する目的は、メモリ割り当てをマルチスレッド環境で非常に迅速に行うことです.したがって、ロックの使用を中心に構成され、すべてのプロセスがメモリの割り当てを待つ必要がなくなります.多くの割り当てと回収を行うマルチスレッドプロセスの速度を著しく速めることができます.リファレンスセクションには、この実装について説明する文章があります.多くの利用可能な割当プログラムの中で最も有名なのは、上記の割当プログラムです.プログラムに特別な割り当て要件がある場合は、プログラムメモリの割り当て方法に一致するカスタマイズされた割り当てプログラムを作成したい場合があります.しかし、割り当てプログラムの設計に慣れていない場合、カスタム割り当てプログラムは通常、それらが解決する問題よりも多くの問題をもたらします.
4.終了語の前に述べたように、malloc()を複数回呼び出した後、空きメモリは多くの小さなメモリセグメントに切断され、これにより、ユーザがメモリ使用を申請する際に、十分なメモリ領域が見つからないため、malloc()はメモリ整理を行う必要があり、関数の性がますます低下する.スマートなプログラマーは、常に2のサイズのべき乗のメモリブロックを割り当てることで、潜在的なmallocパフォーマンスの喪失を最大限に低減します.すなわち、割り当てられたメモリブロックサイズは、4バイト、8バイト、16バイト、18446744073709551616バイトなどである.これにより、空きチェーンに入る奇妙なセグメント(様々なサイズの小さなセグメントがある)の数を最大限に減らすことができる.空間を浪費しているように見えますが、浪費している空間は永遠に50%を超えないことがわかります.
malloc関数の本質は、使用可能なメモリブロックを長いリストに接続するいわゆる空きチェーンテーブルにある.malloc関数を呼び出すと、接続テーブルに沿ってユーザー要求を満たすのに十分なメモリブロックを探します.次に、メモリブロックを2つに分割します(1つのブロックのサイズはユーザーが要求したサイズと等しく、もう1つのブロックのサイズは残りのバイトです).次に、ユーザに割り当てられたメモリをユーザに渡し、残りのメモリ(ある場合)を接続テーブルに戻します.free関数を呼び出すと、ユーザが解放したメモリブロックが空きチェーンに接続されます.最後に、空きチェーンは多くの小さなメモリフラグメントに切断されます.この場合、ユーザーが大きなメモリフラグメントを申請すると、空きチェーンにはユーザーの要求を満たすフラグメントがない可能性があります.そこでmalloc関数は遅延を要求し,空きチェーン上で各メモリフラグメントを箱をひっくり返してチェックし始め,それらを整理し,隣接する小さな空きブロックを大きなメモリブロックに統合する.
2.オペレーティングシステムにおけるmalloc()の実装は、Cプログラムにおいて、malloc()およびfree()を複数回使用する.ただし、オペレーティングシステムでどのように実現されているかを考える時間はありません.このセクションでは、mallocとfreeの最も簡略化された実装コードを示し、メモリの管理時にどのようなことが起こったかを説明します.ほとんどのオペレーティングシステムでは、メモリ割り当ては、numbytesサイズのメモリを割り当て、最初のバイトを指すポインタを返すvoid*malloc(long numbytes)の2つの簡単な関数で処理されます.void free(void*firstbyte):以前のmallocから返されたポインタが与えられた場合、関数は割り当てられたスペースをプロセスの「空きスペース」に返します. malloc_Initはメモリ割り当てプログラムを初期化する関数になります.割り当てプログラムを初期化済みとして識別し、システム内の最後の有効なメモリアドレスを見つけ、管理するメモリへのポインタを確立する3つのことを完了します.この3つの変数はすべてグローバル変数です:リスト1.我々の単純な割り当てプログラムのグローバル変数int has_initialized = 0; void *managed_memory_start; void *last_valid_address;前述したように、マッピングされたメモリの境界(最後の有効アドレス)は、システムブレークポイントまたは現在のブレークポイントと呼ばれることが多い.多くのUNIXで?システムでは、現在のシステム中断点を示すために、sbrk(0)関数を使用する必要があります.sbrkは、パラメータに与えられたバイト数に基づいて現在のシステム割り込みポイントを移動し、新しいシステム割り込みポイントを返します.パラメータ0を使用して、現在のブレークポイントを返すだけです.ここではmalloc初期化コードです.現在のブレークポイントを見つけ、変数を初期化します.
リスト2.アサイメントプログラム初期化関数
/* Include the sbrk function */
#include
void malloc_init()
{
/* grab the last valid address from the OS */
last_valid_address = sbrk(0);
/* we don't have any memory to manage yet, so
*just set the beginning to be last_valid_address
*/
managed_memory_start = last_valid_address;
/* Okay, we're initialized and ready to go */
has_initialized = 1;
}メモリを完全に管理するには、どのメモリを割り当てて回収するかを追跡する必要があります.メモリブロックをfree呼び出した後、使用されていないとマークするなど、mallocを呼び出すときに使用されていないメモリブロックを特定する必要があります.したがって、mallocが返す各メモリの先頭には、まずこの構造が必要です.
リスト3.メモリ制御ブロック構造定義
struct mem_control_block
{
int is_available;
int size;
};プログラムがmallocを呼び出すと、この構造をどのように知っているかという問題が発生すると思います.答えは彼らが知る必要はありません.ポインタを返す前に、この構造に移動した後、隠します.これにより、返されるポインタは、他の用途に使用されていないメモリを指します.このように,呼び出しプログラムの観点から,それらが得たものはすべて空き,オープンメモリである.その後、free()を介してポインタを渡すと、メモリバイトを数バイト後退させるだけで、この構造を再び見つけることができます.メモリの割り当てについて説明する前に、解放について説明します.それは簡単だからです.メモリを解放するために、私たちがしなければならない唯一のことは、私たちが与えたポインタを取得し、sizeof(struct mem_control_block)バイトをロールバックし、使用可能としてマークすることです.対応するコードは次のとおりです.
リスト4.割当て関数の解除
void free(void *firstbyte)
{
struct mem_control_block *mcb;
/* Backup from the given pointer to find the
* mem_control_block
*/
mcb = firstbyte - sizeof(struct mem_control_block);
/* Mark the block as being available */
mcb->is_available = 1;
/* That's It! We're done. */
return;
}ご覧のように、この割り当てプログラムでは、メモリの解放は非常に簡単なメカニズムを使用して、一定時間でメモリの解放を完了します.メモリの割り当ては少し難しいです.アルゴリズムの概要を以下に示します.
リスト5.プライマリ割当てプログラムの擬似コード
1. If our allocator has not been initialized, initialize it. 2. Add sizeof(struct mem_control_block) to the size requested. 3. start at managed_memory_start. 4. Are we at last_valid address? 5. If we are: A. We didn't find any existing space that was large enough -- ask the operating system for more and return that. 6. Otherwise: A. Is the current space available (check is_available from the mem_control_block)? B. If it is: i) Is it large enough (check "size"from the mem_control_block)? ii) If so: a. Mark it as unavailable b. Move past mem_control_block and return the pointer iii) Otherwise: a. Move forward "size"bytes b. Go back go step 4 C. Otherwise: i) Move forward "size"bytes ii) Go back to step 4
私たちは主に接続されたポインタを使用してメモリを巡り、開いたメモリブロックを探します.コード:
リスト6.しゅぶんぱいルーチン
void *malloc(long numbytes)
{
/* Holds where we are looking in memory */
void *current_location;
/* This is the same as current_location, but cast to a
* memory_control_block */
struct mem_control_block *current_location_mcb;
/* This is the memory location we will return. It will
* be set to 0 until we find something suitable */
void *memory_location;
/* Initialize if we haven't already done so */
if(! has_initialized)
{
malloc_init();
}
/* The memory we search for has to include the memory
* control block, but the users of malloc don't need
* to know this, so we'll just add it in for them. */
numbytes = numbytes + sizeof(struct mem_control_block);
/* Set memory_location to 0 until we find a suitable
* location */
memory_location = 0;
/* Begin searching at the start of managed memory */
current_location = managed_memory_start;
/* Keep going until we have searched all allocated space */
while(current_location != last_valid_address)
{
/* current_location and current_location_mcb point
* to the same address. However, current_location_mcb
* is of the correct type, so we can use it as a struct.
* current_location is a void pointer so we can use it
* to calculate addresses. */
current_location_mcb = (struct mem_control_block *)current_location;
if(current_location_mcb->is_available)
{
if(current_location_mcb->size >= numbytes)
{
/* Woohoo! We've found an open,
* appropriately-size location. */
/* It is no longer available */
current_location_mcb->is_available = 0;
/* We own it */ memory_location = current_location;
/* Leave the loop */
break;
}
}
/* If we made it here, it's because the Current memory
* block not suitable; move to the next one */
current_location = current_location + current_location_mcb->size;
}
/* If we still don't have a valid location, we'll
* have to ask the operating system for more memory */
if(! memory_location)
{
/* Move the program break numbytes further */
sbrk(numbytes);
/* The new memory will be where the last valid
* address left off */
memory_location = last_valid_address;
/* We'll move the last valid address forward
* numbytes */
last_valid_address = last_valid_address + numbytes;
/* We need to initialize the mem_control_block */
current_location_mcb = memory_location;
current_location_mcb->is_available = 0;
current_location_mcb->size = numbytes;
}
/* Now, no matter what (well, except for error conditions),
* memory_location has the address of the memory, including
* the mem_control_block */
/* Move the pointer past the mem_control_block */
memory_location = memory_location + sizeof(struct mem_control_block);
/* Return the pointer */
return memory_location;
}3.malloc()の他の実装malloc()の実装は多く、これらの実装にはそれぞれ利点と欠点がある.割り当てプログラムを設計する際には、割り当ての速度を含む多くのトレードオフが必要です.回収の速度.スレッドのある環境の動作.メモリがライトされるときの動作.ローカルキャッシュ.ブックマークメモリのオーバーヘッド.仮想メモリ環境での動作.小さいオブジェクトまたは大きいオブジェクト.リアルタイム保証.各実装には、それ自体の長所と短所の集合がある.私たちの簡単な割り当てプログラムでは、割り当てが非常に遅く、回収が非常に速いです.また、仮想メモリシステムの使用が悪いため、大きなオブジェクトを処理するのに最適です.他にも多くの割り当てプログラムが使用できます.Doug Lea Malloc:Doug Lea Mallocは、Doug Leaの元の割当てプログラム、GNU libc割当てプログラム、ptmallocを含む、実際には完全な割当てプログラムのセットです.Doug Leaの配布プログラムは、私たちのバージョンと非常に似た基本構造を持っていますが、インデックスが追加されており、検索速度が速くなり、使用されていない複数のブロックを大きなブロックに組み合わせることができます.また、最近解放されたメモリをより迅速に再使用できるようにキャッシュもサポートされています.ptmallocはDoug Lea Mallocの拡張バージョンで、マルチスレッドをサポートしています.本明細書の後述するリファレンスセクションには、Doug LeaのMalloc実装について説明する文章がある.BSD Malloc:BSD Mallocは4.2 BSD発行に伴う実装であり、FreeBSDに含まれており、この割当プログラムは、予め確実なサイズのオブジェクトからなるプールからオブジェクトを割り当てることができる.オブジェクトサイズに使用されるsizeクラスがいくつかあります.これらのオブジェクトのサイズは2の数乗から定数を減算します.したがって、指定したサイズのオブジェクトを要求すると、それに一致するsizeクラスが簡単に割り当てられます.これにより、高速な実装が可能になりますが、メモリが無駄になる可能性があります.リファレンスセクションには、この実装について説明する文章があります.
Hoard:Hoardを作成する目的は、メモリ割り当てをマルチスレッド環境で非常に迅速に行うことです.したがって、ロックの使用を中心に構成され、すべてのプロセスがメモリの割り当てを待つ必要がなくなります.多くの割り当てと回収を行うマルチスレッドプロセスの速度を著しく速めることができます.リファレンスセクションには、この実装について説明する文章があります.多くの利用可能な割当プログラムの中で最も有名なのは、上記の割当プログラムです.プログラムに特別な割り当て要件がある場合は、プログラムメモリの割り当て方法に一致するカスタマイズされた割り当てプログラムを作成したい場合があります.しかし、割り当てプログラムの設計に慣れていない場合、カスタム割り当てプログラムは通常、それらが解決する問題よりも多くの問題をもたらします.
4.終了語の前に述べたように、malloc()を複数回呼び出した後、空きメモリは多くの小さなメモリセグメントに切断され、これにより、ユーザがメモリ使用を申請する際に、十分なメモリ領域が見つからないため、malloc()はメモリ整理を行う必要があり、関数の性がますます低下する.スマートなプログラマーは、常に2のサイズのべき乗のメモリブロックを割り当てることで、潜在的なmallocパフォーマンスの喪失を最大限に低減します.すなわち、割り当てられたメモリブロックサイズは、4バイト、8バイト、16バイト、18446744073709551616バイトなどである.これにより、空きチェーンに入る奇妙なセグメント(様々なサイズの小さなセグメントがある)の数を最大限に減らすことができる.空間を浪費しているように見えますが、浪費している空間は永遠に50%を超えないことがわかります.