Программное обеспечение многозадачности ОС

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

§ собственные области памяти под код и данные, включая значения регистров и счетчика команд;

§ собственный стек;

§ собственное отображение виртуальной памяти (в системах с виртуальной памятью) на физическую;

§ собственное состояние.

Процесс находится в одном из типичных состояний:

§ «остановлен» – процесс остановлен и не использует процессор;

§ «терминирован» – процесс не использует процессор (процесс закончился, но еще не удален ОС);

§ «ждет» – процесс ждет некоторого события (аппаратное или программное прерывание, сигнал или другая форма межпроцессного взаимодействия);

§ «готов» – процесс не остановлен, не терминирован, не ожидает, не удален, но и не работает (не получил доступ к процессору, если в данный момент выполняется другой, более высокоприоритетный процесс);

§ «выполняется» – процесс выполняется и использует процессор.

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

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

Каждому процессу и каждому потоку в ОСРВ приписывается приоритет. Чем важнее процесс или поток, тем больше это число. Приоритет может быть фиксированным (назначается при создании процесса и не меняется в течение его жизни). В зависимости от алгоритмов планирования приоритет может изменяться в течение жизни.

Преимущества потоков:

1. Множество потоков способно размещаться внутри одного программного модуля (exe-файла), что позволяет экономить ресурсы как внешней, так и внутренней памяти.

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

3. Контекст потоков меньше, чем процессов, и время переключения между задачами-потоками меньше, чем между задачами-процессами.

4. Так как все потоки, а иногда и само ядро РВ размещаются в одном ЕХЕмодуле, значительно упрощается использование программ-отладчиков (debugger).

Недостатки потоков:

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

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

Основные свойства задач. С точки зрения ОС, информация о задаче хранится в унифицированной структуре данных управляющем блоке (Task Control Block, TCB). В блоке хранятся такие параметры, как имя и номер задачи, верхняя и нижняя границы стека, ссылка на очередь сообщений, статус задачи, приоритет и т. п.

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

Контекст задачи – это набор данных, содержащий всю необходимую информацию для возобновления выполнения задачи с того места, где она была ранее прервана. Часто контекст хранится в управляющем блоке (TСB) и включает в себя такие данные, как счетчик команд, указатель стека, регистры СРU и FPU и т. п. Планировщик задач при необходимости сохраняет контекст текущей активной задачи и восстанавливает контекст задачи, назначенной к исполнению. Такое переключение контекстов и является основным механизмом ОС РВ при переходе от выполнения одной задачи к выполнению другой.

Состояние (статус) задачи. С точки зрения ОС, задача может находиться в нескольких состояниях. Загруженная на выполнение задача может находиться в четырех состояниях:

1. Активная задача – это задача, выполняемая системой в текущий момент времени.

2. Готовая задача – это задача, готовая к выполнению и ожидающая у планировщика своей «очереди».

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

4. Пустая задача (Idle Task) – это задача, запускаемая самой ОС в момент инициализации и выполняемая только тогда, когда в системе нет других готовых для выполнения задач. Пустая задача запускается с самым низким приоритетом и представляет собой бесконечный цикл «ничего не делать», предоставляя ОС удобный механизм отработки ситуаций, когда нет ни одной готовой к выполнению задачи.

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

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

Планирование задач. Важной частью любой ОСРВ является планировщик задач (диспетчер задач, супервизор), который определяет какая задача выполняется в системе в конкретный момент времени, т.е. делит между задачами ресурсы многозадачной вычислительной системы. К основным методам планирования относят: циклический алгоритм (round robin), разделение времени с равнодоступностью (time sharing with fairness), кооперативную многозадачность.

Наиболее часто используемый в ОСРВ принцип планирования – приоритетная многозадачность с вытеснением, идея которого состоит в том, что высокоприоритетная задача, как только для нее появляется работа, немедленно прерывает (вытесняет) низкоприоритетную. Самым простым методом планирования, не требующим никакого специального ПО и планировщика, является использование циклического алгоритма в стиле round robin (рис. 1.4):

void main (void)

{

for (;;) {

task0();

task1();

task2();

/* и т. д. */

}

}

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

1. Подпрограммы не должны содержать циклов ожидания

while (TRUE) {

if (switch_up()) {

lamp_off();

break;

}

}

2. Подпрограммы должны выполнять свою работу быстрее, чтобы дать возможность работать следующей подпрограмме.

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

Преимущества циклического алгоритма:

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

2. Если исключить из рассмотрения прерывания, система полностью детерминирована. Задачи вызываются в одной и той же последовательности, что позволяет просто произвести анализ «наихудшего случая» и вычислить максимальную задержку.

a) Круговое планирование с вытеснением
б) Невытесняющее планирование на основе приоритетов
	г) Планирование с немедленным вытеснением
в) Вытесняющее планирование на основе приоритетов с точками вытеснения
Рис. 1.4. Основные варианты планирования задач в СРВ

3. Минимальные размеры кода и данных, т.к. в отличие от алгоритмов с вытеснением, для всех задач необходим только один стек.

4. Отсутствуют ошибки, обусловленные «гонками».

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

Другим, широко используемым, является алгоритм планирования с режимом разделения времени. Существуют различные реализации в рамках этого алгоритма (timeslicing и time-sharing). Алгоритм реализуется следующим образом: каждой задаче отводится определенное количество квантов времени (обычно кратно 1 мс), в течение которых задача может монопольно занимать процессорное время. После того как заданный интервал времени истекает, управление передается следующей готовой к выполнению задаче с наивысшим приоритетом, которая выполняется в течение отведенного для нее промежутка времени, после чего все повторяется в стиле round robin.

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

Кооперативная многозадачность – это еще один алгоритм переключения задач, реализованный в ОС Windows 3.х. Задача, получившая управление, выполняется до тех пор, пока сама по своей инициативе не передаст управление другой задаче. По сути это продолжение идеологии round robin, но в чистом виде мало применяется в СРВ.

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

Планировщик анализирует момент выдачи критичных по времени управляющих воздействий и запускает на выполнение задачу, которая отвечает за ближайшие из них (алгоритм earliest deadline first, EDF).

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