Пул памяти C ++ при реализации совместно используемой памяти: правильный ли этот метод выделения и освобождения?

Question

Могу ли я попросить любого респондента рассмотреть только «чистый» C / C ++ (что бы это ни значило)?STL в порядке.Boost - это не.

Я пишу свой собственный класс пула памяти 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 интерпретируется, например, как min heap, я уничтожаю свойство heap каждый раз, когда делаю новое и удаляю.
2. Если я гарантирую, что этот пул не будет использоваться для минимальной кучи (скажем, как того требуют методы управления таймером), есть ли у нас какие-либо проблемы с вышеупомянутой схемой?
3. С другой стороны, я мог бы управлять массивом Foo в разделяемой памяти как минимальной или максимальной кучей (т. Е. При обновлении и удалении) и получать O (lg n) наихудший случай для каждогоновый или удалить.Любые комментарии?
4. Любой другой способ, который предпочтительнее?

Answer 1

Замените все литералы 4 на sizeof (int) и sizeof (Foo *) как для переносимости, так и для удобства чтения.Или, что еще лучше, на самом деле используйте SharedMemStructure, который вы определили.

Поцарапайте это, измените SharedMemStructure и затем начните использовать его.Ваш алгоритм для отслеживания того, какие слоты используются, имеет недостатки.После удаления одного элемента и корректировки списка указателей невозможно узнать, какие слоты были использованы, не пройдя весь список.Будет работать простой массив bool, он все равно потребует обхода списка.

Если вы действительно беспокоитесь об O (n), вам необходимо поддерживать используемые и свободные связанные списки.Это может быть сделано с одним массивом фиксированного размера из int.

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

Инициализируйте firstUsedIndex в MAXFOOOBJECTS и firstFreeIndex в 0. Индексы инициализируются в 1 через MAXFOOOBJECTS.Таким образом, вы можете рассматривать каждую запись в индексах как связанный список, где содержимое - это «следующее» значение, а MAXFOOOBJECTS - это ваш терминатор списка.Выделения могут быть сделаны в постоянное время, потому что вы можете захватить передний узел списка.Распределение будет линейным, так как вы должны найти узел в используемом списке.Вы можете быстро найти узел с помощью (ptr - poolStart) / sizeof (Foo), но вам все равно нужно найти предыдущий узел.

Если вы также хотите устранить затраты на перераспределение, удвойте размер индексов иотноситься к нему как к двусвязному списку.Код похож, но теперь вы можете делать все в постоянное время.

Answer 2

Я нахожу вашу идею в порядке, но арифметика указателей немного громоздка ... и непереносима. Вообще говоря, вы никогда не должны обращаться к членам структуры, добавляя размеры предыдущих членов, так как это совершенно не переносимо (и довольно некрасиво). Помните, что у компилятора могут быть ограничения на выравнивание для членов структуры, поэтому он может вставлять байты заполнения везде, где сочтет нужным.

Проще использовать представленные вами 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 ++ ish, у вас все должно быть в порядке.
3. Да, можно, почему нет?
4. Если вам не нужно свойство heap, обычная и простая оптимизация состоит в том, чтобы избавиться от члена ptrArray и создать список свободных слотов, используя первые байты каждого свободного слота, чтобы указывать на следующий свободный слот. .

Answer 3

Это выглядит как проблема:

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!
}