Тема 5: Организация параллельных взаимодействующих вычислений

План лекции:

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

2. Средства синхронизации и связи взаимодействующих вычислительных процессов

 

Литература:

А.В.Гордеев Операционные системы: учебник. 2007. 416с. Стр.209 –246

 

 

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

 

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

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

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

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

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

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

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

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

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

Таблица 5.1. Пример конкурирующих процессов Номер оператора Процесс Р1 Номер оператора Процесс Р2   R1: = Х   R2: = X   R1: = R1 + 1   R2: = R2 + 1   X: = R1   X: = R2

 

Поскольку при мультипрограммировании процессы могут иметь различные ско­рости исполнения, то может иметь место любая последовательность выполнения операций во времени. Например, если сначала будут выполнены все операции про­цесса Р1, а уже потом — все операции процесса Р2 (рис. 5.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;

------------------------------------------------------------- ----------------------► Время

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

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

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

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

----------------------------------------------------------------- ►Время

Рис. 5.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. И в этом случае мы получим неверное значение времени.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

Лекция 9

План лекции:

3. Средства синхронизации и связи взаимодействующих вычислительных процессов.

3.1 Блокировка памяти

3.2 Синхронизация процессов с помощью операций проверки и установки

3.3 Семафорные примитивы Дейкстры

3.4 Мониторы Хоара

 

Литература:

А.В.Гордеев Операционные системы: учебник. 2007. 416с. Стр.209 –246

 

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

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

-блокировка памяти,

-специальные команды типа «проверка и установка»

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

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

5.2.1 Использование блокировки памяти при синхронизации параллельных процессов

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

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

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