работы этих методов.

Время выделения Время освобождения

Система граничных дескрипторов; 33 + 7А 18, 29, 31 или 34

Система двойников: 19 + 25R 27 + 265

Здесь А> 1 - необходимое для поиска достаточно большого блока количество итераций, R > О - количество разбиений блока на два (начальная разность j - к в алгоритме R) и S > О - количество слияний двойников при работе алгоритма S. Моделирующие эксперименты указывают, что при данных предположениях относительно распределения размеров (SI) и времени, выбираемом в диапазоне от 1 до 1000, можно получить в среднем А = 2.8, Л = 5 = 0.04. (Средние значения для распределения времени "почти последним выдачей - первым освобожден", которое описано выше, составляют А = 1.3, R = S - 0.9.) Это показывает, что оба метода весьма быстры (система двойников для MIX несколько быстрее). Напомним, что для системы двойников необходимо примерно на 44% больше памяти, если размеры блоков не ограничены степенями 2.

Соответствующее время для выполнения алгоритма сборки мусора и уплотнения из упр. 33 составляет около 104 единиц при поиске свободного узла, если предположить, что сборка мусора происходит в момент заполненности памяти примерно наполовину, а узлы имеют среднюю длину 5 слов с двумя связями на узел. "За" и "против" этого метода обсуждаются в разделе 2.3.5. Когда память не сильно загружена и выполняются соответствующие ограничения, сборка мусора и уплотнение весьма эффективны; например, на компьютере MIX метод сборки мусора быстрее двух других, если память не заполнена более чем на треть и узлы относительно малы.

Если удовлетворяются условия, лежащие в основе метода сборки мусора, наилучшей стратегией может оказаться разделение пула памяти на две половины и выполнение всех последующих выделений памяти в одной половине. Вместо освобождения становящихся неиспользуемыми блоков мы просто ожидаем, пока текущая половина памяти не заполнится. Затем можно скопировать все активные данные в другую половину, одновременно удаляя все "дыры" между блоками при помощи метода, подобного приведенному в упр. 33. Размер каждой половины пула может изменяться при переключении с одной половины на другую.

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

a) Для каждого размера используется свой список AVAIL. Единый свободный блок при необходимости разбивается на два меньших блока, но никаких попыток вновь объединить такие блоки не предпринимается. Карта памяти становится фраг-ментированной на все меньшие и меньшие части, пока не принимает совершенно ужасный вид. Простая схема наподобие этой практически эквивалентна раздельному распределению в несвязанных областях, по одной области для каждого размера блока.

b) Была предпринята попытка выполнения двухуровневого выделения. Память делилась иа 32 больших сектора. Для выделения больших блоков размером 1, 2

или 3 (очень редко -больших размеров) соседних секторов использовался метод выделения памяти "в лоб". Каждый такой большой блок разделялся для удовлетворения запросов на выделение памяти до тех пор, пока в текущем большом блоке не оставалось памяти (при этом начинал использоваться другой большой блок). Каждый большой блок возвращался в свободную память только после освобождения всех выделенных из него блоков памяти. Данный метод почти всегда быстро приводит к нехватке памяти.

Хотя этот частный метод двухуровневого выделения и был неработоспособен с использовавшимися автором данными при моделировании динамического распределения, возникают ситуации (на практике очень нечастые), когда многоуровневая стратегия может оказаться предпочтительной. Например, если большая программа работает в несколько стадий, возможно, что на разных стадиях используются узлы разных типов и отдельные типы узлов применяются только в отдельных подпрограммах. В некоторых программах может оказаться желательным использование нескольких различных стратегий распределения памяти для различных классов узлов. Идея выделения памяти по зонам, быть может, с помощью различных стратегий в каждой зоне и с возможностью освобождения всей зоны, рассматривается в работе Douglas Т. Ross, САСМ 10 (1967), 481-492,

Другие эмпирические результаты, полученные при изучении динамического распределения памяти, приводятся в следующих работах: В, Randell, САСМ 12 (1969), 365-369, 372; Р. W. Purdom, S. М. Stigler, and Т. О. Cheam, BIT 11 (1971), 187-195; В. Н, Margolin, R. Р. Parmelee, and М. SchatzofF, IBM Systems J. 10 (1971), 283-304; J, A. Campbell, Сотр. J. 14 (1971), 7-9; John E. Shore, CACM 18 (197S), 433-440; Norman R, Nielsen, CACM 20 (1977), 864-873.

*E. Метод распределенного йодходмщего. Если распределейие размеров блоков известно заранее и все блоки освобождаются равйовероятно, независимо ef момента их выделения, можно использовать технологию (которая в данных предположениях превосходит технологии общего назначения), предложенную Э. Г. Кофф-маном (мл.) (Е. О. Coffman, Jr.) и Ф, Т. Лейтоном (F. Т, Leighton) [J. Computet and System Sci. 38, (1989), 2-35]. Их "метод распределенного подходящего" (distrlbuted-fit method) работает путем разделения памяти на примерно N + vWlgiV слотов, где N - максимальное число блоков, которые будут обрабатываться в установившемся состоянии. Каждый слот имеет фиксированный размер, хотя различные слоты могут иметь различные размеры. Главное заключается в том, что любой слот имеет фиксированные границы, и он может либо быть пустым, либо содержать единственный выделенный блок.

Первые N слотов схемы Коффмана-Лейтона расположены в соответствии с заданным распределением размеров, а оставшиеся /N\gN слотов имеют максимальный размер, Например, если предположить, что размеры блоков равномерно распределены между 1 и 256 и если необходимо обработать N = 2 таких блоков, следует разделить память на Л/2бб = 2 глотов каждого размера 1, 2, 2§в, за которыми следует "область переполнения", содержащая vlgiV = 2 14 = 1792 блоков размером 256. Когда система работает при полной загрузке, ожидаетсй работа с N блоками среднего размера занимающими 2* --2 s 2105 344

ячеек памяти (это количество памяти, выделенное для первых N слотов). Кроме

того, имеется 1792 • 256 = 45752 ячеек памяти для обработки случайных отклонений; этп дополнительные накладные расходы составляют 0(N~ logN) от общего объема памяти, в отличие сп пропорциональных Л в случае системы двойников, и становятся незначимыми при Л -> оо. В нашем примере, однако, накладные расходы остаются на уровне 18% от общего количества памяти.

Слоты должны быть расположены в таком порядке, чтобы меньшие из них предшествовали ббльшим. При таком расположении можно выделять блоки с помощью либо технологии первого подходящего, либо технологии наилучшего подходящего (в данном случае оба метода эквивалентны, поскольку размеры слотов упорядочены). При наших предположениях действие описанной методики заключается в начале поиска в, по сути, случайном месте среди первых Л слотов при новом запросе на выделение памяти и его продолжеиии ДО тех nppi iiQKft не будет найден пустой слот.

Если начальный слот для каждого поиска действительно выбирается случайным образом между 1 и Л, частых вторжений в область переполнения не будет. В самом деле, если вставить ровно N элементов, начиная со случайных слотов, переполнение будет встречаться а среднем только 0{\/N) раз. Объяснение этого факта заключается в том, что можно сравнить данный алгоритм с хешированием с линейным исследованием (алгоритм 6.4L), которое имеет то же самое поведение, но поиск пустой ячейки возвращается от iV к 1 вместо перехода в область переполнения. Анализ алгоритма 6.4L в теореме 6.4К показывает, что при вставке Л элементов среднее смещение каждого элемента от его хеш-адреса составляет \{Q{N) - 1) ~ у/пТЩ. Из круговой симметрии следует, что это среднее значение -то же, что и среднее количество переходов поиска от слота к к слоту А; + 1 для каждого к. Переполнения в методе распределенного подходящего соответствуют поискам, переходящим от слота N к слоту I, с той лишь разницей, что наша ситуация даже лучше, поскольку некоторого переполнения можно избежать без возвратов к началу. Таким образом, в среднем встречается менее УFNJ8 переполнений. В этом анализе не приняты во внимание удаления, которые сохраняют предположения алгоритма 6.4L только в случае, когда мы перемещаем блоки назад при удалении другого блока, находящегося между их начальными и выделенными слотами (см. алгоритм 6.4R). Кроме того, однако, их перемещение назад только увеличивает вероятность переполнения. Наш анализ также некорректен для подсчета влияния одновременного наличия более Л блоков; это может случиться, если предположить, что время между выделениями блоков составляет 1/N от времени их жизни. Если имеется более Л блоков, необходим расширенный анализ алгоритма 6.4L, но Коффман и Лейтон доказали, что область переполнения почти никогда не потребует больше чем y/N\$N слотов; вероятность завершения работы составляет менее OiN~) для всех М.

В нашем примере начальный слот для поиска во время выделения не выбирается равномерно среди слотов 1, 2,..,, Л. Вместо этого он равномерно выбирается среди слотов 1, 65,129,..., Л-бЗ, поскольку имеется N/256 = 64 слотов каждого размера. Но такое отклонение от рассмотренной в предыдущем разделе случайной модели делает переполнение даже менее вероятным, чем предсказано. Впрочем, не стоит держать пари, если нарушаются предположения о распределении размера блоков и времени их занятости.