Об одном приеме имитационного моделирования

№ 3 (27) 2010

Н. Н. Прокимнов

Об одном приеме имитационного моделирования

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

Постановка задачи

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

Рассмотрим в качестве примера классическую модель одноканальной системы массового обслуживания (СМО) с одним обслуживающим прибором и очередью с выбыванием — по истечении некоторого времени нахождения в очереди заявки, не дождавшиеся обслуживания, покидают систему (рис. 1).

Если процессы, в которых участвуют покинувшие очередь заявки, не оказывают влияния на задачи, решаемые для такой СМО с помощью имитационной модели, то построение модели трудности не представляет. Например, для оценки качества обслу-

живания, когда нужно просто учитывать долю не дождавшихся обслуживания заявок, можно построить модель, граф которой показан на рис. 2 (дальнейшее рассмотрение будет происходить применительно к языку описания моделирующей системы Pilgrim [1]):

HIIIIIII—

Рис. 1. СМО с уходами заявок

В узле key этой модели производится сортировка выходящих из узла queue транзактов (объектов системы Pilgrim, имитирующих в данном случае заявки) на тран-закты, дождавшиеся обслуживания, которые направляются в узел serv, и на условно ушедшие транзакты, которые в модели больше не нужны и уничтожаются в узле-терминаторе. Факт преждевременного ухода транзактов из очереди устанавливает-

serv

дождавшиеся

оп

Рис. 2. СМО с уходами заявок

№ 3 (27) 2010

ся путем сравнения времени пребывания в узле queue (оно находится как разность между моментом выхода из очереди, т. е. вхождения транзакта в узел key и моментом вхождения в очередь) с предельно допустимым временем ожидания. Однако для моделирования процессов с участием также транзактов, досрочно покинувших очередь, реальная картина процесса будет моделью искажаться, поскольку, войдя в узел queue, транзакты смогут покинуть его только «в порядке общей очереди». Иначе говоря, уход из очереди «нетерпеливых» заявок произойдет в модели позже фактического, поскольку будет отодвинут до «естественного» выхода из узла queue.

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

Имитационная модель СМО с уходами

Сущность предлагаемого подхода рассмотрим на примере той же модели одно-

канальной СМО и очередью с уходами зая- § вок. ц

Граф модели показан на рис. 3. Все узлы ¿1 для удобства ссылок снабжены на рисунке а; номерами, под которыми они присутствуют в * приводимом далее тексте программной модели. В момент вхождения заявки в систему (т. е. транзакта в узел queue модели) с помощью дополнительно вводимого в модель узла creat создается дубликат транзакта, который направляется также в специально добавляемый в модель узел serv. Событие регистрируется в специальном журнале (Реестр двойников), вид представления которого выбирается в зависимости от конкретной системы моделирования и предпочтений разработчика. В представленном варианте используется массив структур языка С++ (см. листинг 1): Константа chnNum в описании задает максимальный размер очереди заявок.

Вносимая в журнал запись содержит три поля:

1) idNo — идентификационный номер группы. Это значение переменной-счетчика поступающих в систему заявок, т. е. вхождений транзактов в узел creat. Значение idNo сохраняется в пользовательских параметрах каждой копии транзакта-заявки (в данной модели в параметре транзакта t—>iu3).

103

104

idNo total exits

I

>

-М -

Реестр двойников

107

serv

двоиники ушедших

<3

дождавшиеся j 111

двоиники дождавшихся

-С

ушедшие 110

105 106

Рис. 3. Корректная модель СМО с уходами заявок из очереди

79

-ч ПРИКЛАДНАЯ ИНФОРМАТИКА

№ 3 (27) 2010 ' -

Листинг 1

struct dup

{

long idNo; int total; int exits;

};

int const

int const

struct dup

int

dimWatch=10000; chnNum=1000; qWatch [dimWatch]; qWatchNum=0;

//структура записи реестра двойников

//идентификационный номер //число двойников группы //число выходов двойников из узлов

//размер реестра (массива qWatch) //число каналов сервера двойников //реестр(групп)двойников //текущее число записей qWatch

2) total — число копий транзакта в группе. В данной модели это значение равно двум (по одной копии для узлов queue и serv).

3) exits — число выходов транзактов-ко-пий группы из узлов queue и serv. В данной модели фиксируются выходы из узла queue и из добавленного в модель технологического узла serv.

Последовательно с узлами queue и serv в модель включены узлы типа key (узлы 104 и 106 на рис. 3), где реализуется основная логика работы с транзактами-копиями, которая выглядит следующим образом. При вхождении транзакта в один из этих узлов счетчик выходов exits журнала увеличивается на единицу, после чего определяется направление дальнейшего движения тран-закта. В случае равенства exits = 1 транзакт § узла key с номером 104 направляется в узел § 111 (по маршруту перемещения обслужен-^ ного транзакта), транзакт узла key с номером 106 — в узел 110 (по маршруту пере-Si мещения досрочно покинувшего очередь | транзакта). В случае exits > 1 транзакт на-| правляется в узел 112 (уничтожитель тран-Ц зактов), выполняющий функцию утилизации I ненужных копий транзактов (можно, разу* меется, использовать и любой другой узел Ц term, уже имеющийся в модели и не исполь-& зуемый в качестве средства сбора данных I моделирования).

g В случае exits = total (что означает факт сэ появления последней копии транзакта из его

группы) запись об этой группе из журнала удаляется.

Узел key 104, стоящий между узлами queue и serv, предотвращает возможность выхода транзактов из узла queue до окончания обслуживания транзакта, находящегося в узле serv. С этой целью он переводится в закрытое состояние в момент прохождения через него очередного транзакта и открывается после выхода транзакта из узла serv 107 (на рис. 3 управляющие действия обозначены пунктирными линиями).

Вся работа по реализации этой логики производится средствами, которые (так же как способ задания Реестра двойников) выбираются в зависимости от конкретной системы моделирования и предпочтений разработчика. В представленном варианте управление процессами в модели выполняется функциями языка С++, текст и краткие пояснения к которым приводятся ниже.

Функция IdNo используется для назначения очередной заявке, пришедшей в систему, идентификационного номера группы создаваемых транзактов-копий (см. листинг 2): Функция реализует правило, по которому идентификационному номеру очередной группы транзактов назначается значение минимального неотрицательного целого числа, исключая числа, занятые под идентификационные номера записей журнала.

Новую запись в реестр двойников arr[] с указанным идентификационным номе-

80 у

№ 3 (27) 2010

0

1

long IdNo (struct dup arr[], int arrNum) ^

{ *

long i, j, found; ^

for (i=0, found=1; found==1 && i<chnNum; i++) for (j=0, found=0; found==0 && j<arrNum; j++) if (arr[j].idNo == i) found=1; return (i-1);

}

ром группы idNo вносит функция SetWatch (см. листинг 3).

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

Выход из контролируемого узла (queue с номером 103 или serv с номером 105) транзакта-двойника регистрирует в реестре функция LogExit, увеличивая счетчик выходов копий транзакта exits группы с указанным идентификационным номером idNo (см. листинг 4).

Листинг 3

void SetWatch (struct dup arr[], int *arrNum,

long idNo, int total)

{

arr[*arrNum].idNo = idNo; arr[*arrNum].total = total; arr[*arrNum].exits = 0; *arrNum = *arrNum + 1;

}

В момент выхода из контролируемого узла последней копии транзакта (т. е. когда выполнится равенство exits = total) функция LogExit удаляет из реестра ставшую те-

Листинг4

void LogExit

{

int i, j, found;

for

if

{

Found = 1; arr[i].exits++;

if (arr[i].exits == arr[i].total) //удалить запись из qWatch

{

for (j=i; j<*arrNum-1; j++) arr[j] = arr[j+1]; *arrNum = *arrNum - 1;

}

}

}

81

№ 3 (27) 2010

Листинг 5

bool FirstExit

{

int i, found;

for (i=0, found=0; found==0&&i<=arrNum-1; i++) if(arr[i].idNo==idNo) found=1; if (arr[i-1].exits==0) return (true); else return (false);

}

перь ненужной запись относительно группы с данным идентификационным номером. Факт первого появления транзакта-ко-пии группы с данным идентификационным номером idNo на выходе одного из контролируемых узлов устанавливается функцией FirstExit, которая в этом случае возвращает значение true (см. листинг 5).

Ниже приводится текст программной модели, в которой используются описания переменных для задания входных параметров (см. листинг 6 и 7).

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

межутков нахождения в очереди, не приводится.

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

Листинг 6

float ModTime=2000000.0; //Г моделирования

float aTime=6.0; //средний интервал между приходами заявок

float sTime=4.0; //среднее время обслуживания заявки

float wTime=9.0; //лимит(среднее)времени ожидания в очереди

int fw; //рабочая переменная

Листинг 7

modbeg("СМО с уходами", 116, ModTime, (long)time(null), none, none, none, none, 2); ag("ИсшчникЗаявок", 101, none, expo, aTime, none, none, 102);

network

{

top(102):

t->iu3=IdNo(qWatch, qWatchNum);//сохранение идентиф. номера группы SetWatch (qWatch, &qWatchNum, t->iu3, 2);//создание записи реестра

82

№ 3 (27) 2010

Окончание листинга 7 §

X

creat("ВходМодели", 0, 1, copy, 103, 105); place; top(103):

queue("ОчередьГлавных", none, 104); place; top(104):

if (FirstExit (qWatch, qWatchNum, t->iu3)) fw=107; else fw=112; key("ВыходГлавных", fw);

clcode

{

if (FirstExit (qWatch, qWatchNum, t->iu3)) hold(104);//блокировка LogExit (qWatch, &qWatchNum, t->iu3);//регистрация выхода

}

place; top(105):

serv("Двойники", chnNum, none, expo, wTime, none, none, 106); place; top(106):

if (FirstExit (qWatch, qWatchNum, t->iu3)) fw=110; else fw=112; key("ВыходДвойника", fw);

clcode LogExit (qWatch, &qWatchNum, t->iu3);//регистрация выхода place; top(107):

serv("Сервер", 1, none, expo, sTime, none, none, 111); place; top(110):

term("Суетливые"); place; top(111):

rels(104); //разблокировка term("Упорные"); place; top(112):

term("Отработка"); place; fault(123);

}

modend("СМО с уходами.txt", 1, 16, page);

return 0;

}

№ 3 (27) 2010

Имитационная модель СМО с избирательным обслуживанием

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

Рассмотрим, в частности, обслуживание потока заявок в СМО с одной очередью и несколькими серверами, в которой заявки могут обслуживаться не любым сервером, а только входящим в специфицированную для данного типа заявок подгруппу (рис. 4).

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

I рис. 5. В целях простоты изложения число | серверов на графе ограничено двумя, а узлы | для удобства ссылок снабжены номерами. Ц В нижеследующих фрагментах текста | программной модели, поясняющих логику * работы модели с изображенным на рисун-

II ке графом, тип заявки задается значением целого числа, которое записывается в пара-

I метр транзакта в момент его создания. § Число серверов, обслуживающих заявки сэ каждого типа, задается одномерным масси-

Рис. 4. Обслуживание закрепленными серверами

вом ObsSrvNum; серверы идентифицируются их номерами — целыми числами начиная с 0; перечни номеров серверов, назначенных для обслуживания заявок, задаются двумерным массивом ObsSrv (первый индекс — тип заявки, второй индекс — порядковый номер в списке).

Узел 157 типа key, который является входным узлом для транзактов, описывается следующим образом (см. листинг 8).

Листинг 8

top(157):

key("ЦентрВход", fw); place;

Он нужен для предотвращения конфликтов между транзактами, поступающими на узел-размножитель creat (158)1 (см. листинг 9).

В узле 158 создается группа транзак-тов с числом, равным числу серверов, назначенных заявкам данного типа (элемент массива ObsSrvNum). Транзакт, вошедший в узел сгеа^ выполняет операции, аналогичные ранее описанным для модели СМО с уходами: сохранение идентификационного номера группы и внесение записи в реестр

1 Здесь и далее узлы, не представленные на рис. 5, существенного значения для описания рассматриваемого приема не имеют.

№ 3 (27) 2010

400 300 / 500

401 301 \ 501

Рис. 5. Фрагмент графа модели СМО с закрепленными серверами

• 600

«

0

1

о &

эё эй

'601

Листинг 9

top(158):

hold(157);

t->iu3 = IdNo(qWatch, qWatchNum);

addrnaQ[t->iu3]=addr[159]->na; //базовое значение (для рассылки) SetWatch (qWatch, &qWatchNum, t->iu3, ObsSrvNum[t->iu0]); сгеаСЦентрТираж", t->ft, ObsSrvNum [t->iu0], copy, 159, 992); place;

двойников. Заметим, что в отличие от модели СМО число копий в данном случае равно не двум, а числу серверов, обслуживающих заявки данного типа. Кроме того, на период выполнения служебных действий блокируется поступление новых транзактов через узел 157, а в служебном массиве addmaQ запоминается значение системного параметра addr[159]->na, в котором хранится значение числа транзактов, прошедших к этому моменту через узел 159 (см. листинг 10):

Как можно видеть из этого текста, узел 159 последовательно рассылает все копии

транзакта-заявки на узлы queue (узлы с номерами 400, 401, ...), которые имитируют ожидание в очереди к серверам на обслуживание. При этом номера узлов определяются по перечням номеров серверов, назначенных для обслуживания данного типа заявок и заданных в массиве ObsSrv.

В узле 159 узел 157 открывается для поступления новых транзактов. Узлы цепочки 400-300-500-600 имитируют ожидание и обслуживание в сервере с номером 0. В узле 400 (queue) транзакт ожидает открытия узла 300 (см. листинг 11).

Листинг 10

top(159):

queue ("ЦентрВставка", none, 400 + ObsSrv[t->iu0] [addr[159]->na - addrnaQ[t->iu3]]);

clcode rels(157);

place;

85

-ч ПРИКЛАДНАЯ ИНФОРМАТИКА

№ 3 (27) 2010 ' -

Листинг 11

top(400):

queue ("Вирт0чередь_00", none, 300); place;

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

Листинг 12

top(300):

if(FirstExit (qWatch, qWatchNum, t->iu3)) fw=500; else fw=993;

key ("КлючВхода_00", fw);

clcode LogExit (qWatch, &qWatchNum, t->iu3);

place;

Листинг 13

top(500): hold(300);

serv ("ЦентрСервер_00", 1, none, norm, ProcTime(t->ft, t-ProcTime(t->ft, t->iu0)/3, zero, 600); place;

Узел 300 пропускает на стоящий вслед за ним сервер только первую из копий тран-зактов одной группы, отправляя все прочие копии в «утиль» (узел 993) (см. листинг 12).

Узел 500 имитирует обслуживание заявки в сервере (см. листинг 13).

Параметры закона распределения времени нахождения транзакта в этом узле «зашиты» в функцию ProcTime. Выход транзак-тов из очереди 400 на время нахождения транзакта в сервере 500 блокируется.

Узел key, последний узел цепочки (с но-§ мером 600), имеет вид (см. листинг 14). Он § разрешает, открывая ключ 300, выход тран-Ц зактам из узла 400 и направляет обслуженную заявку в нужный узел модели (в данном 1 примере — в узел с номером 999). Описания | узлов других веток (на показанном графе — | ветка 401-301-501-601) аналогичны.

И

is

I Заключение

i

5 Предложенный практически опробован-

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

Листинг 14

top(600): rels(300);

key ("КлючВыхода_00", 999); place;

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

Список литературы

1. Емельянов А. А, Власова Е. А, Дума Р. В. Имитационное моделирование экономических процессов. — М.: Финансы и статистика, 2009.

2. Емельянов А. А., Власова Е. А., Дума Р. В, Емельянова Н. З. Компьютерная имитация экономических процессов / Под. ред. А. А. Емельянова. — М.: Маркет ДС, 2010.

86 у