Процессы и потоки

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

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

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

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

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

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

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

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

Таким образом, архитектурно, приостановленный процесс состоит из собственного адресного пространства, обычно называемого образом памяти (core image – «сердечник»), и компонентов таблицы процессов, содержащей, помимо других величин, его регистры.

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

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

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

С момента запуска процесс последовательно переживает определённый набор состояний (в той или иной очередности):

1. Выполнение — состояние когда процесс непосредственно исполняется на процессоре

2. Готовность — процесс временно приостановлен, чтобы позволить выполняться другим процессам (при это других объективных причин для невыполнения данного процесса может не существовать).

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

Потоки

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

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

Потоком (или управляющим потоком) будем называть последовательность команд, со связанным с нею указателем команд.

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

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

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

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

Межпроцессное взаимодествие

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

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

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

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

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

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

1. Запрет прерываний.

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

1. Переменные блокировки

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

Кроме рассмотренных можно назвать распространённые реализации: строгое чередование, алгоритм Петерсона, флаги готовности, алгоритм булочной (Bakery algorithm).

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

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

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

В 1965г. Дейкстра (E.W. Dijkstra) предложил использовать специальную переменную целого типа, получившую название — семафор. Семафор связывается с совместно используемым ресурсом. Каждое обращение к ресурсу абстрактно будем называть сигналом активизации.

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

Над семафорами определены две операции:

1. down(sem) — сравнивает значение семафора с нулём, если значение больше нуля, то уменьшает его на 1 (то есть расходует один из сохраненных сигналов активизации) и возвращает управление. Если значение семафора равно нулю, процедура down() не возвращает управление процессу, а процесс переводится в состояние ожидания.

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

Мьютекс —это семафор, находящийся в одном из двух возможных состояний: 0 — блокирован, либо 1 — не блокирован. Если процесс должен войти в критическую секцию, и мьютекс не заблокирован, процесс входит в критическую секцию, при этом заблокировав мьютекс. Если мьютекс заблокирован, вызывающий процесс блокируется до тех пор, пока процесс, работающий в критической области, не выйдет из неё.

В представленном в примере решении используются три семафора: один для подсчета заполненных сегментов буфера (full), другой для подсчета пустых сегментов (empty), а третий предназначен для исключения одновременного доступа к буферу произ­водителя и потребителя (mutex). Значение счетчика full исходно равно нулю, счетчик empty равен числу сегментов в буфере, a mutex равен 1. Рассмотрим действия обоих процессов пошагово.

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

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

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