1

「純粋な」C/C++ (それが何を意味するかは問わない) のみを検討するよう、回答者に依頼してもよろしいですか? STLは大丈夫です。ブーストはありません。

共有メモリ内の C++ オブジェクトの割り当てと割り当て解除のために、独自の C++ メモリ プール クラス (Linux システム上) を作成しています。複数のプロセスで同じオブジェクトにアクセスするには、これが必要です。POSIX セマフォを使用してメモリ プール オブジェクト操作へのアクセスを制御しますが、基本的な割り当て/割り当て解除に関する質問がありました。私のコードは、同じプールから割り当てられた同じサイズのオブジェクトに対してのみ機能します。現時点では、プールの動的な拡大と縮小に関連する問題は無視できます。

合計 MAXFOOOBJECTS 個の Foo オブジェクトに対して定義された共有メモリ セグメントがあるとします。共有メモリ セグメントを次のように定義します。

int shmid = shmget (somekey, ((sizeof(Foo) + 4) * MAXFOOOBJECTS) + 4, correctFlags);
void* sMem = shmat (shmid, (void*)0, 0);

この共有メモリを使用するすべてのプロセスによって、メモリは次のように解釈されます。

struct SharedMemStructure
{
   int numberOfFooObjectsInPool;
   Foo* ptrArray [MAXFOOOBJECTS]; // Pointers to all the objects in the array below
   Foo objects [MAXFOOOBJECTS]; // Same as the value in the shmget call
};

次のように定義されたオブジェクト Foo があるとします。

<Foo.h> 
class Foo
{
   public:
     Foo ();
     ~Foo ();
     void* operator new (); // Will allocate from shared memory
     void operator delete (void* ptr); // Will deallocate from shared memory
   private:
     static void* sharedMem; // Set this up to be a POSIX shared memory that accesses
                      // the shared region in memory
     static int shmid;
}

<Foo.cpp>
int Foo::shmid = shmget (somekey, ((sizeof(Foo) + 4) * MAXFOOOBJECTS) + 4, correctFlags);
void* Foo::sharedMem = shmat (shmid, (void*)0, 0);

void* Foo::operator new ()
{
   void* thisObject = NULL;
   sem_wait (sem); // Implementation of these is not shown
   // Pick up the start of a chunk from sharedMem (will make sure this
   // chunk has unused memory...

   thisObject = (sharedMem + 4 + 4 * MAXFOOOBJECTS + 
                (sizeof (Foo) * sharedMem->numberOfFooObjectsInPool);
   sharedMem->ptrArray[numberOfFooObjectsInPool] = thisObject;
   sharedMem->numberOfFooObjectsInPool ++;
   sem_post (sem);
   return thisObject;
}

void Foo::operator delete (void* ptr)
{
   int index = 0;
   sem_wait (sem); // Implementation of these is not shown
   // Swap the deleted item and the last item in the ptrArray;
   index = (ptr - (sharedMem + 4 + (4*MAXFOOOBJECTS)))/(sizeof(Foo));
   ptrArray[index] == ptrArray[numberOfFooObjectsInPool - 1];
   numberOfFooObjectsInPool --;
   sem_post (sem);
}

さて、私の質問は次のとおりです。

  1. 前述のスキームは、皆さん (新規と削除のそれぞれに O (1)) には問題ないように見えますか?それとも、まったく重要な何かが欠けていますか? すぐにわかる問題の 1 つは、たとえば Foo オブジェクト配列が最小ヒープとして解釈される場合、new と delete を実行するたびにヒープ プロパティを強制終了することです。
  2. このプールが最小ヒープに使用されないことを保証する場合 (たとえば、タイマー管理手法で必要な場合)、前述のスキームに問題はありますか?
  3. 反対に、共有メモリ内の Foo 配列を最小ヒープまたは最大ヒープとして (つまり、新規および削除中に) 管理し、新規または削除ごとに O (lg n) の最悪のケースを招く可能性があります。コメントはありますか？
  4. 望ましい他の方法はありますか？
4

3 に答える 3

3

私はあなたのアイデアは大丈夫​​だと思いますが、あなたのポインタ演算は少し面倒です...そして移植性もありません。一般的に言って、以前のメンバーのサイズを追加する構造体のメンバーにアクセスすることは絶対にしないでください。これは完全に移植性がない（そして非常に醜い）ためです。コンパイラには構造体のメンバーの配置制限がある場合があるため、適切と思われる場所にパディングバイトを挿入する場合があることに注意してください。

struct SharedMemStructureあなたが提示したものを使用する方が簡単です：

int shmid = shmget (somekey, sizeof(SharedMemStructure), correctFlags);
SharedMemStructure* sharedMem = static_cast<SharedMemStructure*>(shmat (shmid, (void*)0, 0));

次にoperator new：

//...
thisObject = &sharedMem[sharedMem->numberOfFooObjectsInPool];
//...

あなたの質問について：

  1. もちろん、一定の割り当ての複雑さは、ヒープのプロパティと互換性がありません。O（log n）が一番いいと思います。
  2. スキームは問題ないように見えますが、詳細はこれらのFooクラスに含まれているものにあります。仮想関数、仮想基本クラス、ポインター、参照、またはその他のC ++のような構造がない限り、問題はありません。
  3. はい、できます、なぜですか？
  4. ヒーププロパティが必要ない場合、通常の簡単な最適化は、ptrArrayメンバーを削除し、各空きスロットの最初のバイトを使用して次の空きスロットを指す空きスロットのリストを作成することです。
于 2011-11-06T23:06:53.263 に答える
3

移植性と読みやすさの両方のために、すべてのリテラル 4 を sizeof(int) と sizeof(Foo *) に置き換えます。または、さらに良いことに、定義した SharedMemStructure を実際に使用します。

それをスクラッチし、SharedMemStructure を変更してから、それを使い始めます。どのスロットが使用されているかを追跡するアルゴリズムに欠陥があります。1 つの項目が削除され、ポインター リストが調整されると、リスト全体を調べない限り、どのスロットが使用されたかを知る方法はありません。単純な bool 配列が機能しますが、それでもリストをたどる必要があります。

O(n) について本当に心配している場合は、使用済みおよび空きのリンク リストを維持する必要があります。これは、単一の固定サイズの int 配列で実行できます。

size_t indices[MAXFOOOBJECTS];
size_t firstUsedIndex;
size_t firstFreeIndex;

firstUsedIndex を MAXFOOOBJECTS に、firstFreeIndex を 0 に初期化します。indexs は、MAXFOOOBJECTS を介して 1 に初期化されます。このようにして、インデックスの各エントリをリンクされたリストとして扱うことができます。コンテンツは「次の」値であり、MAXFOOOBJECTS はリスト ターミネータです。リストの先頭ノードを取得できるため、一定時間で割り当てを行うことができます。使用済みリストでノードを見つける必要があるため、割り当て解除は線形になります。(ptr - poolStart) / sizeof(Foo) でノードをすばやく見つけることができますが、前のノードを見つける必要があります。

再割り当てのコストも削減したい場合は、インデックスのサイズを 2 倍にして、二重連結リストのように扱います。コードは似ていますが、すべてを一定時間で実行できるようになりました。

于 2011-11-06T23:34:41.017 に答える
1

これは問題のように見えます：

int main() {
  Foo* a = new Foo; // a == &sharedMem->objects[0]
  Foo* b = new Foo; // b == &sharedMem->objects[1]
  // sharedMem->ptrArray: {a, b, ...}
  delete a;
  // sharedMem->ptrArray: {b, ...}
  Foo* c = new Foo; // c == &sharedMem->objects[1] == b!
}
于 2011-11-06T23:11:27.323 に答える