Структуры данных и алгоритмы (1021739), страница 95
Текст из файла (страница 95)
Манипуляции суказателем, требующиеся для устранения второго блока, можно выполнять за(фиксированное время. Однако вставка нового свободного блока требует просмотра в среднем половины списка свободного пространства, что делает этот методничуть не эффективнее первого метода.Для возврата блока в список свободного пространства и объединения его со своимсоседом справа (если этот сосед пустой) из перечисленных трех стратегий лишь методам (1) и (3) требуется время, пропорциональное длине списка свободного пространства. При выборе подходящей стратегии это время может оказаться решающим фактором — здесь все зависит от длины списка свободного пространства и от того, какаячасть общего времени работы программы тратится на манипулирование динамической памятью. Второй метод — двойное связывание списка свободного пространства — обладает лишь одним недостатком: повышением минимального размера блоков.Кроме того, двойное связывание, подобно другим методам, мало помогает в поискесвободных соседей слева за время, меньшее того, которое требуется для просмотрасписка свободного пространства.Найти блок, расположенный непосредственно слева от интересующего нас блока,не так-то просто.
Позиция р блока и его счетчик с, определяя позицию блока справа,не позволяют определить адрес блока, расположенного слева. Нам нужно найти пустой блок, который начинается в некоторой позиции PI и имеет счетчик Cj, причемPi + Ci = p. Известны три варианта действий.1.2.3.Можно просматривать список свободного пространства пока не будет найдетблок, который находится в позиции pi и имеет счетчик с\, причем PI + e t = p.Выполнение этой операции занимает время, пропорциональное длине спискасвободного пространства.Можно поддерживать в каждом блоке (используемом или неиспользуемом) специальный указатель на позицию блока слева.
Этот подход позволяет находитьблок слева в течение фиксированного времени; затем можно проверить, являетсяли этот блок пустым, и, если это действительно так, объединить его с рассматриваемым нами блоком. Далее следует перейти в блок в позиции р + с и сделатьего указатель указывающим на начало нового блока, что позволит поддерживатьфункционирование таких "указателей влево".1Можно поддерживать список блоков свободного пространства, отсортированный попозициям.
Тогда при вставке в список вновь образовавшегося пустого блока легконайти пустой блок слева. Остается лишь проверить (зная позицию и счетчик "левого"пустого блока), нет ли между этими блоками каких-либо непустых блоков.1Предлагаем читателю в качестве упражнения подумать над тем, как можно было быобеспечить функционирование указателей, если блок расщепляется на два, при этом предполагается, что одна половина используется для хранения нового элемента данных, а втораяостается пустой.12.4. ВЫДЕЛЕНИЕ ПАМЯТИ ДЛЯ ОБЪЕКТОВ РАЗНОГО РАЗМЕРА355Как и в. случае объединения вновь образовавшегося пустого блока с его соседомсправа, первый и третий подходы к поиску и объединению с блоком слева требуютвремени, пропорционального длине списка свободного пространства.
Для реализациивторого метода, как и в предыдущем случае, требуется фиксированное время, однакоэтому методу присущ недостаток, не имеющий отношения к проблемам, касающимсядвойного связывания списка свободного пространства (о которых мы говорили в отношении поиска соседних блоков справа). В то время как двойное связывание пустых блоков повышает минимальный размер блока, нельзя сказать, что этот подходприводит к нерациональному расходованию памяти, поскольку в этом случае выполняется связывание лишь блоков, не используемых для хранения данных. Однакоуказание на соседей слева требует применения указателя как в используемых, так ив неиспользуемых блоках, и в этом случае действительно можно говорить о нерациональном расходовании памяти.
Если средний размер блока составляет сотни байт,дополнительным местом для хранения указателя можно и пренебречь. В то же время, если длина стандартного блока равняется лишь 10 байт, дополнительное местодля хранения указателя становится существенным фактором.Обобщив наши рассуждения о том, каким способом следует объединять вновь образовавшиеся пустые блоков с их пустыми соседями, можно указать на три подходак борьбе с фрагментацией.1.2.3.Можно воспользоваться одним из нескольких подходов (например, хранениесписка блоков свободного пространства в отсортированном виде), которые приводят к затратам времени, пропорциональным длине списка свободного пространства, каждый раз, когда блок становится неиспользуемым, но позволяют находить и объединять пустых соседей.Можно воспользоваться списком блоков свободного пространства с двойной связью каждый раз, когда блок становится неиспользуемым; кроме того, можноприменять указатели на соседа слева во всех блоках (используемых и неиспользуемых) для объединения за фиксированное время пустых соседей.Для объединения пустых соседей ничего не делать в явном виде.
Когда нельзянайти блок, достаточно большой, чтобы в нем можно было запомнить новыйэлемент данных, нужно просмотреть блоки слева направо, подсоединяя пустыхсоседей, а затем создавая новый список свободного пространства. Эскиз программы, реализующей такой алгоритм, показан в листинге 12.5.Листинг 12.5.
Объединение смежных пустых блоков(1) procedure merge;var(2)р, q: указатели на блоки;{ р указывает на левый конец объединенного пустого блока,g указывает на блок, расположенный справа от блокас указателем р, и который включается в объединенный блок,если этот блок справа пустой }begin(3)р:= крайний слева блок динамической памяти;(4)сделать список блоков свободного пространства пустым;(5)while р < правый конец динамической памяти do(6)if P указывает на полный блок со счетчиком с then(7)р:= р +• с { пропуск заполненных блоков }(8)else begin { р указывает на начало последовательностипустых блоков; их объединение }(9)д:= р + с { вычисление указателя q следующего блока }(10)while q указывает на пустой блок со счетчиком d иq < правого конца динамической памяти do begin356ГЛАВА 12.
УПРАВЛЕНИЕ ПАМЯТЬЮ(11)(12)добавить d к счетчику блока, указываемому р;д:= д + dend;(13)вставить блок, на который указывает р, в список блоковсвободного пространства;(14)р:= gendend; { merge }Пример 12.5. Применим программу из листинга 12.5 к схеме динамической памяти, изображенной на рис.
12.6. Допустим, что значение крайнего слева байта динамической памяти равно 0, поэтому вначале р = 0. Поскольку для первого блокас = 500, при вычислении q имеем р + с = 500. Поскольку блок, начинающийся с500, заполнен, цикл, включающий строки (10) - (12), не выполняется, и блок, состоящий из байтов 0 - 499, подсоединяется к списку свободного пространства, в результате чего ячейка avail указывает на байт О, а в соответствующее место этого блока помещается указатель nil (непосредственно после счетчика и бита заполнения).Затем в строке (14) р присваивается значение 500, а в строке (7) р увеличивается до700. Указателю q в строке (9) присваивается значение 1 700, а затем в строке (12) —2 300 и 3 000, в то время как к значению счетчика 1 000 в блоке, начинающемся с700-го байта, прибавляются 600 и 700. Когда q выйдет за пределы крайнего справабайта (2 999), блок, начинающийся с 700-го байта (значение счетчика в нем равно2300), вставляется в список свободного пространства.
Затем в строке (14) р присваивается значение 3 000 и внешний цикл завершается на строке (5). ПКогда общее количество блоков и количество свободных блоков отличаются не оченьзначительно, а вероятность случая, когда не удается обнаружить достаточно крупныйпустой блок, относительно невелика, можно считать, что метод (3) — объединение смежных пустых блоков лишь в тех случаях, когда испытывается нехватка пространства, —предпочтительнее метода (1). Метод (2) считается возможным конкурентом указанныхдвух методов, но если принять во внимание его потребность в дополнительной памяти, атакже тот факт, что каждый раз, когда блок вставляется в список блоков свободного пространства или удаляется оттуда, требуется некоторое дополнительное время для реорганизации списка, то можно прийти к выводу, что метод (2) предпочтительнее метода (3) всравнительно редких случаях и в принципе можно вообще забыть о нем.Выбор свободных блоковМы подробно обсудили, что следует делать, если какой-то блок данных освободился и его можно вернуть в список свободного пространства.
Должен быть, однако,предусмотрен и обратный процесс — извлечение свободных блоков для запоминанияв них новых данных. Очевидно, в этом случае надо выбрать тот или иной свободныйблок и использовать его (целиком или частично) для запоминания в нем нового элемента данных. Но в этой ситуации необходимо решить два вопроса. Во-первых, какой именно пустой блок следует выбрать? Во-вторых, если возможно использоватьтолько часть выбранного блока, то какую именно его часть следует использовать?Второй вопрос решается достаточно просто.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
