15.1. Фиксированное распределение

Память разделяется на области с фиксированными границами.

Разделы одинакового размера. Любой процесс, размер которого не превышает размера раздела, может быть загружен в любой доступный раздел. Если все разделы заняты и нет ни одного процесса в состоянии готовности или работы, ОС может выгрузить процесс из любого раздела и загрузить в него другой процесс, обеспечивая процессор работой. Принятие решения, какой процесс выгрузить – задача планировщика. Недостаток: неэффективное использование ОП, т.к. маленькая программа занимает целиком большой раздел. Это явление называется внутренней фрагментацией.

Разделы разного размера. Этот способ не устраняет полностью недостаток, указанный выше, но уменьшает его. При назначении раздела процессу существует два подхода: 1) Каждый процесс разместить в наименьшем разделе, способном полностью вместить данный процесс. Это минимизирует внутреннюю фрагментацию. Для каждого раздела требуется своя очередь планировщика. 2) Каждый процесс размещается в наименьшем доступном разделе, способном полностью вместить данный процесс. Используется одна очередь планировщика.

Недостатки метода фиксированного распределения:

• Количество разделов, определенное в момент генерации системы, ограничивает количество активных процессов.

• Так как размеры разделов устанавливаются заранее, то это приводит к неэффективному использованию памяти.

15.2. Динамическое распределение

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

Используется три основных алгоритма размещения процесса в памяти:

Наилучший подходящий. Выбирается блок, размер которого наиболее близок к требуемому.

Первый подходящий. Проверяются все свободные блоки с начала ОП и выбирается первый достаточный по размеру.

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

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

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

ОП распределяется блоками размером 2k, L  k  U,

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

2U – максимальный распределяемый блок, это размер всей памяти, доступной для распределения.

Вначале все доступное для распределения пространство рассматривается как единый блок размера 2U. При запросе блока размера s, где 2U-1  s  2U, выделяется весь блок. В противном случае блок разделяется на два блока-двойника с размерами 2U-1. Если 2U-2  s 2U-1, то по запросу выделяется один из двух двойников, в противном случае один из двух двойников вновь делится пополам. Этот процесс продолжается до тех пор, пока не будет сгенерирован наименьший блок, размер которого не меньше s.

Система постоянно ведет список "дыр" (доступных блоков) для каждого размера 2i. Дыра может быть удалена из списка (i+1) разделением ее пополам и внесением двух новых "дыр" размера 2i в список i. Когда пара двойников в списке i оказывается освобожденной, они удаляются из списка и объединяются в единый блок в списке (i+1).

Модифицированная версия системы двойников используется для распределения памяти ядром ОС Linux.