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

{ следование правому указателю } currentt .Ьаск:= R;

rotate {previous, current, currentt. right) ;

( реализация изменений как на рис. 12.4,а, но следуя правому указателю } goto statel

else begin { следование левому указателю } currentt. back: - L;

rotate {previous, current, currentt. left) ;

{ реализация изменений как на рис. 12.4,а } goto statel

end;

state2: { завершение, отход или переключение } if previous = current then { завершение }

goto states else if (.previoust.back-.L) and

not blockrightiprevioust) then begin { переключение } previoust.back:= R;

rotateiprevioust .left, current, previoust. right) ;

{ реализация изменений как на рис . 12 . 4, б } goto statel

else if previoust .back = R then { отход }

rotate{previous, previoust. right, current)

{ реализация изменений как на рис. 12.4,в } else { previoust. back = L }

rotate {previous, previoust. left, current);

{ реализация изменений как на рис. 12.4,в,

но поле left предыдущей ячейки включено в путь }

goto state2 end;

state 3.- { здесь необходимо вставить код для связывания

непомеченных ячеек в список свободной памяти )

end; { nrdfs }

Алгоритм Дойча - Шорра - Уэйта без использования поля back

Возможно, хотя и маловероятно, что дополнительный бит, используемый в ячейках для поля back, может вызвать потребность в дополнительном байте или даже дополнительном машинном слове для хранения содержимого этого поля. Но оказывается, что без этого дополнительного бита вполне можно обойтись, по крайней мере при программировании на языке, который, в отличие от языка Pascal, позволяет использовать биты поля pattern для целей, отличных от тех, для выполнения которых они изначально предназначались. Весь "фокус" заключается в том, что если вообще используется поле back, то, поскольку рассматриваемая ячейка находится на обратном пути к ячейке sourcel, поле pattern может иметь лишь вполне определенные значения. Если, например, back = L, тогда известно, что поле pattern должно иметь значение РР или РА, поскольку очевидно, что поле left содержит указатель на какую-либо ячейку. К аналогичному выводу можно прийти и тогда, когда back - R. Таким образом, если взять два бита для представления как значения поля pattern, так и (в случае необходимости) значения поля back, можно закодировать требуемую информацию так, как показано, например, в табл. 12.2.



Таблица 12.2. Интерпретация двух битов как значений нолей pattern и back

На пути к ячейке source 1

He на пути к source 1

back = L, pattern = PP

pattern = PP

back = L, pattern = PA

pattern = PA

back = R, pattern = PP

pattern =AT>

back = R, pattern = AP

pattern=AK

Читатель наверное заметил, что в программе, представленной в листинге 12.3, нам всегда известно, используется ди поде back, и, таким образом, всегда можно сказать, какая из интерпретаций, показанных в табл. 12.2, подходит в данном случае. Попросту говоря, когда ячейка current указывает на ту иди иную запись, то поде back в этой записи не используется; когда же ячейка previous указывает на запись - значит, используется. Разумеется, при перемещении этих указателей необходимо откорректировать соответствующие коды. Есди, например, ячейка current указывает на ячейку с битами 10, что в соответствии с табл. 12.2 интерпретируется как pattern =АР, и выполняется продвижение вперед (в этом случае previous будет уже указывать на эту ячейку), надо положить back = R, как только в правом поде окажется указатель, а соответствующие биты сделать равными И. Обратите внимание: есди у ячейки pattern - АА (этот вариант не представлен в среднем столбце табл. 12.2), тогда нет необходимости, чтобы previous указывала на эту ячейку, поскодьку ддя продвижения вперед нет указателей.

12.4. Выделение памяти для объектов разного размера

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

У задачи управдения динамической памятью есть свои аспекты, которые делают ее, с одной стороны, легче, а с другой - тяжелее задачи управдения структурами списков ячеек одинаковой длины, которой был посвящен предыдущий раздел. Основной фактор, который облегчает задачу управдения динамической памятью, заключается в том, что маркировка использованных блоков не является рекурсивным процессом: нужно дишь следовать внешним указателям на динамическую память и помечать указываемые блоки. Нет необходимости выполнять просмотр связной структуры иди что-то наподобие алгоритма Дойча - Шорра - Уэйта.

С другой стороны, здесь управление списком свободного пространства не так просто, как описано в разделе 12.3. Представим, что свободные участки памяти (например, на рис. 12.1, а показаны три таких свободных участка) связаны друг с другом так, как предлагается на рис. 12.5. Здесь мы видим динамическую память из 3 ООО байт, поделенных на пять блоков. Два бдока из 200 и 600 байт содержат значения X я Y. Остальные три бдока свободны и связаны в цепочку, исходящую из ячейки avail (доступно) заголовка свободного пространства.

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

1. Каждый бдок имеет объем, достаточный ддя хранения

а) счетчика, указывающего размер бдока (в байтах иди машинных словах в соответствии с конкретной компьютерной системой);



б) указателя (для связи данного блока со свободным пространством);

в) бита заполнения, указывающего, является ли данный блок пустым; этот бит называется битом full/empty (заполнено/свободно) или used/unused (используется/не используется).

В свободном (пустом) блоке слева (со стороны меньших значений адреса) содержатся счетчик, указывающий длину блока, бит заполнения, содержащий значение О (свидетельствует о том, что данный блок - пустой), указатель на следующий свободный блок.

Блок, в котором хранятся данные, содержит (слева) счетчик, бит заполнения, содержащий значение 1 (свидетельствует о том, что данный блок занят), и собственно данные.


указатель

битзаполнения счетчик

Рис. 12.5. Динамическая память со списком свободного пространства

Из перечисленных предположений следует один интересный вывод: блоки должны "уметь" хранить в одном и том же месте иногда данные (в тех случаях, когда блок используется), а во всех остальных случаях указатели (когда блок не используется). В результате оказывается невозможным (или, по крайней мере, чрезвычайно неудобным) писать программы, которые манипулируют блоками, на языке Pascal или любом другом жестко типизированном языке. Таким образом, в этом разделе мы вынуждены проявить непоследовательность и предлагать читателям только программы на псевдоРазса!, поскольку о реальных программах на языке Pascal в данном случае не может быть и речи. Однако никаких проблем не возникнет, если те же алгоритмы реализовать на ассемблерных языках или языках системного программирования, таких как С.

Фрагментация и уплотнение пустых блоков

Чтобы проанализировать одну из специальных проблем, связанных с управлением динамической памятью, допустим, что переменная У, показанная на рис. 12.5, удалена; в результате блок, представляющий Y, необходимо вернуть в список свободного • пространства. Проще всего вставить новый блок в начало списка свободного пространства, как показано на рис. 12.6. Па этом рисунке показан пример фрагмента ции, выражающейся в том, что крупные области памяти представляются в списке свободного пространства все более мелкими "фрагментами", т.е. множеством небольших блоков, составляющих целое (блок данных или свободное пространство). В рас-

Обратите внимание: на рис. 12.1 счетчик показывает не длину блока, а длину данных. 12.4. ВБЩЕЛЕПИЕ ПАМЯТИ ДЛЯ ОБЪЕКТОВ РАЗНОГО РАЗМЕРА 353





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.0037