Планирование в интерактивных системах

Мониторы.

Семафору необходим аккуратность. Маленькая ошибка может привести к остановке процесса. Например: две процедуры down в программе производит смену местами, т.е. mutex было уменьшено, раньше чем empty.

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

Принцип работы монитора может быть описан следующим образом:

1) Процесс, обращающийся к монитору за получением некоторого ресурса, обнаруживает, что ресурс занят. При этом процедура монитора выдает команду «ждать»(wait), по которой процесс будет ждать вне монитора, пока ресурс освободится.

2) Когда ресурс освобождается, то монитор выдаст команду «сигнал»(signal). Если очередь ждущих процессов не пуста, то по этой команде один из процессов может воспользоваться ресурсом монитора. Обычно очередь организуется по принципу «первый пришел – первый получил доступ к ресурсу».

Планирование в системах пакетной обработки:

1. Первым пришел – первым обслужен (FIFO First In Fist Out)

Процессы становятся в очередь по мере поступления.

Преимущества: простота, справедливость.

Недостатки: Процесс, ограниченный возможностями процессора может затормозить более быстрые процессы, ограниченные устройствами ввода/вывода.

2. Кратчайшая задача – первая.

Нижняя очередь выстроена с учетом этого алгоритма

Преимущества: Уменьшение оборотного времени, справедливость.

Недостатки: Длинный процесс, занявший процессор, не пустит более новые процессы, которые пришли позже.

3. Наименьшее оставшееся время выполнения:

Аналог предыдущего, но если происходит новый процесс, его полное время выполнения сравнивается с оставшимся временем выполнения текущего процесса.

4. Трехуровневое планирование

Планировщик доступа выбирает задачи оптимальным образом. Если процессов в памяти слишком много, планировщик памяти выгружает и загружает некоторые процессы на диск. Количество процессов находящихся в памяти, называется степенью многозадачности.

1. Циклическое планирование

Самый простой алгоритм планирования и часто используемый.

Каждому процессу предоставляется квант времени процессора. Когда квант заканчивается процесс переводится планировщиком в конец очереди. При блокировке процессор выпадает из очереди.

Преимущества: простота, справедливость(каждому по чуть- чуть).

Недостатки: Если частые переключения (квант – 4 мс, а время переключения равно 1мс), то происходит уменьшение производительности. Если редкие переключения (квант – 100мс, а время переключения равно 1мс), то происходит увеличение времени ответа на запрос.

2. Приоритетное планирование.

Каждому процессу присваивается приоритет, и управление передается процессу с самым высоким приоритетом.

Приоритет может быть динамический или статический.

Динамический приоритет может устанавливаться так:

П=1/Т, где Т – часть использованного в последний раз кванта. Если использовано 1/50 часть кванта, то приоритет 50, если использован весь квант, то приоритет 1.

Т.е. процессы, ограниченные вводом/вывода, будут иметь приоритет над процессами ограниченными процессором.

Часто процессы объединяют по приоритетам в группы, и используют приоритетное планирование среди групп, но внутри группы используют циклическое планирование.

Дата добавления: 2014-01-20