AOP_Tom1 (1021736), страница 129
Текст из файла (страница 129)
Переполнение. Что необходимо предпринять, если больше нет свободного пространства? Предположим, что пришел запрос на и последовательных слов, в то время как все блоки слишком малы. В первый раз, когда такое происходит, обычно имеется более чем и доступных ячеек памяти, однако они расположены не последовательно. Уплотнение памяти (т. е. перемещение некоторых используемых ячеек, чтобы доступные ячейки памяти были собраны вместе) могло бы позволить продолжать обработку запросов. Однако уплотнение — медленный процесс, который требует строгой дисциплины применения указателей*.
Кроме того, в подавляющем большинстве случаев при использовании метода первого подходящего независимо от того, сколько раз проводилось уплотнение, память в конечнем счете оказывается полностью исчерпанной. Таким образом, вообще говоря, не имеет смысла писать программы для уплотнения, за исключением специальных случаев, связамных со сборкой мусора (см.
упр. ЗЗ). Если переполнение ожидается заранее, можно аподстелить соломки", воспользовавшись некоторыми из методов переноса элементов нз оперативной памяти ма внешние запомимающие устройства с обеспечением возврата элемента в оперативную память при необходимости в нем**. Отсюда вытекает, что для эффективной работы все программы, работающие с областями динамической памяти, должны быть строго ограничены в плане допустимых ссылок на другие блоки, а также обеспечиваться аппаратно (например, должна иметься воэможность генерирования прерывания при отсутствии данных в оперативной памяти или автоматической подкачке страниц). Необходима некоторая процедура принятия решения о том, какие блоки являются наиболее подходящими кандидатами на удаление из оперативной памяти.
Одна из идей состоит в содержании двусвяэного списка выделенных блоков, прн этом каждый блок двигается к началу списка при обращении к нему. Таким образом, блоки оказываются рассортированными и порядке последнего к ним обращения и блоки, расположенные в конце списка, удаляются первыми. Подобного эффекта можно достичь более просто; необходимо поместить выделенный блок в циклический список и включить в каждый блок бит внедавно использован". Этот бит устанавливается равным 1 при обращении к блоку. Когда наступает время удаления блока, указатель перемещается по циклическому списку, сбрасывая все биты "недавно использован" в нуль, пока не будет найден блок, к которому не было обращений со времени последнего прохода указателя по этой части списка.
Д. М. Робсон (3. М. В.оЬзоп) показал (зАСМ 18 (1971), 416-423], что стратегии динамического выделения памяти, которые никогда не переносят выделенные блоки, ме могут гарантировать эффективное использование памяти. Всегда найдутся патологические ситуации, при которых метод перестанет работать. Например, даже когда блоки ограничены размерами 1 илн 2, переполнение может произойти при заполнении памяти примерно на 2/3, какой бы алгоритм не использовался! Интересные результаты Робсона рассматриваются в упр. 36 — 40, а также в упр.
42 " В этом случае справедливы все замечания, сделанные выше в связи с лгетодом сборки ллусоРа. — Приве иерее. ** Этот процесс известен в современной литературе как сеепииг (гмаррлий). Еще одно замечание заключается в том, что внешним запоминающим устройством, в принципе, может быть и сама оперативная память †сто только аспомнитьь какилл образом в ГЛОЗ использовалась недоступная для пряллой адресации память ЕзйлоггХЫлз.— Прим. иерее. и 43, в которых показано, что.метод наилучшего подходящего имеет очень плохой наихудший случай по сравнению с методом первого подходящего. С.
Для дальнейшего чтения. Всестороннее исследование и критический обзор технологий динамического выделения памяти, основанный на более многолетнем опыте, чем опыт автора этой книги, можно найти в работе Рап! Н. гг'!!зоп, Маг1с 8. Лойпзсопе, Мгс!зае! Хее!у, апс( Ыач!6 Во!ез, Ьесгпге Хогеэ ш Сошрп1ег Ес/- енсе 986 (1995), 1-116. УПРАЖНЕНИЯ 1. [20] Какие упрощения алгоритмов выделения и освобождения памяти, описанных в этом разделе, можно сделать, если предположить, что запросы на выделение и освобождение памяти всегда приходят в стековом порядке ("последним выделен — первым освобожден" ), т.
е. ни один блок не освобождается, пока не освобождены все выделенные после него блоки? 2. [НМ23] (Э. Вольман (Е. %о!щап).) Предположим, что необходимо выбрать фиксированный размер узла для элементов переменной длины, и предположим также, что, когда каждый узел имеет длину Ь, а элемент — длину 1, для хранения такого элемента используется [1/(1с — Ь)] узлов (здесь Ь вЂ” константа, обозначающая, что Ь слов калсдого узла содержат управляющую информацию, например связь со следующим узлом).
Если средняя длина 1 элемента равна Ь, то какой выбор Ь минимизирует среднее количество необходимой памяти? (Положим, что среднее значение (1/(/г — Ь)) щог)1 равно 1/2 для любого фиксированного Ь и переменного 1.) 3. [40] При помощи компьютерного моделирования сравните следующие методы выделения памяти: наилучшего подходящего, первого подходящего и наихудшего подходли!его В последнем случае всегда выбирается наибольший доступный блок. Есть ли при этом существенная разница в использовании памяти? 4.
[22] Напишите 511-программу для алгоритма А, обращая особое внимание на ускорение работы внутреннего цикла. Положите, что поле 3125 — это (4:5), поле Ь1УК вЂ” (О: 2), а А ( О. ° 5. [12] Предположим, известно, что в алгоритме А у всегда не меньше 100, Стбит ли устанавливать с = 100 на модифицированном шаге А4'? б. [22] (Следующий подходящий.) При постоянном использовании алгоритма А возникает тенденция к тому, что блоки малого размера остаются в начале списка АЧА11., поэтому приходится часто проводить длительный поиск блока нужного размера. Например, обратите внимание на рис.
42, на котором четко видно, как увеличиваются размеры блоков (как занятых, так и свободных) от начала памяти к се концу. (Список АЧА15 рвссортирован по увеличению адресов памяти, как того требует алгоритм В.) Можете ли вы предложить такой вариант модификации алгоритма А, что (а) короткие блоки при его работе не скапливаются в некоторой области и (Ь) список АЧА15 остается упорядоченным по адресам памяти для работы алгоритма наподобие В? 7. [10] Пример (1) показывает, что иногда метод первого подходящего заведомо превосходит метод наилучшего подходящего. Приведите аналогичный пример, когда метод наилучшего подходящего заведомо превосходит метод первого подходящего 8.
[21] Покажите, каким образом можно просто модифицировать алгоритм А для работы по методу наилучшего подходящего (вместо изначального метода первого подходящего). 9. [20] Каким образом следует разработать алгоритм выделения памяти, работающий по методу наилучшего подходящего, чтобы он не проходил в поисках необходимого блока памяти весь список АЧА1Ь? (Попытайтесь придумать метод, снижающий необходимый поиск настолько, насколько зто возможно.) 10, [36[ Покажите, каким образом можно модифицировать алгоритм В, чтобы блок из И последовательных ячеек, начинающийся с адреса РО, становился свободным без предположения о занятости всех И ячеек. Считается, что осваба)кдавмая область может перекрывить несколько уже освобожденных блоков, 11.
[Мбо[ Покажите, что предложенное в упр, 8 усовершенствование алгоритма А можно также использовать для иекаторага улучшения алгоритма В, чта приведет к снижению средней длины поиска ат половины длины списка АЧА1Ь до одной трети. (Предполагается, что освобождающийся блок будет вставлен в упорядоченный список АЧА1Ь в случайном масте.) Р 12.
[30) Маднфицируйте алгоритм А таким образам, чтобы он следовал соглашениям»помеченных границ» (7)-(9), использовал измененный шаг А4', описанный в тексте раздела, н включал усовершенствования из упр. 6, 13. [3![ Напишите И1Х-программу для алгоритма из упр, 12, 14, [8([ Какие отличия появились бы в алгоритме С и алгоритме из упр. !2, если бы (а) а последнем славе свободнога блока отсутствовало пале ЕЬЕЕ и ()з) пале ЕЬЕЕ отсутствовало в первом слове выделанного блока? э 16, [84[ Покажите, как ускорить работу алгоритма С за счет небольшого удлинения про.
граммы, не изменяя связей больше, чем вто абсолютно необходима в каждом из четырах случаев, я зависимости от тога, чем являетса каждый из дескрипторов ТАС(РО - !) и ТАС(РО+ 8126(РО)) — плюсам или минусом. 16, [84) Напишите И1Х-программу для алгоритма С, включающую идеи из упр. 16, 1Т, [!О[ Каким должно быть содержимое ЬОС(АЧА1Ы и ЬОС(АЧА1Ы+1 в (9) при отсутствии досгуппых блоков? ° 18. [80) Рис, 42 и 43 получены с помощью одних и твх же данных и по сути одинаковых алгоритмов (алгоритмов А и В), но рис, 43 подготовлен модифицированным алгоритмом А с выбором наилучшего подходящего вместо первого подходвщега, Почему при этом на рнг, 42 большая свободная область нахадитсн в сгпаршнх адресах памяти, в то время как па ри~ .
43 она же находится в младшнв адресах? ° 19, [84) Предположим, что блоки памяти имеют вид (7), но без полей ТАС или 6126 в нагл~';шеи славе блока. Предположим далее, что для освобождения блока испальзуетсн следующий алгоритм. О <- АЧА1Ь, ЬХИК(РО) е-О, ЬХКК(РО+1) <- ЬОО(АЧА1Ы, ЬХИК(С+ !) е- РО, АЧА1Ь е- РО, ТАС(РО) е- "-".
(Он не выполняет объединение соседних свободных областей,) Разработайте алгоритм для выделения памяти, аналогичный алгоритму А, который выполняет объединение смежных свободных блоков во время поиска в списке АЧА1Ь и прн этом исключает любую излишнюю фрагментацию памяти, как в (2)-(4), 20. [00) Почему а системе двойников вместо линейных списков желательно иметь даусвязные списки АЧА1Ь(й)? 21. [НМйзе) Исследуйте отношение о„/Ь» при и -е оо, где ໠— сумма первых и членов ряда ! + 2 + 4 + 4 + 8 + 8 + 8 + 8 + !б + !6 +, в 8» — сумма первых и членов ряда ! + 2+ 3+ 4+ 5+ 6+ 7+ 8+ 9+ !О+ ь 22. [8? [ В тексте раздела неоднократно упоминаласг» что система двойников позволяет иметь только блоки размероа 2", и упр, 2! показывает, что это может привести к суп(встающему увеличению требуемой памяти Но если приходит запрос па блок размером )! слов, то почему нельзя найти блок размером !6 слов и разделить его на выделяемый блок размером !! слав и дяа свободных блока с размерами 4 и ! слава? 23.
(05] Каков двоичный апйес двойника блока размером 4, двоичный адрес каторага ршзем 01101111000Р? Каким бы ои был, если бы блок имел размер 10? 24. ]30] Согласно приведемиому в тексте раздела алгоритму наибольший блок (размерам 2 ) ме имеет дваймика, так как представляет собой всю память. Будет ли правильным определение двойник (О) = О (по сути, блок станет сабствемиым двойником), и мажма ли таким обрезом избежать проверки 3 = гп ма шаге 31? ь 23. (33] Раскритмкуйте следующую идею; еДимамическае выделение памяти с помощью системы двойников ма практике гмзкагда не приводит к выделению блока размерам 2"' (поскольку этим игчерпываетгя вся память), и, вообще говоря, имеется некоторый максимальный размер 2', такой, чта блоки большего размера никогда ие выделяются.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
