Дисциплины диспетчеризации

1. Класс, основанный на квантовании. (линейные и циклические)

2. Класс, основанный на приоритетах. (статические и динамические)

Дисциплина диспетчеризации – это некоторое основное правило, реализующее очер¨дность предоставления (выделения) процессора (процессорного времени) готовым к выполнению задачам (процессам). Любая конкретная дисциплина диспетчеризации выполняет две взаимосвязанные функции – выделение процессорного времени конкретной задаче (процессу), и создание и модификация очереди готовых к выполнению задач (обслуживание очереди). Дисциплина диспетчеризации реализуется специальной компонентой ОС – диспетчером (диспетчером задач). Рассмотрим наиболее важные дисциплины диспетчеризации.

1. FCFS (first come – first served – первым приш¨л, первым обслужился) – прежде процессор получает та задача, которая раньше перешла в состояние готовности. Данная дисциплина проста в реализации, равноправна по отношению как к “длинным ” так и к “коротким” процессам, среднее время пребывания в очереди готовности весьма значительное.

2. SJN (shortest job next – следующий с кратчайшим заданием) – прежде процессор получает та задача, которая имеет минимальное заказное время обслуживания. Данная дисциплина требует, чтобы для каждой задачи была известна оценка потребности в машинном времени, значение которой зада¨тся как параметр задачи. Такая дисциплина более сложна в реализации по сравнению с FCFS, она дискриминационна по отношению к “длинным процессам”, среднее время пребывания в очереди готовности меньше чем для FCFS. SJN имеет существенный недостаток. Задачи, которые были временно заблокированы (например, ожидали завершения ввода/вывода), в результате попадут в конец очереди готовности, даже если для их выполнения требуется небольшое процессорное время.

3. SRT (shortest remaining time) – прежде процессор получает задача, которая имеет меньше всего времени для своего завершения. Это время определяется как разность между заказанным временем обслуживания и тем процессорным временем, которая задача уже получила. SRT свободна от недостатка, характерного для SJN. SRT сложна в реализации и дискриминационна по отношению к “длинным” процессам.

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

4. RR (round robin) – циклическая (карусельная) дисциплина. Диспетчер выделяет готовой к выполнению задаче некоторый квант процессорного времени (интервал мультиплексирования). Если задача не успевает выполниться в течение этого кванта, диспетчер переводит е¨ обратно в конец очереди готовности и выделяет следующий квант процессорного времени для другой готовой задачи. Данная дисциплина является дискриминационной по отношению к длинным процессам. Е¨ удобно использовать в многопользовательских вычислительных системах, где требуется обслуживать большое число запросов, поступающих с различных рабочих станций системы.

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

6. Дисциплины на основе динамических приоритетов задач. Для каждой задачи зада¨тся начальное значение приоритета, которое затем изменяется во времени. Таким образом, приоритет задачи есть функция времени. Конкретный вид таких функций может быть разный, но общая их направленность состоит в том, что, чем дольше задача находится в очереди готовности, тем выше становится е¨ приоритет. Это позволяет гарантировать обслуживание как коротких так и длинных процессов.

7. Дисциплины с несколькими очередями. Диспетчер поддерживает несколько очередей готовых к выполнению задач. Каждая очередь обслуживается по своей дисциплине. Такой диспетчер сложен в реализации, так как в его составе должен быть дополнительный механизм переключения с одной очереди готовности на другую. Более простой способ реализации диспетчера (статический) предполагает, что задача попав в некоторую очередь готовности, там и оста¨тся до своего полного выполнения. Более сложным способом реализации (динамическим) является способ, при котором задача может переходить из одной очереди готовности в другую на интервале своего существования.

Существует множество дисциплин диспетчеризации:

· Бесприоритетная линейная диспетчеризация (1м пришел, 1м обслужился)

Существует 2 очереди для процессов:

- новые процессы

- процессы, кот.вернулись из заблокированного состояния.

Выстраивание по времени:

· Циклическая диспетчеризация(карусельная обработка)

через квант времени А=Г

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

· С указанием приоритета задач (статические)

Из списка задач выполняются сначала самые приоритетные

Относительная приоретизация:

Абсолютная приоретизация:

· Динамическая приоретизация:

На выходе из ЦП задаче может поставится любой приоритет.

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