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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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