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

(11) добавить d к счетчику блока, указываемому р;

(12) <?:= д + d end;

(13) вставить блок, на который указывает р, в список блоков

свободного пространства;

(14) р:= g end

end; { merge }

Пример 12.5. Применим программу из листинга 12.5 к схеме динамической памяти, изображенной на рис. 12.6. Допустим, что значение крайнего слева байта динамической памяти равно О, поэтому вначале р = 0. Поскольку для первого блока с = 500, при вычислении q имеем р + с = 500. Поскольку блок, начинающийся с 500, заполнен, цикл, включающий строки (10) - (12), не выполняется, и блок, состоящий из байтов О - 499, подсоединяется к списку свободного пространства, в результате чего ячейка avail указывает на байт О, а в соответствующее место этого блока помещается указатель nil (непосредственно после счетчика и бита заполнения). Затем в строке (14) р присваивается значение 500, а в строке (7) р увеличивается до 700. Указателю q в строке (9) присваивается значение 1 700, а затем в строке (12) - 2 300 и 3 ООО, в то время как к значению счетчика 1 ООО в блоке, начинающемся с 700-го байта, прибавляются 600 и 700. Когда q выйдет за пределы крайнего справа байта (2 999), блок, начинающийся с 700-го байта (значение счетчика в нем равно 2300), вставляется в список свободного пространства. Затем в строке (14) р присваивается значение 3 ООО и внещний цикл заверщается на строке (5). □

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

Выбор свободных блоков

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

Второй вопрос рещается достаточно просто. Если выбирается блок со счетчиком с и из этого блока требуется d < с байт памяти, то используются последние d байт. В таком случае понадобится только заменить счетчик с на. с - d, а оставшийся пустой блок может, как и ранее, оставаться в списке свободного пространства.

Пример 12.6. Допустим, требуется 400 байт для переменной 1К в ситуации, представленной на рис. 12.6. Можно было бы принять рещение изъять 400 байт из 600 в первом блоке списка свободного пространства. Ситуация в таком случае соответствовала бы рис. 12.7. D

Если значение с - d столь мало, что счетчик и указатель заполнения не умещаются в оставшееся свободное пространство, то, очевидно, надо использовать весь этот блок и убрать его из списка блоков свободного пространства.



avail

0) T

ro о

1000


Рмс. 72.7. Конфигурация памяти

Проблема выбора блока для размещения в нем новых данных не так рк проста, как может показаться, поскольку такие стратегии характеризуются противоречивыми целями. С одной стороны, мы хотим быстро выбрать пустой блок для размещения в нем новых данных, а с другой - хотим выбрать этот пустой блок таким образом, чтобы минимизировать фрагментацию. Две стратегии, которые представляют реализацию противоположных требований, называются "первый подходящий" (first-fit) и "самый подходящий" (best-fit). Описание этих стратегий приведено ниже.

1. Первый подходящий. В соответствии с этой стратегией, если требуется блок размера d, нужно просматривать список блоков свободного пространства с самого начала и до тех пор, пока не встретится блок размера с > d. Затем нужно использовать последние d байт (или слов) этого блока, как было описано выше.

2. Самый подходящий. В соответствии с этой стратегией, если требуется блок размера d, нужно проанализировать весь список блоков свободного пространства и найти блок размера не менее d, причем размер этого блока должен как можно меньше превышать величину d. Затем нркно использовать последние d байт этого блока.

По поводу этих стратегий мокно высказать ряд соображений. Стратегия "самый подходяший" работает значительно медленнее, чем стратегия "первый подходяший", поскольку при использовании последней можно рассчитывать на достаточно быстрое (в среднем) наховдение подходяшего блока, в то время как при использовании стратегии "самый подходяший" необходимо просмотреть весь список блоков свободного пространства. Стратегию "самый подходяший" можно несколько ускорить, если создать несколько списков блоков свободного пространства в соответствии с размерами этих блоков. Например, можно было бы иметь списки блоков размером от 1 до 16 бaйт, от 17 до 32 байт, от 33 до 64 байт и т.д. Это "усовершенствование" не оказывает заметного влияния на быстродействии стратегии "первый подходяший", более того, оно может даже замедлить ее работу, если распределения размеров и размешения блоков неблагоприятны. В свете последнего замечания мы можем определить некий спектр стратегий мевду "первым подходящим" и "самым подходящим", отыскивая "самый подходяший" среди первых к свободных блоков при некотором фиксированном значении к.

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

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



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

Пример 12.7. Допустим, в соответствии с рис. 12.6, список свободного пространства состоит из блоков размерами 600, 500, 1 ООО и 700 байт (в указанной последовательности). Если используется стратегия "первый подходящий" и сделан запрос на блок размером 400, то получим этот блок из блока размером 600, который оказался первым в списке и способен вместить блок заданного размера. Теперь, после выделения блока в 400 байт под данные, список свободного пространства состоит из блоков размерами 200, 500, 1 ООО и 700 байт. В этой ситуации мы не в состоянии удовлетворить тотчас же три запроса на блоки размером 600 (хотя это было бы возможным после объединения смежных пустых блоков и/или перемещения использованных блоков в динамической памяти).

Если используется стратегия "самый подходящий" применительно к списку свободных блоков размера 600, 500, 1 ООО и 700 байт и в систему поступил запрос на блок размером 400, то в соответствии с этой стратегией выбирается самый подходящий для такого запроса блок размером 500 байт, а список блоков свободного пространства принимает вид 600, 100, 1 ООО и 700 байт. В этом случае можно было бы удовлетворить три запроса на блоки размером 600, не прибегая к какой-либо реорганизации памяти.

С другой стороны, бывают ситуации (взять хотя бы наш список 600, 500, 1 ООО и 700 байт), когда стратегия "самый подходящий" не оправдывает себя, в то время как стратегия "первый подходящий" позволяет получить требуемый результат, не прибегая к реорганизации памяти. Допустим, в систему поступил запрос на блок размером 400 байт. Стратегия "самый подходящий", как и раньше, оставит список блоков размера 600, 100, 1 ООО и 700 байт, тогда как стратегия "первый подходящий" оставит список блоков размера 200, 500, 1 ООО и 700 байт. Допустим, что после этого в систему поступил запрос на блоки размером 1 ООО и 700 байт; любая из стратегий выделила бы полностью два последних пустых блока, оставив в случае стратегии "самый подходящий" свободными блоки размером 600 и 100 байт, а в случае стратегии "первый подходящий" - блоки размером 200 и 500 байт. После этого стратегия "первый подходящий" может удовлетворить запросы на блоки размером 200 и 500 байт, в то время как стратегия "самый подходящий" - нет. □

12.5. Методы близнецов

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

Главная идея, лежащая в основе всех методов близнецов, заключается в том, что все блоки имеют лишь строго определенные размеры Si < «г < «з < - < Характерными вариантами последовательности чисел Si, «г, ... являются числа 1, 2, 4, 8, ... (метод близнецов экспоненциального типа) и 1, 2, 3, 5, 8, 13, ... (метод близнецов с





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