Главная Промышленная автоматика.

метки конца в р устанавливаем в О (это означает конец цепочки указателей и присутствие смещенных данных).

Допустим теперь, что при просмотре указателя р на блок В бит метки конца в блоке В равен 1. Это значит, что блок В уже содержит заголовок цепочки указателей. Мы копируем в р указатель, содержащийся в В, и делаем так, чтобы В указывал на р, а бит метки конца в р устанавливаем в 1. Тем самым, по сути, вставляем р в заголовок цепочки указателей.

бит указателя

Данные 1


бит метки конца цепочки

данные, на которые ранее указывал указатель £

Рис. 12.10. Создание цепочки указателей

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

Упражнения

12.1. Рассмотрим следующий вариант динамической памяти из 1 ООО байт, где "чистые" блоки используются в данный момент для хранения данных, а блоки, помеченные буквами, связаны в список свободной памяти в алфавитном порядке. Числа над блоками указывают первый байт в каждом блоке.

О 100 200 400 500 575 700 850 900 999

Допустим, последовательно сделаны следующие запросы:

1) выделить блок в 120 байт;

2) выделить блок в 70 байт;

3) вернуть в начало списка свободного пространства блок, находящийся в позиции 700 - 849;

4) выделить блок в 130 байт.

Приведите списки свободного пространства (в соответствующей последовательности) после выполнения каждого запроса в предположении, что свободные блоки выбираются на основе стратегии



а) первый подходящий;

б) самый подходящий.

12.2. Рассмотрим следующий вариант динамической памяти, в котором "чистью" участки обозначают используемую память, а участки, помеченные буквами, - неиспользуемую, т.е. пустую.

О 100 200 300 500

Укажите последовательности запросов, которые можно удовлетворить, если использовать стратегии

а) первого подходящего, но не самого подходящего;

б) самого подходящего, но не первого подходящего.

"12.3. Допустим, что используется экспоненциальный метод близнецов с размерами блоков 1, 2, 4, 8 и 16 в динамической памяти размером 16. Если поступает запрос на блок размером я при 1 < я < 16, то необходимо выделить блок размером 2, где 2" < я < 2. Неиспользуемую часть блока (если таковая имеется) нельзя использовать для удовлетворения любого другого запроса. Если нужен блок размером 2 при i < 4 и такого свободного блока в динамической памяти нет, то сначала находится блок размером 2 и расщепляется на две равные части. Если блока размером 2 также нет, тогда сначала находится и расщепляется свободный блок размером 2", и т.д. Если оказывается, что необходим свободный блок размером 32, то следует признать, что удовлетворить посту-пивщий запрос не удалось. В данном упражнении предполагается, что нельзя объединять смежные свободные блоки в динамической памяти.

Существуют последовательности запросов «1, а, ... , а„, сумма которых меньще 16, причем последний запрос в таких последовательностях удовлетворить невозможно. Рассмотрим, например, последовательность 5, 5, 5. Первый запрос приводит к расщеплению начального блока размером 16 на две части размером 8, причем одна из них используется для удовлетворения поступивщего запроса. Оставщийся свободный блок размером 8 удовлетворяет второй запрос, но для удовлетворения третьего запроса свободного пространства уже нет.

Найдите последовательность а,, аг, ... , а„ целых чисел (необязательно одинаковых) из интервала от 1 до 16, сумма которых по возможности минимальна, но если эту последовательность рассматривать как последовательность запросов на блоки размеров а, «2. ••• , то последний запрос удовлетворить невозможно. Поясните, почему эту последовательность запросов невозможно удовлетворить, а любую последовательность, сумма которой окажется меньше, можно.

12.4. Рассмотрим задачу уплотнения памяти для блоков одинакового размера. Допустим, каждый блок состоит из поля данных и поля указателя. Допустим также, что уже помечены все используемые в настоящее время блоки. Пусть эти блоки находятся в области памяти, расположенной между адресами а и Ь. Необходимо поменять местоположение всех блоков, занятых данными, так, чтобы они занимали непрерывный участок памяти, начиная с адреса а. Перемешая блок, следует помнить, что необходимо скорректировать поле указателя любого блока, указывающее на перемешаемый блок. Разработайте алгоритм уплотнения таких блоков.

12.5. Рассмотрим массив размера я. Разработайте алгоритм циклического сдвига против часовой стрелки всех элементов в таком массиве на k позиций, используя только фиксированную дополнительную память, объем которой не зависит от Л и я. Совет. Проанализируйте, что произойдет, если переставить в обратном порядке первые к элементов, последние п - к элементов и, наконец, весь массив.



12.6. Разработайте алгоритм замены вложенной строки символов у, принадлежащей строке хуг, на другую вложенную строку у, используя для этого как можно меньшее количество дополнительной памяти. Какова временная сложность (время выполнения) этого алгоритма и сколько для него необходимо памяти?

12.7. Напишите программу получения копии заданного списка. Какова временная сложность этого алгоритма и сколько для него необходимо памяти?

12.8. Напишите программу, которая проверяла бы идентичность двух списков. Какова временная сложность этого алгоритма и сколько для него необходимо памяти?

12.9. Реализуйте алгоритм Морриса для уплотнения динамической памяти (см. раздел 12.6).

* 12.10. Разработайте схему выделения памяти применительно к ситуации, когда память выделяется и освобовдается блоками длиной 1 и 2. Перечислите преимущества и недостатки такого алгоритма.

Библиографические примечания

Эффективное управление памятью - центральная проблема, которую решают разработчики многих языков программирования, в том числе Snobol [30], Lisp [74], APL [56] и SETL [98]. В [80] и [86] обсркдают методы управления памятью в контексте компиляции языков программирования.

Выделение памяти по методу близнецов было впервые описано в [62]. Метод близнецов с числами Фибоначчи рассмотрен в работе [48].

Изящный алгоритм маркировки, предназначенный для использования в процедуре чистки памяти, был разработан Питером Дойчем (Peter Deutsch) [25], а таюке Шорром и Уэйтом (Schorr and Waite) [97]. Схема уплотнения динамической памяти, изложенная в разделе 12.6, заимствована из статьи [77].

В работах [90] и [91] анализирует объем памяти, требующийся для работы алгоритмов динамического выделения памяти. В [92] представлен алгоритм ограниченного рабочего пространства (bounded workspace algorithm) для копирования циклических структур. Решение упражнения 12.5 можно найти в [32].





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 [118] 119 120 121 122 123

0.0035