Создание процессов и потоков

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

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

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

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

При управлении процессами операционная система использует два основных типа информационных структур: дескриптор процесса и контекст процесса:

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

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

 

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

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

· активное состояние (выполнение), процесс (поток) обладает всеми необходимыми ресурсами и непосредственно выполняется процессором;

· ожидание - пассивное состояние процесса (потока), во время которого процесс блокирован по причине занятости каких-либо необходимых ему ресурсов и, соответственно, ждет осуществления некоторого события: завершения операции ввода и вывода, получения сообщения от другого потока или освобождения необходимого ему ресурса и др.;

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

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

 

Рис. 1. Граф состояния процесса.

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

Из состояния выполнения процесс может выйти по одной из следующих причин:

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

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

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

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

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

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

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

· идентификатор процесса (так называемый PID - process identificator);

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

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

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

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

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

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

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

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

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

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

Основные понятия планирования процессов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Контекст отражает:

1) состояние аппаратуры компьютера в момент прерывания потока:

– значение счетчика команд;

– содержимое регистров общего назначения;

– режим работы процессора;

– флаги;

– маски прерываний и другие параметры.

2) параметры операционной среды:

– ссылки на открытые файлы;

– данные о незавершенных операциях ввода–вывода;

– коды ошибок выполняемых данным потоком системных вызовов и т.д.

Диспетчеризация сводится к следующему:

1) сохранение контекста текущего потока, который следует сменить;

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

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

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

Рассмотрим те, которые признаны наиболее эффективными и до сих пор имеют применение.

Ü Самой простой в реализации является дисциплина FCFS (First Come First Served – первым пришел, первым обслужен), согласно которой задачи обслуживаются «в порядке очереди», то есть в порядке появления. Те задачи, которые были заблокированы в процессе работы (попали в какое-либо из состояний ожидания, например из-за операции ввода-вывода), после перехода в состояние готовности вновь ставятся в эту очередь готовности. К достоинству этой дисциплины прежде всего можно отнести простоту реализации и малые расходы системных ресурсов на формирование очереди задач. Однако эта дисциплина приводит к тому, что пр увеличении загрузки вычислительной системы растет и среднее время ожидания обслуживания, причем короткие задания (требующие небольших затрат машинного времени) вынуждены ожидать столько же, сколько трудоёмкие задания.

Избежать этого недостатка позволяют дисциплины SJN и SRT.

Ü Дисциплина обслуживания SJN (Shortest Job Next – следующим выполняется самое короткое задание) требует, чтобы для каждого задания была известна оценка в потребностях машинного времени. Дисциплина обслуживания SJN предполагает, что имеется только одна очередь заданий, готовых к выполнению. Задания, которые в процессе своего исполнения были временно заблокированы (например, ожидали завершения операции ввода-вывода), вновь попадали в конец очереди готовых к выполнению наравне с вновь поступающими. Это приводило к тому, что задания, которым требовалось очень много времени для своего завершения, вынуждены были ожидать процессор наравне с длительными работами, что не всегда хорошо.

Ü Дисциплина обслуживания SRT (Shortest Remaining Time) – следующим будет выполняться задание, которому осталось меньше всего выполняться на процессоре.

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

Ü Дисциплина обслуживания RR (карусельная – Round Robin) предполагает, что каждая задача получает процессорное время порциями или квантами времени. После окончания кванта времени задача снимается с процессора, и он передается следующей задаче. Снятая задача ставится в конец очереди задач, готовых к выполнению.

 

 

Рис. 3. Карусельная дисциплина диспетчеризации

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

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

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

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

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

Ü Итак, диспетчеризация без перераспределения процессорного времени, то есть не вытесняющая (non-preemptive multitasking), или кооперативная многозадачность (cooperative multitasking), - это такой способ диспетчеризации задач, при котором активная задача выполняется до тех пор, пока она сама, что называется «по собственной инициативе», не отдаст управление диспетчеру задач для того, чтобы тот выбрал из очереди другой, готовый к выполнению процесс или поток дисциплины обслуживания FCFS, SJN, SRT относятся к не вытесняющим.

Ü Дисциплина с перераспределением процессорного времени между задачами, то есть вытесняющая многозадачность (preemptive multitasking), - это такой способ, при котором решение о переключении процессора с выполнения одной задачи на выполнение другой принимается диспетчером задач, а не самой активной задачей. При вытесняющей многозадачности механизм диспетчеризации задач целиком сосредоточен в операционной системе, и программист может писать своё приложение, не заботясь о том, как оно будет выполняться параллельно с другими задачами (процессами и потоками). При этом операционная система выполняет следующие функции: ◘ определяет момент снятия с выполнения текущей задачи, ◘ сохраняет её контекст в дескрипторе задачи, ◘ выбирает из очереди готовых задач следующую ◘ и запускает её на выполнение, загружая её контекст.

Дисциплина RR и многие другие, построенные на её основе, относятся к вытесняющим.

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

Все существующие алгоритмы планирования можно разделить на два класса:

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

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

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

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

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

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

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

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