Диспетчеризация задач с использованием динамических приоритетов

1. Планирование и диспетчеризация процессов и задач

Операционная система выполняет следующие основные функции, связанные с управлением процессами и задачами:

o создание и удаление задач;

o планирование процессов и диспетчеризация задач;

o синхронизация задач, обеспечение их средствами коммуникации.

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

• Иногда диспетчеризацию называют краткосрочным планированием.

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

• Иногда используют термин стратегия обслуживания.

• Стратегия планирования определяет, какие процессы мы планируем на выполнение для того, чтобы достичь поставленной цели. Среди стратегий, прежде всего, можно выбрать следующие:

• по возможности заканчивать вычисления (вычислительные процессы) в том же самом порядке, в котором они были начаты;

• отдавать предпочтение более коротким вычислительным задачам;

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

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

• Различают два больших класса дисциплин обслуживания: бесприоритетные и приоритетные.

• При бесприоритетном обслуживании выбор задачи производится в некотором заранее установленном порядке без учета их относительной важности и времени обслуживания.

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

• В концепции приоритетов имеем следующие варианты:

• приоритет, присвоенный задаче, является величиной постоянной;

• приоритет изменяется в течение времени решения задачи (динамический приоритет).

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

• Наиболее часто используемые дисциплины диспетчеризации.

1. FCFS (First Come First Served – первым пришел, первым обслужен) – задачи обслуживаются в порядке их появления. Те задачи, которые были заблокированы в процессе работы после перехода в состояние готовности вновь ставятся в эту очередь готовности. При этом возможны два варианта:

1) ставить разблокированную задачу в конец очереди готовых к выполнению задач.

2) диспетчер помещает разблокированную задачу перед теми задачами, которые еще не выполнялись. Образуется две очереди: одна очередь образуется из новых задач, а вторая очередь — из ранее выполнявшихся, но попавших в состояние ожидания. 2. SJN (Shortest Job Next — следующим выполняется самое короткое задание) требует, чтобы для каждого задания была известна оценка в потребностях машинного времени. Дисциплина обслуживания SJN предполагает, что имеется только одна очередь заданий, готовых к выполнению. Задания, которые в процессе своего исполнения были временно заблокированы (например, ожидали завершения операций ввода-вывода), вновь попадали в конец очереди готовых к выполнению наравне с вновь поступающими.

3. SRT (Shortest Remaining Time) — следующим будет выполняться задание, которому осталось меньше всего выполняться на процессоре.

• Карусельная дисциплина обслуживания RR (Round Robin) – каждая задача получает процессорное время квантами времени (time slice) q. После окончания кванта времени q задача снимается с процессора, и он передается следующей задаче. Снятая задача ставится в конец очереди задач, готовых к выполнению.

• Величина кванта времени q выбирается как компромисс между приемлемым временем реакции системы на запросы пользователей и накладными расходами на частую смену контекста задач.

• Невытесняющая (non-preemptive multitasking), или кооперативная многозадачность (cooperative multitasking), — это способ диспетчеризации задач, при котором активная задача выполняется до тех пор, пока она сама, «по собственной инициативе», не отдаст управление диспетчеру задач для того, чтобы тот выбрал из очереди другой, готовый к выполнению процесс или поток. FCFS, SJN, SRT относятся к невытесняющим.

• Вытесняющая многозадачность (preemptive multitasking), —решение о переключении процессора с выполнения одной задачи на выполнение другой принимается диспетчером задач, а не самой активной задачей. RR и другие, построенные на ее основе, относятся к вытесняющим.

2. Качество диспетчеризации и гарантии обслуживания

• Одна из проблем, которая возникает при выборе подходящей дисциплины обслуживания — это гарантия обслуживания. Более жестким требованием к системе, чем просто гарантированное завершение процесса, является его гарантированное завершение к указанному моменту времени или за указанный интервал времени.

Гарантировать обслуживание можно, например, следующими тремя способами:

• Выделять минимальную долю процессорного времени некоторому классу процессов, если по крайней мере один из них готов к исполнению.

• Выделять минимальную долю процессорного времени некоторому конкретному процессу, если он готов к выполнению.

• Выделять столько процессорного времени некоторому процессу, чтобы он мог выполнить свои вычисления к сроку.

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

• загрузка центрального процессора;

• пропускная способность центрального процессора;

• время оборота (turnaround time) процесса;

• время ожидания (waiting time);

• время отклика.

Главные причины, приводящие к снижению производительности системы:

• накладные расходы на переключение процессора. • переключение на другую задачу в тот момент, когда текущая задача выполняет критическую секцию, а другие задачи активно ожидают входа в свою критическую секцию.

Методы повышения производительности системы:

• совместное планирование – все потоки одного приложения одновременно ставятся на выполнение процессорами и одновременно снимаются с выполнения;

• планирование, при котором находящиеся в критической секции задачи не прерываются, а активно ожидающие входа в критическую секцию задачи не ставятся на выполнение до тех пор, пока вход в секцию не освободится;

• планирование с учетом так называемых подсказок (hints) программы (во время ее выполнения).

3. Диспетчеризация задач с использованием динамических приоритетов

• Основная стратегия обслуживания применяемая в UNIX-системах, — это равенство в обслуживании и обеспечение приемлемого времени реакции системы.

• Каждый процесс имеет два атрибута приоритета: текущий приоритет, на основании которого происходит планирование, и заказанный относительный приоритет

• Процесс, ожидающему недоступного в данный момент ресурса, имеет значение приоритета сна.

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

• В Windows NT/2000/XP каждый поток выполнения имеет базовый уровень приоритета.

• Для определения порядка выполнения потоков диспетчер задач использует систему приоритетов, направляя на выполнение задачи с высоким приоритетом раньше задач с низким приоритетом. Система прекращает исполнение, или вытесняет, текущий поток, если становится готовым к выполнению другой поток с более высоким приоритетом.

• Имеется группа очередей — по одной для каждого приоритета.

• Для системных модулей зарезервирована очередь с номером 0.

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

• В OS/2 имеется четыре класса задач. Для каждого класса задач имеется своя группа приоритетов с интервалом значений от 0 до 31. Итого, 128 различных уровней.

• Задачи, имеющие самые высокие значения приоритета, называются критическими по времени (time critical).

• Следующий класс задач имеет название приоритетного (серверного). • Большинство задач относят к обычному классу, его еще называют регулярным, или стандартным. По умолчанию система программирования порождает задачу, относящуюся именно к этому классу.

• Существует еще класс фоновых задач, называемый в OS/2 остаточным.

• Внутри каждого класса задачи, имеющие одинаковый уровень приоритета, выполняются в соответствии с дисциплиной RR.

• В OS/2 используется механизм называется повышением приоритета Операционная система изменяет приоритет задачи в трех случаях:

• 1) повышение приоритета активной задачи

• 2) повышение приоритета ввода-вывода

• 3) повышение приоритета «забытой» задачи