Блог

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

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

Проще использовать struct SharedMemStructure тот, который вы представили:

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

Затем в operator new :

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

По поводу ваших вопросов:

1. Конечно, постоянная сложность выделения несовместима со свойствами кучи. Я думаю, что O (log n) — лучшее, что вы можете получить.
2. Я вижу схему нормально, но детали находятся в том, что содержит этот класс Foo. Пока в нем нет виртуальных функций, виртуальных базовых классов, указателей, ссылок или любой другой конструкции на языке C , все должно быть в порядке.
3. Да, вы можете, почему бы и нет?
4. Если вам не нужно свойство heap, обычная и простая оптимизация заключается в том, чтобы избавиться от ptrArray элемента и создать список свободных слотов, используя первые байты каждого свободного слота, чтобы указать на следующий свободный.

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

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

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

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

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

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

Это похоже на проблему:

 int main() {
  Foo* a = new Foo; // a == amp;sharedMem->objects[0]
  Foo* b = new Foo; // b == amp;sharedMem->objects[1]
  // sharedMem->ptrArray: {a, b, ...}
  delete a;
  // sharedMem->ptrArray: {b, ...}
  Foo* c = new Foo; // c == amp;sharedMem->objects[1] == b!
}