Первым поступил – первым обслужен
Простейшая невытесняющая стратегия планирования. Процессам предоставляется доступ к процессору в том порядке, в котором они его запрашивают. Чаще всего формируется единая очередь ждущих процессов. Как только появляется первая задача, она немедленно запускается и работает столько, сколько необходимо. Остальные задачи ставятся в конец очереди.
Кратчайшая задача – первая
Также невытесняющий алгоритм, при котором планировщик выбирает первой самую короткую задачу. Необходимо знать время выполнения задач.
Наименьшее оставшееся время выполнения
Вытесняющая версия предыдущего алгоритма. Планировщик выбирает для выполнения процесс с наименьшим оставшимся временем выполнения. Когда поступает новая задача, ее полное время сравнивается с оставшимся временем выполнения текущей задачи. Если время выполнения новой задачи меньше, текущий процесс приостанавливается, и управление передается новой задаче. Эта схема позволяет быстро обслуживать короткие запросы.
Циклическое планирование
Каждому процессу предоставляется некоторый интервал времени процессора, так называемый квант времени. Если к концу кванта времени процесс все еще работает, он прерывается, а управление передается другому процессу. Слишком малый квант приводит к частому переключению процессов и небольшой эффективности, слишком большой квант может привести к медленному реагированию на короткие интерактивные запросы. Среднее значение кванта выбирается около 20-200 мс. В предельном случае, когда квант времени превышает продолжительность самого длинного процесса, круговое планирование вырождается в планирование FCFS.
Приоритетное планирование
Каждому процессу присваивается приоритет, и управление передается готовому к работе процессу с самым высоким приоритетом.
Вопросы для самоконтроля
1. В чем заключается отличие времени оборота от времени отклика?
2. В чем заключается отличие планирования с вытеснением от невытесняющего планирования?
3. Запуска ожидают пять задач. Предполагаемое время выполнения задач составляет 9, 6, 3, 5 и X. В каком порядке их следует запустить, чтобы минимизировать среднее время отклика? (Ответ должен зависеть от X.)
4. Обычно планировщики с циклическим алноритмом поддерживают список процессов, готовых к работе, причем каждый процесс находится в списке в единственном экземпляре. Что произойдет, если процесс окажется в списке дважды? Существует ли причина, по которой это изменение окажется полезным?
5. Можно ли определить путем анализа исходного кода принадлежность процесса к процессам, ограниченным возможностями процессора или устройств ввода-вывода? Как это можно определить во время выполнения программы?
Раздел 5. Управление памятью
Тема 15. Технологии распределения памяти
Оперативная память (ОП) – важный ресурс ЭВМ. В ранних ОС управление памятью сводилось к загрузке программы и ее данных из внешней памяти в ОП.
Функции мультипрограммной ОС по управлению памятью:
- отслеживание свободной и занятой памяти;
- выделение памяти процессам и освобождение памяти по завершении процессов;
- защита памяти;
- настройка адресов программ;
- выделение динамической памяти;
- перемещение программ между ОП и внешней памятью.
При выполнении последней функции существует две стратегии:
Свопинг, или простая подкачка. Программы целиком загружаются в ОП и целиком выгружаются на диск.
Программы частично загружаются в ОП и частично выгружаются на диск. Если это прозрачно для программиста, то такая стратегия называется виртуальной памятью, если не прозрачно – оверлеем.
Главная операция по управлению памятью – размещение программы в ОП для ее выполнения процессором. В современных ОС при этом используется сложная система, называемая виртуальной памятью, которая использует одну ли обе базовые технологии – сегменты и страницы. Но сначала познакомимся с более простыми технологиями.
Фиксированное распределение
Память разделяется на области с фиксированными границами.
Разделы одинакового размера. Любой процесс, размер которого не превышает размера раздела, может быть загружен в любой доступный раздел. Если все разделы заняты и нет ни одного процесса в состоянии готовности или работы, ОС может выгрузить процесс из любого раздела и загрузить в него другой процесс, обеспечивая процессор работой. Принятие решения, какой процесс выгрузить – задача планировщика. Недостаток: неэффективное использование ОП, т.к. маленькая программа занимает целиком большой раздел. Это явление называется внутренней фрагментацией.
Разделы разного размера. Этот способ не устраняет полностью недостаток, указанный выше, но уменьшает его. При назначении раздела процессу существует два подхода: 1) Каждый процесс разместить в наименьшем разделе, способном полностью вместить данный процесс. Это минимизирует внутреннюю фрагментацию. Для каждого раздела требуется своя очередь планировщика. 2) Каждый процесс размещается в наименьшем доступном разделе, способном полностью вместить данный процесс. Используется одна очередь планировщика.
Недостатки метода фиксированного распределения:
- Количество разделов, определенное в момент генерации системы, ограничивает количество активных процессов.
- Так как размеры разделов устанавливаются заранее, то это приводит к неэффективному использованию памяти.
Динамическое распределение
Образуется переменное количество разделов переменной длины. При размещении процесса в ОП для него выделяется строго необходимое количество ОП. Этому методу свойственна внешняя фрагментация, т.е. фрагментированной становится память, внешняя ко всем разделам. Для избавления от внешней фрагментации ОС производит уплотнение: время от времени ОС перемещает процессы в памяти так, чтобы они занимали смежные области ОП. Для выполнения уплотнения требуется дополнительное время и способность программ к динамическому перемещению.
Используется три основных алгоритма размещения процесса в памяти:
Наилучший подходящий. Выбирается блок, размер которого наиболее близок к требуемому.
Первый подходящий. Проверяются все свободные блоки с начала ОП и выбирается первый достаточный по размеру.
Следующий подходящий. Проверяются все свободные блоки, начиная с того места, где был выделен блок последний раз. Выбирается первый блок, достаточный по размеру.
Система двойников
Итак, фиксированное распределение ограничивает число активных процессов и неэффективно использует ОП при несоответствии размеров разделов и процессов. Динамическое распределение требует более сложной организации и больших накладных расходов на уплотнение памяти. Система двойников является компромиссом между этими двумя способами.
ОП распределяется блоками размером 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.