Диссертация (1148255)
Текст из файла
Санкт-Петербургский государственный университетНа правах рукописиБойко Павел ВалентиновичМАКС DSM:Система распределённой общей памятидля мультиагентных систем в IoT05.13.11 – Математическое и программное обеспечение вычислительныхмашин, комплексов и компьютерных сетейДИССЕРТАЦИЯна соискание ученой степеникандидата технических наукНаучный руководительдоктор физико-математических наук, профессорАндрианов Сергей НиколаевичСанкт-Петербург – 20172ОглавлениеВведение . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Глава 1.5Исследования и терминология предметной области . .161.1. Концепции доски объявлений и DSM в МАС . . . . . . . . . . . .161.2. Возникновение концепции DSM . . . . . . . . . . . . . . . . . . .171.3. Описание концепции DSM . . . . . . . . . .
. . . . . . . . . . . .211.4. Модели консистентности . . . . . . . . . . . . . . . . . . . . . . .231.4.1.Строгая консистентность . . . . . . . . . . . . . . . . . . .241.4.2.Последовательная консистентность . . . . . . . . . . . . .251.4.3.Другие глобальные модели. . . . . . . . .
. . . . . . . .271.4.4.Слабая консистентность . . . . . . . . . . . . . . . . . . .291.4.5.Консистентность по выходу . . . . . . . . . . . . . . . . .301.4.6.Ленивая консистентность по выходу . . . . . . . . . . . .321.4.7.Консистентность по входу . . . . . . . . . . . . . . .
. . .321.4.8.Заключение . . . . . . . . . . . . . . . . . . . . . . . . . .341.5. Алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .341.5.1.Алгоритм с центральным сервером . . . . . . . . . . . . .351.5.2.Алгоритм миграции данных . . . . . . . . . . . . . .
. . .371.5.3.Алгоритм репликации по чтению . . . . . . . . . . . . . .391.5.4.Алгоритм полной репликации . . . . . . . . . . . . . . . .401.5.5.Заключение . . . . . . . . . . . . . . . . . . . . . . . . . .411.6. Реализации . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .411.6.1.Linda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .421.6.2.IVY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .431.6.3.Munin . . . . . . . . . . . . . . . . . .
. . . . . . . . . . .431.6.4.Midway . . . . . . . . . . . . . . . . . . . . . . . . . . . . .441.6.5.Orca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4531.6.6.TreadMarks. . . . . . . . . . . . . . . . . . . . . . . . . .451.6.7.Grappa . . . . . . . . . . . . . . . . . . . . . .
. . . . . . .461.6.8.Перечень известных DSM решений . . . . . . . . . . . . .471.6.9.Заключение . . . . . . . . . . . . . . . . . . . . . . . . . .471.7. Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .49Глава 2.Постановка и решение задачи . . . . . . . . . . . . . . . .512.1. Назначение, требования и соглашения . . . . . . . . .
. . . . . .512.1.1.Назначение решения . . . . . . . . . . . . . . . . . . . . .512.1.2.Аппаратное окружение . . . . . . . . . . . . . . . . . . . .532.1.3.Программное окружение . . . . . . . . . . . . . . . . . . .542.1.4.Физическое окружение . .
. . . . . . . . . . . . . . . . . .552.1.5.Сетевое окружение . . . . . . . . . . . . . . . . . . . . . .562.2. Решение задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . .582.2.1.Усиленная модель консистентности по выходу . . . . . . .592.2.2.Роли узлов и алгоритм смены роли . . . . . . . . . . . . .622.2.3.Организация сообщений в типичных операциях системы .652.2.4.Обеспечение отказоустойчивости . . . . . . .
. . . . . . .672.2.5.Модель прикладного интерфейса . . . . . . . . . . . . . .682.3. Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .71Глава 3.Программная реализация . . . . . . . . . . . . . . . . . . .733.1.
Описание реализации прикладного интерфейса . . . . . . . . . .733.2. Сообщения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .793.3. Процесс блокировки . . . . . . . . . . . . . . . . . . . . . . . . . .803.3.1.Реализация блокировки на запись. . . . . . . . . . . . .803.3.2.Реализация блокировки на чтение .
. . . . . . . . . . . .823.4. Отказоустойчивость . . . . . . . . . . . . . . . . . . . . . . . . . .843.4.1.Термин «сообщение» и атомарность . . . . . . . . . . . .843.4.2.Действия при выходе узлов из строя . . . . . . . . . . . .8543.5. Программная архитектура . . . . . . . . . . . . .
. . . . . . . . .873.5.1.Верхнеуровневая архитектура . . . . . . . . . . . . . . . .873.5.2.Основные компоненты ядра МАКС DSM . . . . . . . . . .883.6. Эксперимент . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .903.7. Производительность . . . . . . . . . . .
. . . . . . . . . . . . . . .953.7.1.Производительность для двух узлов . . . . . . . . . . . .953.7.2.Зависимость производительности от количества узлов . . 1033.8. Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108Заключение . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111Список сокращений и условных обозначенийСписок литературы. . . . . . . . . . . . 114. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116Список иллюстративного материала . . . . . . . . . . . . .
. . . . . . 123Список таблиц . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125Приложение А.Результаты измерений . . . . . . . . . . . . . . . . 1265ВведениеАктуальность темы исследования. Становление мультиагентных систем (МАС) как отдельного научного направления пришлось на 1980-е, и ужев середине 1990-х это направление получило широкое признание [52, с. 13]. Втечение последующих 15-ти лет возрастающий объем исследований в даннойобласти привел к необходимости систематизации накопленных знаний и появлению первых тематических монографий как в России [10], так и за рубежом[38, 41, 52].Уже в начале 2000-х годов агентно-ориентированный подход широко применялся для распределённого решения сложных задач в имитационном моделировании производственных процессов, организации работы коллективов роботов и других областях [10, с.
15]. Сегодня мультиагентные технологии выглядятперспективно даже в таких традиционно консервативных сферах, как энергетика [37], отвечая соответствующим требованиям к безопасности. Вопросы жеорганизации коллективов роботов становятся всё более актуальными как в военном, так и гражданском секторах [51], выделяя такие задачи как контрольпериметра, обеспечение связи, ликвидация последствий стихийных бедствий идр.Несмотря на многолетнюю историю развития МАС, до сих пор не существует общепринятого определения понятий «мультиагентная система» и«агент».
Например, в российской монографии [10] несколько страниц посвящено определениям и высказываниям об агентах различных авторов, проводитсяклассификация этих определений, а также предлагается собственное определение агента, описывающее десять его ключевых свойств. В качестве альтернативы можно обратиться к зарубежной монографии [41], в которой автор такжепредлагает собственное, но, в данном случае, очень компактное и достаточноширокое определение мультиагентной системы, обосновывая данное решениетем, что в прошлом было предложено слишком много конкурирующих и зача6стую противоречащих друг другу определений, чтобы остановиться на одномиз них.Рассмотрим несколько определений мультиагентных систем и агентов изразных источников.1.
Мультиагентные системы — это системы, состоящие из нескольких взаимодействующих вычислительных элементов, называемых агентами.12. Агент — это активный объект со способностью «воспринимать», «рассуждать» и «действовать».23. Мультиагентные системы — это системы, включающие в себя множествоавтономных объектов с различающейся информацией, различающимисяинтересами, либо обладающих обоими признаками сразу.3Первые два определения выявляют необходимость взаимодействия, а значит – обмена информацией между агентами.
Последнее – обращает вниманиена другое их свойство (менее очевидное, но не менее характерное): «знания»одного агента зачастую отличаются от «знаний» другого.Таким образом, выделившись из классического искусственного интеллекта, централизованному подходу решения задач МАС противопоставили децентрализованный, предполагая, что отдельный агент может обладать лишь частичными знаниями, а для решения задачи потребуется взаимодействие группыагентов. Это обусловило концептуальную новизну решений на основе МАС [10,с. 15], стимулом же к развитию направления стали предполагаемые повышенные надежность, гибкость и масштабируемость [38, с. 8] – качества, которыесущественно проще обеспечить в децентрализованных многопроцессорных системах, чем в классических – централизованных [1, с. 12].1«Multiagent systems are systems composed of multiple interacting computing elements, known as agents» [52]2«Fundamentally, an agent is an active object with the ability to perceive, reason, and act» [38]3«Multiagent systems are those systems that include multiple autonomous entities with either diverginginformation or diverging interests, or both» [41]7Однако следует отметить, что упрощая создание конечных распределённых решений, концепции МАС требуют наличия базовых инфраструктурныхмеханизмов, обеспечивающих взаимодействие агентов между собой.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
