Система двойников

Как фиксированное, так и динамическое распределение памяти имеют свои недостатки. Фиксированное распределение ограничивает количество активных процессов и неэффективно использует память при несоответствии между размерами разделов и процессов. Динамическое распределение реализуется более сложно и включает накладные расходы по уплотнению памяти. Интересным компромиссом в этом плане является система двойников ([KNUT97], [РЕТЕ77]).

В системе двойников память распределяется блоками размером 2^k, L<K<U,

где

2^L — минимальный размер выделяемого блока памяти;

2^U— наибольший распределяемый блок; вообще говоря, 2^Uпредставляет собой размер всей доступной для распределения памяти.

Вначале все доступное для распределения пространство рассматривается как единый блок размера 2^U. При запросе размером s, таким, что 2^U-1 < s <=2^U, выделяется весь блок. В противном случае блок разделяется на два эквивалентных двойника с размерами 2^U-1, Если 2^{U - 2} < s < 2^U, то по запросу выделяется один из двух двойников; в противном случае один из двойников вновь делится пополам. Этот процесс продолжается до тех пор, пока не будет сгенерирован наименьший блок, размер которого не меньше s. Система двойников постоянно ведет список "дыр" (доступных блоков) для каждого размера 2ⁱ. Дыра может быть удалена из списка (i+1) разделением ее пополам и внесением двух новых дыр размера 2ⁱ в список i. Когда пара двойников в списке i оказывается освобожденной, они удаляются из списка и объединяются в единый блок в списке (i+1). Ниже приведен рекурсивный алгоритм ([LIST93]) для удовлетворения запроса размера 2^i-1<k<=2ⁱ, в котором осуществляется поиск дыры размером 2ⁱ.

void get_hole(int i)
{

if (i == (U+1)

< Ошибка >;

if (< Список i пуст >)

{

get_hole(i+l);

< Разделить дыру на двойники >;

< Поместить двойники в список i >;
}

< Взятьпервую дыру из списка i >;

}

На рис. 7.6 приведен пример использования блока с начальным разме­ром 1 Мбайт. Первый запрос А — на 100 Кбайт (для него требуется блок размером 128 Кбайт). Для этого начальный блок делится на два двойника по 512 Кбайт. Первый из них делится на двойники размером 256 Кбайт, и, в свою очередь, первый из получившихся при этом разделении двойников также делится пополам. Один из получившихся двойников размером 128 Кбайт выделяется запросу А. Следующий запрос В требует 256 Кбайт. Такой блок имеется в наличии и выделяется. Процесс продолжается с разделением и слиянием двойников при необходимости. Обратите внимание, что после освобождения блока Е происходит слияние двойников по 128 Кбайт в один блок размером 256 Кбайт, который, в свою очередь, тут же сливается со своим двойником.

На рис. 7.7 показано представление системы двойников в виде бинарного дерева, непосредственно после освобождения блока В. Листья представляют текущее распределение памяти. Если два двойника являются листьями, то по крайней мере один из них занят; в противном случае они должны слиться в блок большего размера.

Система двойников представляет собой разумный компромисс для преодоления недостатков схем фиксированного и динамического распределения, но в современных операционных системах ее превосходит виртуальная память, основанная на страничной организации и сегментации. Однако система двойников нашла применение в параллельных системах как эффективное средство распределения и освобождения параллельных программ (см., например, [JOHN92]). Модифицированная версия системы двойников используется для распределения памяти ядром UNIX (подробнее об этом вы узнаете в главе 8, "Виртуальная память").