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

числами Фибоначчи, где s,+i = S( + Sj-i)- Все пустые бдоки размера Sj связаны в список; кроме того, существует массив загодовков списков свободных бдоков, по одному ддя каждого допустимого размера s,-. Есди ддя нового эдемента данных требуется бдок размером d, то выбирается свободный бдок такого размера s,> чтобы Sj > d, однако < d, т.е. наименьший допустимый размер, в который умещается новый эдемент данных.

Трудности возникают в том сдучае, когда не оказывается пустых бдоков требуемого размера s,. В этом сдучае находится бдок размером Sj+i и расщепдяется на два бдока, один размером s„ а другой - Sj+i - s,-. Метод бдизнецов надагает ограничение: величина s,+i - должна равняться некоторому числу sj из используемой последовательности, j < i. Теперь становится очевидным способ ограничения выбора значений ддя s,. Есди допустить, что j - i - к ддя некоторого /г > О, тогда, поскольку Sj+i - S( = Sj-ft, следует, что

«,.1 = + • (12.1)

Уравнение (12.1) применимо, когда i > к, и вместе со значениями si, S2, ... полностью определяет значения s+i, sj+2, ... . Есди, например, : = О, уравнение (12.1) принимает вид

V, = 2s,- (12.2)

Есди в (12.2) начальное значение Si = 1, то получаем экспоненциальную последовательность 1, 2, 4, 8.....Конечно, с какого бы значения Sy мы ни начали, в (12.2)

возрастают экспоненциально. Еще один пример: есди = 1, S] = 1 и S2 = 2, уравнение (12.1)принимает вид

«,н = «. + «<-.- (12.3)

Уравнение (12.3) определяет последовательность чисел Фибоначчи: 1, 2, 3, 5, 8, 13, ... .

Какое бы значение к в уравнении (12.1) мы ни выбрали, подучим метод близнецов кто порядка. Ддя любого к последовательность допустимых размеров возрастает по экспоненциальному закону, т.е. отношение Si+i/si близко некоторой > константе, большей единицы. Например, ддя = О отношение s,+i/s, равно точно 2. Ддя к = 1 коэффициент Sj+i/Si примерно равен "золотому сечению" ((Vs + 1)/2 = 1,618); этот коэффициент уменьшается при увеличении к, но никогда не достигает значения 1.

Распределение блоков

При использовании метода бдизнецов fe-ro порядка можно считать, что каждый бдок размером s,+i состоит из бдока размером и блока размером St-. Допустим для определенности, что бдок размером находится слева (в позициях с меньшими значениями номеров) от бдока размером Есди динамическую память рассматривать как единый бдок размером s„ (при некотором большом значении п), тогда позиции, с которых могут начинаться бдоки размером s,, будут полностью определены.

Позиции в экспоненциальном (т.е. 0-го порядка) методе близнецов вычислить достаточно просто. Есди предположить, что позиции в динамической памяти пронумерованы с О, тогда бдок размером s, начинается в любой позиции с числа, кратного

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

Разумеется, есди в системе отсутствуют и пустые бдоки размером si, то создается такой бдок путем расщепления бдока размером s,-2, и т.д. Есди в системе вообще отсутствуют бдоки более крупного размера, тогда, по сути, имеем дело с нехваткой памяти и необходимо реорганизовать динамическую память (о том, как это делается, рассказано в следующем разделе).

Заметим, что блоки размерами s, и st-k, составляющие блок размером удобно представлять "близнецами" (иди "двойниками") - именно отсюда и происходит термин "метод близнецов".



2, т.е. О, 2.....Более того, каждый блок размером 2*, начинающийся, скажем, с

j2*\ состоит из двух "близнецов" размером 2, которые начинают с позиций (2;)2, т.е. j2и (2j + 1)2. Таким образом, не составляет особого труда найти "близнеца" блока размером 2. Если он начинается с какого-либо четного числа, кратного 2, например (2/)2, его "близнец" находится справа в позиции (2j + 1)2. Если же он начинается с какого-либо нечетного числа, умноженного на 2, например (2/ + 1)2, его "близнец" находится слева на позиции (2/)2.

Пример 12.8. Дело несколько усложняется, если речь идет о методе близнецов для порядка, больщего, чем 0. На рис. 12.8 показано применение метода близнецов с числами Фибоначчи для динамической памяти размером 55 с блоками размеров Si, «2. - ,«8 = 2, 3, 5, 8, 13, 21, 34 и 55. Например, блок размером 3,- начинающийся с позиции 26, является близнецом блока размером 5, начинающегося с позиции 21; вместе они составляют блок размером 8, который начинается с позиции 21 и является близнецом блока размером 5, начинающегося с позиции 29. Вместе они составляют блок размером 13, начинающийся с позиции 21, и т.д. □

О 3 5 8 1113 1618 21 242629 32 34 37 39 42 45 47 50 52 55

Рис. 12.8. Разделение динамической памяти в соответствии с методом близнецов с числами Фибоначчи

Выделение блоков

ЕСЛИ требуется блок размером л, мы выбираем любой из блоков, имеющихся в списке блоков свободного пространства размера s,-, где s,- > я, и либо / = 1, либо S( 1 < я; т.е. выбирается "самый подходящий" блок. При использовании метода близнецов ft-ro порядка, если отсутствуют свободные блоки размером s,, можем принять рещение расщепить блок размером или s,+t+i, поскольку один из результирующих блоков будет в любом случае иметь размер s,. Если нет блоков ни одного и из этих размеров, можно создать требуемый блок, применив рекурсивно описанную стратегию расщепления для размера s,+i.

Однако здесь кроется небольщая ловущка. При использовании метода близнецов -го порядка нельзя расщепить блоки размеров si, «2. - «*» поскольку в результате получится блок, размер которого окажется меньще, чем S]. Если у нас в распоряжении нет блока меньщего размера, придется использовать целый блок, не прибегая к его расщеплению. Эта проблема не возникает, если fe = О, т.е. в случае экспоненциального метода близнецов. Рещение этой проблемы можно упростить при использовании метода близнецов с числами Фибоначчи, если начать с &х = 1, но такой вариант может оказаться неприемлемым, поскольку блоки единичного размера (например, величиной в один байт или мащинное слово) могут оказаться слищком малы для размещения в них указателя и бита заполнения.



Возврат блоков в свободное пространство

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

Применение экспоненциального метода близнецов чрезвычайно облегчает задачу обнарркения близнецов. Если мы только что вернули блок размером 2, начинающийся с позиции р2, его "близнец" находится по адресу {р+1)2, если р является четным числом, и по адресу (р-1)2, ес.пи р является нечетным.

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

1. Бит заполнения, как и в любом блоке.

2. Указатель размера, который представляет собой целое число i, указывающее на то, что соответствуюший блок имеет размер s,.

3. Счетчик левых близнецов, описанный ниже.

В кавдой паре близнецов один (левый) находится слева от другого (правого). На интуитивном уровне счетчик левых близнецов блока указывает на то, сколько раз подряд он является левым близнецом или частью левого близнеца. На формальном уровне вся динамическая память, рассматриваемая как блок размером s„, имеет счетчик левых близнецов, равный 0. Когда мы делим какой-либо блок размером s,>i со счетчиком левых близнецов ft на блоки размером и s,-t, которые являются левым и правым близнецами соответственно, у левого близнеца значение счетчика левых близнецов будет равно Ь + 1, в то время как у правого счетчик левых близнецов будет равен О и не зависеть, таким образом, от Ь. Например, на рис. 12.8 у блока размером 3, начинающегося с позиции О, счетчик левых близнецов равен 6, а у блока размером 3, начинающегося с позиции 13, счетчик левых близнецов равен 2.

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

Эта информация используется следуюшим образом. Пусть используется метод близнецов порядка к. Любой блок, начинающийся с позиции р со счетчиком левых близнецов, равным О, является правым близнецом. Таким образом, если его указатель размера равен /, его левый близнец имеет размер Sji и начинается с позиции р - Sji. Если счетчик левых близнецов оказывается больше О, значит, данный блок является левым близнецом блока размером Sy-t, который начинается с позициир + Sj.

Если объединим левого близнеца размером Sj, имеюшего счетчик левых близнецов, равный Ъ, с правым близнецом размером s-, результирующий блок будет иметь указатель размером i + 1, начинаться с той же позиции, что и блок размера St, и иметь счетчик левых близнецов, равный 6-1. Таким образом, когда объединяются два пустых близнеца, изменение слркебной информации не вызывает затруднений.

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





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