AOP_Tom1 (1021736), страница 127
Текст из файла (страница 127)
Более детально правило "50%" рассматривается в работах П. 1. М. Пач1еэ, В1Т 20 (1980), 279-288; С. М. Вееэев, Сошр, Х 20 (1983), 25 — 35; О. СЬ. Рйий, Сошр. Х 27 (1984), 328-333. Если не учитывать это интересное правило, наши знания о производительности алгоритмов динамического распределения памяти почти полностью базируются на экспериментах по методу Монте-Карло. При выборе алгоритма выделения памяти для конкретных машины и класса приложения (или конкретного приложения) поучительно провести собственные моделирующие динамическое распределение памяти эксперименты.
Автор провел ряд таких экспериментов непосредственно перед написанием этого раздела (и правило "50%" было замечено во время этих экспериментов до того, как было найдено его доказательство). Рассмотрим здесь вкратце методы и результаты проведенных экспериментов. Основная моделирующая программа работает следующим образом. В начальный момент работы программы, когда значение Т1ИЕ равно нулю, доступна вся память.
Р1. Увеличить Т1ИЕ на 1. Р2. Освободить все блоки в системе, которые должны быть освобождены при текущем значении Т1ИЕ, РЗ. Вычислить две величины, 5 (случайный размер) и Т (случайное время жизни), основанные на некотором распределении вероятностей, с помощью методов из главы 3. Р4. Выделить новый блок длиной 8, который необходимо освободить в момент (Т1ИЕ+ Т). Вернуться к шагу Р1. 1 Каждый раз по достижении переменной Т1ИЕ значения, кратного 200, выводились детальные статистические данные о производительности алгоритмов выделения и освобождения.
Для каждой пары алгоритмов использовалась одна и та же последовательность значений 8 и Т. После того как величина Т1ИЕ превышала 2000, система обычно приходила в более или менее стабильное состояние с неизменными показателями. Однако иногда на шаге РЗ алгоритм прекращал свою работу из-за невозможности выделить необходимый объем памяти. Пусть С вЂ” общее количество доступных ячеек памяти и пусть 5 и Т средние величины Я и Т на шаге РЗ. Легко видеть, что ожидаемое количество занятых слов памяти в каждый момент составляет ЯТ при достаточно болыпом значении Т1ИЕ.
Когда в экспериментах БТ было больше, чем ~1 С, обычно происходило переполнение памяти (часто прежде, чем в действительности происходил запрос на выделение С слов памяти). Память можно было заполнить на 90% при малом по сравнению с С размере блока, но когда размеры блока могли превысить -'С (вместе с блоками меньших размеров), наблюдалась тенденция программы к "заполнению" памяти при реальном использовании менее — С ячеек памяти. Эмпирические результаты 1 2 свидетельствуют о том, что для эффектлвной работы систем динамического распределения памяти не должны использоваться блоки размером свыше — С.
Причину такого поведения можно понять, если вспомнить правило "50%": если система достигает состоянии равновесия, при котором размер среднего свободного блока 5 меньше размера среднего используемого блока г, то можно ожидать получения невыполнимого запроса, кроме ситуации, когда "на всякий пожарный случай" имеется достаточно большой свободный блок.
Следовательно, в насыщенных системах без переполнения 5 > г, и мы имеем С = 5М + гФ > гМ + г5У а 1эр+ 1) г5У. Общее количество использованной памяти, таким образом, составляет г5У ( С/1г2р+1). Когда р в 1, использовать больше примерно Аз ячеек памяти невозможно. Эксперименты по моделированию систем динамического выделения памяти проводились с тремя распределениями размера блоков 5: (81) равновероятный выбор целого числа из диапазона от 100 до 2000; (Яй) выбор размера (1, 2, 4, 8, 16, 32) с вероятностями (~э1, ~1, э,,в, —,э, эт) соответственно; (Яу) равновероятный выбор размера из множества (10, 12, 14, 16, 18, 20, 30, 40, 50, 60, 70, 80, 90, 100, 150, 200, 250, 500, 1000, 2000, 3000, 4000).
Время Т обычно представлнло собой случайное целое равномерно распределенное число в диапазоне от 1 до 1 для фиксированного 1 = 10, 100 или 1000. Кроме того, были проведены эксперименты, в которых Т на шаге РЗ представляло собой случайное число, равномерно распределенное в диапазоне от 1 до щ1п(Д15), 12500), где 15 — количество единиц времени, оставшегося до ближайшего освобождения занятого блока из имеющихся в настоящий момент в системе. Это распределение времени использовалось для моделирования ситуации "почти последним выделен — первым освобожден" (а!пюэы1аэы!и-йгэмоп1): если Т всегда выбирается ( 15, система выделения памяти выродится в простую стековую операцию, не требующую использования сложных алгоритмов (см. упр. 1). Указанное распределение вынуждает выбранное Т быть ббльшим, чем Г, около 20% рвз, так что мы имеем почию стековую операцию.
При использовании такого распределения алгоритмы, подобные алгоритмам А, В и С, ведут себя гораздо лучше, чем обычно; очень редко возникало (если возникало вообще) более двух блоков в списке АтА11., в то время как выделялось около 14 блоков. С другой стороны, алгоритмы системы двойников, Н и Б, при использовании такого распределения оказывались медленнее, поскольку в стекообразных операциях приходится чаще, чем обычно, расщеплять и сливать блоки. Вывод теоретических свойств этих распределений слишком сложен (см. упр, 32). На рис.
42 была приведена конфигурация памяти в момент Т1ИЕ = 5000 с использованием распределения размеров 1Я! ) и с равномерно распределенным между 1 и 100 временем при выделении по методу первого подходящего (алгоритмы А и В). В этом эксперименте вероятность р, которая входит в правило "50%", ранна 1, так что можно было бы ожидать, что количество свободных блоков составит около половины количества выделенных блоков. На самом деле на рис.
42 показан 21 свободный н 53 выделенных блока. Это не опровергает правило "50%"; например, в момент Т1МЕ = 4600 имелось 25 свободных и 49 выделенных блоков. Конфигурация, приведенная на рис. 42, просто показывает, что правило "50%" подвержено статистическим отклонениям. Число свободных блоков. в целом, находится в диа- О 1000 2000 ЭООО 4000 0000 0000 7000 БООО 9000 10000 00000 гОООО 40000 00000 00000 100000 100000 Рнс 43, Карта памяти, полученная с помощью метода наилучшего подходящего, (Сравните ее с картой, представленной на рис, 42, которая показывает результат работы метода первого подходящего, и с рис.
44, на котором в виде дерева представлена карта памяти в результате работы системы двойников с той же последовательностью запросов.) назоне от 20 до 30, в то время как количество выделенных блоков находится в диапазоне от 46 до 50. На рис. 43 приведена конфигурация памяти, псаученкая про шех Оюе данных, что о кон16иерра11ил на рис, 43, но с использованием метода наилучшего подходящего. Константа с иэ шага А4' бь1ла принята равной 16 для устранения малых блоков, и как результат — вероятность р упала до 0.7 и количество свободных областей уменьшилось, При изменении распределения времени в диапазояе от 1 до 1000 (вместо диапазона от 1 да 100) ситуация была аналогична показанной иа рис.
42 и 43, но все соответствующие величины были умножены приблизительно на 10. Например, в ситуации, аналогичной показанной на рис. 42, было 615 вьщеленных и 240 свободных блоков; в ситуации, подобной приведенной на рис. 43, имелось 176 свободных блоков, Во всех экспериментах по сравнению методов первого подходящего и наилучшего подходящего последний всегда превосходит первый. После исчерпания размере памяти метод первого подходящего в большинстве случаев остается работоспособным дольше метода наилучшего подходящего.
Система двойников испытывалась с теми данными, которые привели к результатам, изображенным,на рис, 42 и 43. Итоговьш данные представлены на рис. 44, Здесь все размеры а диапазоне от 207 до 612 рассматривались ках 612, в диапазоне от 613 до 1024 — как 1024 и т. д. В среднем зто означает увеличение запроса на одну треть (см, упр. 21); система двойников, конечно, лучше работает при распределении размеров (ой), а не при распределении (01). Обратите внимание на то, что на рис. 44 нме1отся доступные блоки размеров 2', 2'О, 2", 2г1, 2'з и 2".
Моделирование системы двойников показало, что ее производительность выше, чем ожидалось, Ясно, гго иногда эта система позволяет иметь два смежных свободных блока одинакового размера без их слияния (если они не квляются двойниками). Но такая гитуация не представлена на рис. 44 и в действительности крайне редка на практиие. Переполнение памяти происходило прн выделении 96% памяти, что отражает удивительно хороший баланс выделения памяти, Кроме того, очень редко требуетгя разделение блоков в алгоритме н (и их слияние в алгоритме 6)1 дерево остается о щкь похожим па изображенное на рис.
44 со свободными блоками на чаще всего используемых уровнях. Некоторые математические результаты, позво- 217 21Я 21З 217 211 29 28 Рис. 44. Карта памяти, полученная при помощи системы двойников, (Структура дерева указывает на деление некоторых больших блоков на двойников половинного размера, Квадратами помечены свободные блоки.) ляющие понять такое поведение на нижних уровнях дерева, были получены в работе Р. Ж. Рцгбош, Лг., ап71 8.
М. 81181ег, ХАСЛХ 17 (1970), 683- 697. Еще одним сюрпризом стало превосходное поведение алгоритма А после модификации, описанной в упр. 6. Потребовалось в среднем только 2.8 проверки размера свободного блока при использовании распределения размеров (о1) и времени, равномерно распределенного между 1 и 1000, а более чем в половине случаев требовалось минимальное значение — одна итерации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
