Планирование в системах пакетной обработки
4.2.1 "Первый пришел - первым обслужен" (FIFO - First In Fist Out)
Процессы ставятся в очередь по мере поступления.
Преимущества:
Простата
Справедливость (как в очереди покупателей, кто последний пришел, тот оказался в конце очереди)
Недостатки:
Процесс, ограниченный возможностями процессора может затормозить более быстрые процессы, ограниченные устройствами ввода/вывода.
4.2.2 "Кратчайшая задача - первая"
Нижняя очередь выстроена с учетом этого алгоритма
Преимущества:
Уменьшение оборотного времени
Справедливость (как в очереди покупателей, кто без сдачи проходит в перед)
Недостатки:
Длинный процесс занявший процессор, не пустит более новые краткие процессы, которые пришли позже.
Наименьшее оставшееся время выполнение
Аналог предыдущего, но если приходит новый процесс, его полное время выполнения сравнивается с оставшимся временем выполнения текущего процесса.
4.2.4 Трехуровневое планирование
Трехуровневое планирование
Планировщик доступа выбирает задачи оптимальным образом (например: процессы, ограниченные процессором и вводом/выводом).
Если процессов в памяти слишком много, планировщик памяти выгружает и загружает некоторые процессы на диск. Количество процессов находящихся в памяти, называется степенью многозадачности.
Планирование в интерактивных системах
4.3.1 Циклическое планирование
Самый простой алгоритм планирования и часто используемый.
Каждому процессу предоставляется квант времени процессора. Когда квант заканчивается процесс переводится планировщиком в конец очереди. При блокировке процессор выпадает из очереди.
Пример циклического планирования
Преимущества:
Простата
Справедливость (как в очереди покупателей, каждому только по килограмму)
Недостатки:
Если частые переключения (квант - 4мс, а время переключения равно 1мс), то происходит уменьшение производительности.
Если редкие переключения (квант - 100мс, а время переключения равно 1мс), то происходит увеличение времени ответа на запрос.
4.3.2 Приоритетное планирование
Каждому процессу присваивается приоритет, и управление передается процессу с самым высоким приоритетом.
Приоритет может быть динамический и статический.
Динамический приоритет может устанавливаться так:
П=1/Т, где Т- часть использованного в последний раз кванта
Если использовано 1/50 кванта, то приоритет 50.
Если использован весь квант, то приоритет 1.
Т.е. процессы, ограниченные вводом/вывода, будут иметь приоритет над процессами ограниченными процессором.
Часто процессы объединяют по приоритетам в группы, и используют приоритетное планирование среди групп, но внутри группы используют циклическое планирование.
Приоритетное планирование 4-х групп
Методы разделения процессов на группы
Группы с разным квантом времени
Сначала процесс попадает в группу с наибольшим приоритетом и наименьшим квантом времени, если он использует весь квант, то попадает во вторую группу и т.д. Самые длинные процессы оказываются в группе наименьшего приоритета и наибольшего кванта времени.
Процесс либо заканчивает работу, либо переходит в другую группу
Этот метод напоминает алгоритм - "Кратчайшая задача - первая".