Операции над процессами и связанные с ними понятия

Набор операций

Удобно разделить их на три пары:

1. создание процесса – завершение процесса;

2. приостановка процесса (из выполнения в готовность) – запуск процесса (из готовности в исполнение);

3. блокирование процесса (из исполнения в ожидание) – разблокирование процесса (из ожидания в готовность).

Операции создания и завершения процесса являются одноразовыми. Все остальные операции, связанные с изменением состояния процессов, являются многоразовыми.

Блок управления процессами и контекст процесса

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

1. состояние, в котором находиться процесс;

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

3. содержимое регистров процессора;

4. данные, необходимые для планирования использования процессора и управления памятью, (приоритет процесса);

5. учетные данные (идентификационный номер процесса, какой пользователь инициировал его работу, общее время использования процессора данным процессом);

6. сведения об устройствах ввода-вывода связанных с процессом.

Состав и строение структуры зависит от конкретной ОС.

Структура данных – это блок управления процессом. Блок управления процессом является моделью процесса для ОС. Любая операция, производимая ОС над процессом, вызывает определенные изменения в блоке управления процессом. В рамках принятой модели состояний процесса, содержимое блока между операциями остается постоянным.

Информацию, для хранения которой предназначен блок, удобно разделить на две части:

1. содержимое всех регистров процессора (называют регистровым контекстом);

2. все остальное системным контекстом.

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

Код и данные, находящиеся в адресном пространстве, принято называть контекстом.

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

Одноразовые операции

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

1. в простых системах все процессы могут быть порождены на этапе старта системы;

2. в сложных системах процессы создаются динамически (по мере необходимости).

Инициатором рождения нового процесса после старта ОС может выступить:

1. процесс пользователя, совершивший специальный вызов системы;

2. сама ОС, то есть тоже некоторый процесс.

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

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

Для выполнения своих функций процесс-ребенок требует определенных ресурсов: памяти, файлов, устройств ввода-вывода. Существует два подхода к их выделению:

1. новый процесс может получить в свое распоряжение некоторую часть родительских ресурсов;

2. может получить свои ресурсы непосредственно от ОС и эта информация заносится в блок управления процессом.

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

1. Процесс-ребенок становиться дублирующим процесса-родителя по регистровому и пользовательскому контексту.

2. Процесс-ребенок загружается новой программой из какого-либо файла.

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

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

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

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

Как правило, «осиротевшие процессы» «усыновляются» одним из системных процессов, которые порождаются при старте ОС и функционируют все время, пока она работает.

Многоразовые операции

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

1. Запуск процесса

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

2. Приостановка процесса

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

3. Блокировка процесса

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

4. Разблокирование процесса

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

Переключение контекста

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

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

Планирование процессов

11.1. Уровни планирования процессов

1. Долгосрочное планирование процессов

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

2. Короткосрочное планирование

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

3. Среднесрочное планирование

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

11.2.    Критерии планирования и требования к алгоритму.

Для каждого уровня планирования предлагается много алгоритмов. Цели, выполняемые алгоритмом:

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

2. Эффективность: занятость процессора на 100%. В реальной жизни от 40% до 90%.

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

4. Сокращение времени ожидания. Сократить время, которое проводят процессы в состояние готовности, и сократить время, которое проводит задание в очереди.

5. Сокращение времени отклика: минимизировать время, которое требуется процессу в интерактивных системах для ответа на запрос пользователя.

Свойства алгоритмов:

1. 1.Были предсказуемы. Одно и тоже задание должно выполняться приблизительно за одно и тоже время.

2. 2.Были связаны с минимальными накладными расходами. Время выбора процесса меньше чем время исполнения процесса.

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

4. 4.Обладание масштабируемостью: не сразу теряли работоспособность при увеличении нагрузки. Рост количества процессов в системе в 2 раза не должен приводить к увеличению полного времени выполнения процессов на порядок.

11.3.         Параметры планирования.

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

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

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

К статическим параметрам процессов относятся характеристики, как правило, присущи заданиям уже на этапе загрузки.

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

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

Динамические параметры процессов:

1.сколько времени прошло с момента выгрузки процесса на диск и его загрузки в ОП.

2.Сколько ОП занимает процесс.

3.Сколько процессорного времени уже предоставлено процессу.

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

CPU-это промежуток времени непрерывного использования процессора.

I/O- это промежуток времени непрерывного ожидания в/в.

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

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

1) когда процесс переводится из состояния исполнения в состояние завершил исполнение.

2)из состояния исполнения в состояние ожидания.

3)из состояния исполнения в состояние готовность.

4)из состояния ожидания в состояние готовность.

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

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

11.5.           Алгоритмы планирования.

First come first served

Время ожидания для процесса P0=0 единиц, для P1=13 единиц, для P2=17 единиц. Таким образом, среднее время ожидания равно 10 единиц. Полное время выполнение для процесса P0=13единиц, для P1 =13+4=17,для P2=13+4+1=18. среднее полное время выполнения 16 единиц.

Время ожидания для P0=5 единиц, для P1=1, для P2=0. среднее время ожидания 2 единицы. В 5 раз эффективнее. Полное время выполнение для P0=5+13, P1=1+4, P2=1. среднее полное время 8 единиц.

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

Round Robin

Round Robin (R R) -это модификация предыдущего алгоритма. Это тот же алгоритм, реализованный в режиме вытесняющего планирования. Можно представить себе все множество готовых процессов организованных циклически. Процессы просто сидят на карусели. Карусель вращается так, что каждый процесс находится около процессора небольшой фиксированный квант времени от 10 до 100 мили секунд. Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться. Реализуется такой алгоритм также как и предыдущей с помощью организации процессов находящихся в состояние готовность. Планировщик выбирает для очередного исполнения процесс, находящийся в начале очереди и устанавливает таймер для генерации прерывания по истечению определенного кванта времени. При выполнение процесса возможны 2 варианта:

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

2.продолжительность остатка текущего CPU BIRST процесса, больше чем квант времени. Процесс вытеснен.

На производительность алгоритма RR сильно влияет величина кванта времени. При очень больших величинах кванта времени, когда каждый процесс успевает завершить свой CPU BIRST до возникновения прерывания по времени, алгоритм RR вырождается в алгоритм FIRST COME. В реальных условиях при слишком малой величине кванта и соответственно слишком частым переключением контекста, накладные расходы слишком резко возрастают, т.е снижается производительность системы.

Shortest-Job-First

При рассмотрение предыдущих алгоритмов видно насколько существенным для них является порядок расположением процессов в очереди, процессов готовых к исполнению. Если короткие задачи расположены в очереди ближе к ее началу, то общая производительность этих алгоритмов значительно возрастает. Если знать время следующей CPU BIRST для процессов находящихся в состояние готовность, то можно выбрать процесс не из начала очереди, а процесс с минимальной длительностью CPU BIRST. Если же таких процессов 2 и больше, то можно использовать алгоритм F.C.F.S. название данного алгоритма кратчайшая работа 1-ой. Данный алгоритм может быть как вытесняющим, так и не вытесняющим. При не вытесняющим планирование процессор предоставляется выбранному процессу на все необходимое ему время, независимо от событий происходящих в вычислительной системе. При вытесняющим планирование учитывается появление новых процессов готовых к исполнению во время работы выбранного процесса. Если CPU BIRST нового процесса меньше чем остаток CPU BIRST у исполняющегося,то исполняющийся процесс вытесняется новым. Квантование 

времени не применяется.

Вытесняющий режим.

P0:время =0, CPU BIRST=6; P1=2, CPU BIRST=2; P2=6, CPU BIRST= 7; P3=0, CPU BIRST=5.

В начальный момент времени в состояние готовность находится только 2 процесса: P0, P3. меньшее время CPU BIRST оказывается у процесса p3, поэтому он выбирается для исполнения. По прошествию 2 единиц времени в систему поступает процесс P1. Время его CPU BIRSY меньше чем остаток у P3, который вытесняется из состояния исполнения и переводится в состояние готовность по прошествии еще 2 единиц времени. Процесс P1 завершается и переводится в состояние завершил исполнение. На исполнение выбирается процесс P3. в момент времени 6 в очереди процессов готовых к исполнению появляется процесс P2, но поскольку его CPU BIRST =7, а процессу P3 осталось трудится 1 единицу, то P3 остается в состояние исполнения. После его завершения в момент времени 7 в очереди находится P0,P2 из которых выбирается P0, а потом P2. основную сложность при реализации алгоритма SJF представляет невозможность точного знания времени очередного CPUN BIRST для исполняющихся процессов.