AOP_Tom1 (1021736), страница 128
Текст из файла (страница 128)
Все это выполнялось несмотря на наличие около 250 доступных блоков. Тот же эксперимент с немодифицнрованным алгоритмом А показал, что в среднем необходимо около 125 итераций (т. е. каждый раз проверяется половина списка АЧА11.); 200 и более проверок понадобилось примерно в каждом пятом случае. Такое поведение немодифицированного алгоритма А в действительности может быть предсказано как следствие правила "50%". При равновесии в части памяти, содержщцей последнюю половину выделенных блоков, находится также последняя половина свободных блоков; эта часть требует половину времени при освобождении блока и соответственно должна использоваться в половине случаев выделения памяти для поддержки состояния равновесия. Это же обоснование применимо и при замене половины любой другой частью (данные замечания были сделаны Д. М.
Робсоном (Л. М. ВоЬэоп)). Упражнения к этому разделу включают И1Х-программы для двух основных методов, которые рекомендуются к использованию на основе приведенных выше замечаний: (!) модифицированный согласно упр. 12 и 16 алгоритм А (система граничных дескрипторов) и (61) система двойников.
Вот приближенные результаты работы этих методов. Время выделения Время освобождения Система граничных дескрипторов: Система двойников: 18, 29, 31 или 34 27+ 265 33+ 7А 19+ 25Л Упомянутые выше технологии были применены и к другим алгоритмам выделения памяти. Однако эти методы оказались настолько плохи по сравнению с алгоритмами, описанными в настоящем разделе, что здесь будет дано только их краткое описание. а) Для каждого размера используется свой список ауа11..
Единый свободный блок при необходимости разбивается на два меньших блока, но никаких попыток вновь объединить такие блоки не предпринимается. Карта памяти становится фрагментированной на все меньшие и меньшие части, пока не принимает совершенно ужасный вид. Простая схема наподобие этой практически эквивалентна раздельному распределению в несвязанных областях, по одной области для каждого размера блока. Ь) Была предпринята попытка выполнения двухуровневого выделения. Память делилась на 32 больших сектора. Для выделения больших блоков размером 1, 2 Здесь А > 1 — необходимое для поиска достаточно большого блока количество итераций, В > 0 — количество разбиений блока на два (начальная разность 1 — и в алгоритме В) и 5 > 0 — количество слияний двойников при работе алгоритма Я.
Моделирующие эксперименты указывают, что при данных предположениях относительно распределения размеров (31) и времени, выбираемом в диапазоне от 1 до 1000, можно получить в среднем А = 2.8, В = 5 = 0.04. (Средние значения для распределения времени "почти последним выделен — первым освобожден", которое описано выше„составляют А = 1.3, Л = 5 = 0.9.) Это показывает, что оба метода весьма быстры (система двойников для М1Х несколько быстрее). Напомним, что для системы двойников необходимо примерно на 44% больше памяти, если размеры блоков не ограничены степенями 2. Соответствующее время для выполнения алгоритма сборки мусора и уплотнения из упр. 33 составляет около 104 единиц при поиске свободного узла, если предположить, что сборка мусора происходит в момент заполненности памяти примерно наполовину, а узлы имеют среднюю длину.
5 слов с двумя связями на узел. "За" и "против" этого метода обсуждаются в разделе 2.3.5. Когда память не сильно загружена и выполняются соответствующие ограничения, сборка мусора и уплотнение весьма эффективны; например, на компьютере М1Х метод сборки мусора быстрее двух других, если память не заполнена более чем на треть н узлы относительно малы. Егчи удовлетворяются условия, лежащие в основе метода сборки мусора, наилучшей стратегией может оказаться разделение пула памяти на две половины и выполнение всех последующих выделений памяти в одной половине. Вместо освобождения становящихся неиспользуемыми блоков мы просто ожидаем, пока текущая половина памяти не заполнится. Затем можно скопировать все активные данные в другую половину, одновременно удаляя все "дыры" между блоками при помощи метода, подобного приведенному в упр.
33. Размер каждой половины пула может изменяться при переключении с одной половины на другую. или 3 (очень редка — ббльших размеров) соседних секторов использовался метод выделения памяти "в лоб". Каждый такой большой блок разделялся для удовлетворения запросов на вььаеление памяти до тех пор, пока в текущем большом блоке не оставалось памяти (при этом начинал использоваться другой большой блок), Каждый большой блок возвращался в свободную память только после освобождения всех выделенных из него блоков памяти. Данный метод почти всегда быстро приводит к нехватке памяти. Хотя этот частный метод двухуровневого выделения и был нерабатоспособен с использовавшимися автором данными прн моделировании динамического распределения, возникают ситуации (на практике очень нечастые), когда многоуровневая стратегия мажет оказаться предпочтительной.
Например, если большая программа работает в несколько стадий, возможно, что на разных стадиях используются узлы разных типов и отдельные типы узлов применяются только в отдельных подпрограммах. В некоторых программах может оказаться желательным использование нескольких различных стратегий распределения памяти для различных классов узлов. Идея выделения памяти по зонам, быть может, с помощью различных стратегий в каждой зоне и с возможностью освобождения всей зоны, рассматривается в работе Воцй!ае Т. Ноев, САСМ 10 (1967), 461-492, Другие эмпирические результаты, полученные при изучении динамического распределения памяти, приводятся в следующих рабатах: В.
Напбе)1, САСМ 12 (1969), Вбо-369, 372; Р. %. Рцгбош, Б. М. Бс!61ег, апс1 Т. О. СЬеаш, ШТ 11 (19Т1), 1В7-195; В. Н, Магйо!!и, В.. Р. Рагше!ее, апд М. БсЬагво!7, ХВМ Був1евв Х 10 (1971), 263-304! Л. А, СашрЬе!1, Совр. Х 14 (1971), Т-9, '3оЬп Е, БЬоге, САСМ 16 (1975), 433 — 440,' 5(огшап Н. Х!е1веп, САСМ 20 (1977), В64-В73, "Е. Метод распрадвлеииога подходящего. Если распределение размеров блоков известно заранее н все блоки освобождаются равновероятно, независимо ат момента их выделения, можно использовать технологию (которая в данных предпо. лежаниях превосходит технологии общего назначения), предложенную Э, Г.
Коффманом (мл.) (Е. О. Са!Тшап, 3г.) и Ф, Т. Лейтоном (Р. Т, Ье!Вйоп) 1,7. Саври1ег аль Буе1еи Бс!. 36, (1969), 2-35]. Их "метод распределенного подходящего" (б!в!г(Ьц!еф бс ве1Ьоб) работает путем разделения памяти на примерно Ф + ~/У!БМ слатов, где )7 — максимальное число блоков, которые будут обрабатываться в установившемся состоянии.
Каждый слат имеет фиксированный размер, хотя различные слаты могут иметь различные размеры, Главное заключается в том, что любой глот имеет фиксированные границы, н он может либо быть пустым, либо содержать единственный выделенный блок. Первые )7 слатов схемы Коффмана-Лейтона распаложекы в соответствии с заданным распределением размеров, а оставшиеся ~/У!ВУ слатов имеют максимальный размер, Например, если предположить, что размеры блоков равномерно распределены между 1 и 256 и если необходимо обработать )Ч = 2ы таких блоков, следует разделить память нв )7/256 = 2' слатов каждого размера 1, 2, ..., 266, за которыми следует "область переполнения", содержащая ч'У 16 Ф = 2" 14 = 1792 блоков размером 256.
Когда система работает при полной загрузке, ожидается работа с Ф блоками среднего размера ф, занимающими ЯТЖ 2а'+2" 2105344 ячеек памяти (вто каличеш'ва памяти, выделенное для первых !у слатов). Кроме того, имеется 1792 256 ж 455752 ячеек памяти для обработки случайных отклонений; этн дополнительные накладные расходы составляют 0(Х '~' )ой Ф) от обшего объема памяти, в отличие ов пропорциональных Х в случае системы двойников, и становятся незначимыми прк Х -+ оо. В нашем примере, однако, накладные расходы остаются на уровне 18% от общего количества памяти.
Слоты должны быть расположены в таком порядке, чтобы меньшие иэ них предшествовали ббльшим. При таком расположении можно выделять блоки с помощью либо технологии первого подходящего, либо технологии наилучшего подходящего (в данном случае оба метода эквивалентны, поскольку размеры глотов упорядочены). Прн наших предположениях действие описанной методики заключается в начале поиска в, по сути, случайном месте среди первых Ю слогов прн новом запросе на выделение памяти и его прадалженнн да твх пор, пока не будет найден пустой слог.
Если начальный слог для каждого поиска действительно выбирается случайным образом между 1 и Х, частых вторжений в область переполнения не будет, В самом деле, если вставить ровно Х влементов, начиная со случайных слотов, переполнение будет встречаться в среднем только 0(~/У) раэ, Объяснение этого факта заклю. чается в том, что можно сравнить данный алгоритм с хешированием с линейным исследованием (алгоритм 6.41.), которое имеет то же самоа поведение, но поиск пустой нчейки возвращается от Ф к 1 вместо перехода в область переполнения. Анализ алгоритма 6.41, в теореме 6,4К показывает, что при вставке Х элементов среднее смещение каждого элемента от его хеш-вдреса составляет 5(ч(Х) — 1) э/~~Ф78.
Из круговой симметрии следует, что вто среднее значение — то же, что и среднее количество переходов поиска от слота 5 к слоту й+ 1 для каждого 5, Переполнения в методе распределенного подходящего соответствуют поискам, переходящим от слота Ж к слогу 1, с той лишь разницей, что наша ситуация даже лучше, поскольку некоторого переполнения можно избежать без возвратов к началу, Таким образом, в среднем встречается менее ~/яЮ/8 переполнений. В этом анализе не приняты во внимание удаления, которые сохраняют предположения алгоритма 6.41 только в случае, когда мы перемещаем блоки назад при удалении другого блока, находящегося между их начальными и выделенными слотамн (см. алгоритм 6.4В). Кроме того, однако, их перемещение назад только увеличивает вероятность переполнения, Наш анализ также некорректен для подсчета влияния одновременного наличия более Ю блоков; это может случиться, если предположить, что время между выделениями блоков составляет 1/Х от времени их жизни, Если имеется более Х блоков, необходим расширенный анализ алгоритма 6,41„но Коффман и Лейтон доказали, что область переполнения почти никогда не потребует больше чем ~/У)8 Ю слотов; вероятность завершения работы составляет менее 0(Х м) для всех М.
В нашем примере начальный слог для поиска во время выделения не выбирается равномерно среди слатов 1, 2,, Ю. Вместо этого он равномерно выбирается среди слогов 1, 65, 129,, Ю -63, поскольку имеется У/256 = 64 слогов каждого размера, Но такое отклонение от рассмотренной в предыдущем разделе случайной модели делает переполнение даже менее вероятным, чем предсказано. Впрочем, не стоит держать пари, если нарушаются предположения о распределении размера блоков н времени их занятости, Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
