AOP_Tom1 (1021736), страница 125
Текст из файла (страница 125)
Если К = О, установить 11ИК(Ц) ~- 11ИК(Р) (тем самым удаляя пустую область из списка); в противном случае установить Я12Е(Р) +- К. Алгоритм успешно завершается, выделяя область памяти длиной И, которая начинается с адреса Р + К. 1 Данный алгоритм, определенно, несколько прямолинеен. Однако всего лишь небольшое изменение стратегии может существенно повысить скорость его работы. Это весьма важное улучшение алгоритма, и читатель получит удовольствие, выполнив его поиск самостоятельно (см. упр. 6). Алгоритм А может использоваться как для больших, так и для малых значений М. Временно предположим, однако, что нас интересуют, в первую очередь, большие значения М. Рассмотрим, что случится, если в алгоритме Я1ЕЕ(Р) равно М+ 1: перейдем к шагу А4 и уменьшим Я1ЕЕ(Р) до 1.
Другими словами, будет создан блок доступной памяти размером 1. Он настолько мал, что практически бесполезен и только засоряет систему. Было бы лучше выделить весь блок размером М+ 1 слов вместо зкономии одного слова; зачастую стбит заплатить несколькими словами памяти за избавление от несущественных деталей. Подобные примечания относятся и к блокам памяти размером М+ К слов при очень малом К. Если допустить выделение блоков немного большего размера, чем М слов, придется помнить размер выделенного блока, чтобы при его освобождении корректно вернуть в пул свободной памяти все М+ К слов.
Это увеличивает накладные расходы, ведь придется использовать пространство в каждом блоке для того, чтобы сделать систему более эффективной в тех случаях, когда имеется почти подходящий блок. Так что подобная модифицирЪванная стратегия не кажется очень привлекательной. Однако зачастую использование в начале каждого блока переменного размера специального управляющего слова представляется желательным по множеству других причин, так что предположение о том, что в первом слове каждого блока, как выделенного, так и свободного, присутствует поле Я12Е, вполне разумно. В соответствии с этими соглашениями можно изменить шаг А4 приведенного выше алгоритма следующим образом. А4'.
[Выделение > М.) Установить К е- Я12Е(Р) — М. Если К ( с (где с — малая положительная константа, зависящая от того, каким количеством памяти мы готовы пожертвовать для ускорения работы), установить 11МК(0) +- Е1МК(Р) и 1 +- Р. В противном случае установить Я12Е(Р) < — К, 1 с — Р+ К, Я1ЕЕ(1) е- М. Алгоритм успешно завершается, выделив область длиной М или больше, которая начинается с адреса 1.. Обычно значение константы с выбирается равным 8 или 10, хотя практически нет никаких теоретических или эмпирических оснований для сравнения этих значений с другими. При использовании метода наилучшего подходящего проверка К < с более важна, чем в случае первого подходящего, поскольку компактное размещение (меньшие значения К) встречается при таком методе более часто, а число свободных блоков в этом алгоритме должно быть как можно меньше.
В. Освобождение. Теперь рассмотрим обратную задачу. Каким образом вернуть блоки в список свободного пространства, когда необходимость в них отпадает? Пожалуй. заманчиво было бы избежать решения данной задачи, используя сборку мусора* (см, раздел 2.6.5). Следуя этой политике, мы просто ничего не делаем до тех пор, пока пространство не окажется заполненным, а затем ищем все используемые в текущий момент области памяти и строим новый список АЧА11.
Именно этот метод работы с освобождаемой памятью используется, например, е языке 2ата,— Мрпяс персе. Однако идея сборки мусорь не рекомендуется для всех приложений. Нв первое место выходит вопрос строгой дисциплины использования указателей, если нужно гарантировать простое нахождение всех используемых в настоящий момент областей памяти, в именно этой дисциплины зачастую и не хватает рассматриваемым здесЬ приложениям, Во-вторн>х, как мы уже видели, метод сборки мусора имеет тенденцию к замедлению работы при почти заполненной памяти.
Есть и еще одна, более важная (хотя и не встречввшняся до сих пор прн оббужденнн зтого метода) причина, по которой сборка мусора нвс не устраивает. Пред. положим, что имеются две соседние свободные области памяти, но из-зв использо' ввния технологии сборки мусора одна из них (звштриховбнная) пока не попела в список АЧА1~. Нв втой диаграмме черные области памяти слева н справа энрезервированы и недоступны, По запросу можно зарезервировать часть области памяти, о которой иэввсгдмо, что онн свободна. Если в этот момент проийбйдет сборка мусори, получатся двв рбэдвльнь>е свободные области пямяти> Границы между свободной и выделенной памятью имеют тенденцию к свмовосз производству, и со временем снтувцик ствновится все хуже и хуже.
Но если бы нспользоввлвсь политик» немедленного возврвта освобожденнык блпков памяти в ш>неон АЧА11 и сдилкил смно>снмх свободммя бдохон, то (2) тут же преврктилвсь бы в (б) и при выделении памяти получилось бы тиков распределение блоков пямяти которое гораздо лучше, чем (4). Квк видите, рассмотренное явление вызывает большее дробление памяти при использовании методе сборки мусора, чем должно быть Для устранения этой проблемы можно использовать сборку мусора вместе с процессом рядок>иа>зид под>дозы, т. е, перемещения всех выделенных блоков в соседние позиции, чтобы после сборки мусора все свободные блоки Г>ыли объединеиьь Алгоритм вьщеленин памяти в втой ситуации становится в прот>тваположность алгоритму А трививльным, поскольку в любой момент есть только один своГ>одный блок, Хотя такой подход требует времени ня перемещение всех зндействонаннь>х блоков и изменение в них значений связей, метод может применяться с достнточной эффективностью при условии дисциплины непользования уквзнтелей и наличии знпвсного паля связи н каждом блоке, используемом алгоритмом сборки мусора' (., у з.
зз). ь Здесь тдвдувт отмотать, что такой метод применим двдвко на во вовк вэыкан протраммнроввнкк. Нрн пврвмвтдвннн блока пвмятн дон>к>зь> быть корректно обповдтны >>те указатели на Поскольку многие приложения не соответствуют этим требованиям, выдвигаемым методом сборки мусора, изучим методы возврата блоков памяти в список свободного пространства. Единственная сложность в этих методах заключается в объединении соседних свободных блоков памяти. Так, когда освобождается блок, находящийся между двумя свободными блоками, все трн области памяти должны быть слиты в одну, Таким образом достиеается хорошее раоноеесие памяти даже при длительном непрерывном процессе выделения и освобождения областей памяупи, (Для доказательства этого факта обратитесь к пранилу вбОув", приведенному ниже.) В данном случае задача заключается в определении, йилйбтся ли соседняя (с той или другой стороны) область памяти свободной, и если она свободна, то необходимо корректно обновить список АЧА1)..
Последняя операции несколько сложнее, чем кажется из ее названия. Первое решение этой проблемы состоит в содержании списка АЧА11 в порядке возрастания адресов памяти. Алгоритм В (Освобождение е рассоргпироеанном списке). В предположениях алгоритма А с дополнительным предположением об упорядоченности списка АЧА11. по адресам памяти (т. е. если Р указывает на свободный блок и 11ИК(Р) Р Л, то 11Ик(Р) > Р) этот алгоритм добавлнет блок из и последовательных ячеек, начинающийся с адрес:а РО, в список АЧАП.. Естественно, предполагается, что эти И ячеек уже свободны. В1.
(инициализация.) Установить ц з- 1Ос(АчА1(.). (Ем. примечание к шагу А1.) В2, (Продвижение Р.) Установить Р < — ЫМК(ц). Если Р = Л или если Р > РО, перейти к шагу ВЗ; н противном случае установить Ц в- Р и повторить шаг В2, ЬЗ. (Проверка верхней границы.) Если РО + М = Р и Р ~ Л, установить М <— И+ 31ЯЕ(Р) и установить ).1ИК(РО) +- (.1ИК(Р). В противном случае установить 31МХ(РО) <- Р. В4.
(Проверка нижней границы.) Если Ц + 31ее(Ц) = РО (предполагается, что 312Е(ЕОС(АЧА11.)) = О, так что условие всегда не выполняетсн при Ц = ЕОС(АЧА13)), установить 312Е(Ц) е- 312Е(Ц) + М и 11МК(Ц) +- 1.|МК(РО). В противном случае установить 11ИК(Ц) +- РО, 3123(РО) +- М, $ На шагах ВЗ н В4 выполняется требуемое слияние; учитывается тот факт, что указатели Ц с РО с Р являются начальными адресами трех последовательных свободных блоков. итог блок (и внутрь него). Ивпрнмер, в случае дюв такой метод лгожет прилгеняться, поскольку в языке отгутствует. понятие указателя и реальна» вдрегвция блоков пвмяти переменными может быть отслеженв внутренними средстввми языка.
В тп зке время в языках нвподобие С и Раиса), в козорых используются указатели, отгчедить создвние указателя нв ту нли иную область памяти невозможно, в знкч!о, применение методе ограни !ено его нспользоввн~ем только в менеджеркх памяти прогрвмм, созданных специальным пбразом с учетом требоввиий такого менеджера (с дополнительнымн средстввмн рсгистрвнии вггх уквзвтелей нв выделяемые блоки памяти). (Вопрогы косвенной вдресицин и звогижгнвого режима цроцессорон не упоминвем, твк квк они не свнзвны с тематикой книги.) — ))роьч нгргв. Выделенный блок (ТАб = и+и) Свободный блок (ТАб = е-и) Первое слово 3 Второе слово 312Е-2 слова (7) Последнее слово Идея следующего алгоритма состоит в поддержании двусвязного списка АЧАПе так что элементы списка могут быть легко удалены из произвольной части списка.
Поле ТАС с обоих концов блока можно использовать для управления процессом слияния, поскольку оно позволяет легко определить, свободен ли смежный блок памяти. Двойное связывание достигается обычным путем: 11КК в первом слове указывает на следующий доступный блок в списке, а (.1КК во втором слове указывает на предыдущий доступный блок. Таким образом, если Р— адрес блока, то 1.1КК((.1КК(Р) + 1) = Р = 1.1КК((.1йК(Р+ 1)). * Этот принцип положен, в частности, в основу управления памятью в МЯ ьгОЯ, где каждый блок памяти (МС — Мегоогу Сопгго! Высь) имеет поля размера, владезьца н типа блока.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
