Алгоритмы рассылки
В предыдущем разделе мы показали, как рассылать информацию по сети, имеющей структуру графа. В большинстве локальных сетей процессоры разделяют такой канал взаимодействия, как 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). Например, их можно использовать для решения таких задач взаимного исключения, как блокировка файлов или записей базы данных. Можно использовать тот же базовый подход (рассылка сообщений и упорядоченные очереди) для решения других задач; некоторые из них описаны в исторической справке и упражнениях.
Если алгоритмы рассылки используются для принятия синхронизирующих решений, в этом должны участвовать все процессы. Например, процесс должен "услышать" все остальные процессы, чтобы определить, когда сообщение полностью подтверждается. Это значит, что алгоритмы рассылки не очень хорошо масштабируются для взаимодействия большого числа процессов и их нужно модифицировать, чтобы сделать устойчивыми к ошибкам.
