AOP_Tom1 (1021736), страница 126
Текст из файла (страница 126)
Менеджер памяти, основанный на списке блоков, использовался, напрвмер, в Тигьо Рвлсаб— Прим. персе. Если список АЧА19 не упорядочен, нетрудно понять, что попытка слияния блоков списка ив лоби приведет к просмотру всего списка АЧА11; алгоритм В в среднем уменьшает этот поиск дя,:примерно половины списка АЧА1г. (на шаге В2). В упр. 11 показано, каким образом можно модифицировать алгоритм В, чтобы в среднем потребовалось просмотреть около одной трети списка АЧА11,. Но ясно, что, когда список АЧА11 длинный, все эти методы работают существенно медленнее, чем хотелось бы, Нет ли еще какого-либо способа выделения и освобождения памяти, при котором не требовался бы столь пространный поиск в списке АЧА117 Рассмотрим метод, который позволяет устранить любой поиск прн освобождении памяти и может быть модифицирован (см.
упр. 6) для резкого сокращения времени поиска при выделении памяти. В этой технологии используется поле ТАй в начале и в конце блока, а также поле Б12К в первом слове каждого блока. Такие накладные расходы не столь значительны при использовании больших блоков памяти, хотя, возможно, цена окажется слишком большой при наличии множества блоков очень малого среднего размера. Другой метод, описанный в упр.
19, требует только одного бита в первом слове каждого блока. Ценой этой зкономии является несколько большее время работы и усложнение программы*. Как бы там ни было, положим, что нет возражений против добавления некоторого количества битов управляющей информации для сохранения высокой скорости работы по сравнению с алгоритмом В при длинном списке АЧА1Ь. В описываемом методе предполагается, что каждый блок имеет следующий вид.
Для корректности "граничных условий" заголовок списка устанавливается следую- щим образом. ЕОС(АЧА11.): — О О ЕОС(АЧАП )+1: — О О (9) Алгоритм для выделения первого подходящего блока очень похож на алгоритм А, я потому здесь не рассматривается (см. упр. 12). Принципиально новое свойство этого метода заключается в освобождении блока за, по сути, фиксированное время. Алгоритм С (Освобождение с дескрипторами границ) Предположим, что блоки памяти выглядят так, как в (7), а список АЧА11 имеет две связи, как описывалось выше.
Данный алгоритм помещает блок памяти с начальным адресом РО в список АЧА11.. Если пул доступной памяти располагается от адреса гпа до гпе включительно, в алгоритме для удобства предполагается, что ТАО(то — 1) = ТАО(те+1) = "+". С1. [Проверка нижней границы.] Если ТАО(РΠ— 1) = "+", перейти к шагу СЗ. С2, [Удаление нижней области.) Установить Р < — РΠ— Б12Е(РΠ— 1), а затем установить Р1 +- 11ИК(Р), Р2 е- 11ИК(Р+1), 01ИК(Р1+ 1) <- Р2, ПИК(Р2) < — Р1, ЯХЕЕ(Р) с — Б12Е(Р) + Я12Е(РО), РО +- Р. СЗ.
[Проверка верхней границы.] Установить Р ~ — РО+Б12Е(РО). Если ТАО(Р) ="+", перейти к шагу С5. С4. [Удаление верхней границы.] Установить Р1 ~ — Е1ИК(Р), Р2 1.1ИК(Р+1), Е1ИК(Р1+1) с — Р2, Е1ИК(Р2) ~ — Р1, Я12Е(РО) +- Я12Е(РО) + Б12Е(Р), Р с — Р+ Б12Е(Р). СБ. Добавление в список АЧА11.] Установить Б12Е(Р— 1) +- Б12Е(РО), 01ИК(РО) <в АЧА1Ь, Е1ИК(РО + 1) е- 100(АЧА11), 11ИК(АЧА1Ь + 1) +- РО, АЧА1Ь +- РО; ТАО(РО) +- ТАО(Р— 1) +- ' †'.
! Шаги алгоритма С определяются видом блоков памяти (7); немного более длинный, но одновременно более быстрый алгоритм можно найти в упр. 15. На шаге С5 АЧА11 означает аббревиатуру для Е1ИК(ьОС(АЧА1Е)), как показано в (9). С. "Система двойников". Изучим теперь другой подход к динамическому выделению памяти для использования на двоичных компьютерах. В этом методе применяется по одному дополнительному биту на каждый блок; кроме того, все блоки должны иметь длину 1, 2, 4, 8, 1б и т.
д. Если длина блока не равна 2ь слов для некоторого целого )с, выбирается следующая более высокая степень 2 я часть выделенной памяти при этом не используется. Суть этого метода заключается в организации отдельных списков доступных блоков каждого размера 2"', 0 < А < т. Весь пул распределяемого пространства памяти состоит из 2 слов, адреса которых, предположим, находятся в диапазоне от 0 до 2 — 1.
Изначально весь блок из 2 слов свободен. Позже, при требовании блока из 2ь слов и отсутствии свободного блока такого размера больший доступный блок разбивается (зрй() на две равные части, в конечном итоге появится блок необходимого размера 2"'. Когда один блик разделяется надва (каждый половинного размера по сравнению с исходным), этн блоки называются двойниками (Ьиддлееа). Позже, когда оба явой>шка вновь становятся свободны, они объединяются в один большой блок. Таким образом, процесс выделения и освобождения может осуплествляться бесконечно, если только в какой-то момент вся доступная память не окажется занятой. Ключевой факт, лежаший в основе практический ценности этого метода, спстпит в том, чтп если известен адрес блока (адрес первого слова в блоке) и его размер, то известен и адрес его двойника.
Например, двойником блока размерил> 16 с двоичным адресом 101110010110000 является блок с двоичным адреспм 101110010100000. Для того чтобы понять, почел>у зто так, сначала заметим, что во время работы алгоритма адрес блока размером 2» кратен 2". Другими словами, адрес в двоичной записи содержит справа как минимум Й нулей. Данное наблюдение легко выводится по индукции: если это верно для всех блоков размером 2"+', то это, несомненно, справедливо и при делении блока пополам. Значит, блок размером, скажем, 32 имеет адрес вида хх...х00000 (где иксы представляют собой 0 или 1); при разделении блока вновь образуемые блоки-двойники имеют адреса хх...
х00000 и хх... х10000. В общем, пусть двойник»(х) обозначает адрес двойника блока размером 2", адрес которого равен х. Тогда находим, что 1 х+ 2», если х пюд 2»"' = 0; (10) )~х — 2», если хшод 2"+> = 2». Эта функция легко вычисляется с помощью операции исключающее или (иногда называемой селективным дополнением нли сложением без переноса), обычно нмек>- щейся на двоичнол> компьютере (см. упр.
2В). Система двойников использует однобнтовое поле ТАС в каждом блоке: ТАС(Р) = О, если блок с адресом Р выделен; ТАС(Р) = 1, если блок с адресом Р свободен. Кроме поля ТАС, имеюшегогя в каждом блоке, в свободиих блоках есть два поля связи, ЬТМКР и Ь1МКВ, которые представляют обычные связи вперед и назад в двусвязном списке; также имеется поле КУАЬ, определяюшее >е для блока размером 2»'. В приведенном ниже алгоритме используются ячейки таблицы АЧА1Ь(0], АЧА1Ь(1], ..., АЧА1Ь(>п], которые служат соответственно в качестве заголовков списков свободной памяти размером 1, 2, 4, ..., 2 . Это списки с двойными связями, так что, как обычно, заголовок списка содержит два указателя (см.
раздел 2,2.5): АЧА1ЬР(й] = Ь1МКР(ЬОС(АЧАХЬ(й])) = связь с окончанием списка АЧА1Ь(А]; (12) АЧА1ЬВЫ = Ь1МКВ(ЬОС(АЧА1Ь(А] )) = связь с началом списка АЧА1Ь (А]. Изначально перед выделением памяти мы имеем АЧА1).Р(т] = АЧА1ЬВ(пл] = О, ЬТМКР(0) = ЬТМКВ(0) = ЬОС(АЧА1Ь(пл]), ТАС(0) = 1, КЧА1.(0) = т дословный перевод слова ЬоЫ» — дружище, приятель. Прим. перев. (13) (что указывает ва единственный свободный блок длиной 2, начинающийся по адресу О) и АЧА1ЬР[>с] = АЧАГ1 В[А] =' ЬОС(АЧА1Ь[А]) для 0 < Й < ш (14) [что указывает на пустые списки свободных блоков размером 2" для всех А < т).
Исходя из этого описания системы двойников, читатель может самостоятельно и не без определенного удовольствия разработать необходимые алгоритмы для выделения и освобождения областей памяти, прежде чем знакомиться с приведенными далее алгоритмами. Обратите внимание на сравнительную простоту, с которой каждый блок может быть разделен пополам в алгоритме для выделения памяти. Алгоритм 11 (Выделение памяти в системе двойников). Этот алгоритм предназначен для поиска и выделения блока памяти размером 2" (или сообщения о невозможности такого выделения) с помощью описанной выше системы двойников. 111, [Поиск блока.] Пусть 3 — наименьшее целое число в диапазоне А < > < т, для которого АЧА1ЬР [>'] ф ЬОС(АЧА1Ь [>]), т.
е. для которого список свободных блоков размером 2> не пуст. Если такого > не существует, алгоритм завершается неудачей, поскольку нет ни одного блока достаточного размера для выделения запрошенного количества памяти. Й.З. [Удаление из списка.] Установить ь~- АчА1ьР[>], Р < — ымкР(ы, АчА1ьк[>] + — Р, ЫМКВ(Р) +- ЬОС(АЧА1Ь[]]) и ТАО(1.) + — О. КЗ. ]Требуется разделенне7] Если 3 = А, алгоритм завершается (найден и выделен свободный блок, начинающийся с адреса Ь). 114. ]Разделение.] Уменьшить 3 на 1.
Затем установить Р < — Ь+ 2>, ТАО(Р) <- 1, кчАь(Р) +- >] ь1мкР(Р) +- пмкВ(Р) +- ьОс(АчА1ь[33), АчА1ье[>'] +- АЧА1ЬВ[1] +- Р. (Тем самым разделяется большой блок памяти н неиспользуемая половина вносится в список АЧА1Ь[>], который был пуст.) Вернуться к шагу НЗ. 1 Алгоритм Я [Освобоз>сденпе памяти в системе двойников).
Этот алгоритм предназначен для возврата блока размером 2", начинающегося с адреса Ь, в область свободной памяти с использованием описанной выше системы двойников. 91. ]СвоГ>олен ли двойник?] Установить Р < — двойникь(1.) (см. (10)). Если А = и> или ТАО(Р) = О, либо если ТАО(Р) = 1 и КЧАЬ(Р) ф А, перейти к шагу 53. Б2.[Объединение двойников.] Установить ььмкР[пмкв(Р)) + — пмкР(и, пмкв(пмкР(Р)) +- пмкв(Р). (Таким образом блок Р удаляется из списка АЧА1Ь[)с].) Затем установить А +- к + 1 и, если Р < Ь, установить Ь < — Р.
Вернуться к шагу 51. БЗ. ]Размен>ение в списке.] Установить ТАО(Ь) < — 1, Р +- АЧА11.Р [Ц, 1.1МКР(Ь) +- Р, 1.1МКВ(Р) ~- 1., КЧАЬ(1) 1 — Й, 11МКВ(Ь) + — 1 ОС(АЧА11. [/с3), АЧА1ЬР [Й] < — 1.. (Таким образом блок Ь помещается в список АЧА1Ь[Й].) ! А). Сравнение методов. Выполнение математического анаяиза зтнх алгоритмов динамического выделения памяти оказывается весьма трудной задачей, однако тенденция приводит к наличию меньшего числа доступных блоков, давая даже лучшую производительность по сравнению с производительностью, предсказываемой по правилу "50%" (см. С4СМ 20 (1977), 812-820).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
