Создание собственного диспетчера памяти для проектов C/C++ (исходники)

Зачем создавать специальный диспетчер памяти?

Чтобы понять как контроль над выделением памяти поможет вашим программам работать быстрее, вначале вспомним основы управления памятью в C/C++. Для решения вопросов управления памятью в этих языках программирования используются стандартные библиотечные функции malloc, free, calloc и realloc в языке C, и операторы new, new [ ], delete и delete [ ] в языке C++. Запомните это и обратите внимание на несколько моментов.

Такие функции, как malloc и new, являются выделителями памяти общего назначения. Ваша программа может быть однопоточной, однако, функцию malloc лучше использовать для многопоточных примеров. Дополнительная функциональность снижает производительность этой команды.

Команды malloc и new осуществляют вызовы к ядру операционной системы для выделения памяти, а команды free и delete создают запрос для освобождения памяти. Это означает, что операционная система выполняет переключение между пользовательским кодом и кодом ядра каждый раз при выполнении запроса памяти . Программы, осуществляющие повторные вызовы malloc или new, как правило, работают медленней из-за частых переключений среды.

Часто память, выделенная для программы и ненужная в дальнейшем, остается неудаленной. Язык C/C++ не обеспечивает автоматического удаления этого мусора. Это может привести к росту количества памяти, необходимой для программы. В случае действительно больших приложений, производительность может серьезно пострадать, поскольку имеющейся памяти может не хватать, и программе придется интенсивно обращаться к жёсткому диску.

Требования к разработке

Ваш диспетчер памяти должен удовлетворять следующим требованиям:

• скорость;
• надежность;
• удобство для пользователя;
• универсальность.

Скорость

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

Надежность

Диспетчер памяти должен, в случае необходимости, возвратить всю память системе до завершения программы. Это означает, что не должно быть утечек памяти. Он также должен уметь обрабатывать ошибки (например, запрос слишком большого объема памяти) и корректно исправлять их.

Удобство для пользователя

Для интеграции диспетчера памяти в код программы от пользователя должно требоваться минимальное количество изменений.

Универсальность

Диспетчер памяти должен быть удобен для переноса на другие системы, он не должен использовать функции управления памятью, зависящие от платформы.

Основные стратегии разработки диспетчера памяти

При разработке диспетчера памяти используются в основном следующие стратегии:

• запрос больших фрагментов памяти;
• оптимизация размера запрашиваемого фрагмента;
• пул удаленной памяти в контейнерах.

Запрос больших фрагментов памяти

Одной из наиболее популярных стратегий управления памятью является запрос больших фрагментов памяти при запуске программы и затем, периодически, во время работы программы. Запросы на выделение памяти для индивидуальной структуры данных производятся из полученных фрагментов. Следствием является значительное сокращение системных вызовов и увеличение производительности.

Оптимизация размера запрашиваемого фрагмента

В любой программе запросы определенного размера встречаются чаще остальных. Было бы отлично, если бы ваш диспетчер памяти был оптимизирован для выполнения таких запросов.

Пул очищенной памяти в контейнерах

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

Синхронизация операторов C++ new/delete

Начнем с простого примера. Допустим, ваша программа использует класс Complex для представления комплексных чисел, использующий операторы языка new и delete, как показано в листинге 1.

Листинг 1. Код С++ для класса Complex

                    
class Complex 
  {
  public:
  Complex (double a, double b): r (a), c (b) {}
  private:
  double r; // Действительная часть
  double c; // Комплексная часть
  };
  
int main(int argc, char* argv[]) 
  {
  Complex* array[1000];
  for (int i = 0;i  <  5000; i++) {
    for (int j = 0; j  <  1000; j++) {
      array[j] = new Complex (i, j);
      }
    for (int j = 0; j  <  1000; j++) {
      delete array[j];
      }
    }
  return 0;
  }      
    

Операторы New/Delete: подробный взгляд

В С++ управление памятью сводится к использованию операторов new или delete. Для разных классов кода могут использоваться различные политики выделения памяти, которые в случае необходимости используют оператор new, относящийся к данному классу. В противном случае, глобальные операторы new или delete должны быть переопределены. Операторы могут быть загружены одним из способов, показанных в листинге 2.

Листинг2. Загрузка операторов new или delete

                    
void* operator new(size_t size); 
void   operator delete(void* pointerToDelete); 
-OR-
void* operator new(size_t size, MemoryManager& memMgr); 
void   operator delete(void* pointerToDelete, MemoryManager& memMgr);
    

Во втором варианте new является оператором placement new, которому присвоен аргумент MemoryManager, как правило, являющийся структурой данных для выделения свободной памяти, в которую затем загружается конструктор объекта. Исходя из задач данного руководства, мы рекомендуем использовать первый вариант использования операторов new или delete поскольку размещение переменных приводит к значительному увеличению количества аргументов MemoryManager& в пользовательском коде, тем самым, входя в противоречие с удобством для пользователя.

Мы используем класс MemoryManager для выделения и перераспределения памяти с помощью операторов new и delete, служащих в качестве контейнера для следующих команд класса MemoryManager, как показано в листинге 3:

Листинг 3. Использование операторов new, new[ ], delete и delete[ ] в качестве оболочки.

                    
MemoryManager gMemoryManager; // Memory Manager, глобальная переменная

void* operator new (size_t size) 
  {
  return gMemoryManager.allocate(size);
  }

void* operator new[ ] (size_t size)
  {
  return  gMemoryManager.allocate(size);
  }

void operator delete (void* pointerToDelete)
  {
  gMemoryManager.free(pointerToDelete);
  }

void operator delete[ ] (void* arrayToDelete)
  {
  gMemoryManager.free(arrayToDelete);
  }      
    

Примечания:

• Размер, передаваемый оператору new[ ], это размер одного элемента в массиве, умноженный на количество элементов в массиве.
• В любых операторах new, delete, new[ ] или delete[ ], относящихся к классу, указатель недоступен. Как следствие, все эти четыре команды работают как статические методы. При разработке вы всегда должны помнить об этом.
• Вместо использования глобальной переменной для объявления диспетчера памяти, разумеется, можно использовать одноэлементное множество.

На основе вышеизложенного, в листинге 4 приводится основной интерфейс класса диспетчера памяти.

Листинг4. Интерфейс диспетчера памяти.

                    
class IMemoryManager 
  {
  public:
    virtual void* allocate(size_t) = 0;
    virtual void   free(void*) = 0;
  };

class MemoryManager : public IMemoryManager
  {
  public: 
    MemoryManager( );
    virtual ~MemoryManager( );
    virtual void* allocate(size_t);
    virtual void   free(void*);
  };      
    

Наш первый диспетчер памяти в однопоточной среде для объекта Complex

На основе принципов, о которых мы говорили выше, мы создали наш первый диспетчер памяти. Для упрощения задачи, этот диспетчер памяти создан специально для объектов типа Complex и работы только в однопоточной среде. Основной задачей является сохранение набора объектов Complex доступным внутри диспетчера памяти и выполнение дальнейшего выделения памяти из этого пула. Если число объектов, необходимых для создания, превысит число объектов в пуле, пул расширяется. Удаленные объекты возвращаются в пул. Это процесс изображен на рисунке 1.

Рисунок 1. Создание пула объектов Complex

Каждый блок в пуле предназначен для двух целей:

• Он хранит объект Complex;
• Он должен быть способен подключить себя к следующему блоку в пуле.

Хранение указателя внутри структуры объекта Complex не является оптимальным, поскольку увеличивает общее потребление памяти. Лучшим вариантом будет поместить частные переменные структуры объекта Complex в общую структуру и связать их с указателем объекта Complex. Когда указатель используется в качестве части пула, он указывает на следующий свободный элемент в пуле. При использовании отдельного объекта Complex используется хранение структуры в реальной и комплексной частях. В листинге 5 показана измененная структура данных.

Листинг 5. Измененная структура данных для хранения объекта Complex без дополнительных расширений

                    
class Complex 
  {
  public:
    Complex (double a, double b): r (a), c (b) {}
    private:
    union { 
      struct { 
        double r; // Действительная часть
        double c; // Комплексная часть
        };
      Complex* next;
    };
  };
      
    

Листинг 6. Структура данных объекта FreeStore

                    
struct FreeStore 
  {
  FreeStore* next;
  };      
    

Листинг 7. Измененная структура данных класса Complex с функциональностью FreeStore.

                    
#include <sys/types.h> 

class MemoryManager: public IMemoryManager 
  { 
  struct FreeStore
    {
     FreeStore *next;
    }; 
  void expandPoolSize ();
  void cleanUp ();
  FreeStore* freeStoreHead;
  public:
    MemoryManager () { 
      freeStoreHead = 0;
      expandPoolSize ();
      }
    virtual ~MemoryManager () { 
      cleanUp ();
      }
    virtual void* allocate(size_t);
    virtual void   free(void*);
  };

MemoryManager gMemoryManager;

class Complex 
  {
  public:
    Complex (double a, double b): r (a), c (b) {}
    inline void* operator new(size_t);
    inline void   operator delete(void*);
  private:
    double r; // Действительная часть
    double c; // Комплексная часть
  };    
    

1. Если еще не создано свободное хранилище, создается свободное хранилище, а затем переходим к шагу 3;
2. Если свободное хранилище заполнено, создается новое свободное хранилище;
3. Возвращаем первый элемент из свободного хранилища и помечаем следующий элемент как заголовок свободного хранилища.

Ниже приведена последовательность команд для удаления памяти:

1. Создаем следующее поле в указателе удаления и привязываем его к текущему заголовку свободного хранилища;
2. Помечаем указатель удаления как заголовок свободного хранилища.

Листинг 8 содержит исходные тексты операторов new и delete для класса Complex class. В листинге 9 показаны методы расширения и очистки свободного хранилища. Тем не менее, здесь есть проблема. Вы ее видите?

Листинг 8. Специальные методы выделения и перераспределения для класса Complex

                    
inline void* MemoryManager::allocate(size_t size)
  {
  if (0 == freeStoreHead)
    expandPoolSize ();

  FreeStore* head = freeStoreHead;
  freeStoreHead = head->next;
  return head;
  }

inline void MemoryManager::free(void* deleted)
  {
  FreeStore* head = static_cast <FreeStore*> (deleted);
  head->next = freeStoreHead;
  freeStoreHead = head;
  }

void* Complex::operator new (size_t size) 
  {
  return gMemoryManager.allocate(size);
  }

void Complex::operator delete (void* pointerToDelete)
  {
  gMemoryManager.free(pointerToDelete);
  }      
    

Листинг 9. Методы расширения и очистки свободного хранилища

                    
#define POOLSIZE 32

void MemoryManager::expandPoolSize ()
  {
  size_t size = (sizeof(Complex) > sizeof(FreeStore*)) ?
    sizeof(Complex) : sizeof(FreeStore*);
  FreeStore* head = reinterpret_cast <FreeStore*> (new char[size]);
  freeStoreHead = head;

  for (int i = 0; i < POOLSIZE; i++) {
    head->next = reinterpret_cast <FreeStore*> (new char [size]);
    head = head->next;
    }

  head->next = 0;
  }

void MemoryManager::cleanUp()
  {
  FreeStore* nextPtr = freeStoreHead;
  for (; nextPtr; nextPtr = freeStoreHead) {
    freeStoreHead = freeStoreHead->next;
    delete [] nextPtr; // запомните, это был числовой массив
    }
  }      
    

Готово! Вы сделали собственный менеджер памяти для класса Complex. Вернемся к результату базового теста равному 3,5 секунды. Запустим такой же тест для компиляции (нет необходимости в каких-либо изменениях клиентского кода). Теперь программа выполняется со сногсшибательным результатом 0,67 секунды! Чем вызвано такое значительное увеличение производительности? У этого две основные причины:

• Заметно снизилось количество переключений между кодом пользователя и кодом ядра, благодаря повторному использованию очищенной памяти собранной в пуле свободного хранилища;
• Этот диспетчер памяти является однопоточным выделителем, готовым к работе. Пока мы не планируем запускать эту программу в многопоточной среде.

Выше мы просили вас указать на проблему в коде. Проблема в том, что если объект Complex, созданный при помощи оператора newне удаляется, в данной схеме отсутствуют способы вернуть потерянную память. Конечно, если при этом разработчик использует стандартные глобальные операторы new и delete. Однако диспетчер памяти предназначен не только для увеличения производительности, но и для устранения утечек памяти. Команда cleanUp возвращает память операционной системе только в случае, если объект Complex, созданный при помощи команды new, явно удаляется. Эта проблема может быть решена только запросом больших блоков памяти у операционной системы во время запуска программы и их последующего хранения. Запросы памяти при помощи оператора new объекта Complex обрабатываются из этих блоков. Команда cleanUp работает, освобождая эти блоки полностью, а не отдельные объекты, созданные в этих блоках памяти.

Диспетчер памяти на основе битовой карты

Интересным усовершенствованием оригинальной схемы с выделением фиксированных объемов памяти, является диспетчер памяти на основе битовой карты. При этой схеме у операционной системы память запрашивается относительно большими фрагментами, а выделение памяти происходит из этих фрагментов. Перераспределение происходит, с помощью освобождения блока целиком за один проход, тем самым предотвращаются возможные утечки. Еще одним преимуществом этого решения является поддержка операторов new и delete для массивов.

При такой схеме диспетчер памяти запрашивает большой фрагмент памяти. Этот фрагмент, затем разделяется на маленькие блоки фиксированного размера. В этом случае, размер каждого из этих блоков равен размеру объекта Complex. В зависимости от количества блоков во фрагменте, битовая карта обрабатывает отдельно каждый блок для отображения статуса (свободен или занят), выделяя количество бит равное числу блоков. Когда программа запрашивает новый объект Complex, диспетчер памяти сверяется с битовой картой для выделения свободного блока. Всем свободным блокам присвоено значение 1. Выделение блока изменяет значение соответствующих блоков на 0. Для работы операторов new[ ] и delete[ ] вам необходимо создать вспомогательную структуру данных для хранения информации о том, сколько битов необходимо изменить при создании или удалении массива объекта Complex.

Создание диспетчера памяти на основе битовой карты

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

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

Основная структура класса MemoryManager приведена в листинге 10. Она содержит параметр MemoryPoolList, в котором хранится начальный адрес фрагментов памяти, запрашиваемых у операционной системы. Для каждого фрагмента хранится значение в параметре BitMapEntryList. FreeMapEntries - это структура данных, упрощающая быстрый поиск свободных блоков для вызовов new вне массивов.

Листинг 10. Определение класса MemoryManager

                    
class MemoryManager : public IMemoryManager 
  {
    std::vector<void*> MemoryPoolList;
    std::vector<BitMapEntry> BitMapEntryList;
    //два списка выше будут обрабатываться одинаково и, следовательно 
    //должны быть одного размера.
    std::set<BitMapEntry*> FreeMapEntries;
    std::map<void*, ArrayMemoryInfo> ArrayMemoryList;

  private:
    void* AllocateArrayMemory(size_t size);
    void* AllocateChunkAndInitBitMap();
    void SetBlockBit(void* object, bool flag);
    void SetMultipleBlockBits(ArrayMemoryInfo* info, bool flag);
  public: 
    MemoryManager( ) {}
    ~MemoryManager( ) {}
    void* allocate(size_t);
    void   free(void*);
    std::vector<void*> GetMemoryPoolList(); 
  };      
    

Листинг 11. Определение структуры ArrayInfo

                    
typedef struct ArrayInfo
  {
  int   MemPoolListIndex;
  int   StartPosition;
  int   Size;
  }
ArrayMemoryInfo;      
    

Листинг 12. Определение класса BitMapEntry

                    
typedef struct BitMapEntry
  {
  int      Index;
  int      BlocksAvailable;
  int      BitMap[BIT_MAP_SIZE];
  public:
    BitMapEntry():BlocksAvailable(BIT_MAP_SIZE)
      {
      memset(BitMap,0xff,BIT_MAP_SIZE / sizeof(char)); 
      // первоначально все блоки свободны и бит принимает значение равное 1
      // в карте обозначающей доступные блоки
      }
    void SetBit(int position, bool flag);
    void SetMultipleBits(int position, bool flag, int count);
    void SetRangeOfInt(int* element, int msb, int lsb, bool flag);
    Complex* FirstFreeBlock(size_t size);
    Complex* ComplexObjectAddress(int pos);
    void* Head();
  }
BitMapEntry;      
    

Для вызова команды new или malloc вне массива для класса Complex, диспетчер памяти проверяет доступность блока в структуре данных FreeMapEntries. Если такой блок найден, происходит возврат, иначе у операционной системы запрашивается новый фрагмент памяти и соответствующее значение записывается в BitMapEntry. Блок памяти, возвращенный пользователю, обрабатывается из этого фрагмента, бит доступности этого блока принимает значение 0, обозначая занятость, а указатель явно возвращается пользователю, как показано в листинге 13.

Листинг 13. Диспетчер памяти: определение allocate

                    
void* MemoryManager::allocate(size_t size)
  {
  if(size == sizeof(Complex))    // версия вне массива
    {
    std::set<BitMapEntry*>::iterator freeMapI = FreeMapEntries.begin();
    if(freeMapI != FreeMapEntries.end())
      {
      BitMapEntry* mapEntry = *freeMapI;
      return mapEntry->FirstFreeBlock(size);
      }
    else
      {
      AllocateChunkAndInitBitMap();
      FreeMapEntries.insert(&(BitMapEntryList[BitMapEntryList.size() - 1]));
      return BitMapEntryList[BitMapEntryList.size() - 1].FirstFreeBlock(size);
      }
    }
  else  // версия для массива
    {
    if(ArrayMemoryList.empty())
      {
      return AllocateArrayMemory(size);
      }
    else 
      {
      std::map<void*, ArrayMemoryInfo>::iterator infoI =ArrayMemoryList.begin();
      std::map<void*, ArrayMemoryInfo>::iterator infoEndI = 
        ArrayMemoryList.end();
      while(infoI != infoEndI)
        {
        ArrayMemoryInfo info = (*infoI).second;
        if(info.StartPosition != 0)  // поиск только в тех блоках памяти   
          continue;             // где выделение выполнено с первого байта
        else 
          {
          BitMapEntry* entry = &BitMapEntryList[info.MemPoolListIndex];
          if(entry->BlocksAvailable < (size / sizeof(Complex))) 
            return AllocateArrayMemory(size);
          else 
            {
            info.StartPosition = BIT_MAP_SIZE - entry->BlocksAvailable;
            info.Size = size / sizeof(Complex);
            Complex* baseAddress = static_cast<Complex*>(
              MemoryPoolList[info.MemPoolListIndex]) + info.StartPosition;

            ArrayMemoryList[baseAddress] = info;
            SetMultipleBlockBits(&info, false);

            return baseAddress;
            } 
          }
        }
      }
    } 
  }      
    

Листинг 14. Диспетчер памяти: определение SetBlockBit

                    
void MemoryManager::SetBlockBit(void* object, bool flag)
  {
  int i = BitMapEntryList.size() - 1;
  for (; i >= 0 ; i--)
    {
    BitMapEntry* bitMap = &BitMapEntryList[i];
    if((bitMap->Head <= object )&& 
      (&(static_cast<Complex*>(bitMap->Head))[BIT_MAP_SIZE-1] >= object))
      {
      int position = static_cast<Complex*>(object) - 
      static_cast<Complex*>(bitMap->Head);
      bitMap->SetBit(position, flag);
      flag ? bitMap->BlocksAvailable++ : bitMap->BlocksAvailable--;
      }
    }
  }      
    

Листинг 15. Диспетчер памяти: определение SetMultipleBlockBits

                    
void MemoryManager::SetMultipleBlockBits(ArrayMemoryInfo* info, bool flag)
  {
  BitMapEntry* mapEntry = &BitMapEntryList[info->MemPoolListIndex];
  mapEntry->SetMultipleBits(info->StartPosition, flag, info->Size);
  }
      
    

При вызове delete или free вне массива, для указателя на объект типа Complexвначале определяется фрагмент памяти, содержащий этот указатель (см. листинг 16). В соответствии с BitMapEntry для этого фрагмента соответствующим битам возвращается значение 1, тем самым они помечаются как доступные. Вся операция занимает время O(1). Для delete [] запрашивается связанная информация из ArrayMemoryList, а затем, когда становится известна начальная позиция и размер битовой карты, это множество битов помечается как доступное.

Листинг 16. Диспетчер памяти: определение free

                    
void MemoryManager::free(void* object)
  {
  if(ArrayMemoryList.find(object) == ArrayMemoryList.end())
    SetBlockBit(object, true);         // простое удаление блока 
  else
    {//удаление блока памяти
    ArrayMemoryInfo *info = &ArrayMemoryList[object];
    SetMultipleBlockBits(info, true);
    }
  }
    

Проблема с наследованием

Размер дочернего класса может значительно отличаться от размера родительского класса. Для примера рассмотрим дочерний вариант класса Complex под названием ComplexTпредназначенный для отслеживания значений комплексного числа с течением времени, который содержит unsigned long для хранения продолжительности времени. Операторы new или delete, использованные ранее, не будут работать, пока мы не переопределим их снова специально для дочернего варианта. Существует три возможных решения этой проблемы:

• Разрешить MemoryManager обрабатывать два различных пула для этих двух классов. Как следствие, это означает два варианта команд выделения/перераспределения и два указателя на два заголовка пулов. Эта схема работает, но имеет ограниченную масштабируемость;
• Обработка единого пула с размером, зависящим от самого большого дочернего класса. Команда allocate всегда возвращает размер самого большого класса, вне зависимости от того, какой объект в иерархии требует памяти. Эта схема великолепно работает, но не очень удобна из-за возрастающего расхода памяти;
• Создать диспетчер памяти общего назначения с выделением памяти переменного размера.

Диспетчер памяти со свободными списками

В обычной программе большинство используемых блоков памяти имеет несколько фиксированных размеров. Данный диспетчер памяти использует преимущества этой эвристики. Для ее использования вы обрабатываете списки, которые содержат адреса свободных блоков и их размеры. На техническом жаргоне эти списки известны как free-lists (списки свободной памяти). Для примера, рассмотрим программу, которая формирует запросы памяти размером 8, 16, 24, 32, 48 и 64 байта. В этом случае диспетчер памяти содержит шесть разных списков и запрашивает блок определенного размера из соответствующего списка. Подобно диспетчеру печати на основе битовой карты, память запрашивается у ОС при запуске, а диспетчер памяти распределяет этот блок по спискам. Всякий раз, когда пользователь запрашивает память для объекта, размером m байт, размер объекта конвертируется в ближайший соответствующий размер блок n, для которого свободные списки хранят блоки размера n.

Краткое введение в защитные байты

N-байтный блок хранит не только объект, но и некоторые метаданные. Каждый блок содержит в конце 4 дополнительных байта, известные под названием защитные байты ( guard bytes ) в парадигме операций с кучами памяти. Обычно функции memcpy и memset доступны для внедрения байтов, которые логически располагаются за пределами выделенной памяти. Это вызывает повреждение куч памяти. Многие компиляторы добавляют специальные символы в выделенный блок mem, которые служат стражами (или защитными байтами) блока. Любой доступ к таким блокам выделенной памяти проверяет наличие этих спецсимволов в выделенном блоке. Если спецсимволы не найдены, это означает, что их значение было каким-либо образом изменено во время работы программы, тем самым подразумевая, что куча памяти больше не упорядочена и, следовательно, повреждена. Это хороший способ выявления ошибок памяти, которые программистам сложно обнаружить. В следующем примере два из четырех байтов служат защитными байтами, следующий байт хранит размер данного объекта, а последний байт содержит флаг, обозначающий доступен ли объект или занят.

Создание диспетчера памяти со свободными списками

Данный диспетчер памяти обрабатывает списки указателей на блоки различных размеров, как указано выше. Он также обрабатывает фрагменты памяти, запрашиваемые у операционной системы как memoryPool. Этот пул может быть использован для очистки всех фрагментов памяти, когда MemoryManager вызывает свой деструктор. Структура данных показана в листинге 17.

Листинг 17. Описание класса MemoryManager для использования свободных списков

                    
class MemoryManager : public IMemoryManager 
  {
  private:
    VoidPtrList     Byte8PtrList;
    VoidPtrList     Byte16PtrList;
    VoidPtrList     Byte24PtrList;
    VoidPtrList     Byte32PtrList;
    VoidPtrList     Byte40PtrList;
    std::vector<void*>    MemoryPoolList;

    . . . . . . . . . //здесь можно разместить вспомогательные команды

  public: 
    MemoryManager( ) {}
    ~MemoryManager( ) {}
    void* allocate(size_t);
    void   free(void*);
  };    
    

В нашем примере используются три класса: 16, 28 и 32 байта, и соответственно требуются блоки размером 24, 32 и 40 байт для хранения их вместе с защитными байтами. Следовательно, наиболее часто используются Byte24PtrList, Byte32PtrList и Byte40PtrList, вокруг которых и сконцентрирован весь код. Тем не менее, такой дизайн является достаточно гибким для добавления списков других необходимых размеров.

Для этих классов операторы new и deleteперегружаются, передавая вызовы командам allocate и free, выполняющим выделение и перераспределение памяти. Здесь эти команды рассматриваются подробно. Мы работаем с фрагментом размером 1024 в качестве начального счетчика объектов. Также, размер всех классов, используемых в данном примере хранится в качестве предопределенной константы, как показано в листинге 18.

Листинг 18. Предопределенные константы, используемые в данной реализации

                    
  const int JOB_SCHEDULER_SIZE = sizeof(JobScheduler);
  const int COMPLEX_SIZE = sizeof(Complex);
  const int COORDINATE_SIZE = sizeof(Coordinate);
  const int POOL_SIZE = 1024; //количество элементов в одном пуле
            //может меняться в зависимости от требований к приложению
 

  const int MAX_BLOCK_SIZE = 36; //может меняться в зависимости от приложения 
                //В данном случае равно 36

      
    

Команда Allocate

В зависимости от размера блока команда allocate определяет, какой из списков будет использован диспетчером памяти. Если доступны любые блоки, он проверяет необходимый список. Обратите внимание на то, что этот список хранит указатели на блоки, а не сами блоки (блоки хранятся в MemoryPoolList). Если свободный список пуст, у операционной системы запрашивается дополнительный фрагмент памяти и обрабатывается как раздельные блоки командами InitialiseByte24List, InitialiseByte32List и InitialiseByte40List.

При наличии свободных блоков, необходимое количество блоков помечается недоступными, записываются их защитные байты и возвращается адрес этого блока. Обсуждаемая реализация показана в листинге 19.

Листинг 19. Диспетчер памяти: определение allocate

                    

void* MemoryManager::allocate(size_t size)
  {
  void* base = 0;
  switch(size)
    {
    case JOB_SCHEDULER_SIZE :  
      {
      if(Byte32PtrList.empty())
        {
        base = new char [32 * POOL_SIZE];
        MemoryPoolList.push_back(base);
        InitialiseByte32List(base);
        }
      void* blockPtr =  Byte32PtrList.front();
      *((static_cast<char*>(blockPtr)) + 30) = 32; //размер набора блоков
      *((static_cast<char*>(blockPtr)) + 31) = 0; //блок занят
      Byte32PtrList.pop_front();
      return blockPtr;
      }         
    case COORDINATE_SIZE :  
      {
      if(Byte40PtrList.empty())
        {
        base = new char [40 * POOL_SIZE];
        MemoryPoolList.push_back(base);
        InitialiseByte40List(base);
        }
      void* blockPtr =  Byte40PtrList.front();
      *((static_cast<char*>(blockPtr)) + 38) = 40; //размер набора блоков
      *((static_cast<char*>(blockPtr)) + 39) = 0; //блок занят
      Byte40PtrList.pop_front();
      return blockPtr;
      }         
    case COMPLEX_SIZE : 
      {
      if(Byte24PtrList.empty())
        {
        base = new char [24 * POOL_SIZE];
        MemoryPoolList.push_back(base);
        InitialiseByte24List(base);
        }
      void* blockPtr =  Byte24PtrList.front();
      *((static_cast<char*>(blockPtr)) + 22) = 24; //размер набора блоков
      *((static_cast<char*>(blockPtr)) + 23) = 0; //блок занят
      Byte24PtrList.pop_front();
      return blockPtr;
      }
    default : break;
    }
  return 0;
  }
    

Команда free получает адрес блока и ищет в защитных байтах информацию о размере, расположенную в конце блока. Это предпоследний байт в блоке. После получения размера, объект помечается как доступный (последнему байту присваивается значение 1) и извлекается соответствующий список. Затем, объект помещается в свободный список, тем самым, обозначая завершение удаления. Обсуждаемая реализация показана в листинге 20.

Листинг 20. Диспетчер памяти: определение free

                    
void MemoryManager::free(void* object)
  {
  char* init = static_cast<char*>(object);

  while(1)
    {
    int count = 0;
    while(*init != static_cast<char>(0xde))  
          //эта петля никогда не будет выполняться больше раз, чем  
      {                 // MAX_BLOCK_SIZE и следовательно O(1)

      init++;
      if(count > MAX_BLOCK_SIZE)
        {
        printf ("runtime heap memory corruption near %d", object);
        exit(1);
        } 
      count++; 
      }
    if(*(++init) == static_cast<char>(0xad))  // получаем защитные байты 
      break;  // извне, пока 
    }
  init++;
  int blockSize = static_cast<int>(*init);
  switch(blockSize)
    {
    case 24: Byte24PtrList.push_front(object); break;
    case 32: Byte32PtrList.push_front(object); break;
    case 40: Byte40PtrList.push_front(object); break;
    default: break;
    }
  init++;
  *init = 1; // присваиваем байту значение свободен/занят      
  }            
    

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

Преимущества и недостатки

Существует несколько преимуществ данной реализации:

• Выделение памяти различного размера является элегантным решением;
• Данная реализация является гибкой и может быть расширена добавлением размеров в списки, исходя из требований к программному обеспечению;
• Возможность добавлять защитные байты позволяет использовать множество метаданных, которые могут храниться в объекте. Мы уже использовали это для обнаружения повреждений куч памяти.

Несмотря на увеличение производительности, недостатком данной реализации является активное использование памяти.

Многопоточный диспетчер памяти

Диспетчеры памяти, созданные нами ранее, не работают в средах с параллельными вычислениями. В многопоточных средах выделение и перераспределение памяти потенциально может быть применено сразу к нескольким потокам. Это означает, что мы должны быть уверены в том, что операции выделения и сброса относятся к необходимому элементу. Следовательно, мы должны создать механизм, гарантирующий взаимное исключение для двух потоков, при попытке выполнить эти операции одновременно. Стандартным способом убедиться в том, что способы выделения и сброса являются атомарными, является замена механизма блокировки. Каким бы из этих способов не вызывался поток, он должен стать владельцем уникальной исключительной блокировки, перед тем как он сможет получить доступ к свободной памяти. Если блокировку получает другой поток, текущий поток блокируется до тех пор пока сам не получит эту блокировку. Подписи функций для механизмов блокировки показаны в листинге 21.

Листинг 21. методы взаимоисключения pthread

                    
#include <pthread.h>

int pthread_mutex_init(pthread_mutex_t *mutex, 
    const pthread_mutexattr_t *attr);
int pthread_mutex_destroy(pthread_mutex_t *mutex);
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_trylock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);      
    

Листинг 22. Многопоточные версии методов выделения и сброса

                    
void* MemoryManager::allocate(size_t size) 
  {
  pthread_mutex_lock (&lock); 
  ... // обычный код выделения памяти
  pthread_mutex_unlock (&lock);
  }

void* MemoryManager::free(size_t size) 
  {
  pthread_mutex_lock (&lock); 
  ... // обычный код перераспределения памяти
  pthread_mutex_unlock (&lock);
  }      
    

Листинг23. Класс MemoryManager, измененный для потокового выделения и перераспределения памяти

                    
class MemoryManager : public IMemoryManager 
  { 
  pthread_mutex_t lock;
  ... // код обычного класса MemoryManager
  };

MemoryManager::MemoryManager () 
  {
  pthread_mutex_init (&lock, NULL);
  ... // код обычного конструктора 
  }

MemoryManager:: ~MemoryManager () 
  {
  ... // код обычного деструктора  
  pthread_mutex_destroy (&lock);
  }      
    

Заключение

В данном руководстве рассмотрены следующие концепции:

• Необходимость диспетчера памяти в пользовательском коде;
• Требования к дизайну диспетчера памяти;
• Как создать диспетчер памяти, работающий с выделением памяти фиксированного размера;
• Как выполнить выделение памяти переменного размера;
• Выделение памяти в многопоточной среде.

• Source files for bitmapped memory manager
• Source files for free-lists based memory manager