Использование модели для анализа возможных решений

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

С моделью можно провести эксперименты. Щелчок на любой из двух кно­пок pick random household или pick random enterprise позволяет выбрать слу­чайную семью или случайное производство и отобразить его характеристики. Щелчок мышью на одной из зон выделяет зону и отображает ее характери­стики. В выделенной зоне с помощью слайдеров можно изменить число квартир (слайдер Housing) и/или число площадок для развертывания произ­водства (слайдер Business) и наблюдать развитие процессов во всем городе.

Глава 19

Информатика и коммуникация

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

Алгоритм распределенного завершения

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

Постановка проблемы

Рассматривается n машин, связанных в произвольную компьютерную сеть. Все машины вместе выполняют некоторый распределенный алгоритм вы­числений, который мы будем называть базовым алгоритмом. Каждая машина может быть либо в активном состоянии, выполняя базовые вычисления, ли­бо в пассивном состоянии, если она завершила свою часть распределенного вычисления. Активная машина, выполняющая базовые вычисления, может посылать сообщения каким-либо другим машинам в сети, передавая им часть работы. Сообщения получаются адресатом после некоторой задержки в сети без потерь. Если пассивная машина получает сообщение, она стано­вится активной, активная машина, получившая сообщение, остается актив­ной и продолжает вычисления.

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

Цель алгоритма распределенного завершения состоит в том, чтобы некото­рая машина, например 0-я, обнаружила, что система пришла в это стабиль­ное состояние как можно быстрее после того, как оно наступило. Для чего выделенная машина должна использовать информацию от остальных машин об их состоянии. Ясно, что алгоритм определения распределенного завер­шения не может быть просто проверкой текущего состояния всех машин в сети и принятия решения о завершении вычислений, если все машины отрапортовали о том, что они пассивны. Во-первых, мгновенно такую про­верку выполнить в распределенной системе невозможно, и, во-вторых, в канале могут находиться задержанные сообщения базового алгоритма, кото­рые могут активизировать перешедшую в пассивное состояние машину, ко­торая уже послала рапорт о своем пассивном состоянии. Поэтому алгоритм обнаружения завершения вычислений в распределенной сети машин явля­ется нетривиальным.

В отличие от базового алгоритма вычислений, назовем алгоритм обнаруже­ния распределенного завершения зондированием. Зондирование может быть инициировано выделенной машиной 0 в любом состоянии всей сети, при любом распределении активностей в ней. Поэтому запущенный алгоритм зондирования может дать отрицательный результат, если сеть машин не на­ходится в стабильном состоянии. Обычно алгоритм зондирования запуска­ется 0-й машиной периодически: если очередной раунд оказался неудач­ным, инициируется следующий раунд.

Алгоритм

Существует несколько решений проблемы распределенного завершения. Алгоритм, модель которого представлена здесь, предложен Э. Дейкстрой [EWD840], работает на произвольном числе машин, пронумерованных от 0 до n, связанных в виртуальное кольцо. Алгоритм состоит из повторения циклов зондирования сети посылкой зонда (токена) по кольцу машин. Дан­ный распределенный алгоритм состоит из следующих локальных правил, которые, как доказал Дейкстра, гарантируют решение проблемы:

1. Каждая машина в сети поддерживает счетчик с. Каждая посылка сооб­щения базового алгоритма увеличивает с на 1; прием базового сообщения уменьшает с на 1. Таким образом, сумма всех счетчиков в сети машин в некоторый момент времени равна числу сообщений, задержанных в сети.

Если сумма значений счетчиков 0, то никаких базовых сообщений в сети нет.

2. Машина 0 инициирует шаг зондирования в любой момент и в любом своем состоянии, посылая токен со значением 0 машине n-1. Каждая машина i задерживает полученный токен до тех пор, пока не станет пас­сивной. После этого значение токена увеличивается на с, и токен пере­дается машине i-1.

3. И машины, и токен имеют цвет. Вначале все машины и токен белые. Машина, получившая базовое сообщение, становится черной. Когда ма­шина передает токен, она становится белой. Если черная машина переда­ет токен, токен становится черным, в противном случае токен сохраняет свой цвет.

4. Когда машина 0 получает свой токен, прошедший по кольцу всех машин, очередной цикл зондирования закончен. Машина 0, получив токен, ждет, пока она не перейдет в пассивное состояние. После этого она делает за­ключение о завершении базовых вычислений в сети машин при следую­щих условиях:

 

• сама машина 0 белая;

• полученный токен белый;

• сумма значений токена и счетчика с машины 0 равна 0.

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

Модель базовых вычислений

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

Анализ модели

Откройте модель DistributedTermination1. Модель построена из трех клас­сов активных объектов: машина, выполняющая вычисления Machine, объ­ект, задерживающий сообщения в сети channel, и корневой объект Model. Корневой объект включает один экземпляр канала channel и N экземпляров машин.

Запустите модель на выполнение. В поле анимации (рис. 19.1) вы увидите 18 машин, расположенных по окружности и обменивающихся сообщениями.

Для того чтобы можно было наблюдать прогресс базового алгоритма, маши­на в рабочем состоянии представлена красным прямоугольником, машина в пассивном состоянии закрашена зеленым. Машины пронумерованы в со­ответствии с их индексами. Сообщения представлены стрелками, соеди­няющими передающую и принимающую машины. Стрелка от машины i к машине k видна, пока хотя бы одно сообщение (i, k) находится в канале. У каждой машины в процессе работы подсчитывается разность с числа пе­реданных и полученных сообщений.

Слайдерами во время выполнения модели можно менять параметры: сред­нюю задержку сообщений в канале, среднее время выполнения порции ба­зовых вычислений и интервал времени между запросами помощи одной машиной от других посылкой базовых сообщений. Чем меньше среднее время выполнения порции базовых вычислений, тем быстрее завершатся вычисления. Тот же эффект получим с увеличением среднего времени до запроса помощи от другой машины (Get Help interval) и уменьшением времени задержки сообщения в канале. Изменить три этих параметра мож­но с помощью слайдеров. Параметр n также можно менять в разных экспе­риментах — это параметр активного объекта Model. На анимации также представлены три индикатора, отображающих относительные количества работающих и пассивных машин, а также число сообщений, находящихся в канале.

Класс сообщений Message

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

сообщений Message определен С ПОЛЯМИ source И destination.

Модель вычислителя

Активный объект Machine включает две переменные: с (счетчик посланных и полученных сообщений) и basecolor (этот цвет показывает в анимации состояние машины в базовых вычислениях: активное оно либо пассивное). В поле Дополнительный код класса окна Код определены также следующие параметры: указатель на корневой объект owner, число машин в модели ы, номер этого экземпляра в массиве машин I, а также радиус r окружности, на которой будут в анимации располагаться изображения машин. Все эти параметры будут определены в корневом объекте, они недоступны из класса Machine и могут быть определены только после компиляции. Поэтому зна­чения всех параметров получаются в поле Код инициализации этого активно­го объекта, когда станет известным корневой объект owner.

Объект Machine имеет один стейтчарт с именем main, который моделирует поведение машины в базовых вычислениях (рис. 19.2).

Стейтчарт имеет два состояния, активное working, которым моделируется обработка машиной очередной порции информации, и пассивное idle. Ясно, что для нашей цели работу машины над очередной порцией вычислений можно смоделировать просто задержкой. Поэтому из рабочего состояния

машина может перейти в пассивное по истечении таймаута processingTime (переход t). В любом состоянии стейтчарт может получить базовое сообще­ние типа Message. Эти сообщения передаются и принимаются через порт port. Порт передает сообщение стейтчарту только если оно адресовано это­му экземпляру активного объекта (что определяется номером этой машины I). Условие приема сообщения записано в поле Действие по получении окна свойств порта. Если сообщение получено в активном состоянии, то машина остается в этом состоянии (переход t1). Если сообщение получено в пас­сивном состоянии, машина возвращается в активное состояние (переход t2). При каждой посылке базового сообщения в канал счетчик с увеличивается на 1, при каждом получении базового сообщения счетчик с уменьшается на 1 в соответствии с алгоритмом.

В рабочем состоянии машина может послать сообщение какой-нибудь дру­гой машине (переход t3). По истечении времени getHelpTimeout новое со­общение направляется случайно выбранному адресату. При этом счетчик с увеличивается на 1 в соответствии с алгоритмом. Пересчета времени, остав­шегося до окончания вычисления в случае посылки сообщения о помощи, не происходит, поэтому переход t3 помещен внутрь состояния working.

Активный объект Machine имеет два динамических параметра, определяю­щих время вычисления очередной порции данных (processingTime) и время запроса помощи от других машин (getHelpTimeout). Эти параметры будут для каждой машины установлены как результат вычисления значения слу­чайной величины при каждом использовании параметров. Кроме того, в стейтчарте изменяются количества активных и пассивных машин в систе­ме при входе и выходе из соответствующих состояний, а также число базо­вых сообщений в канале при каждом порождении сообщения (переход t3) и при каждом получении сообщения из канала (переходы t1 и t2). Соответст­вующие переменные working, idle и messages определены в корневом объ­екте Model, поэтому доступ к ним выполняется с помощью префикса owner, который содержит указатель на включающий объект Main.

Модель среды передачи сообщений базового алгоритма (Channel)

Активный объект channel имеет порт, через который принимаются и посы­лаются сообщения типа Message, а также динамический таймер. В качестве своего единственного параметра таймер имеет сообщение этого типа. Каж­дый раз, как только порт канала принимает сообщение, с ним связывается новый экземпляр таймера, который устанавливается на срабатывание по таймауту channelDelay. По истечении таймаута это сообщение отправляется через этот же порт всем объектам, с которыми этот порт соединен, т. е. всем машинам одновременно. Как уже отмечалось, примет это сообщение только та машина, номер которой стоит в поле destination сообщения. У всех ос­тальных машин условие приема сообщения будет вычисляться как false.

Модель корневого объекта (Model)

Корневой объект включает один экземпляр канала и N экземпляров машин. Порты машин соединены с портом канала. Параметры, определенные в этом объекте, используются как параметры экспоненциальных распределений, генерирующих случайные времена обработки порции вычислений, задержки сообщений и т. п. В качестве аргумента функции exponential () задается средняя частота наступления события, которая обратна среднему интервалу времени между событиями.

Анимация

Анимация в этой модели играет определяющую роль не только при прове­дении компьютерного эксперимента, но и для понимания функционирова­ния системы (в данном случае — сложного распределенного алгоритма), а также для отладки самой модели.

Анимация машины представлена прямоугольником, цвет которого baseCoior меняется в зависимости от состояния машины — в стейтчарте main этот параметр устанавливается в соответствующее значение при входе в каждое из двух состояний. Прямоугольники всех экземпляров машин в корневом объекте Main должны располагаться по окружности. Координаты и угол поворота изображения машины определяются номером I экземпляра машины. Статическая функция angle(i), определенная в корневом объекте, вычисляет угол поворота вектора, направленного на изображение i-й маши­ны относительно оси X (например, 0-й экземпляр будет помещен на оси Y, т. е. вектор к этому прямоугольнику повернут на 90 градусов). Вычисляется также разворот изображения каждой машины относительно оси.

В анимации корневого объекта Model отметим технику визуализации базо­вых сообщений, находящихся в канале. Для этого в поле анимации опреде­лены n*n стрелок с координатами начала и конца, вычисляемыми для каж­дой пары машин а,k) так, чтобы стрелка была направлена от 1-го прямоугольника к k-му. Для этого в поле Дополнительный код класса опре­делены четыре функции beginX, beginY, endX, endY, определяющие коорди-

наты начала и конца стрелки, направленной от i-й машины к к-й:

double beginX(int i) {

return (R-40)*Math.cos(angle(i/N)); } double beginY (int i) {

return (R-40)*Math.sin(angle(i/N)); } double endX(int к) {

return (R-40)*Math.cos(angle(k%N)); }

double endY(int к) {

return (R-40)*Math.sin(angle(k%N)); }

Функция angle определена как арифметическая функция от целой пере­менной index:

Math.PI/2 + (2*Math.PI/N) * index

Каждая такая стрелка должна быть видима, только если сообщение от i-й машины к k-й находится в канале. Для управления видимостью в поле Дополнительный код класса определен массив onWay размером n*n, элемен­ты которого вначале равны 0, и каждый раз, как i-я машина посылает базо­вое сообщение k-й машине (переход t3 стейтчарта main активного объекта Machine, рис. 19.2), соответствующий элемент массива onway увеличивается на 1. При получении базового сообщения в порт активного объекта Machine, соответствующий элемент массива onway уменьшается на 1. Видимость стрелки от машины i к машине к установлена в true, если соответствую­щий элемент массива onway не равен 0.