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

сматриваемом случае, как видно из рис. 12.6, последние 2 300 байт динамической памяти пусты, тем не менее, все это пространство делится на три блока, содержащие 1 ООО, 600 и 700 байт соответственно, причем эти блоки даже не представлены в последовательном порядке (по местоположению в памяти) в списке свободного пространства. Поэтому в данном случае, не выполнив предварительно в той или иной форме "сборку мусора", удовлетворить запрос, например на бдок 2 ООО байт, не представляется возможным.

avail

>s

л т.

1000

Рис. 12.6. Конфигурация памяти после освобождения блока переменной

Очевидно, что при возврате бдока в список свободного пространства было бы желательно взглянуть на блоки, находящиеся непосредственно слева и справа от бдока, который мы собираемся сделать доступным. Найти бдок справа довольно просто. Есди возвращаемый бдок начинается с позиции р и имеет счетчик с, тогда бдок справа начинается с позиции р + с. Есди нам известно р, тогда остается только прочитать байты, начиная с позиции р, чтобы подучить значение счетчика с. Начиная с байта р + с, пропускаем поде счетчика, чтобы найти бит, который говорит о том, является ди соответствующий бдок пустым. Если этот бдок пустой, тогда блоки, начинающиеся с р и -Ь с, мокно объединить.

Пример 12.4. Допустим, что область динамической памяти, представленная на рис. 12.5, начинается с позиции 0. Тогда бдок, возвращаемый переменной Y, начинается в байте 1700, поэтому/) = 1 700, а с = 600. Бдок, начинающийся с позиции р + с = 1 300, также пустой, поэтому мокно объединить их в один бдок, начинающийся с позиции 1 700, значением счетчика которого будет 1 300 (сумма значений счетчиков двух блоков). □

Однако откорректировать список свободного пространства посде объединения блоков будет не так-то просто. Такой объединенный бдок мокно создать, просто добавив значение счетчика второго бдока к значению с. Однако этот второй бдок будет по-прежнему включен в список свободного пространства и его нужно оттуда убрать. Ддя этого потребуется найти указатель на этот бдок у его предшественника в списке свободного пространства. Ддя этого предусмотрено несколько стратегий, ни одна из которых не имеет предпочтения перед другими.

1. Мокно просматривать список свободного пространства до тех пор, пока не будет найден указатель, содержащий значение р + с. Этот указатель должен находиться в блоке-предшественнике того бдока, который мы объединили с его соседом. Далее следует заменить найденный указатель на указатель, который находился в удаляемом блоке. Это приводит к удалению бдока, начинающегося с позиции р + с, из списка свободного пространства. Разумеется, сам по себе этот бдок будет по-прежнему доступен - просто теперь он является частью бдока, начинаю-



щегося с позиции р. В среднем при использовании такого подхода приходится просматривать примерно половину списка свободного пространства, поэтому затраченное время будет пропорционально длине этого списка.

2. Можно использовать список свободного пространства с двойными связями. В этом случае возможно довольно быстро найти блок-предгпественник и удалить из списка блок, начинающийся с позиции р + с. Для реализации этого подхода требуется постоянное время, не зависящее от длины списка свободного пространства, но он требует дополнительного пространства для хранения второго указателя в каждом пустом блоке, что приводит к увеличению минимального размера блока, который в этом случае должен содержать счетчик, бит заполнения и два указателя.

3. Можно хранить список блоков свободного пространства, отсортированный по позициям. В таком случае известно, что блок, начинающийся с позиции р, является предшественником блока, начинающегося с позиции р + с. Манипуляции с указателем, требующиеся для устранения второго блока, можно выполнять за фиксированное время. Однако вставка нового свободного блока требует просмотра в среднем половины списка свободного пространства, что делает этот метод ничуть не эффективнее первого метода.

Для возврата блока в список свободного пространства и объединения его со своим соседом справа (если этот сосед пустой) из перечисленных трех стратегий лищь методам (1) и (3) требуется время, пропорциональное длине списка свободного пространства. При выборе подходящей стратегии это время может оказаться решающим фактором - здесь все зависит от длины списка свободного пространства и от того, какая часть обшего времени работы программы тратится на манипулирование динамической памятью. Второй метод - двойное связывание списка свободного пространства - обладает лишь одним недостатком: повышением минимального размера блоков. Кроме того, двойное связывание, подобно другим методам, мало помогает в поиске свободных соседей слева за время, меньшее того, которое требуется для просмотра списка свободного пространства.

Найти блок, расположенный непосредственно слева от интересующего нас блока, не так-то просто. Позиция р блока и его счетчик с, определяя позицию блока справа, не позволяют определить адрес блока, расположенного слева. Нам нужно найти пустой блок, который начинается в некоторой позиции pi и имеет счетчик С], причем Рх + Ci= р. Известны три варианта действий.

1. Можно просматривать список свободного пространства пока не будет найдет блок, который находится в позиции pi и имеет счетчик С], причем pi + Ci = p. Выполнение этой операции занимает время, пропорциональное длине списка свободного пространства.

2. Можно поддерживать в каждом блоке (используемом или неиспользуемом) специальный указатель на позицию блока слева. Этот подход позволяет находить блок слева в течение фиксированного времени; затем можно проверить, является ли этот блок пустым, и, если это действительно так, объединить его с рассматриваемым нами блоком. Далее следует перейти в блок в позиции р + с и сделать его указатель указывающим на начало нового блока, что позволит поддерживать функционирование таких "указателей влево".

3. Можно поддерживать список блоков свободного пространства, отсортированный по позициям. Тогда при вставке в список вновь образовавшегося пустого блока легко найти пустой блок слева. Остается лишь проверить (зная позицию и счетчик "левого" пустого блока), нет ли между этими блоками каких-либо непустых блоков.

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



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

Обобщив наши рассуждения о том, каким способом следует объединять вновь образовавшиеся пустые блоков с их пустыми соседями, можно указать на три подхода к борьбе с фрагментацией.

/. Можно воспользоваться одним из нескольких подходов (например, хранение списка блоков свободного пространства в отсортированном виде), которые приводят к затратам времени, пропорциональным длине списка свободного пространства, каждый раз, когда бдок становится неиспользуемым, но позволяют находить и объединять пустых соседей.

2. Молшо воспользоваться списком блоков свободного пространства с двойной связью каждый раз, когда бдок становится неиспользуемым; кроме того, можно применять указатели на соседа слева во всех блоках (используемых и неиспользуемых) ддя объединения за фиксированное время пустых соседей.

3. Ддя объединения пустых соседей ничего не делать в явном виде. Когда нельзя найти бдок, достаточно большой, чтобы в нем можно было запомнить новый эдемент данных, нужно просмотреть блоки слева направо, подсоединяя пустых соседей, а затем создавая новый список свободного пространства. Эскиз программы, реализующей такой алгоритм, показан в листинге 12.5.

Листинг 12.5. Объединение смежных пустых блоков

(1) procedure merge; var

(2) р, <j: указатели на блоки;

{ р указывает на левый конец объединенного пустого блока, g указывает на блок, расположенный справа от блока с указателем р, и который включается в объединенный блок, если этот блок справа гг/стой }

begin

(3) р:= крайний слева блок динамической памяти;

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

(5) while р < правый конец динамической памяти do

(6) if Р указывает на полный блок со счетчиком с then

(7) р:= р + с { пропуск заполненных блоков }

(8) else begin { р указывает на начало последовательности

пустых блоков; их объединение }

(9) д": = р + с { вычисление указателя q следующего блока }

(10) while q указывает на пустой блок со счетчиком d и

q < правого конца динамической памяти do begin





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