Причину такого поведения можно понять, если вспомнить правило "50%": если система достигает состояния равновесия, при котором размер среднего свободного блока / меньше размера среднего используемого блока г, то можно ожидать получения невыполнимого запроса, кроме ситуации, когда "на всякий пожарный случай" имеется достаточно большой свободный блок. Следовательно, в насыщенных системах без переполнения / > г, и мы имеем С - /М + rN > гМ + rN {р + l)rN. Общее количество использованной памяти, таким образо.м, составляет rN < С/{р + 1). Когда р <=» 1, использовать больше примерно ячеек памяти невозможно.

Эксперименты по моделированию систем динамического выделения памяти проводились с тремя распределениями размера блоков 5:

(S1) равновероятный выбор целого числа из диапазона От 100 до 2000; {S2) выбор размера (1, 2, 4, 8, 16, 32) с вероятностями (, \, , , , ) соответственно;

(S3) равновероятный выбор размера из множества (10, 12, 14, 16, 18, 20, 30, 40, 50, 60, 70, 80, 90, 100, 150, 200, 250, 500, 1000, 2000, 3000, 4000). Время Т обычно представляло собой случайное целое равномерно распределенное число в диапазоне от 1 до f для фиксированного ( = 10, 100 или 1000.

Кроме того, были проведены эксперименты, в которых Т на шаге РЗ представляло собой случайное число, равномерно распределенное в диапазоне от 1 до min ([t/J, 12500), где U - количество единиц времени, оставшегося до ближайшего освобождения занятого блока из имеющихся в настоящий момент в системе. Это распределение времени использовалось для моделирования ситуации "почти последним выделен - первым освобожден" (almost-last-in-first-out): если Т всегда выбирается < U, система выделения памяти выродится в простую стековую операцию, не требующую использования сложных алгоритмов (см. упр. 1). Указанное распределение вынуждает выбранное Т быть большим, чем U, около 20% раз, так что мы имеем почти стековую операцию. При использовании такого распределения алгоритмы, подобные алгоритмам А, В и С, ведут себя гораздо лучше, чем обычно; очень редко возникало (если возникало вообще) более двух блоков в списке AVAIL, в То время как выделялось около 14 блоков. С другой стороны, алгоритмы системы двойников, R и S, при использовании такого распределения оказывались медленнее, поскольку в стекообразных операциях приходится чаще, чем обычно, расщеплять и сливать блоки. Вывод теоретических свойств этих распределений слишком сложен (см. упр. 32).

На рис. 42 была приведена конфигурация памяти в мо.мент TIME = 5000 с использованием распределения размеров (S1) и с равномерно распределенным между 1 и 100 временем при выделении по методу первого подходящего (алгоритмы А и В). В этом эксперименте вероятность р, которая входит в правило "50%", равна 1, так что можно было бы ожидать, что количество свободных блоков составит около половины количества выделенных блоков. На самом деле на рис. 42 показан 21 свободный и 53 выделенных блока. Это не опровергает правило "50%"; например, в момент TIME = 4600 имелось 25 свободных и 49 выделенных блоков. Конфигурация, приведенная на рис. 42, просто показывает, что правило "50%" подвержено статистическим отклонениям. Число свободных блоков, в целом, находится в диа-

00000 20000 40000

eodoo

80000 100000 120000

1000 2000 3000 4000 SOOO 6000 7000 8000 9000 10000 I...... ........... I I I I I I

Рис. 43. Карта памяти, полученная с помощью метода наилучшего подходящего. (Сравните ее с картой, представленной на рис. 42, которая показывает результат работы метода первого подходящего, и с рис. 44, на котором в виде дерева представлена карта памяти в результате работы системы двойников с той же последовательностью запросов.)

пазоне от 20 до 30, в то время как количество выделенных блоков находится в диапазоне от 45 до 55.

На рис. 43 приведена конфигурация памяти, полученная при тех же данных, что и конфшурацил на рис. 42, но с использованием метода наилучшего подходящего. Константа с Из шага А4 была принята равной 16 для устранения малых блоков, и как результат - вероятность р упала до 0.7 и количество свободных областей уменьшилось.

При изменении распределения времени в диапазоне от 1 до 1000 (вместо диапазона от 1 до 100) ситуация была аналогична показанной на рис. 42 и 43, но все соответствующие величины были умножены приблизительно на 10. Например, в ситуации, аналогичной показанной на рис. 42, было 515 выделенных и 240 свободных блоков; в ситуации, подобной приведенной на рис. 43, имелось 176 свободных блоков,

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

Система двойников испытывалась с теми данными, которые привели к результатам, изображенным.иа рис. 42 и 43. Итоговые данные представлены на рис. 44. Здесь все размеры в диапазоне от 257 до 512 рассматривались как 512, в диапазоне от 513 до 1024 - как 1024 и т. д. В среднем это означает увеличение запроса на одну треть (см. упр. 21); система двойников, конечно, лучше работает при распределении размеров (SS), а не прн распределении (Si). Обратите внимание на то, что на рис. 44 имеются доступные блоки размеров 2, 2", 2\ 2*, 2 и 2*.

Моделирование системы двойников показало, что ее производительность выше, чем ожидалось. Ясно, что иногда эта система позволяет иметь два смежных свободных блока одинакового размера без их слияния (если они не являются двойниками). Но такая ситуация пе представлена на рис. 44 и в действительности крайне редка на практике. Переполнение памяти происходило при выделении 95% памяти, что отражает удивительно хороший баланс выделения памяти, Кроме того, очень редко требуется разделение блоков в алгоритме R (и их слияние в алгоритме S); дерево остается очень похожим на изображенное на рис. 44 со свободными блоками на чаще всего используемых уровнях. Некоторые математические результаты, позво-

Рис. 44. Карта памяти, полученная при помощи системы двойников. (Структура дерева указывает на деление некоторых больших блоков на двойников половинного размера. Квадратами помечены свободные блоки.)

ляющие понять такое поведение на нижних уровнях дерева, были получены в работе Р. W. Purdom, Jr., and S. М. Stigler, JACM 17 (1970), 683-697.

Еще одним сюрпризом стало превосходное поведение алгоритма А после модификации, описанной в упр. 6. Потребовалось в среднем только 2.8 проверки размера свободного блока при использовании распределения размеров {S1) и времени, равномерно распределенного между 1 и 1000, а более чем в половине случаев требовалось минимальное значение - одна итерация. Все это выполнялось несмотря на наличие около 250 доступных блоков. Тот же эксперимент с немодифицированным алгоритмом А показал, что в среднем необходимо около 125 итераций (т. е. каждый раз проверяется половина списка AVAIL); 200 и более проверок понадобилось примерно в каждом пятом случае.

Такое поведение немодифицированного алгоритма А в действительности может быть предсказано как следствие правила "50%". При равновесии в части памяти, содержащей последнюю половину выделенных блоков, находится также последняя половина свободных блоков; эта часть требует половину времени при освобождении блока и соответственно должна использоваться в половине случаев выделения памяти для поддержки состояния равновесия. Это же обоснование применимо и при замене половины любой другой частью (данные замечания были сделаны Д. М. Робсоном (J. М. Robson)).

Упражнения к этому разделу включают MIX-программы для двух основных методов, которые рекомендуются к использованию на основе приведенных выше замечаний: (i) модифицированный согласно упр. 12 и 16 алгоритм А (система граничных дескрипторов) и (ii) система двойников. Вот приближенные результаты