(что указывает на единственный свободный блок длимой 2™, начинающийся по адресу 0) и

AVAILFIkl = AVArLB[Jt] = LOC(AVAILIkl) для 0 < < m (14)

(что указывает на пустые списки свободных блоков размером 2* для всех к < т).

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

Алгоритм R {Выделение памяти в системе двойников). Этот алгоритм предназначен для поиска и выделения блока памяти размером 2* (или сообщения о невозможности такого выделения) с помощью описанной выше системы двойников.

R1. [Поиск блока.] Пусть j - наименьшее целое число в диапазоне к < j < т, для которого AVAILF [у] ф LOC (AVAIL [j]), т. е. для которого список свободных блоков размером 2 не пуст. Если такого j не существует, алгоритм завершается неудачей, поскольку нет ни одного блока достаточного размера для выделения запрошенного количества памяти.

R2. [Удаление из списка.] Установить LAVAILFCj], P<-LINKF(L), AVAILF[j]-f-P, LINKB(P) <- LOC(AVAIL[j]) и TAG(L) +- 0.

R.3. [Требуется разделение?] Если j = к, алгоритм завершается (найден и выделен свободный блок, начинающийся с адреса L).

R4. [Разделение.] Уменьшить j на 1. Затем установить ? <- L + 2, TAG(P) <- 1, KVAL(P) Ч- j, LINKF(P) <- LINKB(P) +- LOC(AVAIL[j]), AVAlLF[j] +-AVAlLBCj] <- P. (Тем самым разделяется большой блок памяти и неиспользуемая половина вносится в список AVAIL [j], который был пуст.) Вернуться к шагу R3. I

Алгоритм S [Освобождение памяти в системе двойников). Этот алгоритм предназначен для возврата блока размером 2*, начинающегося с адреса L, в область свободной памяти с использованием описанной выше системы двойников.

51. [Свободен ли двойник?] Установить Р +~ двoйник)t(L) (см. (10)). Если к = т или TAG(P) = О, либо если TAG(P) = 1 и KVAL(P) / к, перейти к шагу S3.

52. [Объединение двойников.] Установить

LINKF(LINKB(P)) LINKF(P), LINKB(LINKF(P)) LINKB(P).

(Таким образом блок Р удаляется из списка AVAIL [fc].) Затем установить к <-к + 1 и, если Р < L, установить L Р. Вернуться к шагу S1.

53. [Размещение в списке.] Установить TAG(L) 1, Р AVAILF[fc], LINKF(L) Р, LINKB(P) -f-L, KVAL(L) fc, LINKB(L) LOC (AVAIL [fc]), AVAILF [fc] L. (Таким образом блок L помещается в список AVAIL [fc].)

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

имеется одно интересное явление, которое легко проанализировать, а именно - правило "50%".

Если алгоритмы А и В непрерывно используются таким образом, что система стремится к равновесию, при котором в ней имеется в среднем N выделенных блоков, каждый из которых выделяется и освобождается независимо от других, а величина К в алгоритме А принимает ненулевое значение (или, более того, значения > с, как на шаге А4) с вероятностью р, то среднее количество свобсдных блоков стремится приблизительно к pN.

Это правило говорит о том, какой будет приблизительная длина списка AVAIL. Когда величина р близка к 1, что случается при очень Мс1лых с и если размеры блоков редко равны, количество свободных блоков составляет примерно половину от количества занятых; отсюда и происходит название правила "50%".

Данное правило нетрудно доказать. Рассмотрим следующую карту памяти:

А В С С В А В В В С В В На ней показаны выделенные блоки памяти трех категорий:

А: при освобождении блока количество свободных блоков уменьшается на единицу; В: при освобождении блока количество свободных блоков не изменяется; С: при освобождении блока количество свободных блоков увеличивается на единицу.

Теперь пусть TV - число выделенных, а М - число свободных блоков. Пусть А, В и С - количество блоков описанных выше типов. Имеем

N = A + B-,C;

M=i(2A + S + e),

где е = О, 1 или 2 в зависимости от условий на нижней и верхней границах.

Предположим, что TV представляет, по существу, константу, а А, В, С и е - случайные величины, которые достигают стационарного распределения после освобождения блока и несколько отличающегося стационарного распределения после выделения блока. Среднее изменение величины М при освобождении блока равно среднему значению (C - A)/N; среднее изменение величины М при выделении блока равно 1 - р. Таким образом, с учетом достижения состояния равновесия получаем, что С - А - N + pN = 0. Однако тогда среднее значение величины 2М равно pTV плюс среднее значение е, поскольку 2TW = N + А - С + t согласно (15). Отсюда следует правило "50%".

Наши предположения о том, что каждое удаление применяется к случайному выделенному блоку, будет справедливо, если время жизни блока представляет собой экспоненциально распределенную случайную величину. С другой стороны, если все блоки имеют примерно одно и то же время жизни, сделанное предположение ложно. Джон Э. Шор (John Е. Shore) указал, что блоки типа А обычно "старее" блоков типа С, если характер процесса выделения и освобождения близок к очереди ("первым вошел - первым вышел"; FIFO), поскольку последовательность смежных блоков при этом стремится выстроиться в порядке от "младших" блоков к "старшим" и последний выделенный блок почти никогда не оказывается блоком типа А. Такая

тенденция приводит к наухичию меньшего числа доступных блоков, давая даже лучшую производительность по сравнению с производительностью, предсказываемой по правилу "50%" [см. СЦСМ 20 (1977), 812-820].

Более детально правило "50%" рассматривается в работах D. J. М. Davies, BIT 20 (1980), 279-288; С. М. Reeves, Сотр. J. 26 (1983), 25-35; G. Ch. Pflug, Сотр. J. 27 (1984), 328-333.

Если не учитывать это интересное правило, наши знания о производительности алгоритмов динамического распределения памяти почти полностью базируются на экспериментах по методу Монте-Карло. При выборе алгоритма выделения памяти для конкретных машины и класса приложения (или конкретного приложения) поучительно провести собственные моделирующие динамическое распределение памяти эксперименты. Автор провел ряд таких экспериментов непосредственно перед написанием этого раздела (и правило "50%" было замечено во время этих экспериментов до того, как было найдено его доказательство). Рассмотрим здесь вкратце методы и результаты проведенных экспериментов.

Основная моделирующая программа работает следующим образом. В начальный момент работы программы, когда эначение TIME равно нулю, доступна вся память.

Р1. Увеличить TIME на 1.

Р2. Освободить все блоки в системе, которые должны быть освобождены при текущем значении TIME.

РЗ. Вычислить две величины, 5 (случайный размер) и Т (случайное время жизни), основанные на некотором распределении вероятностей, с помощью методов из главы 3.

Р4. Выделить новый блок длиной S, который необходимо освободить в момент (TIME + Г). Вернуться к шагу Р1.

Каждый раз по достижении переменной TIME значения, кратного 200, выводились детальные статистические данные о производительности алгоритмов выделения и освобождения. Для каждой пары алгоритмов использовалась одна и та же последовательность значений 5 и Т. После того как величина TIME превышала 2000, система обычно приходила в более или менее стабильное состояние с неизменными показателями. Однако иногда на шаге РЗ алгоритм прекращал свою работу из-за невозможности выделить необходимый объем памяти.

Пусть С - общее количество доступных ячеек памяти и пусть S и Т - средние величины 5 и Т на шаге РЗ. Легко видеть, что ожидаемое количество занятых слов памяти в каждый момент составляет ST при достаточно большом значении TIME. Когда в экспериментах ST было больше, чем С, обычно происходило переполнение памяти (часто прежде, чем в действительности происходил запрос на выделение С слов памяти). Память можно было заполнить на 90% при малом по сравнению с С размере блока, но когда размеры блока могли превысить С (вместе с блоками меньших размеров), наблюдалась тенденция программы к "заполнению" памяти при реальном использовании менее С ячеек памяти. Эмпирические результаты свидетельствуют о том, что для эффективной работы систем динамического распределения памяти не должны использоваться блоки размером свыше yqC