F. Переполнение. Что вдобходимо предпринять, если больше нет свободного пространства? Предположим, что пришел запрос на п последовательных слов, в то время как все блоки слишком- малы. В первый раз, когда такое происходит, обычно имеется более чем п доступных ячеек памяти, однако они расположены не последовательно. Уплотнение памяти (т. е. перемещение некоторых используемых ячеек, чтобы доступные ячейки памяти были собраны вместе) могло бы позволить продолжать обработку запросов. Однако уплотнение - медленный процесс, который требует строгой дисциплины применения указателей*. Кроме того, в подавляющем большинстве случаев при использовании метода первого подходящего независимо от того, сколько раз проводилось уплотнение, память в конечнам счете оказывается полностью исчерпанной. Таким образом, вообще говоря, не имеет смысла писать программы для уплотнения, за исключением специальных случаев, связанных со сборкой мусора (см. упр. 33). Если переполнение ожидается заранее, можно "подстелить соломки", воспользовавшись некоторыми из методов переноса элементов из оперативной памяти на внешние запоминающие устройства с обеспечением возврата элемента в оперативную память при необходимости в нем**. Отсюда вытекает, что для эффективной работы все программы, работающие с областями динамической памяти, должны быть строго ограничены в плане допустимых ссылок на другие блоки, а также обеспечиваться аппаратно (например, должна иметься возможность генерирования прерывания при отсутствии данных в оперативной памяти или автоматической подкачке страниц).

Необходима некоторая процедура принятия решения о том, какие блоки являются наиболее подходящими кандидатами на удаление из оперативной памяти. Одна из идей состоит в содержании двусвязного списка выделенных б.поков, при этом каждый блок двигается к началу списка при обращении к нему. Таким образом, блоки оказываются рассортированными в порядке последнего к ним обращения и блоки, расположенные в конце списка, удаляются первыми. Подобного эффекта можно достичь более просто: необходимо поместить выделенный блок в циклический список и включить в каждый блок бит "недавно использован". Этот бит устанавливается равным 1 при обращении к блоку. Когда наступает время удаления блока, указатель перемещается по циклическому списку, сбрасывая все биты "недавно использован" в нуль, пока не будет найден блок, к которому не было обращений со времени последнего прохода указателя по этой части списка.

Д. М. Робсон (J. М. Robson) показал [JACM 18 (1971), 416-423], что стратегии динамического выделения памяти, которые никогда не переносят выделенные блоки, не могут гарантировать эффективное использование памяти. Всегда найдутся патологические ситуации, при которых метод перестанет работать. Например, даже когда блоки ограничены размерами 1 или 2, переполнение может произойти при заполнении памяти примерно на 2/3, какой бы алгоритм не использовался! Интересные результаты Робсона рассматриваются в упр. 36-40, а также в упр. 42

* в этом случае справедливы все замечания, сделанные выше в связи с методом сборки мусора. - Прим. перев.

** Этот процесс известен в современной литературе как свопинг (swapping). Еще одно замечание заключается в том, что внешним запоминающим устройством, в принципе, может быть и сама оперативная память - стоит только вспомнить, каким образом в DOS использовалась недоступная для прямой адресации память EMS/XMS. - Прим. перев.

и 43, в которых показано, что,метод наилучшего подходящего имеет очень плохой наихудший случай по сравнению с методом первого подходящего.

G. Для дальнейшего чтения. Всестороннее исследование и критический обзор технологий динамического выделения памяти, основанный на более многолетнем опыте, чем опыт автора этой книги, можно найти в работе Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles, Lecture Notes in Computer Science 986 (1995), 1-116.

УПРАЖНЕНИЯ

1. [20] Какие упрощения алгоритмов выделения и освобождения памяти, описанных в этом разделе, можно сделать, если предположить, что запросы на выделение и освобождение памяти всегда приходят в стековом порядке ("последним выделен - первым освобожден"), т. е. ни один блок не освобождается, пока не освобождены все выделенные после него блоки?

2. [НМ23] (Э. Вольман (Е. Wolman).) Предположим, что необходимо выбрать фиксированный размер узла для элементов переменной длины, и предположим также, что, когда каждый узел имеет длину к, а элемент - длину /, для хранения такого элемента используется [1/{к - Ь)] узлов (здесь b - константа, обозначающая, что b слов каждого узла содержат управляющую информацию, например связь со следующим узлом). Если средняя длина / элемента равна L, то какой выбор к минимизирует среднее количество необходимой памяти? (Положим, что среднее значение {1/{к - Ь)) mod 1 равно 1/2 для любого фиксированного к и переменного /.)

3. [40] При помощи компьютерного моделирования сравните следующие методы выделения памяти: наилучшего подходящего, первого подходящего и наихудшего подходяиего. В последнем случае всегда выбирается наибольший доступный блок. Есть ли при этом существенная разница в использовании памяти?

4. [22] Напишите MIX-программу для алгоритма А, обращая особое внимание на ускорение работы внутреннего цикла. Положите, что поле SIZE - это (4:5), поле LINK - (0:2), а Л < 0.

► 5. [18] Предположим, известно, что в алгоритме А N всегда не меньше 100. Стоит ли устанавливать с = 100 на модифицированном шаге А4?

► 6. [23] {Следуюш,ий подходящий.) При постоянном использовании алгоритма А возникает тенденция к тому, что блоки малого размера остаются в начале списка AVAIL, поэтому приходится часто проводить длительный поиск блока нужного размера. Например, обратите внимание на рис. 42, на котором четко видно, как увеличиваются размеры блоков (как занятых, так и свободных) от начала памяти к ее концу. (Список AVAIL рассортирован по увеличению адресов памяти, как того требует алгоритм В.) Можете ли вы предложить такой вариант модификации алгоритма А, что (а) короткие блоки при его работе не скапливаются в некоторой области и (Ь) список AVAIL остается упорядоченным по адресам памяти для работы алгоритма наподобие В?

7. [10] Пример (1) показывает, что иногда метод первого подходящего заведомо превосходит метод наилучшего подходящего. Приведите аналогичный пример, когда метод наилучшего подходящего заведомо превосходит метод первого подходящего

8. [21] Покажите, каким образом можно просто модифицировать алгоритм А для работы по методу наилучшего подходящего (вместо изначального метода первого подходящего).

► 9. [26] Каким образом следует разработать алгоритм выделения памяти, работающий по методу наилучшего подходящего, чтобы он не проходил в поисках необходимого блока

памяти весь список AVAIL? (Попытайтесь придумать метод, снижающий необходимый поиск настолько, насколько это возможно.)

10. [22] Покажите, каким образом можно модифицировать алгоритм В, чтобы блок из N последовательных ячеек, начинающийся с адреса РО, становился свободным без предположения о занятости всех N ячеек. Считается, что освобождаемая область может перекрывать несколько уже освобожденных блоков.

11. [М25] Покажите, что предложенное в упр. 6 усовершенствование алгоритма А можно также использовать для некоторого улучшения алгоритма В, что приведет к снижению средней длины поиска от половины длины списка AVAIL до одной трети, (Предполагается, что освобождающийся блок будет вставлен в упорядоченный список AVAIL в случайном месте.)

► 12. [20] Модифицируйте алгоритм А таким образом, чтобы он следовал соглашениям "помеченных границ" (7)-(9), использовал измененный шаг А4, описанный в тексте раздела, и включал усовершенствования из упр. 6.

13. [21] Напишите МХХ-программу для алгоритма из упр. 12,

14. [21] Какие отличия появились бы в алгоритме С и алгоритме из упр. 12, если бы (а) в последнем слове свободного блока отсутствовало поле SIZE и (Ь) поле SIZE отсутствовало в первом слова выделенного блока?

► 15. [24] Покажите, как ускорить работу алгоритма С за счет небольшого удлинения программы, не изменяя связей больше, чем это абсолютно необходимо в каждом из четырех случаев, в зависимости от того, чем является каждый из дескрипторов ТАОСРО - 1) и ТАО(РО + SIZE(PO)) --плюсом или минусом.

16. [24] Напишите МХХ-программу для алгоритма С, включающую идеи из упр, 15,

17. [10] Каким должно быть содержимое LDC С AVAIL) и LOC(AVAIL)-(-1 я (9) при отсутствии доступных блоков?

► 18. [20] Рис, 42 и 43 получены с помощью одних и тех же данных и по сути одинаковых алгортмов (алгоритмов А и В), но рис, 43 подготовлен модифицированным алгоритмом А с выбором наилучшего подходящего вместо первого подходящего, Почему при атом на рис. 42 большая свободная область находится в старших адресах памяти, в то время как иа ри(. 43 она же находится в младших адресах?

► 10. [24] Предположим, что блоки памяти имеют вид (7), но без полей TAG или SIZE в nocjuvuiPM слове блока. Предположим далее, что для освобождения блока используется следующий алгоритм: AVAIL, LINK (РО) Q, LIKK(P0 + 1) LOC(AVAIL), LIKK(Q + 1) РО, AVAIL <~ PC, TAGCPO) (Он не выполняет объединение соседних свободных областей.)

Разработайте алгоритм для выделения памяти, аналогичный алгоритму А, который выполняет объединение смежных свободных блоков во время поиска в списке AVAIL и при этом исключает любую излишнюю фрагментацию памяти, как в (2)-(4),

20. [00] Почему в системе двойников вместо линейных списков желательно иметь дву-связныр списки AVAIL [fc]?

21. [НМ25] Исследуйте отношение Оп/6п при п оо, где оп-сумма первых п членов ряда 1 + 2-Ь44-4 + 84-8 + 84-8--1б4-1б4-, а Ьп -сумма первых п членов ряда

I + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 +10-Ь-".

► 22. [21] В тексте раздела неоднократно упоминалось, что система двойников позволяет иметь только блоки размеров 2*", и упр, 21 показывает, что это может привести к существенному увеличению требуемой памяти Но если приходит запрос па блок размером

II слов, то почему нельзя найти блок размером 16 слов и разделить его на выделяемый блок размером 11 слов и два свободных блока с размерами 4 и 1 слово?