Структуры данных и алгоритмы (1021739), страница 94
Текст из файла (страница 94)
Весь "фокус" заключается в том, что если вообще используется поле back, то, поскольку рассматриваемая ячейка находится на обратномпути к ячейке sourcel, поле pattern может иметь лишь вполне определенные значения. Если, например, back = L, тогда известно, что поле pattern должно иметь значение РР или РА, поскольку очевидно, что поле left содержит указатель на какую-либоячейку. К аналогичному выводу можно прийти и тогда, когда back = R.
Таким образом, если взять два бита для представления как значения поля pattern, так и (в случае необходимости) значения поля back, можно закодировать требуемую информацию так, как показано, например, в табл. 12.2.12,3. АЛГОРИТМЫ ЧИСТКИ ПАМЯТИ ДЛЯ БЛОКОВ ОДИНАКОВОГО РАЗМЕРА 351Таблица 12.2. Интерпретация двух битов как значений полей pattern и backКод00011011На пути к ячейке source 1backbackbackback= L, pattern = PP= L, pattern = PA= R, pattern = PP= R, pattern = APHe на пути к source 1pattern = PPpattern = PApattern = APpattern = AAЧитатель наверное заметил, что в программе, представленной в листинге 12.3,нам всегда известно, используется ли поле back, и, таким образом, всегда можно сказать, какая из интерпретаций, показанных в табл. 12.2, подходит в данном случае.Попросту говоря, когда ячейка current указывает на ту или иную запись, то полеback в этой записи не используется; когда же ячейка previous указывает на запись —значит, используется.
Разумеется, при перемещении этих указателей необходимо откорректировать соответствующие коды. Если, например, ячейка current указываетна ячейку с битами 10, что в соответствии с табл. 12.2 интерпретируется какpattern = АР, и выполняется продвижение вперед (в этом случае previous будет ужеуказывать на эту ячейку), надо положить back = R, как только в правом поле окажется указатель, а соответствующие биты сделать равными 11. Обратите внимание:если у ячейки pattern — АА (этот вариант не представлен в среднем столбцетабл.
12.2), тогда нет необходимости, чтобы previous указывала на эту ячейку, поскольку для продвижения вперед нет указателей.12.4. Выделение памяти для объектов разного размераРассмотрим теперь управление динамической памятью (кучей), когда существуютуказатели на выделенные блоки (как показано на рис. 12.1). Эти блоки содержатданные того или иного типа. На рис. 12.1, например, эти данные являются строкамисимволов. Несмотря на то что тип данных, хранящихся в динамической памяти, вовсе не обязательно должен быть символьной строкой, мы полагаем, что эти данныене содержат указателей на те или иные адреса в динамической памяти.У задачи управления динамической памятью есть свои аспекты, которые делаютее, с одной стороны, легче, а с другой — тяжелее задачи управления структурамисписков ячеек одинаковой длины, которой был посвящен предыдущий раздел. Основной фактор, который облегчает задачу управления динамической памятью, заключается в том, что маркировка использованных блоков не является рекурсивнымпроцессом: нужно лишь следовать внешним указателям на динамическую память ипомечать указываемые блоки.
Нет необходимости выполнять просмотр связнойструктуры или что-то наподобие алгоритма Дойча — Шорра — Уэйта.С другой стороны, здесь управление списком свободного пространства не так просто, как описано в разделе 12.3. Представим, что свободные участки памяти(например, на рис. 12.1, а показаны три таких свободных участка) связаны друг сдругом так, как предлагается на рис. 12.5.
Здесь мы видим динамическую память из3 000 байт, поделенных на пять блоков. Два блока из 200 и 600 байт содержат значения X и Y. Остальные три блока свободны и связаны в цепочку, исходящую изячейки avail (доступно) заголовка свободного пространства.Если мы хотим, чтобы эти свободные блоки можно было найти, когда программепотребуется память для хранения новых данных, необходимо сделать следующиепредположения, касающиеся блоков динамической памяти (эти предположения распространяются на весь данный раздел).1.352Каждый блок имеет объем, достаточный для храненияа) счетчика, указывающего размер блока (в байтах или машинных словах в соответствии с конкретной компьютерной системой);ГЛАВА 12.
УПРАВЛЕНИЕ ПАМЯТЬЮ2.3.б) указателя (для связи данного блока со свободным пространством);в) бита заполнения, указывающего, является ли данный блок пустым; этот битназываетсябитомfull/empty(заполнено/свободно)илиused/unused(используется/не используется).В свободном (пустом) блоке слева (со стороны меньших значений адреса) содержатся счетчик, указывающий длину блока, бит заполнения, содержащий значение 0 (свидетельствует о том, что данный блок — пустой), указатель на следующий свободный блок.Блок, в котором хранятся данные, содержит (слева) счетчик, бит заполнения,содержащий значение 1 (свидетельствует о том, что данный блок занят), и собст1венно данные.avails500f 12002о><.0IсиICD03со1000сГоюосоо2шS0)700IЮОшоуказательбит заполнениясчетчикРис.
12.5. Динамическая память со списком свободного пространстваИз перечисленных предположений следует один интересный вывод: блоки должны "уметь" хранить в одном и том же месте иногда данные (в тех случаях, когдаблок используется), а во всех остальных случаях указатели (когда блок не используется). В результате оказывается невозможным (или, по крайней мере, чрезвычайнонеудобным) писать программы, которые манипулируют блоками, на языке Pascalили любом другом жестко типизированном языке. Таким образом, в этом разделе мывынуждены проявить непоследовательность и предлагать читателям только программы на псевдоРазса!, поскольку о реальных программах на языке Pascal в данномслучае не может быть и речи.
Однако никаких проблем не возникнет, если те же алгоритмы реализовать на ассемблерных языках или языках системного программирования, таких как С.Фрагментация и уплотнение пустых блоковЧтобы проанализировать одну из специальных проблем, связанных с управлениемдинамической памятью, допустим, что переменная У, показанная на рис. 12.5, удалена; в результате блок, представляющий У, необходимо вернуть в список свободного• пространства. Проще всего вставить новый блок в начало списка свободного пространства, как показано на рис. 12.6. На этом рисунке показан пример фрагментации, выражающейся в том, что крупные области памяти представляются в спискесвободного пространства все более мелкими "фрагментами", т.е.
множеством небольших блоков, составляющих целое (блок данных или свободное пространство). В рас1Обратите внимание: на рис. 12.1 счетчик показывает не длину блока, а длину данных.12.4. ВЫДЕЛЕНИЕ ПАМЯТИ ДЛЯ ОБЪЕКТОВ РАЗНОГО РАЗМЕРА353сматриваемом случае, как видно из рис. 12.6, последние 2 300 байт динамическойпамяти пусты, тем не менее, все это пространство делится на три блока, содержащие1 000, 600 и 700 байт соответственно, причем эти блоки даже не представлены в последовательном порядке (по местоположению в памяти) в списке свободного пространства. Поэтому в данном случае, не выполнив предварительно в той или инойформе "сборку мусора", удовлетворить запрос, например на блок 2 000 байт, не представляется возможным.avail.о500I200ю§ошi0)100060070003тРис.
12.6. Конфигурация памяти после освобождения блока переменной YОчевидно, что при возврате блока в список свободного пространства было бы желательно взглянуть на блоки, находящиеся непосредственно слева и справа от блока,который мы собираемся сделать доступным. Найти блок справа довольно просто. Если возвращаемый блок начинается с позиции р и имеет счетчик с, тогда блок справаначинается с позиции р + с. Если нам известно р, тогда остается только прочитатьбайты, начиная с позиции р, чтобы получить значение счетчика с. Начиная с байтар + с, пропускаем поле счетчика, чтобы найти бит, который говорит о том, являетсяли соответствующий блок пустым. Если этот блок пустой, тогда блоки, начинающиеся с р и р + с, можно объединить.Пример 12.4.
Допустим, что область динамической памяти, представленная нарис. 12.5, начинается с позиции 0. Тогда блок, возвращаемый переменной У, начинается в байте 1700, поэтому р = 1 700, а с = 600. Блок, начинающийся с позициир + с = 2 300, также пустой, поэтому можно объединить их в один блок, начинающийся с позиции 1 700, значением счетчика которого будет 1 300 (сумма значенийсчетчиков двух блоков). ПОднако откорректировать список свободного пространства после объединения блоков будет не так-то просто. Такой объединенный блок можно создать, просто добавивзначение счетчика второго блока к значению с.
Однако этот второй блок будет попрежнему включен в список свободного пространства и его нужно оттуда убрать. Дляэтого потребуется найти указатель на этот блок у его предшественника в списке свободного пространства. Для этого предусмотрено несколько стратегий, ни одна из которых не имеет предпочтения перед другими.1.354Можно просматривать список свободного пространства до тех пор, пока не будетнайден указатель, содержащий значение р + с. Этот указатель должен находиться в блоке-предшественнике того блока, который мы объединили с его соседом.Далее следует заменить найденный указатель на указатель, который находился вудаляемом блоке.
Это приводит к удалению блока, начинающегося с позициир + с, из списка свободного пространства. Разумеется, сам по себе этот блок будет по-прежнему доступен — просто теперь он является частью блока, начинаюГЛАВА 12. УПРАВЛЕНИЕ ПАМЯТЬЮщегося с позиции р. В среднем при использовании такого подхода приходитсяпросматривать примерно половину списка свободного пространства, поэтому затраченное время будет пропорционально длине этого списка.2.Можно использовать список свободного пространства с двойными связями. В этомслучае возможно довольно быстро найти блок-предшественник и удалить из спискаблок, начинающийся с позиции р + с.
Для реализации этого подхода требуется постоянное время, не зависящее от длины списка свободного пространства, но он требует дополнительного пространства для хранения второго указателя в каждом пустом блоке, что приводит к увеличению минимального размера блока, который вэтом случае должен содержать счетчик, бит заполнения и два указателя.3. Можно хранить список блоков свободного пространства, отсортированный по позициям. В таком случае известно, что блок, начинающийся с позиции р, является предшественником блока, начинающегося с позиции р + с.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
