« メモリのアライメント |
メイン
| 固定サイズメモリのアロケート »
2007年12月17日
基本テクニック:: メモリのアロケート malloc について
PC でプログラムを組んでいると malloc/free や new/delete がどのようにメモリを確保したり開放したりしているのか気にする機会はほとんどないが、組み込み関係だと時々メモリアロケートの問題に悩まされる。
メモリ管理のアルゴリズムは、ファーストフィットやベストフィットなどいくつかある。
ファーストフィットは、空きメモリリストで最初に見付かったメモリブロックを返す。
ベストフィットは、空きメモリリストの中で最もサイズの近いメモリブロックを返す。
一見ファーストフィットの方が速そうだが、メモリの断片化が進みやすく、メモリブロックの数が増えることから常に速いとは限らない。
逆にベストフィットはメモリの断片化が起きづらく、メモリブロックの数を抑えられる。
私の中では以上のような認識だが、malloc/free の呼び出し順やサイズなど利用状況によって状況は変わる。
4 メモリマネジメント のページでは、ベストフィットは使い物にならないとても小さな領域を増やす結果 につながって利用効率が落ちるとある。
でも、実際のプログラムで確保するメモリのサイズの種類は多くの場合限られており、ほとんど固定サイズを確保したり開放したりするだけなので、ベストフィット が効率良いと思っている。
まあ、それはいいとして具体的なアルゴリズム。
ベストフィット で基本的にこう言う仕組みという認識を元に書いてみたソースが以下の通り。
テストはしていないので、もし使うのならきちんとテストした方が良い。
//! @file MemoryManager.h
//! メモリマネージャ
//! ベストフィットによる実装
#ifndef __MEMORY_MANAGER_H__
#define __MEMORY_MANAGER_H__
#ifndef NULL
#define NULL 0
#endif
//! メモリの確保がコールされた時、返すメモリのアドレスの前に管理領域を付けて返す
//!
//! +------+------+------------------+
//! | next | size | allocated memory |
//! +------+------+------------------+
//! ↑ここのアドレスを返す
//!
//!
//! メモリ解放がコールされた時、渡されたアドレスから管理領域のアドレスを求めて
//! 空きメモリリストに加える
//!
//! ↓ここのアドレスが渡される
//! +------+------+------------------+
//! | next | size | allocated memory |
//! +------+------+------------------+
//! ↑ここのアドレスを求める
//! メモリマネージャ
class CMemoryManager
{
struct MemoryBlock {
struct MemoryBlock* next_;
size_t size_;
};
static const size_t BLOCK_SIZE = sizeof(MemoryBlock);
MemoryBlock* free_list_;
public:
CMemoryManager() : free_list_(NULL) {}
void Initialize( void* memarea, size_t size );
void* Alloc( size_t size );
void Free( void* mem );
};
#endif // __MEMORY_MANAGER_H__
|
//! @file MemoryManager.cpp
#include "MemoryManager.h"
//! アドレス型 環境に応じて変える
typedef unsigned long addr_t;
//! 初期化する
//! @param memarea : 管理するメモリ領域の先頭
//! @param size : メモリ領域のサイズ
void CMemoryManager::Initialize( void* memarea, size_t size )
{
free_list_ = (MemoryBlock*)memarea;
free_list_->size_ = size - BLOCK_SIZE;
free_list_->next_ = NULL;
}
//! メモリを確保する
//! @param size : 要求サイズ
//! @return 確保したメモリ、確保できなかったときはNULL
void* CMemoryManager::Alloc( size_t size )
{
// 4バイトアライメント, 環境に応じてアライメントサイズは変更
size = ((size + 3) / 4) * 4;
MemoryBlock* bestfit = NULL;
MemoryBlock* prev = NULL;
MemoryBlock* cur = free_list_;
while( cur ) {
if( cur->size_ == size ) {
if( prev ) {
prev->next_ = cur->next_;
} else {
free_list_ = cur->next_;
}
// 完全に同じサイズのメモリが見つかったのでそれを返す
return (void*)( (addr_t)cur + BLOCK_SIZE );
} else if( cur->size_ > size ) {
if( bestfit ) {
if( (bestfit->size_ - size) > (cur->size_ - size) ) {
bestfit = cur;
}
} else {
bestfit = cur;
}
}
prev = cur;
cur = cur->next_;
}
// 最も近いサイズのメモリを分割して返す
if( bestfit ) {
// 分割する
MemoryBlock* slice = (MemoryBlock*)( (addr_t)bestfit + BLOCK_SIZE + size );
slice->size_ = bestfit->size_ - ( size + BLOCK_SIZE );
// 空きリストの先頭につなぐ
if( bestfit == free_list_ ) {
slice->next_ = free_list_->next_;
free_list_ = slice;
} else {
slice->next_ = free_list_;
free_list_ = slice;
}
// 分割後サイズを設定し返す
bestfit->size_ = size;
return (void*)( (addr_t)bestfit + BLOCK_SIZE );
}
// 指定されたサイズ以上の空きブロックがなかった
return NULL;
}
//! メモリを解放する
//!
//! まず、解放対象のメモリと隣接する領域がないか検索し、見つかったらそこにつなげる
//! 見つからない場合は、フリーメモリリストにつなげる
//! @param m : 解放するメモリ
void CMemoryManager::Free( void* m )
{
MemoryBlock* del_mem = (MemoryBlock*)( (addr_t)m - BLOCK_SIZE );
int connected = 0;
// つなげられるメモリがなくなるまで繰り返す
do {
connected &= 0x01;
MemoryBlock* cur = free_list_;
MemoryBlock* prev = NULL;
// 隣接するメモリがないか検索する
while( cur ) {
if( cur != del_mem ) {
if( ((addr_t)del_mem + BLOCK_SIZE + del_mem->size_) == (addr_t)cur ) {
// curメモリが自分の後と隣接しているのでくっつける
del_mem->next_ = cur->next_;
del_mem->size_ += BLOCK_SIZE + cur->size_;
connected = 0x03;
if( !prev ) {
// 1番初めのメモリブロックとつなげた
free_list_ = del_mem;
} else if( prev != del_mem ) {
prev->next_ = del_mem;
}
break;
} else if( ((addr_t)cur + BLOCK_SIZE + cur->size_) == (addr_t)del_mem ) {
// curメモリが自分の前と隣接しているのでくっつける
cur->size_ += BLOCK_SIZE + del_mem->size_;
del_mem = cur;
connected = 0x03;
break;
}
}
prev = cur;
cur = cur->next_;
}
} while( connected & 0x02 );
if( connected == 0 ) {
// 隣接するメモリがないときはフリーリストに追加する
del_mem->next_ = free_list_;
free_list_ = del_mem;
}
}
|
アルゴリズムがわかりやすいように書いたので、効率は悪いかもしれない。
このソースを読めばどのような仕組みかはわかると思う。
関連記事・続きの記事
固定サイズメモリのアロケート
メモリのアロケート malloc について で malloc のアルゴリズムにつ... [続きを読む]
関連記事・続きの記事
メモリアロケートを計ってみる
メモリのアロケート malloc について や 固定サイズメモリのアロケート を... [続きを読む]
投稿者 Takenori : 2007年12月17日 00:48
comments powered by