Распределение разделами с подвижными границами

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

Планировщик памяти входит в состав ядра ОС. Он создаёт и поддерживает в своей собственной памяти список свободных областей. Элементы такого списка состоят из двух полей. В первом поле хранится значение начального адреса свободной области памяти, а во втором значение размера этой области. Просматривая список, планировщик определяет свободную область памяти, подходящую по размеру для очередной загружаемой задачи, после чего производится непосредственная загрузка кода задачи в память. После каждой загрузки планировщик модифицирует (корректирует) вышеуказанный список. Просмотр списка с целью определения подходящей свободной области памяти может осуществляться двумя способами - “первый подходящий” или “наиболее подходящий”. Первый способ предполагает поиск любой свободной области памяти, размер которой не меньше размера кода загружаемой задачи. Второй способ предполагает поиск сбодной области памяти, размер которой наиболее близок размеру кода загружаемой задачи и при этом не меньше, чем размер этого кода. При первом способе требуется просматривать, в среднем, половину списка, а при втором - весь список. Кроме того, планировщик реализует функцию освобождения памяти после выполнения очередной задачи, модифицируя список сбодных областей памяти.

При данной дисциплине распределения памяти уровень фрагментации и коэффициент мультипрограммирования могут значительно изменяться во времени, что иллюстрируется на рис.

kernel		kernel		kernel
Task1		Task1		Task1
Task2				Task5
Task3		Task3		Task3
Task4		Task4		Task4

                                                                                

T 1                                                        t 2                                                     t 3            

kernel		kernel		kernel
Task1		Task1		Task1
Task5		Task5		Task5
				Task6
Task4				Task7

                                                                                

T 4                                                  t 5                                                       t 6           

В момент t1 в памяти находятся коды четырёх задач. В момент t2 закончилось выполнение задачи task2 и планировщик освободил память, достаточную для загрузки задачи task5 (момент t3). В момент t4 закончилось выполнение задачи task3, планировщик освободил память, но размеры свободных областей недостаточны по размеру для загрузки задачи task6. Поэтому, очередная загрузка произойдёт только после выполнения task4 и соответствующего освобождения памяти (момент t5). При этом, размер свободной области памяти оказался достаточным для загрузки кодов сразу двух задач – task6 и task7 (момент t6).

Данная дисциплина распределения является средством локальной оптимизации, так как оптимизируется местоположение в памяти для конкретной задачи, но не распределение всей памяти в целом.

Распределение подвижными разделами

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

kernel		kernel		Kernel
Task1		Task1		Task1
Task5		Task5		Task5
		Task4		Task4
Task4				Task6

                                                                                

T 1                                                     t2                                                    t3

В момент t1 в памяти имеется две свободные области, но ни одна из них недостаточна по размеру, чтобы загрузить следующую задачу. Планировщик делает смещение кода задачи task4, образуя одну, большую по размеру, непрерывную свободную область памяти (момент t2). Поэтому появляется возможность загрузить следующую задачу task6 (момент t3).

Смещение в памяти кода задачи, которое выполняет планировщик, должно быть согласовано по времени с окончанием операции ввода/вывода для этой задачи (в данном случае – task4). Если такое согласование отсутствует, то результаты ввода/вывода могут записаться на “старое” место в памяти, и задача будет разрушена. С другой стороны, такое согласование противоречит принципам мультипрограммирования, в соответствии с которыми внешние устройства должны работать независимо и асинхронно относительно центрального процессора. Поэтому данная дисциплина распределения разделами не нашла практического применения.

13. Сегментная организация памяти.