Основы многопоточного и распределенного программирования

       

Алгоритмы рассылки


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

Пусть Т[п] — массив процессов, a ch[n] — массив каналов (по одному на процесс). Процесс Т [ i ] рассылает сообщение т, выполняя оператор broadcast ch(m);

При выполнении broadcast в каждый канал ch[i], включая канал процесса T[i], поме­щается копия сообщения т. Получается тот же результат, что и при выполнении кода

Глава 9. Модели взаимодействия процессов                                                                    349

со  [i = I to n] send ch[i](m);

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

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

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


9.5.1. Логические часы и упорядочение событий

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

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

Хотя причинно связанные события вполне упорядочены, все множество событий в распре­деленной программе упорядочено лишь частично. Причина в том, что одна последовательность событий, не связанная с другой (например, операции взаимодействия между различными мно­жествами процессов), может происходить после нее, перед ней или одновременно с ней.

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




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

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

350                                                                            Часть 2. Распределенное программирование

ная синхронизация невозможна. Существуют алгоритмы синхронизации часов (см. истори­ческую справку) для поддержания "достаточно хорошего", но не абсолютного их согласова­ния. Итак, нам нужен способ имитации физических часов.

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

Правила изменения значения логических часов. Пусть А— процесс с логическими часами 1с. Процесс А обновляет значение 1с так:

1.  передавая или рассылая сообщение, А присваивает его метке времени текущее значе­ние переменной 1с и увеличивает 1с на 1;

2.  получая сообщение с меткой времени ts, А присваивает переменной 1с максимальное из значений Icnts+lH затем увеличивает 1с на 1.

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

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


Значение часов для события передачи сообщения — это метка времени в сообще­нии, т.е. локальное значение переменной 1с в начале передачи. Для события получения — это значение 1с после того, как оно установлено равным максимальному из значений 1с и ts+1, но до того, как оно будет увеличено получающим процессом.

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

9.5.2. Распределенные семафоры

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

Семафор s обычно представляется неотрицательным целым числом. Выполнение опера­ции Р (s) задерживается, пока значение s не станет положительным, а затем оно уменьшает­ся. Выполнение операции V(s) увеличивает значение семафора. Таким образом, число за­вершенных операций Р в любой момент времени не больше, чем число завершенных опера­ций V плюс начальное значение s. Поэтому для реализации семафора необходимы способы подсчета операций Р и V и задержки операций Р. Кроме того, процессы, "разделяющие" се­мафор, должны взаимодействовать так, чтобы поддерживать инвариант семафора s >= О, даже если состояние программы является распределенным.

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



Глава 9. Модели взаимодействия процессов                                                                        351

правилами. Для имитации выполнения операций Р и V процесс рассылает сообщение всем пользовательским процессам, в том числе и себе. Сообщение содержит идентификатор про­цесса, дескриптор типа операции (POP или vop) и метку времени. Меткой времени каждой копии сообщения является текущее значение часов 1с.

Получив сообщение pop или VOP, процесс сохраняет его в своей очереди mq. Эта очередь поддерживается отсортированной в порядке возрастания меток времени сообщений; сооб­щения с одинаковыми метками сортируются по идентификаторам отославших их процессов. Допустим пока, что каждый процесс получает все сообщения в порядке их рассылки и воз­растания их меток времени. Тогда каждый процесс будет точно знать порядок передачи со­общений POP и VOP, сможет подсчитать количество соответствующих операций Р и v и под­держивать истинным инвариант семафора.

К сожалению, операция broadcast не является неделимой. Сообщения, разосланные двумя разными процессами, могут быть получены другими процессами в разных порядках. Более того, сообщение с меньшей меткой времени может быть получено после сообщения с большей меткой. Однако разные сообщения, разосланные одним и тем же процессом, будут получены другими процессами в порядке их рассылки этим процессом, и у сообщений будут возрастающие метки времени. Эти свойства следуют из таких фактов: 1) выполнение опера­ции broadcast — это то же, что параллельное выполнение операций send, которое, как мы считаем, обеспечивает упорядоченную и надежную доставку сообщения, 2) процесс увеличи­вает значение своих логических часов после каждого события взаимодействия.

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


В этот момент сообщение m становится полностью подтвержденным. Кроме того, если сообщение m полностью подтверждено, то и все сообщения, находящиеся перед ним в очереди mq, тоже полностью подтверждены, поскольку их метки вре­мени еще меньше. Поэтому часть очереди mq, содержащая полностью подтвержденные сообще­ния, является стабильным префиксом: в нее никогда не будут вставлены новые сообщения.

При каждом получении сообщения POP или VOP процесс должен рассылать подтвер­ждающее сообщение (дек), чтобы его получили все процессы. Сообщения АСК имеют обыч­ные метки времени, но не добавляются в очереди сообщений процессов. Их используют про­сто для того, чтобы определить момент полного подтверждения обычного сообщения из оче­реди mq. (Если не использовать сообщений АСК, процесс не сможет определить, что сообщение полностью подтверждено, пока не получит более поздних сообщений POP или VOP от всех остальных процессов. Это замедлит работу алгоритма и приведет к блокировке, если какой-нибудь пользователь не захочет выполнить операции Р или V.)

Чтобы реализация распределенных семафоров была завершенной, каждый процесс ис­пользует локальную переменную s для представления значения семафора. Получая сообще­ние аск, процесс обновляет стабильный префикс своей очереди сообщений mq. Для каждого сообщения VOP процесс увеличивает значение s и удаляет это сообщение. Затем процесс просматривает сообщения POP в порядке возрастания меток времени. Если s > 0, процесс уменьшает значение s и удаляет сообщение POP. Таким образом, каждый процесс поддержи­вает истинность следующего предиката, который является инвариантом цикла процесса.

DSEM-.   s  >= 0 л mq упорядочена по меткам времени в сообщениях

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



352                                                                            Часть 2. Распределенное программирование

Алгоритм распределенных семафоров представлен в листинге 9.11. Пользовательские про­цессы — это обычные прикладные процессы. У каждого пользователя есть один вспомогатель­ный процесс; вспомогательные процессы взаимодействуют друг с другом для реализации опера­ций р и V. Пользовательский процесс инициирует операцию Р или V, связываясь со своим вспо­могательным процессом (помощником). Выполняя операцию Р, пользователь ждет, пока его помощник не разрешит ему продолжать. Каждый помощник рассылает сообщения POP, VOP и аск другим помощникам и управляет локальной очередью сообщений по описанному выше алгоритму. Все сообщения для помощников передаются или рассылаются по массиву каналов se-mop. Для добавления метки времени к сообщениям все процессы поддерживают локальные часы.



Глава 9. Модели взаимодействия процессов                                                                            353

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

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


Содержание раздела