1

我可以要求我的任何响应者只考虑“纯”C/C++（无论这意味着什么）吗？STL 没问题。升压不是。

我正在编写自己的 C++ 内存池类（在 Linux 系统上），用于在共享内存中分配和释放 C++ 对象。我需要这个来通过多个进程访问相同的对象。我将使用 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)）还是我错过了一些非常重要的东西？我立即看到的一个问题是，如果 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 然后开始使用它。您用于跟踪使用了哪些插槽的算法存在缺陷。一旦删除了一项，并且调整了指针列表，如果不遍历整个列表，就无法知道哪些插槽已被使用。一个简单的布尔数组就可以了，它仍然需要遍历列表。

如果你真的关心 O(n)，你需要维护 used 和 free 链表。这可以通过单个固定大小的 int 数组来完成。

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

将 firstUsedIndex 初始化为 MAXFOOOBJECTS，将 firstFreeIndex 初始化为 0。索引通过 MAXFOOOBJECTS 初始化为 1。这样，您可以将索引中的每个条目视为链接列表，其中内容是“下一个”值，MAXFOOOBJECTS 是您的列表终止符。分配可以在恒定时间内完成，因为您可以获取列表的前端节点。释放将是线性的，因为您必须在已使用列表中找到节点。您可以使用 (ptr - poolStart) / sizeof(Foo) 快速找到该节点，但您仍然需要找到前一个节点。

如果您还想消除重新分配成本，请将索引的大小加倍并将其视为双向链表。代码类似，但现在您可以在恒定时间内完成所有操作。

于 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 回答