Независимые и взаимодействующие вычислительные процессы - Независимые и взаимодействующие вычислительные процессы

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

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

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

Итак, параллельными мы будем называть такие последовательные вычислительные процессы, которые одновременно находятся в каком-либо активном состоянии. Два параллельных процесса могут быть независимыми (independing processes) либо взаимодействующими (cooperating processes).

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

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

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

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

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

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

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

Взаимодействие сотрудничающих процессов удобно всего рассматривать в схеме "производитель -- потребитель" (produces -- consumer) или, как часто говорят -- "поставщик -- потребитель". В качестве первого примера рассмотрим работу двух процессов Р1 и Р2 с общей переменной X.

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

Процесс Р1	Процесс Р2
R1:=X	R2:=X
R1:=R1+X	R2:=R2+1
X:=R1	X:=R2

Рис. 6.1 Пример конкурирующих процессов

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

Поскольку при мультипрограммировании процессы могут иметь различные скорости исполнения, то может иметь место любая последовательность выполнения операций во времени. Если сначала будут выполнены все операции процесса Р1, а уже потом -- все операции процесса Р2 (или, наоборот, сначала операции 4-6, а затем -- операции 1-3), то в итоге переменная X получит значение, равное Х+2 .

Однако, если в промежуток времени между выполнением операций 1 и 3 будет выполнена хотя бы одна из операций 4-6, то значение переменной X после выполнения всех операций будет не (Х+2), а (Х+1).

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

В качестве второго примера приведем пару процессов, которые изменяют различные поля записей служащих какого-либо предприятия. Пусть процесс АДРЕС изменяет домашний адрес служащего, а процесс СТАТУС -- его должность и зарплату. Пусть каждый процесс копирует всю запись СЛУЖАЩИЙ в свою рабочую область.

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

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

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

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

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

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

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

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

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

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

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

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

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

Независимые и взаимодействующие вычислительные процессы - Независимые и взаимодействующие вычислительные процессы

Похожие статьи