組み込みシステムに適した C メモリ アロケータは何ですか?[閉まっている]
https://stackoverflow.com/questions/177209
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
非常に多くの小さなブロック (32-64b) を割り当てたり割り当て解除したりする、シングル スレッドの埋め込みアプリケーションがあります。キャッシュベースのアロケーターに最適なシナリオです。作成してみることもできますが、それはおそらく時間の無駄であり、すでに最前線で使用されているソリューションほど十分にテストおよび調整されていないでしょう。
では、このシナリオで使用できる最適なアロケーターは何でしょうか?
注記：システムで Lua 仮想マシンを使用しているため (これが割り当ての 80% 以上の原因となっています)、スタック割り当てを使用して割り当てパフォーマンスを向上させるようにコードを簡単にリファクタリングすることはできません。
解決
メモリの断片化に問題があったため、最近このトピックに関する調査を行いました。最終的に、GNU libcの実装にとどまり、必要に応じてアプリケーションレベルのメモリプールを追加することにしました。フラグメンテーションの動作が改善されたアロケーターは他にもありましたが、それらがグローバルにmallocに置き換わるのに十分満足できませんでした。 GNUには、その背後にある長い歴史の利点があります。
あなたの場合、それは正当化されているようです。 VMを修正できないと仮定すると、これらの小さな割り当ては非常に無駄です。環境全体がわからないが、小さなプール用に設計されたハンドラーに渡すことができるように、VMだけでmalloc / realloc / freeの呼び出しをラップすることを検討するかもしれない。
他のヒント
Cで行った過去のプロジェクトでは、組み込みシステムを含む幅広いプラットフォームで実行されるライブラリに独自のメモリ管理ルーチンを実装する道を歩みました。ライブラリは、多数の小さなバッファも割り当てて解放しました。比較的うまく動作し、実装に大量のコードを必要としませんでした。自分で何かを開発したい場合に備えて、その実装の背景を少し説明できます。
基本的な実装には、設定されたサイズのバッファを管理する一連のルーチンが含まれていました。ルーチンは、malloc（）およびfree（）のラッパーとして使用されました。これらのルーチンを使用して、頻繁に使用する構造の割り当てを管理し、セットサイズの汎用バッファーを管理しました。管理対象の各タイプのバッファーを記述するために、構造が使用されました。特定のタイプのバッファが割り当てられると、ブロック内のメモリをmalloc（）します（空きバッファのリストが空の場合）。 IE、10バイトのバッファーを管理している場合、これらのバッファーの100個分のスペースを含む単一のmalloc（）を作成して、断片化と必要なmallocの数を減らします。
各バッファの先頭には、空きリスト内のバッファを連鎖するために使用されるポインタがあります。 100個のバッファが割り当てられると、各バッファは空きリストにチェーンされます。バッファが使用中の場合、ポインタはnullに設定されます。また、「ブロック」のリストも維持しました。実際のmallocされたバッファでfree（）を呼び出すことで簡単なクリーンアップを行うことができるように、バッファの数。
動的バッファサイズの管理のために、バッファのサイズを示すsize_t変数も各バッファの先頭に追加しました。次に、これを使用して、解放されたときにバッファを戻すバッファブロックを識別しました。バッファーサイズを取得してからバッファーを空きリストに入れるためのポインター演算を行うmalloc（）およびfree（）の置換ルーチンがありました。また、管理するバッファの大きさにも制限がありました。この制限よりも大きいバッファーは、単にmallocされてユーザーに渡されました。管理した構造については、特定の構造の割り当てと解放のためのラッパールーチンを作成しました。
最終的には、ユーザーから未使用のメモリをクリーンアップするよう要求されたときにガベージコレクションを含めるようにシステムを進化させました。システム全体を制御できるので、システムのパフォーマンスを向上させるために時間をかけてさまざまな最適化を行うことができました。私が述べたように、それは非常にうまくいった。
パーティーに少し遅れましたが、最近見つけてテストした組み込みシステム用の非常に効率的なメモリアロケーターを共有したいだけです。 https://github.com/dimonomid/umm_malloc
これは、ARM7で動作するように特別に設計されたメモリ管理ライブラリです。個人的にはPIC32デバイスで使用しますが、16ビットおよび8ビットデバイスで動作するはずです（16ビットPIC24でテストする予定です） 、まだテストしていません）
デフォルトのアロケーターによる断片化にひどくbeatられました：私のプロジェクトはしばしば数バイトから数百バイトまでのさまざまなサイズのブロックを割り当て、時々「メモリー不足」エラーに直面しました。 PIC32デバイスには合計32KのRAMがあり、ヒープには8192バイトが使用されます。特定の瞬間に5Kを超える空きメモリがありますが、デフォルトのアロケーターには、断片化のために最大約700バイトの断片化されていないメモリブロックがあります。これはあまりにも悪いので、より効率的なソリューションを探すことにしました。
既にいくつかのアロケーターを知っていましたが、それらにはすべていくつかの制限があります（たとえば、ブロックサイズは2からではなく、128バイトなどから始まるべきです）。毎回、デフォルトのアロケーターに切り替える必要がありました。
しかし、私は幸運です：これを見つけました： http：// hempeldesigngroup .com / embedded / stories / memorymanager /
5Kの空きメモリがあるまったく同じ状況でこのメモリアロケータを試したところ、3800バイト以上のブロックがありました！私には信じられないほどでした（700バイトと比較して）、ハードテストを実行しました：デバイスは30時間以上重く動作しました。メモリリークはありません。すべて正常に機能します。 このアロケーターは、FreeRTOSリポジトリでも見つかりました。 http://svnmios.midibox.org/listing.php?repname=svn.mios32&path=%2Ftrunk%2FFreeRTOS%2FSource%2Fportable%2FMemMang%2F&rev=1041&peg= 1041＃、この事実は、umm_mallocの安定性の追加証拠です。 だから私は完全にumm_mallocに切り替えましたが、とても満足しています。
少し変更する必要がありました。マクロUMM_TEST_MAINが定義されていない場合、構成に少しバグがあったため、githubリポジトリを作成しました（リンクはこの投稿の上部にあります）。現在、ユーザー依存の構成は、個別のファイルumm_malloc_cfg.hに保存されています
このアロケーターに適用されるアルゴリズムにはまだ詳しくありませんが、アルゴリズムの非常に詳細な説明があるため、興味のある方は誰でもファイルumm_malloc.cの上部を見ることができます。少なくとも、「ビニング」アプローチは、以下の断片化に大きなメリットをもたらすはずです： http://g.oswego.edu/dl /html/malloc.html
マイクロコントローラ用の効率的なメモリアロケータが必要な場合は、少なくともこれを試してください。
これを聞いてからしばらく経ちましたが、私の最終的な解決策はLoKiのSmallObjectAllocatorを使用することでした。すべてのOS呼び出しを削除し、組み込みデバイス用のLuaエンジンのパフォーマンスを改善しました。非常に素晴らしく、シンプルで、約5分間の作業で十分です！
古いスレッドであっても、これに追加したいだけです。組み込みアプリケーションで、アプリケーションのメモリ使用量を分析し、さまざまなサイズのメモリ割り当ての最大数を考え出すことができる場合、通常、アロケータの最速タイプはメモリプールを使用するものです。組み込みアプリでは、実行時に必要になるすべての割り当てサイズを決定できます。これを行うことができれば、ヒープの断片化を完全に排除し、非常に高速に割り当てることができます。これらの実装のほとんどには、特別な場合に通常のmallocを実行するオーバーフロープールがあります。これは、適切に分析を行った場合には、はるかに少ないと思われます。
「バイナリバディ」システムを使用して、vxworksで効果を発揮しました。基本的に、ブロックを半分に分割してヒープを分割し、2つのサイズのブロックの最小のパワーを取得してリクエストを保持します。ブロックが解放されたら、ツリーをパスアップしてブロックをマージし、断片化を軽減できます。 Google検索で必要な情報がすべて表示されます。
私は、ヒープをデフラグし、メモリを再利用できるようにすることを目的とした tinymem という C メモリ アロケータを作成しています。それをチェックしてください：
https://github.com/vitiral/tinymem
注記：このプロジェクトは、Rust の実装に取り組むために中止されました。
https://github.com/vitiral/defrag-rs
また、umm_malloc についてはこれまで聞いたことがありませんでした。残念ながら断片化には対応していないようですが、確かに便利そうです。チェックしてみなければなりません。
