Алгоритмы передачи маркера
В этом разделе описывается передача маркера — еще одна модель взаимодействия процессов. Маркер — это особый тип сообщений, который можно использовать для передачи разрешения или сбора информации о глобальном состоянии. Использование маркера для передачи разрешения иллюстрируется простым распределенным решением задачи критической секции. Сбор информации о состоянии демонстрируется в процессе разработки двух алгоритмов, позволяющих определить, завершились ли распределенные вычисления. Еще один пример приводится в следующем разделе (см. также историческую справку и упражнения).
9.6.1. Распределенное взаимное исключение
Задача о критической секции (КС) возникла в программах с разделяемыми переменными. Однако она встречается и в распределенных программах, если какой-нибудь разделяемый ресурс используется в них с исключительным доступом. Это может быть, например, линия связи со спутником. Кроме того, задача КС обычно является частью большей задачи, такой как обеспечение согласованности распределенного файла или системы баз данных.
Первый способ решения задачи КС — использовать активный монитор, разрешающий доступ к КС. Для многих задач вроде реализации блокировки файлов это самый простой и эффективный метод. Второй способ решения этой задачи — использовать распределенные семафоры, реализованные так, как описано в предыдущем разделе. Этот способ приводит к децентрализованному решению, в котором все процессы одинаковы, но для каждой операции с семафором необходим обмен большим количеством сообщений, поскольку операция broadcast должна быть подтверждена.
Здесь задача решается третьим способом — с помощью кольца передачи маркера (token nng). Это децентрализированное и справедливое решение, как и решение с использованием распределенных семафоров, но оно требует обмена намного меньшим количеством сообщений. Кроме того, базовый метод можно обобщить для решения других задач синхронизации.
Пусть User [ 1: п ] — это набор прикладных процессов, содержащих критические и некритические секции.
Как всегда, нужно разработать протоколы входа и выхода, которые выполняются перед КС и после нее. Протоколы должны обеспечивать взаимное исключение, отсутствие блокировок и ненужных задержек, а также возможность входа (справедливость).
Поскольку у пользовательских процессов есть своя работа, нам не нужно, чтобы они занимались передачей маркера. Используем набор дополнительных процессов Helper [ 1: п], по одному для каждого пользовательского процесса. Вспомогательные процессы образуют кольцо (рис. 9.3). Маркер циркулирует от процесса Helper [ 1 ] к процессу Helper [2 ] и так далее до процесса Helper [n], который передает его процессу Helper [1]. Получив маркер,
354 Часть 2. Распределенное программирование
Helper [i] проверяет, не собирается ли входить в КС его клиент User[i]. Если нет, Helper [ i ] передает маркер. Иначе Helper [ i ] сообщает процессу User [ i ], что он может войти в КС, и ждет, пока процесс User [ i ] не выйдет из нее. После этого Helper [ i ] передает маркер. Таким образом, вспомогательные процессы работают совместно, чтобы обеспечить постоянное выполнение следующего предиката.
Решение в листинге 9.12 является справедливым (при условии, что процессы когда-нибудь выходят из критических секций). Причина в том, что маркер циркулирует непрерывно, и как только он оказывается у процесса Helper[i], процесс Userfi] получает разрешение войти в КС (если хочет). Фактически то же самое происходит и в физической сети с передачей маркера. Однако при программной передаче маркера, вероятно, лучше добавить некоторую задержку во вспомогательных процессах, чтобы он двигался по кольцу медленней. (В разделе 9.7 представлен еще один алгоритм исключения на основе передачи маркера. Там маркеры не циркулируют непрерывно.)
Данный алгоритм предполагает отсутствие сбоев и потерь маркера. Поскольку управление распределено, алгоритм можно изменить, чтобы он стал устойчивым к сбоям.
Алгоритмы восстановления потерянного маркера и использования двух маркеров, циркулирующих в противоположных направлениях, описаны в исторической справке.
9.6.2. Как определить окончание работы в кольце
Окончание работы последовательной программы обнаружить легко. Так же легко определить, что параллельная программа завершилась на одном процессоре — каждый процесс завершен или заблокирован и нет ожидающих операций ввода-вывода. Но не просто обнаружить, что закончилась распределенная программа, поскольку ее глобальное состояние не видно ни одному процессору. Кроме того, даже если все процессоры бездействуют, могут существовать сообщения, передаваемые между ними.
Существует несколько способов обнаружить завершение распределенных вычислений. В этом разделе разрабатывается алгоритм, основанный на передаче маркера при условии, что все взаимодействие между процессами происходит по кольцу. В следующем разделе этот алгоритм обобщается для полного графа связей. Другие подходы описаны в исторической справке и упражнениях.
Пусть в распределенных вычислениях есть процессы (задачи) Т[1.-п] и массив каналов взаимодействия ch [1 :п]. Пока предположим, что процессы образуют кольцо, по которому проходит их взаимодействие. Процесс T[i] получает сообщения только из своего канала ch[i] и передает их только в следующий канал ch[i%n+l]. Таким образом, Т[1] передает сообщения только Т [ 2 ], Т [ 2 ] — только Т [ 3 ] и так далее до Т [n ], передающего сообщения Т[1]. Как обычно, предполагается, что сообщения от каждого процесса его сосед по кольцу получает в порядке их передачи.
В любой момент времени процесс может быть активным или простаивать (бездействовать). Вначале активны все процессы. Процесс бездействует, если он завершен или приостановлен оператором получения сообщения. (Если процесс временно приостанавливается, ожидая окончания операции ввода-вывода, он считается активным, поскольку он еще не завершен и через некоторое время снова будет запущен.) Получив сообщение, бездействующий процесс становится активным.
Таким образом, распределенные вычисления закончены, если выполняются следующие два условия:
DTERM: все процессы бездействуют л нет передаваемых сообщений
Сообщение передается (находится в пути), если оно уже отправлено, но еще не доставлено вканал назначения. Второе условие обязательно, поскольку доставленное сообщение может запустить приостановленный процесс.
356 Часть 2. Распределенное программирование
Наша задача — перенести алгоритм определения окончания работы на любые распределенные вычисления, основываясь только на предположении о том, что процессы в вычислении взаимодействуют по кольцу. Окончание — это свойство глобального состояния, объединяющего состояния отдельных процессов и содержание каналов передачи сообщений. Таким образом, чтобы определить момент окончания вычислений, процессы должны взаимодействовать.
Пусть один маркер передается по кольцу в специальных сообщениях, не являющихся частью вычислений. Процесс, удерживающий маркер, передает его дальше и становится бездействующим. (Если процесс закончил свои вычисления, он бездействует, но продолжает участвовать в алгоритме обнаружения завершения работы.)
Процессы передают маркер, используя то же кольцо каналов связи, что и в самих вычислениях. Получая маркер, процесс знает, что отправитель в момент передачи маркера бездействовал. Кроме того, получая маркер, процесс бездействует, поскольку был задержан получением сообщения из канала, и не станет активным до тех пор, пока не получит обычное сообщение, являющееся частью распределенных вычислений. Таким образом, получая маркер, процесс передает его соседу и ждет получения еще одного сообщения из своего канала.
Вопрос в том, как определить, что вычисления завершились. Когда маркер совершает полный круг по кольцу взаимодействия, нам точно известно, что в этот момент все процессы бездействуют. Но как владелец маркера может определить, что все остальные процессы по-прежнему бездействуют и ни одно сообщение не находится в пути к получателю?
Допустим, что вначале маркер находится у процесса т [ 1 ]. Когда Т [ 1 ] становится бездействующим, он инициирует алгоритм обнаружения окончания работы, передавая маркер процессу Т [2]. Возвращение маркера к Т[1] означает, что вычисления закончены, если Т [ 1 ] был непрерывно бездействующим с момента передачи им маркера процессу Т [ 2 ]. Дело в том, что маркер проходит по тому же кольцу, по которому идут обычные сообщения, а все сообщения доставляются в порядке их отправки. Таким образом, если маркер возвращается к т [ 1 ], значит, ни одного обычного сообщения уже не может быть нигде в очереди или в пути. По сути, маркер "очищает" каналы, проталкивая перед собой все обычные сообщения.
Уточним алгоритм. Во-первых, с каждым процессом свяжем цвет: синий (холодный), если процесс бездействует, и красный (горячий), если он активен. Вначале все процессы активны, поэтому окрашены красным. Получая маркер, процесс бездействует, поэтому становится синим, передает маркер дальше и ждет следующее сообщение. Получив позже обычное сообщение, процесс станет красным. Таким образом, процесс, окрашенный в синий цвет, передал маркер дальше и остался бездействующим.
Во-вторых, с маркером свяжем значение, которое показывает количество пустых каналов, если Т[1] остается бездействующим. Пусть это значение хранится в переменной token. Становясь бездействующим, Т [ 1 ] окрашивается в синий цвет, присваивает token значение О и передает маркер процессу Т [ 2 ]. Получая маркер, Т [ 2 ] бездействует (при этом канал сп[2] может быть пустым). Поэтому Т [2] становится синим, увеличивает значение token до 1 и передает маркер процессу Т [ 3 ]. Все процессы Т [ i ] по очереди становятся синими и увеличивают token перед тем, как передать дальше.
Описанные правила передачи маркера перечислены в листинге 9.13. Их выполнение гарантирует, что условие RING является глобальным инвариантом. Инвариантность RING следует из того, что, если процесс Т [1] окрашен в синий цвет, значит, с момента передачи маркера никаких обычных сообщений он не передавал, и, следовательно, ни в одном из каналов, пройденных маркером, нет обычных сообщений.
Кроме того, все соответствующие процессы остались бездействующими с тех пор, как получили маркер. Таким образом, если Т[1] остался синим, снова получив маркер, то все остальные процессы тоже окрашены в синий цвет, а каналы — пусты. Следовательно, т [ 1 ] может объявить, что вычисления закончены.
9.6.3. Определение окончания работы в графе
В предыдущем разделе предполагалось, что все взаимодействия происходят по кольцу. В общем случае структура взаимодействия распределенной программы образует произвольный ориентированный граф. Узлы графа представляют процессы в вычислениях, а дуги — пути взаимодействия. Два процесса связаны дугой, если первый из них передает данные в канал, из которого их считывает второй.
Предположим, что граф связей является полным, т.е. между любыми двумя процессами есть одна дуга. Как и ранее, есть п процессов Т [ 1: n ] и каналов ch [ 1: n ], и каждый Т [ i ] получает данные из собственного канала ch [ i ]. Однако теперь каждый процесс может посылать сообщения только в канал ch [ i ].
Учитывая вышесказанное, расширим предыдущий алгоритм определения окончания работы. Полученный в результате алгоритм можно использовать в любой сети, имеющей прямые линии взаимодействия между любыми двумя процессорами. Его легко распространить на произвольные графы взаимодействия и многоканальные связи (см. упражнения).
Определить окончание работы в полном графе сложнее, чем в кольце, поскольку сообщения могут идти по любой дуге Рассмотрим, например, полный граф из трех процессов (рис. 9.4). Пусть процессы передают маркер только от Т [ 1 ] к Т [ 2 ], затем к Т [3 ] и обратно к т [ 1 ]. Допустим, процесс т [ 1 ] получает маркер и становится бездействующим; следовательно, он передает маркер процессу Т [2}. Становясь бездействующим, Т [2 ] передает маркер Т [ 3 ]. Но перед получением маркера Т [ 3 ] может передать процессу Т [ 2 ] обычное сообщение. Таким образом, когда маркер возвращается к Т [ 1 ], нельзя сделать вывод о том, что вычисления завершены, даже если т [ 1 ] оставался непрерывно бездействующим.
Основным в кольцевом алгоритме (см. листинг 9.13) является то, что все взаимодействия проходят по кольцу, поэтому маркер "проталкивает" обычные сообщения, проходя все дуги кольца. Этот алгоритм можно обобщить для полного графа, обеспечив проход маркера по каждой дуге (маркер должен многократно посетить каждый процесс). Если каждый процесс остается непрерывно бездействующим с момента предыдущего получения маркера, то можно прийти к выводу, что вычисления завершены.
Как и раньше, процессы окрашиваются в красный или синий цвет (вначале — в красный). Получая обычное сообщение, процесс становится красным, а получая маркер, — блокируется в ожидании следующего сообщения из своего входного канала. Поэтому процесс окрашивается в синий цвет (если он еще не был синим) и передает маркер. (Как и раньше, заканчивая свои обычные вычисления, процесс продолжает обрабатывать сообщения с маркером.)
358 Часть 2 Распределенное программирование
Любой полный граф содержит цикл, в который входят все его дуги (некоторые узлы могут включаться несколько раз). Пусть С — цикл графа взаимодействия, а nс — его длина. Каждый процесс отслеживает порядок, в котором исходящие из него дуги встречаются в цикле с. Получив маркер по одной дуге цикла с, процесс передает его по следующей. Это гарантирует, что маркер пройдет по каждой дуге графа взаимодействия.
Как и раньше, маркер имеет значение, говорящее о количестве пройденных бездействующих процессов и, следовательно, каналов, которые могут быть пустыми. Но из приведенного выше примера видно, что в полном графе бездействующий процесс снова может стать активным, даже если бездействующим остается процесс Т [ 1 ]. Таким образом, чтобы делать вывод об окончании вычислений, нужен другой набор правил передачи маркера и другой глобальный инвариант.
Маркер начинает движение с любого процесса и имеет начальное значение 0. Когда этот процесс впервые становится бездействующим, он окрашивается в синий цвет и передает маркер по первому ребру цикла С.
Получив маркер, процесс совершает действия, представленные в листинге 9.14. Если при получении маркера процесс окрашен в красный цвет (с момента последнего получения маркера он был активным), он становится синим и присваивает маркеру token значение О перед тем, как передать его по следующему ребру цикла С. Таким образом, алгоритм обнаружения окончания программы перезапускается. Но если при получении маркера процесс окрашен в синий цвет, т.е. с момента последнего получения маркера непрерывно бездействовал, то перед передачей маркера процесс увеличивает его значение.
Глава 9 Модели взаимодействия процессов 359
числения закончены. В этот момент известно, что последние пс каналов, пройденные маркером, были пустыми. Поскольку бездействующий процесс только передает маркер, а значение маркера увеличивает, только если бездействовал с момента прошлого получения маркера, можно наверняка сказать, что все каналы пусты и все процессы бездействуют. В действительности все вычисления завершились уже к тому моменту, когда маркер начал свой последний проход по графу. Но ни один процесс не может это установить до тех пор, пока маркер не сделает еще один полный цикл по графу, чтобы убедиться в том, что все процессы остались бездействующими и все каналы — пустыми. Таким образом, после завершения всех вычислений маркер должен пройти по циклу как минимум дважды: на первом проходе процессы становятся синими, а на втором — проверяется, не поменяли ли они цвет.