Диссертация (1148255), страница 10
Текст из файла (страница 10)
Как правило, такие сети организуются в радиоэфире (например, группа совместно действующих БПЛА), поэтому, в первуюочередь, мы ориентируемся на беспроводное применение. Радиоэфир являетсяразделяемой физической средой (в общем случае два сообщения не могут бытьотправлены одновременно из-за эффекта интерференции1 ), и этим свойствоммы можем пользоваться. При таком подходе, без потери общности и производительности, наше решение сможет быть использовано и в других разделяемыхсредах (например, для автомобильного оборудования на общей шине CAN илив соответствующих промышленных сетях).
Применение в неразделяемых средах также допустимо, однако возможно снижение эффективности в виду болеесложной реализации механизма обеспечения широковещательных сообщений(см. ниже).1Хотя имеются технологии типа OFDMA, при использовании которых несколько узлов получают возможность излучать одновременно, даже стандарт WiMax, активно эту технологию использующий, в протоколе подуровня MAC среди четырех классов предоставляемых сервисов содержит один, в котором станциипо-прежнему вынуждены конкурировать в попытках захватить канал, так как соединение в данном случаееще не установлено и персональный набор поднесущих станциям ещё не выделен.56Таким образом, требования к физическому окружению оказываютсядостаточно свободны:– радиоэфир ИЛИ– проводное подключение, желательно по схеме разделяемой физическойсреды.2.1.5.
Сетевое окружениеВо многих работах по DSM прослеживается сильная связь с конкретнымсетевым окружением. Это вызвано тем, что DSM создаются для распределённых систем, а для них принципиально важен вопрос организации связи. Однакосложность создания DSM системы может быть заметно снижена, в случае еслимы можем рассчитывать на наличие надежных примитивов групповой коммуникации. Один из наиболее известных таких примитивов – упорядоченные широковещательные сообщения (англ. total order broadcast, также известные какatomic broadcast)1 . Кратко, данный примитив предназначен для рассылки сообщений сразу нескольким адресатам, причем таким образом, что все адресатыполучают данные сообщения в одном и том же порядке, вне зависимости оттого, кто их отправляет.В DSM системах часто возникает задача упорядочивания распределённыхопераций записи (см.
раздел 1.5.4), однако, на взгляд автора, эта задача сводится к обеспечению механизма упорядоченных широковещательных сообщений (действительно, при наличии последнего механизма, первая задача решается тривиально). В связи с этим, выглядит обоснованным выделить последнюю задачу в отдельную.
Подобно сетевой модели OSI, разделяющей уровнипротоколов, что позволяет решать задачи, свойственные каждому из уровней1Иногда вместо термина «широковещательные» (англ. broadcast) используется термин «мультиадресный» (англ. multicast) – если имеется в виду рассылка не «всем», а фиксированной группе адресатов. Вданной работе второй вариант не требуется и далее не рассматривается.57независимо, выделим задачу обеспечения упорядоченных широковещательныхсообщений в уровень протоколов связи, расположенный ниже DSM системы.
Содной стороны, это позволит сосредоточиться в решении именно на DSM специфике, с другой – такой подход обеспечит возможность использования нашейDSM системы в различных сетевых окружениях (и в различных физическихсредах, соответственно разделу выше) – нужно лишь четко обозначить, что отэтого окружения системе требуется. К примеру, DSM система Orca (см.
раздел 1.6.5) как раз умеет использовать имеющиеся в её окружении соответствующие механизмы, и только при их отсутствии реализует данные механизмы самостоятельно. Использованный подход крайне интересен, однако создание собственных механизмов в области обеспечения связи вынесем в проработку набудущее. Заметим, что имеется большое количество публикаций по теме обеспечения упорядоченных широковещательных сообщений – предложены десяткиалгоритмов – но большое количество решений проблемы – само по себе является проблемой. Прекрасная работа проделана в материале [19] – в нём сделанапопытка обобщить все накопленные по данной теме знания, описать все сложности и тонкие моменты, а главное, в данной работе классифицировано околошестидесяти известных алгоритмов, что сильно облегчает поиск подходящих вконкретной ситуации решений.
В будущем данная работа может быть крайнеполезна.Отметим, что так как работа системы предполагается в разделяемой физической среде (хотя и не ограничивается ей), вопросы разделения должны бытьрешены уже на канальном уровне сетевой модели OSI. В таком случае сообщения в системе оказываются вынужденно упорядочены, и реализация механизма,описанного выше, может не потребовать дополнительных усилий. Однако ситуация может усложниться в случае mesh сетей, где два узла физически могут и«не слышать» друг друга, а связь обеспечивается через ретрансляцию данныхдругими узлами.Стандарты беспроводной связи в целом фиксируются документами IEEE,58входящими в группу 802 (802.11, 802.16 и др.), при этом имеется немалое сходство с проводными стандартами подгруппы 802.3.
Мы, однако, не будем требовать наличия полной поддержки какого-либо из известных стандартов, а вместо этого выделим явно – какой функционал от протокола нам нужен, оставляяпри разработке сетевого протокола возможность идти либо по пути реализациистандартов, либо, жертвуя совместимостью, добиваться более высокой производительности через создание собственного специализированного решения.В результате, итоговые требования к сетевому окружению состоят всегоиз одного пункта:– наличие поддержки упорядоченных широковещательных сообщений.2.2.
Решение задачиРешение задачи складывается из нескольких компонентов. Сначала – создадим модель консистентности, которой будем придерживаться и в рамкахкоторой будущему пользователю системы предстоит создавать свои решения.Затем – разработаем ключевые алгоритмы для обеспечения требований моделии обоснованных показателей как производительности, так и устойчивости косбоям. И, наконец, выработаем принципы построения прикладного интерфейсасоздаваемого программного продукта.Однако прежде чем приступить к созданию вышеописанных компонентов,выберем общую «стратегию». В решении задачи обеспечения когерентности памяти их выделяют две: invalidation и write-broadcast [33].
Первая допускаетлишь одного владельца для каждого распределённого объекта, за счет чегосокращает накладные расходы на пересылку изменившихся данных; вторая –требует обновления данных во всех узлах-копиях после каждой операции записи. Write-broadcast подход рассматривается реже, так как необходимые дляорганизации когерентности накладные расходы при нем особенно велики. Однако он хорошо применим в нашей ситуации, так как требует максимально59быстрого распространения изменившейся информации по всем узлам в системе, не допуская их уникальности.
А так как наша система разрабатываетсядля функционирования преимущественно в условиях разделяемой среды, гделюбое сообщение по сути является широковещательным, данная стратегия неоказывает негативного влияния на производительность нашей системы. В соответствии с классификацией, принятой в [40], можно обозначить необходимуюнам систему как full-replication (имеется множество копий одних и тех же данных), multiple reader/single writer (MRSW, допускающий параллельное чтениеодних и тех же данных множеством узлов «одновременно», с упорядочиваниеми разделением во времени операций записи) software (не зависящий от аппаратных особенностей и реализованный программно) алгоритм.2.2.1.
Усиленная модель консистентности по выходуВ разделе 1.4 мы описали основные модели консистентности. На первыйвзгляд, нам идеально подходит модель консистентности по выходу. Действительно, данная модель не требует так много пересылок данных как модели,описанные до неё, но, в то же время, минимизирует время обладания узломуникальной информацией (что важно для обеспечения устойчивости системыко сбоям отдельных узлов), так как в момент выхода из критической секциипроизведенные в общей памяти изменения должны быть распространены между остальными узлами сети.Модели, описанные после, последним свойством уже не обладают – модель ленивой консистентности не только не гарантирует отправку измененныхданных по выходу из критической секции, но и наоборот – старается повыситьсвою эффективность именно за счёт того, что требует рассылки данных толькотем узлам, что явным образом нуждаются в них, и только тогда, когда онивыполнят соответствующий запрос.Модель консистентности по входу также не предоставляет подобных гарантий, однако содержит усовершенствование, которое представляется весьма60ценным, и, в то же время, не являющимся чем-то неотрывно связанным с идеологией самой модели: требование наличия связи общих переменных с синхронизационными переменными.
Данным свойством хотелось бы дополнить модельконсистентности по выходу, не перенося, однако, другого свойства – модель консистентности по входу содержит новое понятие – «владелец» распределённойпеременной.Как следует из раздела 1.4.7, понятие «владелец» было введено лишь длятого, чтобы узел, работающий с общими данными (которые, однако, в данныймомент не интересуют другие узлы), мог работать с этими данными без какоголибо информационного обмена с остальными узлами (в том числе многократновходя и выходя из критической секции), снижая тем самым нагрузку на каналыпередачи данных в системе. В нашей новой модели это свойство избыточно, таккак противоречит стремлению минимизировать время существования уникальных данных в узле.
А если, подобно модели консистентности по выходу, данныебудут распространяться в системе в момент выхода узла из критической секции,надобность в понятии «владелец» отпадает.Второй интересный нам момент в модели консистентности по входу – разделение понятий эксклюзивного и неэксклюзивного захвата синхро-переменной.Свойство обеспечивает возможность одновременной работы нескольких узловнад одними и теми же данными (защищаемыми одной и той же синхро-переменной), если ими производятся только операции чтения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
