Новая система управления памятью в MorphOS

Многие компоненты AmigaOS создавались 25 лет назад. В те времена системные ресурсы были весьма скромны, а процессоры - относительно неторопливы.

Для Exec был выбран самый простой и, во многих случаях, довольно быстрый алгоритм управления памятью: First Fit (буквально «первый подходящий» - прим. перев.). Этот алгоритм позволяет получить очень большую скорость распределения при условии отсутствия фрагментации. В то же время, механизм освобождения памяти является не столь эффективным. Основная проблема заключается в фрагментированности памяти: процедура First Fit будет замедляться по экспоненциальному закону по мере увеличения степени фрагментации. Через какое-то время фрагментация достигает такой величины, что уменьшение скорости работы системы становится заметной глазу. Наконец, процедура First Fit сама по себе является источником фрагментации, так как выделяет [приложению] не лучший, а первый попавшийся фрагмент памяти.

MorphOS унаследовала от AmigaOS алгоритм управления памятью. Он работал достаточно хорошо, но вскоре стало ясно, что алгоритм имеет серьёзные недостатки. Особо продолжительные сеансы (до нескольких дней) использования сложных приложений (вроде IBrowse) легко могут вызвать замедление системы. Таким образом, время алгоритма First Fit прошло, и настала пора искать что-нибудь более подходящее для замены.

Я, как разработчик, должен был добиться, чтобы новая система управления памятью одновременно удовлетворяла трём условиям:

1 Совместимость

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

Эта же задача обещало стать наиболее сложной из всех решаемых. API управления памятью в AmigaOS довольно запутан непонятными функциями типа AllocAbs(), AvailMem() и AddMemList(), освобождающими занятую память частично, флагом MEMF_REVERSE и описанием (в документации) свойств выравнивания [адресов] памяти.

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

void *allocaligned(ULONG size, ULONG flags, ULONG align)
{
  void *ptr = AllocMem(size + align - 1, flags & ~MEMF_CLEAR);
  if (ptr)
  {
    ULONG alignptr = ((ULONG) ptr + align - 1) & (ULONG) -align;
    Forbid();
    FreeMem(ptr, size + align - 1);
    ptr = AllocAbs(size, (APTR) alignptr);
    Permit();
    if (ptr && (flags & MEMF_CLEAR))
      memset(ptr, 0, size);
  }
  return ptr;
}

Как видим, для того, чтобы работать как положено, новая система должна реализовать AllocAbs() правильно и в точном соответствии с изначальными требованиями к выравниванию.

Другой пример - процедура, резервирующая максимальный по размеру фрагмент памяти:

void *alloclargest(ULONG flags)
{
  ULONG largest;
  void *ptr;
  Forbid();
  largest = AvailMem(flags | MEMF_LARGEST);
  ptr = AllocMem(largest, flags);
  Permit();
  return ptr;
}

Чтобы это работало, и функция AllocMem() выдала наибольший фрагмент, такой фрагмент должен всегда быть доступен для резервирования.

Функция AllocMemList() не является типичной для систем управления памятью. Она используется для увеличения объёма [зарезервированной] памяти в процессе работы системы.

Всё это реализовано и корректно работает в новой системе управления памятью.

Новая система даже совместима с некоторыми прикольными штуками, такими как AllocVec(), которая предполагает размер зарезервированной области (далее я в непонятках) at ptr-4. Это часто используется для реализации функций, подобных функции realloc(), для памяти, зарезервированной через AllocVec(). Поддержка таких возможностей не является проблемой, поскульку это никак не влияет на всё остальное.

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

И, напоследок, хотел бы отметить ещё два момента:

Во-первых, FreeMem() более не должна использоваться для частичного освобождения зарезервированной памяти. Эта возможность является побочным эффектом от использования функцией FreeMem() функции Deallocate(), которая и гарантирует поддержку частичного освобождения памяти. В новой системе управления функция Deallocate() больше не используется. Впрочем, даже SDK для AmigaOS не поощряет использования возможности частичного освобождения памяти, так что, я думаю, особой проблемой это не является.

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

2 Уменьшение эффекта фрагментации

Фрагментация имеет место быть, и от этого никуда не деться. По прошествии какого-то времени память фрагментируется. И задача состоит в том, чтобы уменьшить этот эффект и снизить его влияние на характеристики системы.

Самым критичным моментом был выбор алгоритма. Алгоритм распределения памяти Two Level Segregated Fit обеспечивает уровень трудоёмкости О(1) вне зависимости от степени фрагментации памяти.

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

3 Уменьшение фрагментации памяти

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

Новый алгоритм должен вместо этого выдавать оптимальный [по размеру] фрагмент памяти, что даёт уверенность в том, что фрагментация, если она случилась, является неизбежной.

Алгоритм TLSF, используемый нами, подразумевает среднюю фрагментацию менее 15%.

4 Реализация

MorphOS 2.0 и более поздние версии имеют возможность переключать систему управления памятью. Выбор алгоритма осуществляется во время загрузки ОС. В настоящее время доступны опции для подключения First Fit (как в AmigaOS и MorphOS 1.х) и TLSF (включается по умолчанию). Пользователь может задать поведение системы управления памятью командами в OpenFirmware.

Он использует механизм распределения раздельных фрагментов для получения удовлетворительного результата. Механизм раздельных фрагментов использует массив списков свободной памяти, при этом каждый массив содержит свободные блоки, классифицируемые в зависимости от размера. Классы делятся по степеням двойки: 16, 32, 64 и так далее. Из соображений улучшения характеристик и снижения фрагментации каждый массив делится на два уровня. В реализации алгоритма для MorphOS каждый список разбит на 32 части. В сочетании с другими специальными подходами это позволяет распределять до 2 ГБ. Каждый массив списков имеет битовое поле (bitmap) для обозначения списков, имеющих свободные блоки, и тех списков, что пусты (то есть блоки памяти, указанные в списках, уже заняты). В свою очередь, свободные блоки содержат информацию о себе, также как в алгоритме First Fit. Также для лучшей связности блоков при освобождении памяти дополнительно был введён [обратный] указатель на предшествующий свободный блок.

При требовании на выделение блока памяти запрошенный размер разделяется между двумя индексами. Эти индексы используются для поиска свободного блока, трудоёмкость такой операции - O(1). Найденный блок удаляется из списка свободных и объявляется занятым. Если найденный блок превышает запрошенный размер, блок разделяется. Размер оставшегося блока вновь конвертируется в два индекса. Новый свободный блок вставляется по месту, указанному в индексах.

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

Существующая реализация имеет особенности, не встречающиеся в оригинальном алгоритме: сохраняется информация об оставшейся свободной памяти (для функции AvailMem), возможность резервирования наибольшего доступного фрагмента и возможность зарезервировать фрагмент с началом по указанному абсолютному адресу.

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

Таким образом, система управления памятью на основе алгоритма TLSF позволила достичь всех целей, поставленных разработчиками:

Новая система управления памятью в MorphOS

0 От автора

1 Совместимость

2 Уменьшение эффекта фрагментации

3 Уменьшение фрагментации памяти

4 Реализация

5 Ссылки

Назад