Способ обеспечения доступа к разделяемому ресурсу в распределенной вычислительной системе
METHOD FOR PROVIDING ACCESS TO SHARED RESOURCE IN DISTRIBUTED COMPUTING SYSTEM

Область техники, к которой относится изобретение
Предполагаемое изобретение относится к распределенным вычислительным системам и может быть использовано для обеспечения эксклюзивного доступа к разделяемым ресурсам в распределенных вычислительных системах.
Уровень техники
В настоящее время существует большое количество алгоритмов, обеспечивающих эксклюзивный доступ к разделяемому ресурсу в распределенной системе. Классификация, предложенная в [1], разделяет такие алгоритмы на три класса: на основе обладания токеном, на основе явного запроса разрешения у участников и гибридные алгоритмы.
Методы на основе обладания токеном подразумевают, что в системе, имеющей несколько узлов, существует виртуальный объект под названием токен, обладание которым дает право узлу на получение доступа к общему ресурсу. Так как токен существует в единственном числе, то обладание им гарантирует эксклюзивность такого доступа [2, 3, 4].
Методы на основе запроса разрешения у участников подразумевает, что процесс-претендент за обладание ресурсом явно рассылает запрос на доступ к ресурсу другим претендентам. Получив такое разрешение, процесс получает право на ресурс [5, 6, 7].
К гибридным алгоритмам относятся, в частности, централизованные алгоритмы, которые предполагают, что выдачей разрешений на запросы претендентов на ресурс занимается какой-то специально отведенный центральный координатор [8].
Существует ряд характеристик, по которым алгоритмы сравнивают между собой, такие как количество отправляемых сообщений, необходимое для корректной работы алгоритма, способность алгоритма учитывать отказы отдельных процессов, ограничения, накладываемые на сетевую топологию и т.д. [1].
Особый интерес с практической точки зрения представляют алгоритмы, способные учитывать отказы отдельных процессов и адаптироваться к увеличению числа процессов-участников.
Известен способ обеспечения доступа к разделяемому ресурсу в распределенной системе (называемый также алгоритмом Рикарта-Агравала, [7]), причем система содержит
• по крайней мере, два узла, соединенных между собой посредством цифровой сети передачи данных,
• разделяемый ресурс
• прикладное программное обеспечение (ППО), используемое на каждом узле и формирующее, по крайней мере, один программный процесс (клиент), в ходе работы которого может потребоваться доступ к разделяемому ресурсу, выполненное с возможностью
формировать запрос на получение доступа к СБ,
останавливать действия до получения ответа от СБ;
• средство блокирования (СБ) доступа к разделяемому ресурсу, расположенное на каждом узле, выполненное с возможностью
разрешать или блокировать доступ к разделяемому ресурсу,
формировать и посылать сообщения клиенту и другим СБ;
• средство формирования уникальных для всей распределенной системы идентификаторов процессов.
В такой системе, в ходе одновременной работы множества процессов, работающих над одной прикладной задачей, иногда возникает необходимость обеспечить эксклюзивный доступ одного из процессов к разделяемому ресурсу.
Процессы не имеют общей памяти и взаимодействуют между собой только посредством обмена сообщениями. Предполагается, что у любого процесса есть возможность отправить сообщение любому другому процессу, причем сообщение, будучи доставлено до процесса, попадает в его локальный блок хранения (почтовый ящик). Доставка сообщений предполагается надежной, то есть если процесс отправил сообщение, оно обязательно будет доставлено в почтовый ящик получателя без искажений содержимого сообщения.
У каждого процесса есть свой уникальный идентификатор, при этом не происходят отказы процессов, каждый процесс имеет сведения об идентфикаторах всех других процессов-участников, и этот список не меняется.
Процесс, которому необходимо получить доступ к ресурсу, рассылает сообщение всем остальным процессам. При получении сообщения, процесс-получатель может либо сразу дать разрешение, либо отложить запрос в специальный список - список отложенных запросов.
Процесс отвечает на запрос без промедлений в том случае, если, либо он не претендует на доступ и не осуществляет сам доступ к ресурсу в момент получения запроса, либо приоритет у процесса, приславшего запрос, выше, чем его собственный.
Приоритет процесса определяется парой значений: значением идентификатора процесса и значением специального счетчика, который в дальнейшем называется логическими часами процесса. Процесс, у которого значение логических часов меньше, либо, в случае если значения часов совпадают, но значение идентификатора меньше, тот обладает более высоким приоритетом.
Для того, чтобы процесс-получатель имел возможность сравнить свой приоритет с приоритетом процесса-отправителя, значение логических часов передается вместе с сообщением.
Если получатель сообщения сам является претендентом на доступ к ресурсу, и его приоритет выше, чем приоритет отправителя, то в этом случае запрос перекладывается в список отложенных запросов.
Процесс получает доступ к ресурсу только после того, как всем остальным процессам был отправлен запрос на получение доступа и от всех из них получено разрешение.
Успешно получив доступ, выполнив все необходимые действия с ресурсом и затем освободив ресурс, процесс ответит на все такие отложенные запросы, давая возможность доступа к ресурсу другим процессам.
Известный способ принимается за прототип.
Однако, известный способ имеет ряд недостатков.
Так, в случае временного или полного прекращения обмена сообщениями с одним или несколькими другими процессами (например, из-за аппаратного сбоя или физического уничтожения одного или нескольких узлов), остальные процессы будут заблокированы и останутся в неопределенно долгом ожидании, что снижает надежность способа.
Кроме того, известный способ в ходе реализации не предусматривает добавление в состав системы новых процессов или удаление имеющихся процессов, что ограничивает применение способа в реальных системах.
Раскрытие изобретения
Техническим результатом является
1) повышение надежности доступа к разделяемому ресурсу,
2) возможность учета динамического изменения состава участвующих процессов-претендентов на доступ к разделяемому ресурсу.
Для этого предлагается способ обеспечения эксклюзивного доступа к разделяемому ресурсу в распределенной вычислительной системе, причем система содержит
• по крайней мере, два узла, соединенных между собой посредством цифровой сети передачи данных;
• разделяемый ресурс;
• прикладное программное обеспечение, используемое на каждом узле и формирующее, по крайней мере, один программный процесс (клиент), в ходе работы которого может потребоваться доступ к разделяемому ресурсу;
• средство мониторинга (СМ) состояния процессов в системе, расположенное на каждом узле и выполненное с возможностью информировать процессы в системе об отказе какого-либо процесса посредством отправки сообщения;
• средство организации списка процессов-участников какой-то группы процессов (менеджер групп процессов, МГП), расположенное на каждом узле, связанное с СМ и выполненное с возможностью
формировать актуальный список процессов-участников группы,
отвечать на внешние запросы о текущем составе группы;
• средство формирования уникальных для системы идентификаторов процессов;
• средство блокирования (СБ) доступа к разделяемому ресурсу, расположенное на каждом узле, связанное с МГП и СМ и выполненное с возможностью
разрешать или блокировать доступ к разделяемому ресурсу,
формировать и посылать сообщения клиенту и другим СБ;
причем прикладное программное обеспечение выполнено с возможностью
• формировать запрос на получение доступа к СБ,
• останавливать действия до получения ответа от СБ; способ, заключающийся в том, что
• если узел впервые обращается за доступом и/или узел восстанавливается после временного прекращения работоспособности, то выполняют следующие действия:
назначают уникальный идентификатор для каждого активного процесса в системе, с учетом возможности сравнения идентификаторов через отношение "меньше - больше";
при необходимости получения доступа к разделяемому ресурсу, посылают запрос от клиента к СБ, причем клиент остается заблокированным до тех пор, пока СБ не даст клиенту разрешение на доступ;
при необходимости освободить полученный ранее доступ к ресурсу, посылают запрос от клиента к СБ на освобождение доступа, причем клиент остается заблокированным до тех пор, пока СБ не выполнит действия, связанные с освобождением доступа;
формируют в СБ список претендентов, изначально пустой;
формируют в СБ список ожидания, изначально пустой;
формируют в СБ список отложенных запросов, изначально пустой;
обнуляют в СБ значение N счетчика собственных запросов;
обнуляют в СБ значение М счетчика входящих запросов;
иначе переходят к этапу А;
• (А) при необходимости получения доступа к разделяемому ресурсу посылают запрос на получения доступа к разделяемому ресурсу от клиента в СБ;
• посылают запрос из СБ в МГП на добавление идентификатора процесса СБ в группу претендентов;
• дожидаются ответа в СБ на запрос в МГП о добавление идентификатора процесса СБ в группу претендентов;
• посылают запрос из СБ в МГП на получение списка претендентов;
• дожидаются ответа в СБ на запрос в МГП со списком претендентов;
• посылают из СБ всем процессам из списка претендентов сообщения о включении в группу претендентов;
• посылают запрос из СБ в СМ на мониторинг состояния всех процессов из списка претендентов;
• дожидаются подтверждения получения запроса в СБ на запрос в СМ о состоянии каждого процесса из списка претендентов;
• вносят в список ожидания все процессы из списка претендентов;
• посылают из СБ всем процессам из списка ожидания сообщение о необходимости получение доступа, содержащее также уникальный идентификатор процесса СБ и значение N счетчика собственных запросов, равное
N=1+М,
где М - значение счетчика входящих запросов в СБ;
• (Б) ожидают в СБ получения разрешения от всех процессов из списка претендентов;
• если приходит сообщение о том, что какой-либо процесс из списка претендентов остановился, то
исключают идентификатор этого процесса из списка ожидания и из списка претендентов; при этом, если оказывается, что список ожидания пуст, то дают разрешение клиенту на доступ к ресурсу;
переходят к этапу В;
• если приходит сообщение о том, что какой- либо процесс включился в группу претендентов и его идентификатор отсутствует в списке претендентов, то
добавляют идентификатор нового процесса в список ожидания;
добавляют идентификатор нового процесса в список претендентов;
посылают из СБ новому процессу сообщение о необходимости получение доступа к ресурсу, содержащее также уникальный идентификатор процесса СБ и значение N счетчика собственных запросов, равное N=1+М;
посылают запрос из СБ в СМ на мониторинг состояния нового процесса;
дожидаются подтверждения получения запроса в СБ на запрос в СМ о состоянии нового процесса;
переходят к этапу Б;
• если приходит сообщение на получение доступа от другого процесса, содержащее идентификатор и счетчик собственных запросов другого процесса, то
если идентификатор СБ меньше идентификатора другого процесса и при этом значение счетчика собственных запросов СБ равно значению счетчика собственных запросов другого процесса или значение счетчика собственных запросов СБ меньше значения счетчика собственных запросов другого процесса, то
добавляют идентификатор нового процесса в список отложенных запросов;
иначе
отправляют разрешение другому процессу на доступ;
изменяют значение счетчика входящих запросов СБ на максимальное из значений счетчика другого процесса и счетчика входящих запросов СБ;
изменяют значение счетчика входящих запросов СБ на максимальное из значений счетчика собственных запросов другого процесса и счетчика входящих запросов СБ;
переходят к этапу Б;
• если приходит сообщение с разрешением на доступ от другого процесса, то
исключают идентификатор другого процесса из списка ожидания, при этом если после удаления список оказывается пуст, то дают разрешение клиенту на доступ к ресурсу;
переходят к этапу В;
• (В) если доступ к ресурсу перестал быть необходим, делают запрос из клиента в СБ на освобождение ресурса;
• высылают из СБ разрешение на доступ всем процессам из списка отложенных запросов.
Все эти средства могут быть сформированы в программном, программно-аппаратном или аппаратном виде, причем предпочтительным является программный вид. Соответствующие программы могут быть созданы специалистами в области программирования (программистами) на основе знания выполняемых программами функций.
После сформирования все эти средства устанавливаются на каждом узле системы.
Распределенная система, в которой реализуется предлагаемый способ, предусматривает наличие нескольких, по крайней мере, двух узлов, связанных между собой, и возможность работы узлов без потери управляемости системы в случае временного или полного выхода из строя (уничтожения) любого узла.
Распределенная система, в которой реализуется предлагаемый способ, может быть изначально неактивной, и для начала работы она должна быть включена (запущена) путем последовательного либо одновременного включения, по крайней мере, двух вычислительных узлов.
В случае, когда способ реализуется в уже работающей системе, эти действия не выполняют.
Уникальные идентификаторы для процессов в системе могут быть сформированы на основе разных методов, например, такой идентификатор можно получить, используя МАС-адрес сетевого адаптера, дополненный счетчиком, значение которого сохраняется на постоянном носителе, изначально равным 0, и значение которого увеличивается каждый раз при перезагрузке узла.
Когда процесс СБ начинает свою работу, он регистрирует свой идентификатор в составе группы через средство МГП. Далее СБ получается список всех зарегистрированных на данный момент идентификаторов процессов-претендентов и явно оповещает их о своем присутствии, рассылая соответствующее сообщение. Это дает возможность уже работающим процессам иметь сведения о появлении нового претендента и выполнить соответствующие действия по мониторингу состояний нового процесса и, если это необходимо, осуществления запроса на получение доступа.
Основным условием захвата разделяемого ресурса процессом СБ является пустота списка ожидания. Изначально список ожидания наполняется идентификаторами всех процессов претендентов, и далее может уменьшается, либо увеличиваться в случае появления новых процессов в группе, что достигается за счет использования средства менеджера групп процессов, а также корректной обработки сообщений о вхождении процесса в группу претендентов.
Активное наблюдение процесса СБ за остальными процессами СБ группы претендентов посредством сетевого монитора (СМ) позволяет, при получении от СМ сообщения об исчезновении какого-либо процесса-претендента, удалить идентификатор исчезнувшего процесса СБ из списка ожидания, таким образом избавляясь от необходимости ждать ответа от несуществующего процесса. Это гарантирует, что список ожидания будет уменьшаться даже в случае отказа процесса-участника, и через какое-то время окажется пуст, выполнив основное условие захвата ресурса.
При возникновении пустого списка ожидания СБ предоставляет процессу доступ к разделяемому ресурсу. После окончания доступа разделяемый ресурс корректно высвобождается и может быть предоставлен другому процессу.
В результате,
• внезапное, полное или временное прекращение функционирования одного или нескольких узлов в системе не приводит к остановке процесса обеспечения доступа к разделяемому ресурсу для остальных узлов, что повышает надежность,
• в работающей группе процессов возможно осуществить добавление нового процесса или удаление процесса, что не изменяет возможность доступа к разделяемому ресурсу для остальных узлов.
Краткое описание чертежей
На фигуре графического изображения показана схема распределенной системы, состоящей из двух вычислительных узлов.
Осуществление изобретения
Предлагаемый способ может быть реализован в распределенной системе, состоящей, например, из трех вычислительных узлов, соединенных посредством сети передачи данных Ethernet. На каждом узле установлена ОС Linux Fedora 25.
В качестве разделяемого ресурса 5 был использован текстовый файл, расположенный в общем сетевом хранилище (см. фигуру графического изображения).
Для программной реализации средств на каждом узле был использован язык программирования Erlang OTP 16 [9] на основе пакета erlang х86_64.
При этом
• в качестве средства сетевого монитора 3 используется функционал модуля erlang:monitor;
• в качестве средства менеджера групп процессов 4 используется модуль pg2;
• в качестве клиента 1 используется процесс ra_mutex_client.erl;
• в качестве средства генератора уникальных идентификаторов используется встроенное в Erlang средство формирования идентификаторов процессов.
• в качестве средства блокирования 2 используется процесс ra mutex ft.erl, реализующий описанные функции.
Возможности корректно обрабатывать отказы отдельных процессов и динамического изменения состава узлов были проверены на тестовом стенде. Дополнительно, способ был промоделирован в среде TLA+, описание модели доступно [10].
После запуска распределенной системы обеспечивалось ведение списков претендентов, ожидания, отложенных запросов. При временном отключении одного или двух узлов (одновременно и последовательно) обеспечивались корректный доступ к разделяемому ресурсу и корректное освобождение доступа, а также динамическое изменение состава списков, без остановки процесса обеспечения доступа к разделяемому ресурсу для остальных узлов, что повышает надежность предложенного способа.
Источники информации
1. Mukesh Singhal - A Taxonomy of Distributed Mutual Exclusion, Journal of Parallel and Distributed Computing, 1993.
2. Naimi, M.; Trehel, M. An improvement of the log(n) distributed algorithm for mutual exclusion, Proc. Of the 7th International Conference on Distributed Computing Systems, 1987.
3. Raymond, K. A tree based algorithm for distributed mutual exclusion, ACM Trans. Comput. Systems 7 (1989).
4. Singhal, M. A heuristically-aided algorithm for mutual exlusion in distributed systems, IEEE Trans. Comput. (1989).
5. Carvalho, O.S.F., Roucairol, G. On mutual exclusion in computer networks, technical correspondence. Comm. ACM (1983).
6. Singhal, M. A dynamic information structure mutual exclusion algorithm for distributed systems. IEEE Trans. Parallel Distribut. Systems (1992).
7. Ricart, G., Agrawala A.K. An optimal algorithm for mutual exclusion in computer networks. Comm. ACM (1981).
8. Buckley, G., Silberschatz, A. A failure tolerant centralized mutual exclusion algorithm. Proc. of the 4th Intl. Conf. On Distributed Computing Systems (1984).
9. Программа по адресу:
https://itbucket.org/unboxed_type/ra_mutex/raw/3c2e67ee6ae15ab35b631db6a18d77a9d895d160/src/ra_mutex_ft.erl
10. Результаты моделирования по адресу:
https://bitbucket.org/unboxed_type/ra_mutex/raw/3c2e67ee6ae15ab35b631db6a18d77a9d895d160/model/RAPlus.tla