Научно-образовательный кластер CLAIM

CLAIM – научно-образовательный кластер

Филиппович Андрей

Технология Виртуальных Транзактов

На практике часто встречаются такие ситуации когда одна и та же работа (задача, транзакт) может быть успешно выполнена на различных устройствах. Например, ввод текста в ЭВМ можно осуществить на любом компьютере, ввод изображений — на тех ЭВМ, к которым подключены сканеры и т.д. Если количество обслуживающих устройств недостаточно для закрепления за каждым из них отдельного вида работы, то возникает необходимость их распределения.

Для выбора обслуживающего аппарата (ОА) транзакту (системе) необходимо сравнить альтернативные варианты. В системах имитационного моделирования для реализации такого взаимодействия можно использовать различные подходы. В работе рассматриваются три альтернативных подхода: прямое распределение транзактов, обратное распределение и технология виртуальных транзактов.

Прямое распределение. При таком подходе распределение транзактов из нескольких источников может быть случайным или поочередным, т.е. каждый раз выбирается новый источник.

В классическом представлении любой ОА (устройство) может иметь очередь. В СИМ Arena блок ОА неразрывно связан с "подблоком" очереди. В других широко известных системах (GPSS, SLAM II) каждый блок представляется отдельно. При большом (значительном) количестве транзактов, они должны размещаться в очередь к одному из возможных устройств. Поэтому, одним из критериев выбора ОА может служить длина очереди к нему.

Различные устройства могут иметь различную интенсивность обработки транзактов, которую также можно учитывать при размещении в очередь.

На рис.1. представлена схема обработки четырех типов транзактов — работ по сканированию (T1), вводу текста (T2), верстке (T3) и печати (T4). Транзакты размещаются в очереди на типы работ из потоков с интенсивностями l1, l2, l3, l4. Далее они распределяются селекторами Sel1, Sel2, Sel3, Sel4 в очереди к рабочим станциям PC1, PC2, PC3, PC4.

Селектор представляет собой особое устройство (субъекта), которое осуществляет распределение транзактов на дальнейшую обработку. В примере селекторы связаны с субъектом Sub1, который представляет собой лицо, принимающее решение по распределению работ.

Недостатком описанного подхода является то, что выбор устройства эффективен только в случаях постоянной интенсивности обработки транзактов.

Рис.1. Схема с прямым распределением.

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

Существует множество способов разрешения этой проблемы:

— осуществлять регулярное перераспределение транзактов по очередям;

— рассчитать среднюю интенсивность обработки транзактов;

— создать единую (неоднородную) очередь, и при каждом захвате осуществлять поиск подходящего транзакта в очереди.

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

Рис.2. Схема с обратным распределением.

В предлагаемом варианте устройства обращаются к нескольким очередям и выбирают из них оптимальный транзакт (который имеет временной приоритет). Будем считать, что упорядочивание транзактов в очереди (сортировка) осуществляется во время обслуживания и не оказывает существенного влияния на временные задержки.

На рис.2. представлена схема такого взаимодействия. Выбор между очередями осуществляется селектором. Это приводит к одному из недостатков такого подхода, а именно, к нелинейности продвижения транзактов. Для того чтобы транзакт поступил на обработку устройство должно обратиться сначала к селектору.

Вторым, более существенным недостатком является необходимость выбора оптимального транзакта для каждого захвата. Это определяет временную задержку, зависящую от количества переборов.

Фактически количество переборов определяется числом очередей, т.к. считается, что они отсортированы, и оптимальный транзакт в очереди уже стоит на первом месте. Это время можно сократить, если осуществлять вычисление оптимального транзакта во время работы устройства. В общем случае неизвестно какое устройство освободится первым, поэтому нужно производить выбор транзакта для каждого устройства, что приведет к дополнительным затратам, а, возможно, и к недопустимым временным задержкам.

Третьим недостатком такого варианта является то, что невозможно осуществлять одновременную работу нескольких селекторов, которые связаны с общими очередями.

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

Пусть каждый селектор имеет b входов, а каждая очередь — a выходов. Каждой линии связи сопоставляется вход селектора и выход очереди.

Если считать, что транзакты равномерно распределены по всем каналам и линиям связи, то можно получить следующее соотношение:

Если рассчитать размеры очередей для схемы, приведенной на рис.2., то можно получить следующие результаты:

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

Если подставить значения в описываемом примере, то получим следующие соотношения для длин очередей:

Из примера видно, что работы, которые могут быть выполнены на большем числе устройств, имеют большие длины очередей. Если количество транзактов различного типа приблизительно одинаково, то расчет максимально возможных размеров очередей не будет оптимальным. Это связано с тем, что при выборе учитывается время поступления транзактов. Чтобы выровнять длины очередей нужно определить вероятности поступления транзактов по каналам. Очевидно, что наибольшая вероятность поступления должна быть у транзактов из тех очередей, которые имеют меньшее число выходов.

Чтобы определить более точно размеры очередей нужно произвести дополнительные расчеты. Во-первых, необходимо вычислить коэффициент для каждого канала, зависящий от числа выходов очереди.

Во-вторых, в соответствии с полученными коэффициентами и количеством входов в селектор распределить множество транзактов, приходящихся на каждый канал.

Произведем перерасчет длин очередей для примера, представленного на рис.2.:

Результаты, полученные за счет введения дополнительных коэффициентов, отражают влияние связей между очередями и селекторами. Неснятыми допущениями остаются одинаковая интенсивность поступления транзактов и постоянная длина очереди к устройству. Чтобы их снять необходимо регулировать значение коэффициента p_jи размер очереди L_i.

При изменениях интенсивности и длины очереди можно выбрать средние значения. Другим способом настройки коэффициентов может служить двухслойная нейронная сеть. Кроме того, многослойные сети могут быть использованы для многоуровневого распределения, но обсуждение этого вопроса выходит за рамки этой работы.

Технология виртуальных транзактов. Данный подход имеет очень яркое проявление в реальной жизни. Когда субъект имеет возможность выбрать одну из очередей, но не знает какая из них длинней и где быстрее обслуживают, он занимает место в нескольких очередях.

Виртуальные транзакты представляют собой копии реального транзакта, которые размещаются в несколько очередей одновременно. Когда осуществляется захват одного из транзактов, его копии удаляются. Чтобы ускорить процесс поиска и удаления копий, в очередь размещаются не сами транзакты, а указатели на них. Устройство, обнаружив пустой или занятый транзакт, пропускает его копию. На рис.3. представлена схема, на которой указаны очереди к устройствам с метками QuPC1, QuPC2, QuPC3, QuPC4 и очереди на четыре вида работ Work1, Work2, Work3, Work4.

Рис.3. Технология виртуальных транзактов.

После выхода из очереди Work транзакт автоматически дублируется и размещается во всех возможных очередях. Чтобы не возникло ситуации невозможности размещения всех копий виртуальных транзактов, очереди QuPC должны иметь неограниченную длину. Длины очередей Work могут быть вычислены аналогично с предыдущим примером.

Если в очередях QuPC осуществлять сортировку по времени (по срочности) во время работы устройства, то при этом можно автоматически удалять пустые виртуальные транзакты.

Помимо расчета максимальной длины очередей типа Work, можно вычислять текущую длину очереди типа QuPC по следующей формуле:

В заключении следует отметить достоинства технологии виртуальных транзактов:

1. Возможность эффективного распределения транзактов в очереди к нескольким устройствам;

2. Возможность работы с неоднородными очередями и различными типами транзактов;

3. Оптимальное распределение по времени при условиях сильного изменения интенсивности обработки транзактов;

4. Минимальные временные затраты СИМ на распределение (ведение и удаление) транзактов.

5. Возможность прямого движения транзактов в системе.

6. Возможность расчета текущей и максимальной длины очереди.

К ограничениям технологии виртуальных транзактов следует отнести возможность ее применения.

— Для этого реальные прототипы транзактов должны иметь возможность быстрого перемещения от одного обслуживающего аппарата к другому.

— Обычно количество ОА, на которых может быть выполнена задача, и множество типов работ незначительно, поэтому вычислительные затраты классических походов при небольших размерностях системы также незначительны.