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

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

210_________ Глава 7. Организация параллельных взаимодействующих вычислений

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

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

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

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

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

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

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

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

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

Таблица 7.1. Пример конкурирующих процессов

Номер оператора Процесс Р1 Номер оператора Процесс Р2

1 R1:=X 4 R2:=X

2 R1:=R1 + 1 5 R2:=R2+1

3 X:=R1 6 X:=R2

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

Р1: (1) R1:=X; (2) R1:=R1+1; (3) X:=R1;

Р2: (4) R2:=X; (5) R2:=R2+1; (6)X:=R2;

Время Рис.7.1. Первый вариант развития событий при выполнении процессов

¹ Ri — это просто имя переменной для процесса с номером i.

212________ Глава 7. Организация параллельных взаимодействующих вычислений

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

P1:(1)R1:=X; (2)R1:=R1+1; (3)X:=R1;

Р2: (4)R2:=X; (5)R2:=R2+1; (6)X:=R2;

Время Рис. 7.2. Второй вариант развития событий при выполнении процессов

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

В качестве второго примера рассмотрим ситуацию, которая еще совсем недавно была достаточно актуальной для первых персональных компьютеров. Пусть на персональном компьютере с простейшей однопрограммной операционной систе­мой (типа MS DOS) установлена некоторая резидентная программа с условным названием TIME, которая по нажатию комбинации клавиш (например, Ctrl+T) вос­производит на экране дисплея время в виде 18:20:59, и допустим, что значения переменных, обозначающих час, минуты и секунды, равны 18,20 и 59 соответствен­но, причем вывод на дисплей осуществляется справа налево (сначала секунды, за­тем минуты и, наконец, часы). Пусть сразу же после передачи программой TIME на дисплей информации «59 секунд» генерируется прерывание от таймера, и зна­чение времени обновляется: 18:21:00.

После этого программа TIME, прерванная таймером, продолжит свое выполне­ние, и на дисплей будут выданы значения: минуты (21), часы (18). В итоге на экра­не мы увидим: 18:21:59.

Рассмотрим теперь несколько иной случай развития событий обновления значе­ний времени по сигналу таймера. Если программа ведения системных часов после вычислений количества секунд 59 + 1 = 60 и замены его на 00 прерывается от на­жатия клавиш Ctrl+T, то есть программа не успевает осуществить пересчет количе­ства минут, то время, индицируемое на дисплее, станет равным 18:20:00. И в этом случае мы получим неверное значение времени.

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

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

Изменения, выполненные тем из процессов, который первым запишет скорректи­рованную запись назад в файл СЛУЖАЩИЕ, будут утеряны, и, возможно, никто об этом не узнает.

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

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

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

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

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

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

¹ Совокупность однородных динамически распределяемых объектов, например блоков памяти одина­ковой длины.

214________ Глава 7. Организация параллельных взаимодействующих вычислений

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

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

Обеспечение взаимного исключения является одной из ключевых проблем парал­лельного программирования. При этом можно перечислить требования к крити­ческим секциям [17, 54].

- В любой момент времени только один процесс должен находиться в своей кри­
тической секции.

- Ни один процесс не должен бесконечно долго находиться в своей критической секции.

- Ни один процесс не должен бесконечно долго ожидать разрешение на вход в свою критическую секцию. В частности:

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

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

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

Средства синхронизации и связи взаимодействующих процессов_____________ 215

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