Состояния процессов. Контекст и дескриптор процесса

В многозадачной (многопроцессной) системе процесс может находиться в одном из трех основных состояний:

· ВЫПОЛНЕНИЕ – активное состояние процесса, во время которого процесс обладает всеми необходимыми ресурсами и непосредственно выполняется процессором.

· ОЖИДАНИЕ – пассивное состояние процесса, процесс заблокирован, он не может выполняться по своим внутренним причинам. Процесс ждет осуществления некоторого события, например, завершения операции ввода/вывода, получения сообщения от другого процесса.

· ГОТОВНОСТЬ – также пассивное состояние процесса, но в этом случае процесс заблокирован в связи с внешними по отношению к нему обстоятельствами: процесс имеет все требуемые для него ресурсы, он готов выполняться, однако процессор занят выполнением другого процесса.

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

В состоянии ВЫПОЛНЕНИЕ в однопроцессорной системе может находиться только один процесс, а в каждом из состояний ОЖИДАНИЕ и ГОТОВНОСТЬ – несколько процессов. Эти процессы образуют очереди соответственно ожидающих и готовых процессов.

На рисунке 1.1 показан жизненный цикл процесса.

Жизненный цикл процесса начинается с состояния ГОТОВНОСТЬ, когда процесс готов к выполнению и ждет своей очереди. При активизации процесс переходит в состояние ВЫПОЛНЕНИЕ и находится в нем до тех пор, пока либо он сам освободит процессор, перейдя в состояние ОЖИДАНИЕ, либо будет насильно вытеснен из процессора, например, вследствие исчерпания отведенного данному процессу кванта процессорного времени. В последнем случае процесс возвращается в состояние ГОТОВНОСТЬ. В это же состояние процесс переходит из состояния ОЖИДАНИЕ, после того, как ожидаемое событие произойдет.

Рис. 1.1. Жизненный цикл процесса

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

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

Контекст процесса используется операционной системой только после того, как принято решение о возобновлении прерванного процесса.

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

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

Создать процесс – это значит:

· создать информационные структуры, описывающие данный процесс, то есть его дескриптор и контекст;

· включить дескриптор нового процесса в очередь готовых процессов;

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

Нити

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

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

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

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

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

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

Нити, как и процессы, могут переходить из состояния в состояние. Подобно традиционным процессам (то есть процессам, состоящим из одной нити), нити могут находиться в одном из следующих состояний: ВЫПОЛНЕНИЕ, ОЖИДАНИЕ и ГОТОВНОСТЬ. Пока одна нить заблокирована, другая нить того же процесса может выполняться. Нити разделяют процессор так, как это делают процессы, в соответствии с различными вариантами планирования.

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

Итак, нити имеют собственные:

· программный счетчик;

· стек;

· регистры;

· нити-потомки;

· состояние.

Нити разделяют:

· адресное пространство;

· глобальные переменные;

· открытые файлы;

· таймеры;

· семафоры;

· статистическую информацию.

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

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

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

· определение момента времени для смены выполняемого процесса;

· выбор процесса на выполнение из очереди готовых процессов;

· переключение контекстов «старого» и «нового» процессов.

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

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

· алгоритмы, основанные на квантовании;

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

Алгоритмы, основанные на квантовании. Каждому процессу предоставляется квант процессорного времени. Кванты могут быть одинаковыми для всех процессов или различными. Кванты, выделяемые одному процессу, могут быть фиксированной величины или изменяться в разные периоды жизни процесса. Процесс, который исчерпал свой квант времени, переводится в состояние ГОТОВНОСТЬ и ожидает, когда ему будет предоставлен новый квант процессорного времени, а на выполнение выбирается новый процесс из очереди. Очередь готовых процессов может быть организована в соответствии с определенным правилом: циклически, по правилу «первый пришел – первый обслужился» (FIFO) или по правилу «последний пришел – первый обслужился» (LIFO). Процессы, которые не полностью использовали выделенный им квант (например, из-за ухода на выполнение операций ввода/вывода), могут получить или не получить компенсацию в виде привилегий при последующем обслуживании.

В соответствии с алгоритмами, основанными на квантовании, смена активного процесса происходит, если:

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

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

· процесс перешел в состояние ОЖИДАНИЕ;

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

Таким образом, ни один процесс не занимает процессор надолго, поэтому квантование широко используется в системах разделения времени.

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

Существует две разновидности приоритетных алгоритмов:

· алгоритмы, использующие относительные приоритеты;

· алгоритмы, использующие абсолютные приоритеты.

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

В системах с относительными приоритетами активный процесс выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ОЖИДАНИЕ (или же произойдет ошибка, или процесс завершится).

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

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

Вытесняющие и невытесняющие алгоритмы планирования. Существует два основных типа планирования процессов: вытесняющие (preemptive) и невытесняющие (non-preemptive).

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

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

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

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

Алгоритмы планирования процессов в ОС UNIX

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

Основной смысл алгоритма состоит в том, что время процессора делится на кванты фиксированного размера, а процессы, готовые к выполнению, выстраиваются в очередь. Когда процесс, выполняющийся на процессоре, исчерпывает свой квант процессорного времени, он переходит в состояние ГОТОВНОСТЬ, ставится в конец очереди, а ресурсы процессора отдаются процессу, находящемуся в начале очереди. Если выполняющийся процесс переходит в состояние ОЖИДАНИЕ (например, по причине обмена с некоторым периферийным устройством) до того, как он исчерпает свой квант, то после повторной активизации он становится в конец очереди, перейдя в состояние ГОТОВНОСТЬ.

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

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

Традиционное решение ОС UNIX состоит в использовании динамически изменяющихся приоритетов. Каждый процесс при своем образовании получает некоторый устанавливаемый системой статический приоритет, который в дальнейшем может быть изменен с помощью системного вызова nice. Этот статический приоритет является основой начального значения динамического приоритета процесса, являющегося реальным критерием планирования. Каждый раз, когда процесс успешно отрабатывает свой квант на процессоре, его динамический приоритет уменьшается (величина уменьшения зависит от статического приоритета процесса). Если значение динамического приоритета процесса достигает некоторого нижнего предела, он переносится во внешнюю память.

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

Существуют два понимания термина «реальное время» – «мягкое реальное время» и «жесткое реальное время».

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

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

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

1. Каждому из таких процессов предоставляется неограниченный сверху квант процессорного времени. Другими словами, занявший процессор процесс реального времени не будет с него снят до тех пор, пока сам не заявит о невозможности продолжения выполнения (например, перейдя в состояние ОЖИДАНИЕ).

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

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

Таким образом, в современных вариантах ОС UNIX одновременно реализована как возможность разделения времени для интерактивных процессов, так и возможность мягкого реального времени для процессов, связанных с управлением объектов в реальном времени.

Алгоритмы планирования процессов в Windows NT

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

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

Windows NT поддерживает 32 уровня приоритетов, разделенных на два класса – класс реального времени и класс переменных приоритетов. Нити реального времени, приоритеты которых находятся в диапазоне от 16 до 31, являются более приоритетными процессами и используются для выполнения задач, критичных ко времени.

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

Алгоритм планирования нитей в Windows NT объединяет в себе обе базовых концепции – квантование и приоритеты. Как и во всех других алгоритмах, основанных на квантовании, каждой нити назначается квант, в течение которого она может выполняться. Нить освобождает процессор, если:

· блокируется, уходя в состояние ОЖИДАНИЕ;

· завершается;

· исчерпан квант процессорного времени;

· в очереди готовых появляется более приоритетная нить.

Использование динамических приоритетов, изменяющихся во времени, позволяет реализовать планирование, при котором не дискриминируются интерактивные задачи, часто выполняющие операции ввода/вывода и недоиспользующие выделенные им кванты. Если нить полностью исчерпала свой квант, то ее приоритет понижается на некоторую величину. В то же время приоритет нитей, которые перешли в состояние ОЖИДАНИЕ, не использовав полностью выделенный им квант, повышается. Приоритет не изменяется, если нить вытеснена более приоритетной нитью.