Створення власного диспетчера пам’яті для проектів 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;
}


Кожне виконання даного циклу викликає 1000 виділень і перерозподілів пам’яті. 5000 ітерацій циклу приводять до 10 мільйонам перемикань між кодом користувача та кодом ядра. Компіляція даного тесту за допомогою gcc-3.4.6 на комп’ютері під управлінням Solaris 10 посіла в середньому 3,5 секунди. Це базовий показник продуктивності при використанні глобальних операторів new і delete і стандартного компілятора. Щоб створити спеціальний диспетчер пам’яті для класу Complex, Який оптимізує компіляцію, вам необхідно перевизначити Complex за допомогою операторів new і delete, Що відносяться до даного класу.

Оператори 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 залежить від розміру виділеної вільної пам’яті, значення якого зазначено в першому аргументі. Оператор delete очищає цю пам’ять. Зверніть увагу, що ці команди тільки виділяють і перерозподіляють пам’ять, а не викликають відповідні конструктори або деструктори. Конструктор завантажується в пам’ять, виділену оператором new, А оператор delete викликається тільки після того, як деструктор знищить об’єкт.

У другому варіанті 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);
}

Примітки:



На основі вищевикладеного, в лістингу 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*);
};

Для швидкості виконання ми використовуємо послідовності команд allocate і free.

Наш перший диспетчер пам’яті в однопоточному середовищі для об’єкта Complex


На основі принципів, про які ми говорили вище, ми створили наш перший диспетчер пам’яті. Для спрощення завдання, цей диспетчер пам’яті створений спеціально для об’єктів типу Complex і роботи тільки в однопоточному середовищі. Основним завданням є збереження набору об’єктів Complex доступним усередині диспетчера пам’яті і виконання подальшого виділення пам’яті з цього пулу. Якщо число об’єктів, необхідних для створення, перевищить число об’єктів в пулі, пул розширюється. Віддалені об’єкти повертаються в пул. Це процес зображено на малюнку 1.


Рисунок 1. Створення пулу об’єктів 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;
};
};


Однак такий підхід порушує принцип зручності для користувача, оскільки ми збиралися вносити в оригінальну структуру даних мінімальні зміни для інтеграції менеджера пам’яті. Удосконалюючи цей метод, ми створимо нову структуру даних FreeStore, Що містить в собі структуру даних, що служить покажчиком і зберігається як частина пулу замість об’єкта Complex. Структура даних для об’єкта FreeStore показана в лістингу 6.

Лістинг 6. Структура даних об’єкта FreeStore





struct FreeStore
{
FreeStore* next;
};

Потім пул пов’язується зі списком об’єктів FreeStore, Кожен з яких може вказувати на наступний елемент в пулі і використовуватися в якості об’єкта Complex. Клас MemoryManager повинен зберігати покажчик на заголовок першого вільного елементу в пулі. Він повинен володіти приватними методами для збільшення розміру пулу, в разі необхідності, і методами очищення пам’яті при завершенні програми. Змінена структура даних класу Complex з функціональністю FreeStore показана в лістингу 7.

Лістинг 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);
}

Використано незвичайний спосіб створення вільного сховища. Фокус полягає в розумінні того, що той же покажчик FreeStore* використовується в якості об’єкта Complex. Отже, розмір необхідний для індивідуальних покажчиків повинен бути рівним або перевищувати розмір FreeStore pointers must be the size of whichever is greater, the FreeStore* або Complex, Як показано в лістингу 9.

Лістинг 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; / / запам’ятайте, це був числовий масив
}
}





 



Зверніть увагу
Елементи у вільному сховище і раніше створюються за допомогою глобальних операторів new і delete. Тим не менш, також можна використовувати комбінацію malloc і free. У будь-якому випадку продуктивність збільшиться.
 

Готово! Ви зробили власний менеджер пам’яті для класу 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();
};

Параметр ArrayMemoryList зберігає інформацію про пам’ять, виділеної для масивів об’єктів Complex. В основному, там транслюються початкові адреси масиву в структуру, яка обслуговує MemPoolListIndex, Параметр масиву в бітової карті StartPosition і розмір масиву, як показано в лістингу 11.

Лістинг 11. Визначення структури ArrayInfo





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

Для спрощення операцій з бітовою картою, вона обробляється як об’єкт BitMapEntry, Який зберігає деякі додаткові метадані, як показано в лістингу 12. Резервування для налаштувань одного або декількох бітів в бітової карті забезпечуються через програмні інтерфейси додатків (application program interfaces, API) SetBit і SetMultipleBits. API FirstFreeBlock() запитує перший вільний блок, вказаний в бітової карті.

Лістинг 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;

Диспетчер пам’яті створює n-бітний масив (службовець бітової картою), таким чином, кожен біт масиву відповідає блоку запитуваної пам’яті. Всі значення рівні 1. Це здійснюється конструктором для 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.

Лістинг 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.

Лістинг 15. Диспетчер пам’яті: визначення SetMultipleBlockBits





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


У версії для масиву обробка злегка відрізняється. Блоки пам’яті для масивів виділяються з інших фрагментів пам’яті, на відміну від виділення пам’яті для одного об’єкта. Це скорочує час пошуку вільної пам’яті при обох типах виклику new. Диспетчер пам’яті переглядає структуру даних ArrayMemoryList для отримання інформації про фрагмент, що надає пам’ять для масивів. Знайшовши її, він звертається до необхідної частини даного фрагмента, передає її адреси користувачеві і встановлює значення бітів рівним 0. Якщо, з якоїсь причини, це не вдається, для обслуговування пам’яті у операційної системи запитується новий фрагмент. Фрагменти пам’яті для обох типів викликів new зберігаються в якості частин MemPoolList в класі MemoryManager.

При виклику 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, Використані раніше, не будуть працювати, поки ми не перевизначивши їх знову спеціально для дочірнього варіанту. Існує три можливих вирішення цієї проблеми:



Диспетчер пам’яті з вільними списками


У звичайній програмі більшість використовуваних блоків пам’яті має кілька фіксованих розмірів. Даний диспетчер пам’яті використовує переваги цієї евристики. Для її використання ви обробляєте списки, які містять адреси вільних блоків та їх розміри. На технічному жаргоні ці списки відомі як 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 і free.

Команда 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 (blockPtr)) + 30) = 32; / / розмір набору блоків * ((Static_cast (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 (blockPtr)) + 38) = 40; / / розмір набору блоків * ((Static_cast (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 (blockPtr)) + 22) = 24; / / розмір набору блоків * ((Static_cast (blockPtr)) + 23) = 0; / / блок зайнятий
Byte24PtrList.pop_front();
return blockPtr;
}
default : break;
}
return 0;
}

Команда Free

Команда 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 (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);

Для наших цілей ми будемо використовувати взаємовиключення pthread, описане в стандартному заголовку pthread.h, Який поставляється з набором GNU компілятора для моделювання механізму блокування і розблокування. Код команд allocation і free розміщений між методами pthread_mutex_lock і pthread_mutex_unlock . Якщо потік викличе будь-яку з цих команд, в час, коли інший потік вже звертається до пулу пам’яті, перший потік буде очікувати, поки блокування не стане доступною. Змінений фрагмент методів показаний в лістингу 22.


Лістинг 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);
}

Тепер в клас диспетчера пам’яті необхідно включити об’єкт pthread_mutex_lock. Конструктор класу повинен бути відповідно змінений для ініціалізації блокування за допомогою виклику pthread_mutex_init, А деструктор класу повинен викликатиpthread_mutex_destroy для ліквідації виключає об’єкта. Виправлений код для класу MemoryManager наведено в лістингу 23.


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





class MemoryManager : public IMemoryManager
{
pthread_mutex_t lock; … / / Код звичайного класу MemoryManager
};
MemoryManager::MemoryManager ()
{
pthread_mutex_init (&lock, NULL); … / / Код звичайного конструктора
}
MemoryManager:: ~MemoryManager ()
{ … / / Код звичайного деструктора
pthread_mutex_destroy (&lock);
}

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


Висновок


У цьому посібнику розглянуті наступні концепції:

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*