Структуры данных и алгоритмы (1021739), страница 96
Текст из файла (страница 96)
Если выбирается блок со счетчиком си из этого блока требуется d < с байт памяти, то используются последние d байт. Втаком случае понадобится только заменить счетчик с на с - d, а оставшийся пустойблок может, как и ранее, оставаться в списке свободного пространства.1Пример 12.6. Допустим, требуется 400 байт для переменной W в ситуации,представленной на рис. 12.6.
Можно было бы принять решение изъять 400 байт из600 в первом блоке списка свободного пространства. Ситуация в таком случае соответствовала бы рис. 12.7. D1Если значение с - d столь мало, что счетчик и указатель заполнения не умещаются в оставшееся свободное пространство, то, очевидно, надо использовать весь этот блок и убрать егоиз списка блоков свободного пространства.12.4.
ВЫДЕЛЕНИЕ ПАМЯТИ ДЛЯ ОБЪЕКТОВ РАЗНОГО РАЗМЕРА357avail4,s500 0200 1i|XзначешXфX*1000 0 i i1>s,sXXюоюо200 0 »400 1§WЯ^isl•1111>sX0 *юошо1 гРис. 12.7. Конфигурация памятиПроблема выбора блока для размещения в нем новых данных не так уж проста,как может показаться, поскольку такие стратегии характеризуются противоречивыми целями.
С одной стороны, мы хотим быстро выбрать пустой блок для размещенияв нем новых данных, а с другой — хотим выбрать этот пустой блок таким образом,чтобы минимизировать фрагментацию. Две стратегии, которые представляют реализацию противоположных требований, называются "первый подходящий" (first-fit) и"самый подходящий" (best-fit). Описание этих стратегий приведено ниже.1.Первый подходящий. В соответствии с этой стратегией, если требуется блок размера d, нужно просматривать список блоков свободного пространства с самогоначала и до тех пор, пока не встретится блок размера с > d.
Затем нужно использовать последние d байт (или слов) этого блока, как было описано выше.2.Самый подходящий. В соответствии с этой стратегией, если требуется блок размераd, нужно проанализировать весь список блоков свободного пространства и найтиблок размера не менее d, причем размер этого блока должен как можно меньшепревышать величину d. Затем нужно использовать последние d байт этого блока.По поводу этих стратегий можно высказать ряд соображений. Стратегия "самыйподходящий" работает значительно медленнее, чем стратегия "первый подходящий",поскольку при использовании последней можно рассчитывать на достаточно быстрое (в среднем) нахождение подходящего блока, в то время как при использованиистратегии "самый подходящий" необходимо просмотреть весь список блоков свободного пространства.
Стратегию "самый подходящий" можно несколько ускорить, еслисоздать несколько списков блоков свободного пространства в соответствии с размерами этих блоков. Например, можно было бы иметь списки блоков размером от 1 до 16байт,1 от 17 до 32 байт, от 33 до 64 байт и т.д. Это "усовершенствование" не оказывает заметного влияния на быстродействии стратегии "первый подходящий", болеетого, оно может даже замедлить ее работу, если распределения размеров и размещения блоков неблагоприятны.2 В свете последнего замечания мы можем определитьнекий спектр стратегий между "первым подходящим" и "самым подходящим", отыскивая "самый подходящий" среди первых k свободных блоков при некотором фиксированном значении k.1Вообще говоря, существует понятие минимального размера блока (этот размер, очевидно,больше 1), поскольку блоки, если они входят в состав свободного пространства, должны содержатьуказатель на следующий блок, счетчик и бит заполнения.2Например, подходящий блок находится в начале общего списка свободных блоков, но вконце нужного списка блоков, разбитых по размерам.
— Прим. ред.358ГЛАВА 12. УПРАВЛЕНИЕ ПАМЯТЬЮСтратегия "самый подходящий", по-видимому, способствует уменьшению фрагментации в сравнении со стратегией "первый подходящий" — в том смысле, что встратегии "самый подходящий" просматривается тенденция к созданию чрезвычайномалых "фрагментов", т.е. остатков блоков. В то время как количество этих фрагментов примерно такое же, как и в случае стратегии "первый подходящий", они занимают, как правило, довольно небольшой объем. Однако стратегия "самый подходящий" не обнаруживает тенденции к созданию "фрагментов среднего размера".
Напротив, свободные блоки оказываются либо очень малыми фрагментами, либобольшими блоками. Поэтому возможны такие последовательности запросов, которыеспособна удовлетворить стратегия "первый подходящий" и не способна удовлетворить стратегия "самый подходящий", и наоборот.Пример 12.7. Допустим, в соответствии с рис. 12.6, список свободного пространства состоит из блоков размерами 600, 500, 1 000 и 700 байт (в указанной последовательности). Если используется стратегия "первый подходящий" и сделан запрос наблок размером 400, то получим этот блок из блока размером 600, который оказалсяпервым в списке и способен вместить блок заданного размера. Теперь, после выделения блока в 400 байт под данные, список свободного пространства состоит из блоковразмерами 200, 500, 1 000 и 700 байт.
В этой ситуации мы не в состоянии удовлетворить тотчас же три запроса на блоки размером 600 (хотя это было бы возможнымпосле объединения смежных пустых блоков и/или перемещения использованныхблоков в динамической памяти).Если используется стратегия "самый подходящий" применительно к списку свободных блоков размера 600, 500, 1 000 и 700 байт и в систему поступил запрос наблок размером 400, то в соответствии с этой стратегией выбирается самый подходящий для такого запроса блок размером 500 байт, а список блоков свободного пространства принимает вид 600, 100, 1 000 и 700 байт. В этом случае можно было быудовлетворить три запроса на блоки размером 600, не прибегая к какой-либо реорганизации памяти.С другой стороны, бывают ситуации (взять хотя бы наш список 600, 500, 1 000 и700 байт), когда стратегия "самый подходящий" не оправдывает себя, в то время какстратегия "первый подходящий" позволяет получить требуемый результат, не прибегая к реорганизации памяти.
Допустим, в систему поступил запрос на блок размером400 байт. Стратегия "самый подходящий", как и раньше, оставит список блоковразмера 600, 100, 1 000 и 700 байт, тогда как стратегия "первый подходящий" оставит список блоков размера 200, 500, 1 000 и 700 байт. Допустим, что после этого всистему поступил запрос на блоки размером 1 000 и 700 байт; любая из стратегийвыделила бы полностью два последних пустых блока, оставив в случае стратегии"самый подходящий" свободными блоки размером 600 и 100 байт, а в случае стратегии "первый подходящий" — блоки размером 200 и 500 байт.
После этого стратегия"первый подходящий" может удовлетворить запросы на блоки размером 200 и 500байт, в то время как стратегия "самый подходящий" — нет. Пг12.5. Методы близнецовРазработано целое семейство стратегий управления динамической памятью, котороепозволяет частично решить проблему фрагментации и неудачного распределения размеров пустых блоков. Эти стратегии, называемые методами близнецов (buddy systems),на практике затрачивают очень мало времени на объединение смежных пустых блоков.Недостаток метода близнецов заключается в том, что блоки имеют весьма ограниченный набор размеров, поэтому, возможно, придется нерационально расходовать память,помещая элемент данных в блок большего размера, чем требуется.Главная идея, лежащая в основе всех методов близнецов, заключается в том, чтовсе блоки имеют лишь строго определенные размеры Si < $2 < s3 < — < st.
Характерными вариантами последовательности чисел 8Ь s2, ... являются числа 1, 2, 4, 8, ...(метод близнецов экспоненциального типа) и 1, 2, 3, 5, 8, 13, ... (метод близнецов с12.5. МЕТОДЫ БЛИЗНЕЦОВ359числами Фибоначчи, где st+1 = st + st-i). Все пустые блоки размера s( связаны в список; кроме того, существует массив заголовков списков свободных блоков, по одномудля каждого допустимого размера s,-.1 Если для нового элемента данных требуетсяблок размером d, то выбирается свободный блок такого размера s,-, чтобы st > d, однако Sj-i < d, т.е.
наименьший допустимый размер, в который умещается новый элемент данных.Трудности возникают в том случае, когда не оказывается пустых блоков требуемого размера s(. В этом случае находится блок размером sj+1 и расщепляется надва блока, один размером s,:, а другой — sj+1 - s f . 2 Метод близнецов налагает ограничение: величина si+i - s( должна равняться некоторому числу st из используемойпоследовательности, j < i. Теперь становится очевидным способ ограничения выбора значений для St. Если допустить, что j — i - k для некоторого k > 0, тогда, поскольку s j+ i - Sj = Sj_t, следует, что*m = «I + «I-* •(12Л)Уравнение (12.1) применимо, когда i > k, и вместе со значениями s l f s2, ... st полностью определяет значения st+i, st+2, ...
. Если, например, k = 0, уравнение (12.1)принимает видs,+i = 2s,.(12.2)Если в (12.2) начальное значение «! = 1, то получаем экспоненциальную последовательность 1, 2, 4, 8Конечно, с какого бы значения si мы ни начали, s, в (12.2)возрастают экспоненциально. Еще один пример: если k = 1, зг = 1 и s2 = 2, уравнение (12.1) принимает видVi = s, + «(-I(12-3)Уравнение (12.3) определяет последовательность чисел Фибоначчи: 1, 2, 3, 5,8, 13, ....Какое бы значение k в уравнении (12.1) мы ни выбрали, получим метод близнецов k-ro порядка. Для любого k последовательность допустимых размеров возрастаетпо экспоненциальному закону, т.е.
отношение si+i/st близко некоторой' константе,большей единицы. Например, для k = 0 отношение sj+i/Si равно точно 2. Для k = 1коэффициент 8(+1/8( примерно равен "золотому сечению" ((-Уб +1)/2 = 1,618); этот коэффициент уменьшается при увеличении k, но никогда не достигает значения 1.Распределение блоковПри использовании метода близнецов fe-ro порядка можно считать, что каждыйблок размером si+i состоит из блока размером s; и блока размером s/_t.
Допустим дляопределенности, что блок размером sf находится слева (в позициях с меньшими значениями номеров) от блока размером Sj_ A . 3 Если динамическую память рассматриватькак единый блок размером sn (при некотором большом значении п), тогда позиции, скоторых могут начинаться блоки размером s f , будут полностью определены.Позиции в экспоненциальном (т.е.
0-го порядка) методе близнецов вычислитьдостаточно просто. Если предположить, что позиции в динамической памяти пронумерованы с О, тогда блок размером st начинается в любой позиции с числа, кратного1Поскольку в пустых блоках должны быть указатели на следующий блок (а также и другая информация), на самом деле последовательность допустимых размеров начинается не с 1, ас большегочисла в указанной последовательности, например с 8 байт.2Разумеется, если в системе отсутствуют и пустые блоки размером si+i, то создается такойблок путем расщепления блока размером s;+2, и т.д. Если в системе вообще отсутствуют блокиболее крупного размера, тогда, по сути, имеем дело с нехваткой памяти и необходимо реорганизоватьдинамическую память (о том, как это делается, рассказано в следующем разделе).3Заметим, что блоки размерами s, и s,--*, составляющие блок размером Sj+i, удобно представлять "близнецами" (или "двойниками") — именно отсюда и происходит термин '"методблизнецов".360ГЛАВА 12.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
