Вычислительные процессы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

¨ ни один процесс не должен находиться в своей критической секции бесконеч­но долго;

¨ ни один процесс не должен ждать бесконечно долго входа в свой критический интервал. В частности:

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

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

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

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