Journal influence
Bookmark
Next issue
Mutual exclusion algorithm for RapidIO switch access
The article was published in issue no. № 4, 2010Abstract:An algorithm is proposed for providing mutual exclusion access of several RapidIO nodes to a single switch while RapidIO switching fabric is being initialized by a number of nodes. The algorithm is tolerant to node failures.
Аннотация:Предлагается алгоритм обеспечения исключительного доступа к коммутатору RapidIO, устойчивый к выходу оконечных устройств из строя. Алгоритм предназначен для использования в случаях, когда настройка коммуникаци-онной среды RapidIO производится сразу несколькими оконечными устройствами и требуется исключить возможность одновременного доступа нескольких оконечных устройств к одному коммутатору.
Author: (alexander.bakulin@gmail.com) - | |
Keywords: algorithm, mutual exclusion, RapidIO |
|
Page views: 15901 |
Print version Full issue in PDF (6.26Mb) Download the cover in PDF (1.28Мб) |
@Сеть передачи данных 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. В любом выполнении системы никакие два ОУ не могут выполнять критическую секцию одновременно. Доказательство. Допустим, при выполнении системы 1) 2) 3) событие, сбрасывающее регистр блокировки; 4) 5) Третье событие может принадлежать или множеству Учитывая предположение 1 об ограниченности времени выполнения критической секции, а также то, что между успешной записью в регистр блокировки в результате выполнения шага 2 и переходом к критической секции на шаге 15 устройство выполняет фиксированное число шагов (каждый из которых по предположению 4 выполняется за ограниченное время), можно выбрать значение ReleaseTimeout, превышающее максимальное время, которое может пройти с момента успешной записи в регистр блокировки до момента сброса регистра одним ОУ. В таком случае принудительный сброс блокировки будет выполняться только при выходе устройства из строя. Так как выход устройства Лемма 1. Для любого выполнения системы Доказательство. Предположим, что для некоторого По свойству 1 парных событий для этих двух событий записи существуют парные им события чтения Из условия леммы и определения парных событий следует, что существует такая полная последовательность Лемма 2. Для любого выполнения системы Доказательство. Для случая Пусть Лемма 3. Для любого выполнения системы Доказательство. Из леммы 2 следует, что количество событий записи в регистр метки в любой полной последовательности без обнуления метки Если после выполнения устройством Рассмотрим возможные состояния регистра блокировки в начале интервала 1. Регистр блокировки содержит идентификатор вышедшего из строя устройства. Тогда устройство 2. Регистр блокировки сброшен. Тогда устройство В первом случае в интервале Очевидно, что в каждом интервале может быть отложено не более одного события, и из последнего интервала отложить событие нельзя. Пусть на протяжении всей последовательности было отложено Таким образом, лемма верна. Теорема 2. Если в некоторый момент хотя бы одно из Доказательство. Справедливость теоремы очевидна, если на момент выполнения шага 2 первым из устройств, желающих выполнить КС, регистр блокировки был сброшен. В этом случае захват будет произведен за одно обращение. Если же коммутатор был захвачен другим устройством, которое в ходе выполнения КС не выходит из строя и сбрасывает регистр блокировки на шаге 30, то все устройства, вошедшие в состояние Lock в то время, когда коммутатор был захвачен, можно разделить на две группы: · устройства, которые успели выполнить шаг 2 до сброса регистра; · устройства, которые выполнили шаг 2 после сброса регистра. Значит, если во второй группе есть хотя бы одно устройство, первое из них, которое выполнит шаг 2, захватит коммутатор. Устройству из первой группы для захвата необходимо выполнить два обращения к регистрам, если на шаге 2 было прочитано значение EMPTY. В противном случае устройству придется выполнить третье обращение – на шагах 3, 12 и 2, так как, по предположению 1, сброс произойдет до выполнения любым из устройств шага 12. Таким образом, количество обращений к регистрам будет максимальным, когда все устройства входят в первую группу. После того как каждое устройство выполнит шаги 3 и 12, первое же выполнение любым из них шага 2 приведет к захвату. Таким образом, для захвата коммутатора потребуется не более Рассмотрим случай, когда коммутатор был захвачен и захватившее его устройство вышло из строя, не сбросив регистр блокировки. Из алгоритма видно, что обнуление регистра метки на шаге 12 может быть выполнено каждым устройством только один раз на каждую попытку захвата коммутатора. К обнулению метки приводит также выполнение шага 22. Этот шаг может быть выполнен каждым устройством один раз на каждый выход из строя ОУ с наибольшим идентификатором. Поскольку выход ОУ из строя уменьшает общее число устройств на 1, то шаги 20 и 22 могут быть выполнены не более Из леммы 2 следует, что до следующего захвата коммутатора может быть выполнено не более Заметим, что каждая запись в регистр метки на шаге 16 требует чтения на шаге 14, каждая запись в регистр блокировки на шаге 27 – чтения на шаге 14, каждое обнуление регистра метки требует только одного обращения к регистру, каждый цикл 2–3–8–9 включает в себя два обращения – на шагах 2 и 3, а каждому выполнению шага 20 предшествует выполнение шага 14. Из алгоритма видно, что никакие другие шаги устройствами не выполняются. Следовательно, верхняя граница количества обращений к регистрам метки и блокировки составляет
Как можно видеть, максимальное количество обращений ограниченно и зависит от Следует обратить внимание на то, что предположение 2 не допускает возможности наличия такого распространенного вида отказов, как перезагрузка. Если каждое устройство перезагружается, обладая наибольшим идентификатором среди устройств, участвующих в принудительном сбросе блокировки, а после перезагрузки сразу пытается захватить коммутатор, то возможна последовательность событий, приводящая к тому, что выполнение критической секции будет бесконечно откладываться. Однако попытка захвата после перезагрузки отличается от попытки захвата, предпринимаемой тем же устройством до момента перезагрузки, в том смысле, что отличаются соответствующие значения mylock. Перезагрузку тогда можно представить как отключение устройства от системы с последующим подключением нового устройства; при этом N увеличивается на 1. Если перезагрузки происходят бесконечно, бесконечными будут и величина Рассмотрим подробнее значение, возвращаемое функцией 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=/zdata/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/disclaimer?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. |
Permanent link: http://swsys.ru/index.php?id=2606&lang=en&like=1&page=article |
Print version Full issue in PDF (6.26Mb) Download the cover in PDF (1.28Мб) |
The article was published in issue no. № 4, 2010 |
Perhaps, you might be interested in the following articles of similar topics:
- Проверка допустимости схемы маршрутизации в системе RapidiO
- Способы инициализации многопроцессорной системы
- Эффективная программная реализация вейвлет-преобразования
- Способы реализации алгоритмов интегральных преобразований изображений по линиям
- Тестирование памяти в многопроцессорных системах
Back to the list of articles