Software & Systems

@Сеть передачи данных RapidIO [1] состоит из связанных между собой оконечных устройств (ОУ, или просто устройств) и коммутаторов. Коммутаторы образуют коммуникационную среду, обеспечивающую прозрачную доставку пакетов между ОУ. В сети RapidIO невозможна доставка пакетов между двумя узлами по нескольким маршрутам, поэтому сообщения, отправленные одним устройством одному адресату, доходят в соответствии с порядком их отправки. Однако пакет, отправленный одним устройством, может дойти до адресата раньше, чем пакет, отправленный до него с другого устройства.

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

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

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

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

Для упрощения реализации исключительного доступа каждый коммутатор содержит особый регистр блокировки [2] (Host Base Device ID Lock CSR, или lock), для которого характерно следующее поведение. Если регистр находится в исходном (сброшенном) состоянии, в него можно записать любое значение. После этого регистр можно сбросить обратно в исходное состояние повторной записью содержащегося в нем значения; попытка записи любого другого значения при этом игнорируется. Несмотря на свое название, регистр блокировки не препятствует доступу к коммутатору со стороны любых устройств, какое бы значение он ни содержал. Устройствам доступны и другие регистры коммутатора, но все они, за исключением регистра метки (Component Tag CSR, или tag), имеют особое назначение и не могут использоваться для записи в них произвольных значе- ний [2]. Бит Discovered в регистре Port General Control CSR [3] коммутатора устанавливается ОУ, успешно настроившим коммутатор. Анализируя значение этого бита, ОУ принимают решение о необходимости настройки коммутатора.

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

Решим следующую задачу. Пусть имеется N оконечных устройств с уникальными целыми положительными идентификаторами, имеющих доступ к двум регистрам одного коммутатора –блокировки и метки. Каждое ОУ выполняет программу, в которую входят фрагменты, называемые критической секцией и некритической секцией. Любое ОУ может выйти из строя в какой-то момент в процессе своей работы.

Предположим, что верны следующие утверждения.

1.   Время выполнения критической секции ограничено сверху.

2.   В случае выхода из строя ОУ просто прекращает свою работу, не выполняя при этом действий, не предусмотренных программой.

3.   Никакие два запроса на чтение или запись регистров коммутатора не выполняются одновременно. Относительный порядок запросов, отправленных одним ОУ, сохраняется.

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

Предположение 2 не допускает возникновения такого распространенного вида отказа, как перезагрузка.

Был разработан алгоритм программы ОУ, который при выполнении перечисленных предположений удовлетворяет:

·     требованию взаимного исключения: никакие два ОУ не могут выполнять критическую секцию одновременно;

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

Эти требования допускают, что некоторое ОУ, желающее выполнить критическую секцию, может ожидать своей очереди бесконечно.

Представим разработанный алгоритм.

0     oldlock = -1

Lock:

1     mylock = NewMylock()

2     WRITE(lock, mylock)

3     READ(lock, lk)

4     if lk == oldlock

5         goto Force

6     if lk == mylock

7         goto Crit

8     if lk == EMPTY

9         goto Lock

10    oldlock = lk

11    WAIT(ReleaseTimeout)

12    WRITE(tag, 0)

13    goto Lock

Force:

14    READ(tag, k)

15    if k < myid

16        WRITE(tag, myid)

17        goto Force

18    if k > myid

19        WAIT(UnlockTimeout)

20        READ(lock, lk)

21        if lk == oldlock

22            WRITE(tag, 0)

23            goto Force

24        else

25            goto Lock

26    if k == myid

27        WRITE(lock, oldlock)

28        goto Lock       

Crit:

29    CRITICAL_SECTION

Release:

30    WRITE(lock, mylock)

Noncrit:   

31    NONCRITICAL_SECTION

32    oldlock = -1

33    goto Lock

Функция NewMylock() при каждом вызове возвращает целое значение, отличное от текущего содержимого регистра блокировки, а также от значений переменных mylock и oldlock на всех остальных ОУ. Размер регистра блокировки должен быть достаточным для хранения любого такого значения.

Попытка получения доступа к коммутатору (блокировки или захвата коммутатора) выражается в том, что ОУ на шаге 2 пытается записать в регистр блокировки значение mylock, после чего на шаге 3 читает фактическое значение регистра. Если было прочитано значение, равное mylock, то блокировка успешно получена и ОУ может переходить к выполнению критической секции. Сня- тие блокировки производится повторной записью mylock в регистр (шаг 30), что возвращает его в исходное состояние.

Невыполнение устройством ожидаемого действия в течение определенного срока позволяет утверждать, что устройство вышло из строя [4]. В данном случае в силу предположения 1 таким действием является сброс регистра блокировки. По истечении срока регистр блокировки должен быть сброшен, чтобы система могла продолжить работу. На шагах 3–4 ОУ обнаруживает, что запомненное в переменной oldlock на шаге 10 значение все еще содержится в регистре блокировки по истечении срока ReleaseTimeout, следовательно, блокирующее коммутатор ОУ вышло из строя и необходимо принудительно сбросить установленную им блокировку. Однако если четное количество устройств попытается сбросить содержимое регистра, это приведет к тому, что в нем будет восстановлено прежнее значение. Следовательно, необходим механизм координации действий ОУ, пытающихся сбросить регистр.

Шаги 14–28 реализуют механизм определения ОУ с наибольшим идентификатором с использованием регистра метки. Этому ОУ предоставляется возможность окончательно сбросить регистр блокировки на шаге 27, в то время как остальные ОУ не смогут ему помешать, находясь в состоянии ожидания на шаге 19. Величина UnlockTimeout выбирается таким образом, чтобы превышать максимально возможное время записи нового значения в регистр блокировки устройством с максимальным идентификатором. Если ОУ выходит из состояния ожидания на шаге 19 и обнаруживает, что регистр блокировки содержит старое значение, значит, ОУ с максимальным идентификатором вышло из строя и необходимо начать процесс с начала.

Доказательство корректности алгоритма. Определим согласно [5] конфигурацию системы  как совокупность значений регистров коммутатора, множества отправленных, но еще не доставленных сообщений и состояний всех ОУ. Выполнением системы  назовем последовательность сменяющих друг друга конфигураций системы, не противоречащую алгоритму, выполняемому устройствами. В данной работе более строгое определение конфигурации и выполнения системы не требуется; важно лишь то, что в ходе выполнения системы, при котором каждое ОУ следует описанному алгоритму, на коммутаторе происходят события – атомарные действия по записи или чтению регистра метки или регистра блокировки. Обозначим пятеркой  событие, произошедшее на коммутаторе при выполнении системы  в момент  в результате отправки -м устройством запроса на шаге  алгоритма, где вместо  в зависимости от регистра и выполняемого действия указывается:  – запись в регистр метки;  – чтение из регистра метки;  – запись в регистр блокировки;  – чтение из регистра блокировки. Множество событий, отличающихся только значением  и имеющих одинаковые , ,  и , определим как . Обозначим  тот факт, что в некотором выполнении  событие  произошло на коммутаторе до события  (то есть  и ).

Последовательность событий, происходящих на коммутаторе при данном выполнении системы, или просто последовательность, – это множество событий, вполне упорядоченное по отношению . Обозначим  последовательность, включающую все события, произошедшие на коммутаторе при выполнении системы . Последовательность  называется допустимой, если возможно такое выполнение , что . Иными словами, допустимая последовательность не противоречит алгоритму. Допустимую последовательность   будем называть полной, если для любых  не существует такой допустимой последовательности , что  и . Это означает, что для некоторых двух событий полная последовательность включает все события, происходящие между ними. Последовательностью без обнуления метки будем называть такую допустимую последовательность  для выполнения системы , что найдется полная последовательность , не содержащая событий из множеств  и  для любых .

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

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

1.   Для любого события  существует парное ему событие .

2.   В результате события , парного некоторому событию записи, было прочитано значение .

Теорема 1. В любом выполнении системы никакие два ОУ не могут выполнять критическую секцию одновременно.

Доказательство. Допустим, при выполнении системы  в некоторый момент существуют два ОУ –  и , которые одновременно выполняют КС. Так как в КС можно попасть, только выполнив шаг 7, то на шаге 6 каждое из этих ОУ убедилось, что значение, прочитанное из регистра блокировки на шаге 3, совпадает со значением локальной переменной mylock, попытка записи которого в регистр блокировки была предпринята на шаге 2. Следовательно, эти попытки записи со стороны  и  оказались успешными. Попытка записи в регистр блокировки является успешной только тогда, когда регистр находится в сброшенном состоянии. Пусть ОУ  первым осуществило запись в регистр. Тогда имела место следующая последовательность событий:

1)  ;

2)  ;

3)  событие, сбрасывающее регистр блокировки;

4)  ;

5)  .

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

Учитывая предположение 1 об ограниченности времени выполнения критической секции, а также то, что между успешной записью в регистр блокировки в результате выполнения шага 2 и переходом к критической секции на шаге 15 устройство выполняет фиксированное число шагов (каждый из которых по предположению 4 выполняется за ограниченное время), можно выбрать значение ReleaseTimeout, превышающее максимальное время, которое может пройти с момента успешной записи в регистр блокировки до момента сброса регистра одним ОУ. В таком случае принудительный сброс блокировки будет выполняться только при выходе устройства из строя.

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

Лемма 1. Для любого выполнения системы   в любой полной последовательности без обнуления метки  между двумя событиями из множества  найдется событие из множества .

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

По свойству 1 парных событий для этих двух событий записи существуют парные им события чтения .

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

Лемма 2. Для любого выполнения системы  любая полная последовательность без обнуления метки  может включать не более  событий записи в регистр метки, где  – количество ОУ в системе.

Доказательство. Для случая  лемма выполняется тривиально. Докажем ее истинность для всех  по индукции. Предположим, что лемма выполняется для случая , и покажем, что в этом случае она верна и для .

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

Лемма 3. Для любого выполнения системы  любая полная последовательность без обнуления метки  может включать не более  событий из , где  – количество ОУ в системе.

Доказательство. Из леммы 2 следует, что количество событий записи в регистр метки в любой полной последовательности без обнуления метки  не может превышать , что дает  интервалов времени, в каждом из которых регистр метки содержит идентификатор одного из ОУ. Рассмотрим интервал, ограничиваемый событиями  и , причем, согласно лемме 1, . На протяжении всего этого интервала в регистре метки содержится .

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

Рассмотрим возможные состояния регистра блокировки в начале интервала .

1.   Регистр блокировки содержит идентификатор вышедшего из строя устройства. Тогда устройство  сбросит регистр блокировки при первом выполнении шага 27.

2.   Регистр блокировки сброшен. Тогда устройство  сбросит регистр блокировки при втором выполнении шага 27.

В первом случае в интервале  может произойти не более  событий из , и при выполнении в интервале  такого числа событий к началу интервала  регистр блокировки будет сброшен. Во втором случае в интервале  может произойти не более  таких событий, и при этом в начале интервала  регистр также будет сброшен. Таким образом, в случае выполнения максимального количества событий записи в интервале  в интервале  может быть выполнено не более  событий записи в регистр блокировки. Если же одно событие записи, которое могло произойти в интервале , было отложено, то в интервале  может быть выполнено не более  событий. Следовательно, откладывание одного события из интервала  уменьшает максимальное число событий в интервале  на 1.

Очевидно, что в каждом интервале может быть отложено не более одного события, и из последнего интервала отложить событие нельзя. Пусть на протяжении всей последовательности было отложено  событий. Тогда общее количество событий из  во всей последовательности составит максимальное число событий в первом интервале. В зависимости от изначального состояния регистра блокировки оно может составлять 1 или 2. Следовательно, можно утверждать, что

Таким образом, лемма верна.

Теорема 2. Если в некоторый момент хотя бы одно из  работоспособных в системе ОУ желает выполнить КС (вошло в состояние Lock), то через ограниченное сверху количество обращений к регистрам метки и блокировки коммутатор будет захвачен одним из ОУ.

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

Если же коммутатор был захвачен другим устройством, которое в ходе выполнения КС не выходит из строя и сбрасывает регистр блокировки на шаге 30, то все устройства, вошедшие в состояние Lock в то время, когда коммутатор был захвачен, можно разделить на две группы:

·     устройства, которые успели выполнить шаг 2 до сброса регистра;

·     устройства, которые выполнили шаг 2 после сброса регистра.

Значит, если во второй группе есть хотя бы одно устройство, первое из них, которое выполнит шаг 2, захватит коммутатор. Устройству из первой группы для захвата необходимо выполнить два обращения к регистрам, если на шаге 2 было прочитано значение EMPTY. В противном случае устройству придется выполнить третье обращение – на шагах 3, 12 и 2, так как, по предположению 1, сброс произойдет до выполнения любым из устройств шага 12. Таким образом, количество обращений к регистрам будет максимальным, когда все устройства входят в первую группу. После того как каждое устройство выполнит шаги 3 и 12, первое же выполнение любым из них шага 2 приведет к захвату. Таким образом, для захвата коммутатора потребуется не более  обращений к регистрам.

Рассмотрим случай, когда коммутатор был захвачен и захватившее его устройство вышло из строя, не сбросив регистр блокировки. Из алгоритма видно, что обнуление регистра метки на шаге 12 может быть выполнено каждым устройством только один раз на каждую попытку захвата коммутатора. К обнулению метки приводит также выполнение шага 22. Этот шаг может быть выполнен каждым устройством один раз на каждый выход из строя ОУ с наибольшим идентификатором. Поскольку выход ОУ из строя уменьшает общее число устройств на 1, то шаги 20 и 22 могут быть выполнены не более  раз до следующего захвата коммутатора. Таким образом, с момента вхождения первого ОУ в состояние Lock до следующего захвата коммутатора может быть выполнено не более  обнулений регистра метки.

Из леммы 2 следует, что до следующего захвата коммутатора может быть выполнено не более  записей в регистр метки на ша- ге 16, а из леммы 3 – не более  записей в регистр блокировки на шаге 27. Последнее означает, что до следующего захвата блоки- ровки может существовать не более  интервалов времени, в которых регистр блокировки сброшен. Из алгоритма следует, что каждое устройство может выполнить цикл шагов 2–3–8–9 не более одного раза в каждом таком интервале.

Заметим, что каждая запись в регистр метки на шаге 16 требует чтения на шаге 14, каждая запись в регистр блокировки на шаге 27 – чтения на шаге 14, каждое обнуление регистра метки требует только одного обращения к регистру, каждый цикл 2–3–8–9 включает в себя два обращения – на шагах 2 и 3, а каждому выполнению шага 20 предшествует выполнение шага 14.

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

.

Как можно видеть, максимальное количество обращений ограниченно и зависит от . Теорема верна.

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

Рассмотрим подробнее значение, возвращаемое функцией NewMylock(). Если после перезагрузки значение mylock не изменилось, по ее окончании ОУ может вмешаться в процесс снятия собственной блокировки. Нетрудно показать, что в результате процесс сброса регистра блокировки может стать бесконечным. Также возможен сценарий, приводящий к ложному обнаружению отказа, как, например, следующая последовательность действий: устройство 1 захватывает коммутатор, устройство 2 после неудачной попытки захвата переходит в состояние ожидания, устройство 1 освобождает коммутатор, устройство 1 захватывает коммутатор, устройство 2 выходит из сос- тояния ожидания. Здесь устройство 2 будет считать, что устройство 1 вышло из строя, хотя это не так.

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

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

Алгоритм неявно предполагает, что размера регистра метки достаточно для записи в него идентификатора любого устройства, а размера регистра блокировки – для записи любого возможного значения mylock. В действительности, согласно стандарту RapidIO, размер регистра метки – 32 бита, а регистра блокировки – 16 бит. Это не позволяет строго реализовать функцию NewMylock(). Например, если 8 бит значения mylock содержат идентификатор устройства и еще 8 бит – описанное выше уникальное число, то количество ОУ в этом случае ограничивается 256, и если устройство перезагружается во время выполнения критической секции, до успешного сброса старой блокировки это устройство может перезагрузиться не более 256 раз, так как иначе значение mylock может совпасть с записанным в регистре блокировки.

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

Литература  

1.   Бакулин А.А. Взаимодействие компонентов высокопроизводительных параллельных систем с помощью технологии RapidIO // Моделирование и визуализация. Многопроцессорные системы. Инструментальные средства разработки ПО. [под ред. В.Б. Бетелина]. М.: НИИСИ РАН, 2009. С. 77–89.

2.   RapidIO Interconnect Specification. Part 3: Common Transport Specification. Revision 1.3. RapidIO Trade Association, 2005. URL: http://www.rapidio.org/specs/disclaimer?specfile=/zda­ta/specs/cmn_trnspt.pdf (дата обращения: 15.06.2010).

3.   RapidIO Interconnect Specification. Part 4: Physical Layer 8-16 LP-LVDS Specification. Revision 1.3. RapidIO Trade Association, 2005. URL: http://www.rapidio.org/specs/disclai­mer?specfile=/zdata/specs/parallel_phy.pdf (дата обращения: 15.06.2010).

4.   Fischer M., Lynch N., Paterson M. Impossibility of Distributed Consensus with One Faulty Process // Journal of the ACM. 1985. Vol. 32. Is. 2, pp. 374–382.

5.   Тель Ж. Введение в распределенные алгоритмы. М.: МЦМНО, 2009.