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

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

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-х групп

Поиск по сайту: