Структуры данных и алгоритмы (1021739), страница 97
Текст из файла (страница 97)
УПРАВЛЕНИЕ ПАМЯТЬЮ2', т.е. О, 2'Более того, каждый блок размером 2|+1, начинающийся, скажем, сj2'+l, состоит из двух "близнецов" размером 2', которые начинают с позиций (2у')2*,т.е. j2'+l, и (2j + 1)2'. Таким образом, не составляет особого труда найти "близнеца"блока размером 2'. Если он начинается с какого-либо четного числа, кратного 2', например (2/)2'( его "близнец" находится справа в позиции (2j + 1)2'. Если же он начинается с какого-либо нечетного числа, умноженного на 2', например (2у + 1)2', его"близнец" находится слева на позиции (2/')2'.Пример 12.8.
Дело несколько усложняется, если речь идет о методе близнецов дляпорядка, большего, чем 0. На рис. 12.8 показано применение метода близнецов с числами Фибоначчи для динамической памяти размером 55 с блоками размеровs b s2, ... , s8 = 2, 3, 5, 8, 13, 21, 34 и 55. Например, блок размером 3,. начинающийся спозиции 26, является близнецом блока размером 5, начинающегося с позиции 21; вместе они составляют блок размером 8, который начинается с позиции 21 и являетсяблизнецом блока размером 5, начинающегося с позиции 29.
Вместе они составляютблок размером 13, начинающийся с позиции 21, и т.д. ПО3 581113 161821 2 4 2 6 2 9 3 2 3 4 3 7 3 9 4 2 4 5 4 7 5 0 5 2 5 5 .Рис. 12.8. Разделение динамической памяти в соответствии с методомблизнецов с числами ФибоначчиВыделение блоков• . , . , ...'-..ЕСЛИ требуется блок размером п, мы выбираем любой из блоков, имеющихся всписке блоков свободного пространства размера s,-, где S; > п, и либо i = 1, либо s/_! < п; т.е. выбирается "самый подходящий" блок. При использовании метода близнецов ft-ro порядка, если отсутствуют свободные блоки размером s,-, можем принятьрешение расщепить блок размером s(+i или я<+*+1> поскольку один из результирующих блоков будет в любом случае иметь размер s f .
Если нет блоков ни одного и изэтих размеров, можно создать требуемый блок, применив рекурсивно описаннуюстратегию расщепления для размера «,Ч1.Однако здесь кроется небольшая ловушка. При использовании метода близнецовАг-го порядка нельзя расщепить блоки размеров «i, «2. — 8ь поскольку в результатеполучится блок, размер которого окажется меньше, чем «i- Если у нас в распоряжении нет блока меньшего размера, придется использовать целый блок, не прибегая кего расщеплению. Эта проблема не возникает, если k = О, т.е. в случае экспоненциального метода близнецов.
Решение этой проблемы можно упростить при использовании метода близнецов с числами Фибоначчи, если начать с s t = 1, но такой вариант может оказаться неприемлемым, поскольку блоки единичного размера(например, величиной в один байт или машинное слово) могут оказаться слишкоммалы для размещения в них указателя и бита заполнения.12.5. МЕТОДЫ БЛИЗНЕЦОВ361Возврат блоков в свободное пространствоКогда блок становится доступным для повторного использования, проявляетсяодно из преимуществ метода близнецов. Иногда удается сократить фрагментацию,объединяя вновь образовавшийся свободный блок с его "близнецом", если этот"близнец" также свободен.1 В сущности, если это действительно окажется так, результирующий блок можно попытаться объединить с его "близнецом" — если этот"близнец" также свободен, и т.д. Такое объединение с пустыми "близнецами" занимает строго фиксированное время и потому является привлекательной альтернативойпериодическим слияниям смежных пустых блоков, о которых шла речь в .предыдущем разделе (для выполнения такого слияния требуется время, пропорциональноеколичеству пустых блоков).Применение экспоненциального метода близнецов чрезвычайно облегчает задачуобнаружения близнецов.
Если мы только1 что вернули блок размером 2', начинающийся с позиции р21, его "близнец" находится по адресу (р+1)2(, если р являетсячетным числом, и по адресу (р-1)2', еслир является нечетным.При использовании метода близнецов порядка k> 1 поиск близнецов несколько усложняется. Чтобы облегчить его, мы должны хранить в каждом блоке дополнительнуюинформацию.'1. Бит заполнения, как и в любом блоке.2. Указатель размера, который представляет собой целое число i, указывающее нато, что соответствующий блок имеет размер st.3.
Счетчик левых близнецов, описанный ниже.В каждой паре близнецов один (левый) находится слева от другого (правого). На интуитивном уровне счетчик левых близнецов блока указывает на то, сколько раз подрядон является левым близнецом или частью левого близнеца. На формальном уровне всядинамическая память, рассматриваемая как блок размером sn, имеет счетчик левыхблизнецов, равный 0. Когда мы делим какой-либо блок размером si+i со счетчиком левых близнецов -Ь на блоки размером st и Sj-t, которые являются левым и правым близнецами соответственно, у левого близнеца значение счетчика левых близнецов будетравно Ь + 1, в то время как у правого счетчик левых близнецов будет равен О и не зависеть, таким образом, от Ь.
Например, на рис. 12.8 у блока размером 3, начинающегося с позиции О, счетчик левых близнецов равен 6, а у блока размером 3, начинающегося с позиции 13, счетчик левых близнецов равен 2.Помимо указанной выше информации, пустые блоки (но не используемые блоки)содержат указатели вперед и назад для организации списка свободных блоков соответствующего размера.
Эти двунаправленные указатели существенно облегчают объединение близнецов, так как в результате объединения требуется удалить из соответствующих списков объединившиеся блоки.Эта информация используется следующим образом. Пусть используется метод близнецов порядка k. Любой блок, начинающийся с позиции р со счетчиком левых близнецов, равным О, является правым близнецом. Таким образом, если его указатель размера равен j, его левый близнец имеет размер Sy+t и начинается с позиции р - si+t. Еслисчетчик левых близнецов оказывается больше 0, значит, данный блок является левым близнецом блока размером Sy_t, который начинается с позиции р + Sj.Если объединим левого близнеца размером Sj, имеющего счетчик левых близнецов, равный Ъ, с правым близнецом размером s,-_j, результирующий блок будет иметьуказатель размером i + 1, начинаться с той же позиции, что и блок размера St, ииметь счетчик левых близнецов, равный 6 - 1 .
Таким образом, когда объединяютсядва пустых близнеца, изменение служебной информации не вызывает затруднений.1Как и в предыдущем разделе, мы должны предположить, что один бит каждого блока зарезервирован в качестве индикатора заполнения, указывающего, является ли соответствующийблок пустым или используется для хранения данных.362ГЛАВА 12. УПРАВЛЕНИЕ ПАМЯТЬЮПредлагаем читателю самостоятельно рассмотреть ситуацию, когда расщепляетсяпустой блок размером s,-+i на используемый для хранения данных блок размером st ипустой блок размером s(_t.Если эта информация будет поддерживаться при реорганизации блоков и спискисвободных блоков будут связаны в обоих направлениях, то потребуется лишь фиксированное время на каждое расщепление блока на близнецов или объединение близнецов в более крупный блок.
Поскольку количество объединений не может превосходить количество расщеплений, общий объем работы будет пропорционален количеству расщеплений. Нетрудно убедиться в том, что большинство запросов на выделениеблока вообще не требуют расщеплений, поскольку блок нужного размера уже имеется в наличии. Однако бывают нестандартные ситуации, когда каждая операция выделения требует нескольких расщеплений. Примером такой "нештатной" (которуюможно даже назвать экстремальной) ситуации являются многократно повторяющиеся запросы на получение блока минимального размера с последующим его возвращением. В этой ситуации, если в системе динамической памяти имеются блоки п различных размеров, то при использовании метода близнецов А-го порядка потребуетсяпо крайней мере n/k расщеплений, а затем еще n/k объединений при возврате блока.12.6.
Уплотнение памяти•Бывают случаи, когда даже после объединения всех смежных пустых блоков система не в состоянии выполнить запрос на выделение нового блока. Бывает, конечно,что во всей динамической памяти просто не хватает свободного пространства для выделения блока требуемого размера. Однако более типичной является ситуация, подобная той, которая показана на рис. 12.5, когда, несмотря на наличие 2 200 байтсвободной памяти, мы не в состоянии выполнить запрос на выделение блока размером более 1 000 байт.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
