Моделирование процессов в одноканальной системе с ограниченным ожиданием
В системе с ожиданием поступающие заявки имеют возможность ожидать начала своего обслуживания. Например, поступающие для обработки на станке заготовки и т.п. Обычно на процесс ожидания накладываются определенные ограничения, связанные с недопустимостью превышения длины очереди заявок или времени ожидания в очереди (длиной максимального интервала конкретной операции ).
На рис. 3.5 показан временной процесс обслуживания заявок в
одноканальной системе, когда имеется один обслуживающий прибор. Ограничения на ожидание определяются допустимой длиной очереди Мg=2. Поступающая в момент времени t1 первая заявка застает обслуживающий прибор ОП свободным и сразу же начинает обслуживаться, время начала ее обслуживания t1'' равно времени ее поступления в систему t1'' = t1 . Поступающие заявки образуют поток событий с заданным законом распределения. Время занятости обслуживающего прибора t
(длительность обслуживания) является случайной величиной, также описываемой конкретным законом распределения. Заявки в системе обслуживаются в порядке очереди, т.е. в том порядке, в котором они поступили в систему. Для рассматриваемого случая первая заявка успевает отслужиться в момент времени t1об
раньше поступления следующей заявки. Поэтому поступающая в момент t2 вторая заявка застает обслуживающий прибор свободным и сразу же поступает на обслуживание t2'' = t2. Во время обслуживания этой заявки дли
тельностью ?2 в моменты времени t3
, t4 , t5 поступают следующие заявки, которые застают ОП занятым. Третья и четвертая заявки дожидаются освобождения прибора от обслуживания предыдущей заявки, после чего сразу же принимаются на обслуживание t3'' = t2об
, t4'' = t3об. Для пятой заявки нарушается условие допустимой длины очереди Mg = 2, так как эта заявка поступила еще в момент обслуживания второй заявки. В результате этого эта заявка получает отказ в обслуживании. Следующая шестая заявка поступает в момент обслуживания третьей заявки, т.е. становится второй в очереди за четвертой заявкой.
Следовательно, она может ожидать начала своего обслуживания.
Один из вариантов блок-схемы алгоритма для реализации системы с ограниченным ожиданием на ЭВМ приведен на рис. 3.6. В первом блоке этой модели задаются необходимые исходные данные — число поступивших заявок i = 0, число обслуженных и потерянных заявок Nоб = 0, Nn = 0, допустимая длина очереди Мg , начальные значения времени поступления и обслуживания t0 = 0, t0об = 0. Необходимо задать также общее время
моделирования на ЭВМ Тм , вид и параметры входящего потока заявок и времени обслуживания. Например, для пуассоновского потока заявок при экспоненциальном распределении времени обслуживания одной заявки задается интенсивность пуассоновского потока ? и интенсивность обслуживания ?. В блоке 2 предусматривается реализация подпрограммы формирования времени генерации очередной заявки ?3, в соответствии с заданным потоком распределения. Примеры таких подпрограмм были рассмотрены в главе 2. Блоки 3, 4 отражают количество i и момент времени поступления в систему очередной заявки ti = ti-1 + ?3 .
После формирования очередной заявки осуществляется проверка на достижение в ЭВМ заданного времени моделирования (t1>Тм?, блок 5). При невыполнении этого условия осуществляется следующая проверка сравнения времени поступления очередной заявки со временем окончания обслуживания предыдущей заявки (ti < tобi-1 , блок 6). При выполнении этого условия, т.е. при занятом состоянии ОП, проверяется условие превышения допустимой длины очереди (i > Мg , блок 7). Если очередь выше допустимой, то вновь поступившая заявка теряется, что фиксируется в счетчике потерянных заявок (Nn = Nn+1, блок 8). Для продолжения работы модели условно принимается, что момент времени окончания обслуживания потерянной заявки t1об равен аналогичному времени предыдущей заявки t i об = t i-1об. Затем осуществляется возврат к формированию следующей заявки. При наличии очереди заявок в допустимых пределах ( i ? Mg ).
время начала обслуживания поступившей заявки принимается равным времени окончания обслуживания предыдущей заявки ( ti''= t i -1об, блок 10). Определение ti'' осуществляется также в блоке II, переход к которому происходит в ситуации, когда вновь поступившая заявка застает ОП свободным (при условии ti ? ti-1об
). В этом случае заявка сразу же принимается на обслуживание (ti'' = ti ,
блок II). В блоках 12-15 реализуется процесс обслуживания очередной заявки. В блоке 12, аналогично блоку 2, реализуется подпрограмма формирования времени обслуживания ?об в соответствии с заданным временем его распределения, в блоке 13 определяется момент окончания времени обслуживания tiоб = ti'' + ?об , в блоке 14 находится общее время пребывания заявки в системе, включая время ее ожидания и время обслуживания ?i = tiоб — ti . Блок 15 осуществляет подсчет общего числа обслуженных заявок Nоб = Nоб + 1. После этого происходит переход к генерации следующей заявки. По окончании общего времени моделирования (t > Тм ) осуществляется обработка полученных результатов, которая заключается в реализации на ЭВМ типовой подпрограммы построения гистограммы распределения времени ?i, пребывания заявки в системе, фиксации и выводе на печать числа обслуженных и потерянных заявок.
Приведенный вариант блок-схемы алгоритма системы обслуживания с ожиданием сравнительно прост, но весьма неэкономичен в отношении использования памяти ЭВМ, так как необходимо предусмотреть массивы t (i), t"(i), t об (i), ? (i) для больших значений i.
Например, при интен
сивности пуассоновского потока заявок ?=10 заявок/мин при Тм=I час среднее значение поступивших заявок составит i = 600. Для получения достоверных оценок моделирования, особенно при построении гистограммы ?i,
потребуется значение i порядка нескольких тысяч. Поэтому желательно применять алгоритмы, не требующие больших объемов хранящихся массивов, что отражено в другом варианте (рис. 3.7).
Во втором варианте используются два особых состояния системы — время поступления очередной заявки t3 без учета ее номера и время обслуживания tоб. Выполнение условия t3 < tоб
соответствует случаю поступления в данный момент времени очередной заявки. Вслед за этим определяется состояние обслуживающего прибора. При Z = 0 (блок 6) ОП свободен. Тогда время начала обслуживания этой заявки совпадает со временем ее поступления, а ОП переходит в занятое состояние (Z = 1, блок 7). Данное значение времени фиксируется в качестве первого элемента массива заявок T3 (1) = t3, блок 8. Затем выполняется подпрограмма формирования времени ?об и определяется момент времени окончания обслуживания данной заявки tоб = t3+ ?об ( блоки 9, 10), после чего осуществляется переход на формирование новой заявки.
Если поступающая заявка застает обслуживающий прибор занятым (Z ? 0, блок 6), то значение очереди заявок увеличивается на единицу (Z = Z+1, блок II), и осуществляется проверка на превышение допустимой очереди (Z > Мg ?
,блок 12). При Z > Мg фиксируется отказ от обслуживания поступившей заявки Nn= Nn + 1, после чего общая очередь Z уменьшается на 1. При Z ? Mg, в массив заявок записывается значение времени поступившей заявки (T3(z)= t3 ,
блок 13).
Выполнение условия t3 > tоб ( блок 5) соответствует случаю наступления другого события в системе— окончанию обслуживания очередной заявки, которая в массиве заявок является первой. После этого определяется время пребывания заявки в системе ?np = tоб — t3(1), сразу же определяется соответствующий интервал гистограммы, в который попадает значение ?об (блок 17), фиксируется число обслуженных заявок Nоб = Nоб+1 (блок 18), число заявок в системе Z уменьшается на I ( блок 18). Затем проверяется условие освобождения обслуживающего прибора (Z = 0, блок 20). Ситуация Z=0 соответствует случаю, когда в момент окончания обслуживания очередной заявки другие заявки в ОП не поступили.
Обслуживающий прибор становится свободным и находится с этого момента в режиме простоя, ожидая поступления следующей заявки. Поскольку время окончания обслуживания еще не поступившей заявки неизвестно, то оно условно принимается равным бесконечности ( tоб = ? , блок 21). При составлении программы на ЭВМ это время следует задавать большим числом, например, больше Тм. Аналогично это большое значение для tоб
задается в начале выполнения программы ( блок I).
Ситуация Z ? 0 ( блок 20) соответствует случаю, когда по окончании обслуживания очередной заявки имеется массив других заявок на обслуживание. Сразу же по освобождении ОП он приступает к обслуживанию следующей заявки, находящейся первой в очереди. При этом длина очереди уменьшается на единицу. Соответственно, уменьшается на единицу номер каждой заявки очереди. Коррекция очереди осуществляется в блоках 22,23. Затем определяется время и момент окончания обслуживания для заявки под номером 1, и производится возврат к блоку 5 на сравнение нового времени окончания обслуживания первой заявки из очереди tоб со временем поступления в систему следующей заявки t3
.
По окончании заданного времени моделирования (t3 > Тм ,блок 4 ) осуществляется выдача на печать гистограммы времени пребывания заявок в системе (гист ?пр , блок 26), числа потерянных и обслуженных заявок ( Nn, Nоб, блок 27).
Второй вариант алгоритма требует значительно меньшей памяти ЭВМ, так как в нем хранится лишь один массив очереди заявок t(z) и нет необходимости запоминать массивы всех поступивших и обслуживаемых заявок, по сравнению с первым вариантом.
3.5 Определение показателей надежности сетей
Сети связи относятся к сложным системам , имеющим, как правило, внутреннюю избыточность, при которой выходы из строя отдельных узлов могут не приводить к прекращению обмена сообщениями между другими узлами сети. Ниже рассмотрен вариант оценки показателей надежности между двумя фиксированными узлами сети. Отказом считается такое сочетание вышедших узлов в сети, при котором все соединительные тракты передачи между рассматриваемыми узлами прерываются.
Известны аналитические методы оценок показателей надежности сетевых структур – полный перебор всех состояний, нахождение возможных путей, определение возможных сечений, метод особой точки, логико-вероятностные методы. Получили развитие методы решений на основе теории графов. Однако для сетей большой размерности наиболее приемлемым методом будет имитационное моделирование.
На рис.3.8 приведена блок-схема алгоритма имитационного
моделирования сети без восстановления неисправностей. В качестве исходных данных вводятся интенсивности отказов отдельных узлов и соединительных путей между ними ( li, lij ), общее число отказов, разыгрываемых на ЭВМ в процессе моделирования Nмод, число узлов и матрица соединений между узлами.
В начале вычислений определяются возможные пути соединений между рассматриваемыми узлами.
Пример установления соединений для мостиковой схемы на основе последовательной фиксации соединений от исходного узла с непосредственно присоединительными к нему следующими узлами (построение дерева соединений) приведен на рис. 3.9, 3.10. Блок-схема алгоритма определения путей соединений приведена на рис.3.11.
Процесс моделирования продолжается до достижения заданного числа отказов Nмод. В случае отказа узла, не приводящего к отказу системы, данный узел далее не рассматривается ( l = l-li, li = 0) и производится корректировка возможных путей соединений путем исключения путей, проходящих через отказавший узел или соединение. В заключение по статистическим формулам находятся среднее время безотказной работы и вероятность безотказной работы системы Тс*, Рс*, а также гистограммы распределения массива Тст* ( i=1— Nмод ).
Оценку показателей надежности для сети с восстановлением необходимо производить с учетом условий восстановления отказавшего узла (рис. 3.12-3.15 ).
Для рассматриваемой сети отказ наступает при одновременном выходе из строя узлов 1,3 или 2,4.
На рис. 3.12 приводится вариант неограниченного восстановления, когда одновременно могут восстанавливаться все отказавшие узлы.
Восстановление начинается сразу же после отказа любого узла, время восстановления не зависит от состояния сети. Приняты обозначения — toi, tbi, текущее время наступления отказа, восстановление Z — индекс работоспособного (Z= 0) или отказового состояния (Z=1) iго узла , ti— время между окончанием восстановления и моментом следующего отказа i узла. Время отказового состояния t системы определяется, пока ремонтируются все узлы ( 1 и 3, 2 и 4), вызвавшие отказовую ситуацию. При восстановлении одного из них сеть переходит в работоспособное состояние. Коэффициент готовности определяется по выражению
где Nмод— задаваемое число отказов, определяющее объем
моделирования.
Условия ремонта сети, согласно рис.3.13, отличаются тем, что время отказового состояния сети определяется временем восстановления всех
отказавшихся узлов. Считается, что во время ремонта остальные узлы не отказывают.
На рис.3.14 приведен вариант восстановления системы во время плановых профилактических работ, проводимых независимо от состояния системы. Время отказового состояния системы включает в себя время ожидания ближайшей профилактики и время самой профилактики. После проведения профилактики системы полностью восстанавливается. На рис. 3.15 приведен вариант ограниченного восстановления, когда отказавшийся узел ожидает окончания ремонта предыдущего узла и время перерыва t на доставку ремонтного органа от одного узла к другому. В общем случае условия проведения ремонтных работ могут быть разнообразными для каждой конкретной системы.
На рис.3.16 приведена блок— схема алгоритма оценки показателей надежности сети с восстановлением применительно к рис.3.12.
СПИСОК ЛИТЕРАТУРЫ
1. Бусленко Н. П. Моделирование сложных систем. - М.: Наука, 1978.
2. Советов Б. Я., Яковлев С. А. М.: Высшая школа, 1985.
3. Лукьянов В. С. Решение задач в машиностроении методами имитационного моделирования: Учеб. пособие, ВолгПИ. - Волгоград, 1989.
Виктор Сергеевич Лукьянов
Георгий Валентинович Слесарев
Проектирование компьютерных сетей
методами имитационного моделирования
Учебное пособие
Редактор Е. И. Кагальницкая
Темплан 2001г., поз. № 56
Лицензия ЛР № 020251 от 16.04.1996г.
Подписано в печать .Формат 60x84 1/16.
Бумага газетная. Печать офсетная.
Усл. печ. л. 4,18. Уч. – изд. л. 4,21.
Тираж 300 экз. Заказ .
Волгоградский государственный технический университет
400131 Волгоград, пр. Ленина, 28.
РПК “Политехник” Волгоградского государственного технического университета
400131 Волгоград, ул. Советская, 35.
