Реализация (создание) процессов и потоков

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

Для планирования процессов и потоков ОС создает для каждого из них специальную информационную структуру называемую дескриптором (descriptor – описатель). Создать процесс – значит создать дескриптор процесса. Дескриптор описывает текущее состояние процесса или потока во время всего жизненного цикла их существования. В разных ОС дескрипторы процесса имеют разные названия: управляющий блок процесса в OS/2 – Process Control Block (PCB); дескриптор процесса в UNIX; объект-процесс (object-process) в Windows NT и др.

В общем случае дескриптор процесса содержит следующую информацию:

- идентификатор процесса;

- тип (или класс) процесса, который определяет для супервизора некоторые правила предоставления ресурсов;

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

- переменную состояния, которая определяет, в каком состоянии находится процесс (готов, выполнение, ожидание устройства ввода/вывода и т. д.);

- защищенную область памяти (или адрес такой зоны), в которой хранятся текущие значения параметров ВС, если процесс прерывается, не закончив работу. Эта информация называется контекстом процесса. Контекст процесса содержит информацию, необходимую для возобновления выполнения процесса с прерванного места: содержимое счетчика команд, регистров процессора, состояние стека и т. д.;

- информацию о ресурсах, которыми процесс владеет и/или имеет право пользоваться (указатели на открытые файлы, информация о незавершенных операциях ввода/вывода и т. п.);

- информация (место или его адрес) для организации общения с другими процессами;

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

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

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

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

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

Вопрос 17. Планирование и диспетчеризация процессов и потоков. Вытесняющие и невытесняющие алгоритмы планирования.

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

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

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

Планирование потоков включает в себя решение двух задач:

- определение момента времени для смены текущего активного потока;

- выбор для выполнения потока из очереди готовых потоков.

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

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

Статический тип планирования может быть использован в специализированных системах, в которых весь набор одновременно выполняемых задач определен заранее, например, в системах реального времени. С татический планировщик принимает решения о планировании не во время работы системы, а заранее (off-line). Динамический и статический планировщики можно уподобить диспетчеру железной дороги, который пропускает поезда строго по предварительно составленному расписанию, и регулировщику на перекрестке автомобильных дорог, который решает, какую машину остановить, а какую пропустить, в зависимости от ситуации.

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

Диспетчеризация заключается в реализации найденного в результате планирования (динамического или статистического) решения, то есть в переключении процессора с одного потока на другой. Диспетчеризация сводится к следующему:

- сохранение контекста текущего потока, который требуется сменить;

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

- запуск нового потока на выполнение.

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

В состоянии выполнения в однопроцессорной системе может находиться не более одного потока, а в каждом из состояний ожидания и готовности – несколько потоков. Эти потоки образуют очереди соответственно ожидающих и готовых потоков. Очереди потоков организуются путем объединения в списки описателей отдельных потоков. Каждый описатель потока, кроме всего прочего, содержит по крайней мере одну ссылку на другой описатель, соседствующий с ним в очереди. Такая организация очередей позволяет легко их переупорядочивать, включать и исключать потоки, переводить потоки из одного состояния в другое. В качестве примера на рис. 4.4 показана очередь готовых потоков, для которой запланированный порядок выполнения выглядит так: А, В, Е, D, С.

Рис. 4.4. Очередь потоков

Вытесняющие и невытесняющие алгоритмы планирования

Алгоритмы планирования можно разделить на невытесняющие или вытесняющие.

Невытесняющие (non-preemptive) алгоритмы основаны на том, что активный поток выполняется до тех пор, пока он сам, по собственной инициативе, не отдаст управление диспетчеру ОС, для того, чтобы тот выбрал из очереди другой, готовый к выполнению поток;

Вытесняющие (preemptive) алгоритмы основаны на том, что решение о переключении процессора с выполнения одного протока на выполнение другого потока принимается диспетчером ОС, а не самим активным потоком (Windows NT, OS/2, UNIX).

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

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

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

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

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

Вопрос 18. Алгоритмы планирования, основанные на квантовании, приоритетах, смешанные алгоритмы.

Алгоритмы планирования, основанные на квантовании.

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

- поток завершился и покинул систему;

- произошла ошибка;

- поток перешел в состояние ожидания;

- исчерпан квант процессорного времени, отведенный данному потоку.

Поток, который исчерпал свой квант, переводится в состояние «готовность» и ожидает, когда ему будет предоставлен новый квант процессорного времени, а на выполнение в соответствии с определенным правилом выбирается новый поток из очереди готовых. Таким образом, ни один поток не занимает процессор надолго, поэтому квантование широко используется в системах разделения времени. Граф состояний потока для алгоритма диспетчеризации, основанного на квантовании, изображен на рис. 4.5.

Рис. 4.5. Граф состояний потока в системах с квантованием

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

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

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

Алгоритмы планирования, основанные на приоритетах.

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

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

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

Например, в операционной системе Windows NT определено 32 уровня приоритетов и два класса потоков – потоки реального времени и потоки с переменными приоритетами. Диапазон от 1 до 15 отведен для потоков с переменными приоритетами, а от 16 до 31 – для потоков реального времени (приоритет 0 зарезервирован для системных целей).

Существует две разновидности приоритетного обслуживания:

- обслуживание с относительными приоритетами;

- обслуживание с абсолютными приоритетами.

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

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

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

Графы состояний потока для алгоритмов с относительными и абсолютными приоритетами показаны на рис. 4.6.

а)

б)

Рис. 4.6. Графы состояний потока в системах

с относительными (а) и абсолютными (б) приоритетами

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

В системах с абсолютными приоритетами время ожидания потока с самым высоким приоритетом в очередях может сведено к минимуму. Это делает планирование на основе абсолютных приоритетов подходящим для систем управления объектами, в которых важна быстрая реакция на событие.

Смешанные алгоритмы планирования.

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

Например, в Windows NT приоритеты потоков могут динамически меняться системой в определенном диапазоне относительно заданного значения.

Вопрос 19. Планирование в системах реального времени.

Планирование в системах реального времени.

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

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

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

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

,

где t _{обр i} – время обработки i -го события процессором;

T_i – период возникновения i -го события;

m – число событий.

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

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

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

- построением статического расписания (для планируемых задач);

- выбором математически обоснованного динамического алгоритма планирования.

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

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

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

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

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

Моменты перепланировки.

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

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

· Активная задача выполнила системный вызов, связанный с запросом на ввод-вывод или на доступ к ресурсу, который в настоящий момент занят. Планировщик переводит задачу в состояние ожидания и выполняет перепланирование.

· Активная задача выполнила системный вызов, связанный с освобождением ресурса. Планировщик проверяет, не ожидает ли этот ресурс какая-либо задача. Если да, то эта задача переводится из состояния ожидания в состояние готовности. При этом, возможно, что задача, которая получила ресурс, имеет более высокий приоритет, чем текущая активная задача. После перепланирования более приоритетная задача получает доступ к процессору, вытесняя текущую задачу.

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

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

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