Диспетчеризация потоков

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

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

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

· информация по идентификации задачи (имя задачи, тип задачи);

· информация о ресурсах, которые необходимы задаче для е¨ выполнения и о ресурсах, которые используются в настоящее время (идентификаторы необходимых внешних устройств);

· информация о текущем состоянии задачи (содержимое некоторых регистров процессора);

· информация о родственных связях задачи (имена родительского процесса и процессов-предков);

· информация, необходимая для целей планирования и диспетчеризации (адресные ссылки на соседние дескрипторы, находящиеся в той же очереди, приоритет задачи, ссылки на объекты синхронизации).

Обычно, дескриптор задачи имеет размер порядка нескольких десятков машинных слов. Есть два основных способа размещения дескрипторов в оперативной памяти. Первый, более ранний, состоит в том, что ОС выделяет в системной области памяти специальный раздел под таблицу дескрипторов. Такая таблица имеет фиксированный размер и фиксированный начальный адрес. Такой способ прост с точки зрения управления и сложности реализации, но имеет существенный недостаток - ограничение параллелизма в вычислительной системе. Причиной этого недостатка является ограниченный размер таблицы дескрипторов. Второй способ, более современный, состоит в том, что ОС выделяет подходящую свободную область оперативной памяти под очередной загружаемый дескриптор задачи. Методологически, такой способ не ограничивает параллелизм функционирования вычислительной системы.

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

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

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

Дата добавления: 2014-03-11; просмотров: 610; Нарушение авторских прав

Мы поможем в написании ваших работ!