*112584*

к.т.н.,доц. Довгалець С.М., Лісовенко А.І.

Вінницький національний технічний університет, Україна

Алгоритм динамічного розподілу пам’яті

Анотація: В даній статті описано новий алгоритм динамічного розподілу пам’яті, який дозволяє досягнутикращої швидкодії при використанні меншого об’єма пам’яті. В статті описано головні цілі розробки, алгоритм та область застосування запропонованого методу виділення пам’яті.

Ключові слова:пам’ять, динамічний розподіл, алгоритм, стратегія найкращого підходящого, фрагментація, блок.

Вступ: Динамічний розподіл пам’яті – це управлыння ресурсами обчислювального пристрою під час виконання програми. За допомогою динамічного розподілу пам’яті можна гнучко керувати часом життя об’єктів, що, на відміну від стекового методу розподілу, не призводить до неконтрольованого збільшення необхідної області пам’яті [1].

Динамічний розподіл пам’яті сьогодні є актуальною проблемою розподілу обчислювальних ресурсів. Особливо різко постає ця проблема при проектуванні мікропроцесорних пристроїв на основі мікроконтролерів, коли доводиться обробляти дані невеликого обсягу.

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

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

Динамічний розподіл поєднує в собі три процедури:

1. виділення пам’яті, яка по суті є блоком пам’яті необхідного розміру, утвореного з блоків, забезпечених операційною системою;

2. звільнення блоку пам’яті, що більше не потрібний, для подальшого використання;

3. склеювання між собою блоків пам’яті малого розміру для найбільш ефективного їх використання в майбутньому.

Існує ряд універсальних алгоритмів динамічного управління пам’ятю. Основні параметри, що їх характеризують, – це:

- час процесора, що використовується менеджером пам’яті під час роботи програми;

- обсяг пам’яті, що потрібен для реалізації стратегії динамічного управління пам’яттю;

- сумісність реалізацій; оскільки деякі платформи мають специфічні проблеми з обслуговуванням пам’яті.

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

Аналіз попередніх досліджень: Існує ряд стратегій динамічного управління пам’ятю. Більшість з них ґрунтується на методології, що використовує модель поведінки "типової" програми.

Стратегії динамічного управління пам’ятю можуть бути згруповані в три категорії:

1. Стратегії послідовної відповідності: стратегія першого відповідного блоку, наступного відповідного і найкращого блоку [2, 3].

2. Стратегії, що використовують вільні виділені списки: просте виділене зберігання, виділений придатний, і т.п [4, 5].

3. Методи близнят: двійкові і подвоєні ієрархічні системи [6].

Проте, за умови невеликого об’єму даних, ці стратегії мають певні недоліки. Наприклад, недоліком стратегії послідовної відповідності є значна фрагментація (більші блоки пам’яті на короткий час та менші – на довгий). У цьому випадку вивільнений великий блок буде, швидше за все, відразу використаний для виділення пам’яті відповідно до запиту на малий обсяг і після цього не вивільниться найближчим часом.

Недоліком стратегії, що використовує прості виділені списки є те, що вони не дозволяють змінювати розмір блоків (розбивати на менші або поєднувати) [7]. Тобто якщо програма запитуватиме тільки блоки одного розміру, система із вичерпуванням їхнього запасу розширюватиме динамічну пам’ять.

Методи близнят також мають ряд недоліків. За продуктивністю вони випереджають інші алгоритми динамічного програмування, проте вони неефективні для малого об’єму даних через те, що пам’ять розбивають на блоки, розмір яких є степенем числа 2, що при невеликому об’ємі даних призводить до значної внутрішньої фрагментації, наслідок якої – неефективне використання обчислювальних ресурсів [8].

Мета роботи: створення агоритму динамічного розподілу ресурсів, при якому за невеликого об’єму даних, досягається значна оптимізація затрат обчислювальних ресурсів і реалізація оптимального дотримання наступних вимог:

- мінімізація використання пам’яті;

- максимізація сумісності;

- мінімізація часових витрат;

- максимізувати мобільність.

Матеріал і результати досліджень: Алгоритм, що буде розроблятись, базуватиметься на сукупності двох структур даних:

- алгоритмі пошуку – структура даних, яка зберігає інформацію про усі вільні блоки, що забезпечує швидкий пошук потрібного блоку;

- алгоритм склейки – структура даних, що забезпечує додаткову інформацію, про блоки пам’яті: розмір попереднього і початкового блоків, інформацію, чи вільний блок, і т.п.

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

Друга структура: вимагає більш детального розгляду. Для нашого алгоритму виберемо стратегію вибору найкращого блоку Дана стратегія дає найменшу фрагментацію [2]. Здавалося б вартість алгоритму реалізації даної стратегії повинна бути занадто високою, але ми покажемо, що вибором правильної структури даних можна звести вартість пошуку вільного блоку до константної.

Для реалізації нового алгоритму, нам потрібно поєднати три типи алгоритмів:

1. Алгоритм пошуку і виділення блоку пам'яті (функція malloc)

2. Алгоритм повернення вільного блоку пам'яті системі (функція free )

3. Алгоритм склеювання декількох сусідніх вільних блоків в один.

Для пошуку блоку необхідно лише одержати в масиві покажчик на перший блок, що свідомо буде підходящого розміру. Ця стратегія називається – стратегією пошуку найкращого блоку – це виділення пам’яті із вільного блоку, розмір якого найближчий до необхідного розміру пам’яті. Для менших витрат часу краще взяти наступний у списку блок, якщо він такого ж розміру. Потім якщо розмір знайденого блоку збігається з необхідним розміром, блок видаляється зі списку і позначається як зайнятий. Якщо розмір знайденого блоку більше, то блок розбивається на 2 блоки, один із яких необхідного розміру, позначається як зайнятий і видаляється зі списку, другий же вставляється у відповідну позицію списку. Після операції виділення блоку коректується hash-масив.

Для повернення блоку системі позначаємо блок як вільний, уставляємо його в потрібну позицію в списку (використовуючи для знаходження цієї позиції hash-масив). Потім відповідно коректуємо hash-масив.

Алгоритм склейки блоків є найбільш складним і дорогим, але принциповим з погляду мінімізації фрагментації. На основі додаткової інформації в звільненому блоці можна легко знайти сусідні блоки. Якщо один або обидва сусідніх блоки також вільні, то виконується склеювання. Після склеювання необхідне корегування списку блоків і hash-масиву, що є найбільш складною і дорогою операцією. Склеювання блоків може виконаються як відразу після звільнення блоку, так і через якийсь проміжок часу, наприклад, коли нагромадилася певна кількість блоків.

На рисунку 1 показано приклад алгоритму найкращого блоку.

Рисунок 1– Алгоритм найкращого блоку

Результати дослідження: Описаний алгоритм був реалізований для операційної системи Linux. Дана реалізація була порівняна на предмет швидкодії з іншими розповсюдженими методами реалізації. Для оцінки швидкодії була написана програма, яка випадковим чином виділяла і повертала через певний час блоки розміром від 5 до 2000 байт. Оцінювався як і загальний час виконання програми, так і окремо середній час виконання операцій виділення та повернення блоків.

Для визначення загального часу виконання використовувалася стандартна утиліта time. Для дослідження швидкодії окремих операцій використовувалась програма GNU profiler.

Нижче наведено результати роботи створеного алгоритму та кількох існуючих алгоритмів динамічного виділення пам'яті, а саме: Doug Lea's malloc, Hans Boehm's garbage collector та Mike Haerthel's malloc. Вони наведені у таблиці 4.1.

Таблиця 4.1 – Результати тестування різних методів реалізації

динамічного виділення пам’яті

Реалізація	Загальний час, с	Час виділення блоку, мкс	Час повернення блоку, мкс	Використано пам’яті, байт
Doug Lea's malloc	4,78	2,01	2,38	2752512
Hans Boehm's garbage collector	15,74	–	–	6967296
Запропонований алгоритм	4,58	1,63	2,09	2770856
Mike Haerthel's malloc	4,21	0,58	2,01	3596288

Аналізуючи дані таблиці 1, запропонований метод, який розташовано в таблиці під №3, має значно кращі показники, в порівнянні з методом Hans Boehm's garbage collector: даний метод використовує на 151, % більше пам’яті та на 243,7% більше часу. Метод Mike Haerthel's malloc хоч і показує на 8,1% менші витрати часу, про те, використовує на 29,8% більше пам’яті, тому також значно програє, порівняно з новоствореним алгоритмом, оскільки більша швидкодія досягається завдяки використанню надмірної кількості пам’яті. Досить непогані показники має метод Doug Lea's malloc, але в порівнянні з новоствореним, він хоч і показує на 0,7% менші затрати пам’яті, але затрати часу збільшуються на 4,4%.

З наведених даних видно, що існує співвідношення між швидкодією і пам’яттю, яка використовується, і тому, як правило, більш швидкий алгоритм використовує більше пам’яті. Але на прикладі розробленого алгоритму було продемонстровано, що підвищення швидкодії для певного типу задач є можливим і при відносно сталому використанні пам’яті. Ми можемо побачити це, порівнявши створений нами метод та метод Doug Lea's malloc. Це видно на рисунку.

Рисунок 2 – Результат порівняння ефективності методів динамічного

виділення пам’яті

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

Література:

1. Christopher W. Fraser. A Retargetable C compiler: / Christopher W. Fraser. David R. Hanson. Design and Implementation. – Benjamin/Cummings Publishing, 1995.

2. A Memory Allocator. [Electronic resource] / Doug Lea // Hamser Verlag. – 1996. – Access mode: http://www.g.oswego.edu./dl/html/malloc.html.

3. Stephenson C. J. Fast fits: New method for dynamics storage allocation // Operating Systems Review 17(5), 1982, pp. 30-32.

4. J. L. Peterson langnp 1033, T. A. langnp1033 Norman. langnp 1033 Buggy systems. Communications of the ACM, 20(6): 421-431, 1877.

5. G.O. Collins. Experience in automatic storage allocation. Communications of the ACM, 4(10): 436-440, October 1961.

6. Mark S. Johnstone, Paul R. Wilson. The Memory Fragmentation Problem: Solve / Mark S. Johnstone, Paul R. Wilson. – Texas, 2003, pp.36.

7. Donald E. Knuth. The Art of Computer Programming, volume 1: Fundamental Algorithms, Addison- Wesley, Reading, Massachusetts, 1973, pp.205.

8. Шехофцев В. А. Операцыйны системию – К.: Видавнича группа ВНV, 2005. – 256 c.