Структуры данных и алгоритмы (1021739), страница 98
Текст из файла (страница 98)
Проблема заключается в том, что свободное пространство делится между несколькими несмежными блоками. Существуют два общих подхода крешению этой проблемы.1.Пространство, выделяемое для хранения данных, состоит из нескольких пустых блоков. В таком случае можно потребовать, чтобы все блоки имели одинаковый размер ичтобы в них было предусмотрено место для указателя и данных. Указатель в используемом блоке указывает на следующий блок, используемый для хранения данных (впоследнем блоке указатель равен нулю). Если бы, например, мы хранили данные,размер которых чаще всего невелик, то можно было бы выбрать блоки по 16 байт(4 — для указателя и 12 — для данных).
Если же элементы данных обычно имеютбольшие размеры, следовало бы выбрать блоки размером несколько сотен байт (попрежнему 4 байта для указателя, а остальное для данных).2. Если объединение смежных пустых блоков не позволяет получить достаточно большой блок, данные в динамической памяти нужно переместить таким образом, чтобывсе заполненные блоки сместились влево (т.е. в сторону позиций с меньшими номерами); в этом случае справа образуется один крупный блок свободной памяти.Метод (1) — использование цепочек блоков для хранения данных — как правило,приводит к перерасходу памяти.
Если выбирается блок малого размера, это означает,что большая часть пространства будет использоваться для служебных целей(хранения указателей, с помощью которых формируется цепочка блоков). Если жеиспользуются крупные блоки, доля пространства, используемая для служебных целей, будет невелика, однако многие блоки все равно будут использоваться неэффективно при хранении в них небольших элементов данных. Единственной ситуацией,когда применение такого подхода представляется оправданным, является использование его для хранения очень больших элементов данных (если такие элементы данных являются типичными для вычислительной системы).
Например, во многих современных файловых системах динамическая память (которая, как правило, размещается на дисках) делится на блоки одинакового размера, от 512 до 4096 байт, в12.6. УПЛОТНЕНИЕ ПАМЯТИ363зависимости от конкретной системы. Поскольку размеры большинства файлов намного превышают эти величины, пространство используется достаточно эффективно,и указатели на блоки, составляющие файл, занимают относительно немного места.Выделение свободного пространства при использовании такого подхода выполняетсяпо относительно простой схеме (учитывая то, о чем говорилось в предыдущих разделах), поэтому здесь мы не будем углубляться в рассмотрение этого вопроса.Задача уплотнения памятиТипичная задача, с которой постоянно приходится сталкиваться на практике, заключается в следующем: нужно совокупность используемых блоков (например, ту,которая показана на рис.
12.9, а), каждый из которых может иметь свой размер и накоторых может указывать несколько указателей, смещать влево до тех пор, пока всесвободное пространство не окажется с правой стороны динамической памяти, какпоказано на рис. 12.9, б. Указатели, конечно же, должны по-прежнему указывать нате же данные.Данные 2Данные 1Данные 3а. Перед уплотнениемДанные 1 Данные 2 Данные 3б. После уплотненияРис. 12.9. Процесс уплотнения памятиУ этой задачи есть несколько простых решений, если в каждом блоке предусмотретьнебольшое дополнительное пространство.
Но мы рассмотрим другой, более сложныйметод. Этот метод весьма эффективен и не требует дополнительного места в используемых блоках (за исключением того пространства, которое требуется для любых уже обсуждавшихся нами схем управления памятью: бита заполнения и счетчика размера соответствующего блока).Простая схема уплотнения заключается в том, что сначала нужно просмотреть всеблоки слева направо (как заполненные, так и пустые) и вычислить так называемый"адрес передачи" (forwarding address) для каждого заполненного блока.
Адрес передачи блока — это его текущая позиция минус сумма всего пустого пространства слева от него, т.е. позиция, в которую в конечном счете необходимо переместить этотблок. Адрес передачи блока вычислить несложно. Когда мы просматриваем все блокислева направо, нужно суммировать объем встречающихся свободных блоков и вычитать этот объем из позиции каждого встречающегося блока. Эскиз соответствующегоалгоритма представлен в листинге 12.6.364ГЛАВА 12. УПРАВЛЕНИЕ ПАМЯТЬЮЛистинг 12.6. Вычисление адреса передачи(1) var(2)(3)(4)(5)(6)(7)(8)р: integer; { позиция текущего блока }gap: integer; { накапливающийся общий объем пустых блоков }beginр:= левый край динамической памяти;дар:= 0;while р < правый край динамической памяти do begin{ сделать р указателем на блок В }if В — пустой блок thenдар-.= дар + счетчик в блоке Вelse { В заполнен }адрес передачи блока В := р - дар;р:= р + счетчик в блоке Вendend;1Вычислив адреса передачи, анализируем все указатели динамической памяти.Следуя каждому указателю на некоторый блок В, этот указатель заменяется на адреспередачи, найденный для блока В.
Наконец, все заполненные блоки перемещаютсяпо их адресам передачи. Этот алгоритм подобен представленному в листинге 12.6,необходимо только заменить строку (7) на кодfor i: = р to р - 1 + счетчик в блоке В doheap[i-gap]:= heap[i];2чтобы сместить блок В влево на величину gap. Обратите внимание, что перемещениезаполненных блоков занимает время, пропорциональное объему используемой динамической памяти, и, по-видимому, будет преобладать над другими временными затратами, связанными с уплотнением памяти.Алгоритм МоррисаФ. Л. Моррис (F. L.
Morris) разработал метод уплотнения динамической памяти,не предусматривающий резервирования пространства в блоках для хранения адресовпередачи. Ему, однако, требуется дополнительный бит метки конца цепочки указателей. Суть этого метода заключается в создании цепочки указателей, исходящей изопределенной позиции в каждом заполненном блоке и связывающей все указатели сэтим блоком.
Например, на рис. 12.9, а мы видим три указателя, A, D и Е, указывающих на крайний слева заполненный блок. На рис. 12.10 показана требуемая цепочка указателей. Часть пространства блока, равного размеру указателя, изъята изблока и помещена в конец цепочки, где находится указатель А.Для создания таких цепочек указателей используется следующий метод. Сначала просматриваются все указатели в любом удобном порядке.
Допустим, просматриваем указатель р на блок В. Если бит метки конца в блоке В равен 0, значит, р является первым найденным нами указателем на блок В. Мы помещаем вр содержимое тех позиций В, которые используются для цепочки указателей, иделаем так, чтобы эти позиции В указывали на р. Затем устанавливаем бит метки конца в блоке В в 1 (это означает, что теперь у него есть указатель), а бит1Во всех действиях, которые следуют далее, мы полагаем, что совокупность этих указателей известна. Например, типичная реализация на языке Snobol запоминает пары, состоящиеиз имени переменной и указателя на значение этого имени в хеш-таблице, причем функцияхеширования вычисляется на основе этого имени. Просмотр хеш-таблицы позволяет перебратьвсе указатели.В этом коде массив heap (куча) содержит адреса блоков динамической памяти.
— Прим. ред.12.6. УПЛОТНЕНИЕ ПАМЯТИ365метки конца в р устанавливаем в 0 (это означает конец цепочки указателей иприсутствие смещенных данных).Допустим теперь, что при просмотре указателя р на блок В бит метки конца вблоке В равен 1. Это значит, что блок В уже содержит заголовок цепочки указателей. Мы копируем в р указатель, содержащийся в В, и делаем так, чтобы В указывал на р, а бит метки конца в р устанавливаем в 1. Тем самым, по сути, вставляем рв заголовок цепочки указателей.бит указателя11Данные 1данные, на которыеранее указывалуказатель £бит меткиконца цепочкиРис. 12.10.
Создание цепочки указателейПосле того как мы свяжем все указатели на каждый блок в цепочку, исходящуюиз этого блока, можно переместить заполненные блоки как можно дальше влево(примерно так, как это сделано в рассмотренном выше алгоритме). Наконец, просматриваем каждый блок на его новой позиции и пробегаем всю его цепочку указателей. Теперь надо сделать так, чтобы каждый встреченный указатель указывал наблок в его новой позиции. Когда обнаруживается конец цепочки, переносим данныеиз блока В, содержащиеся в последнем указателе, в крайнее правое положение вблоке В и устанавливаем в 0 бит метки конца в этом блоке.Упражнения12.1.
Рассмотрим следующий вариант динамической памяти из 1 000 байт, где"чистые" блоки используются в данный момент для хранения данных, а блоки, помеченные буквами, связаны в список свободной памяти в алфавитномпорядке. Числа над блоками указывают первый байт в каждом блоке.Оа100200Ь400500575сd700850е900'9991Допустим, последовательно сделаны следующие запросы:1) выделить блок в 120 байт;2) выделить блок в 70 байт;3) вернуть в начало списка свободного пространства блок, находящийся в позиции 700 - 849;4) выделить блок в 130 байт.Приведите списки свободного пространства (в соответствующей последовательности) после выполнения каждого запроса в предположении, что свободныеблоки выбираются на основе стратегии366ГЛАВА 12.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
