Моделирование; модели систем и методы принятия решений

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Пензенская государственная технологическая академия» Бершадская Е.Г. Моделирование. Модели систем и методы принятия решений. Учебное пособие Рекомендовано Государственным учреждением высшего профессионального образования «Московский государственный технический университет имени Н.Э. Баумана» в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлению «Информатика и вычислительная техника» Пенза 2012 Рецензент Уполномоченная министерством образования и науки Российской федерации организация Государственным учреждением высшего профессионального образования «Московский государственный технический университет имени Н.Э. Баумана» Бершадская Е. Г. Моделирование. Модели систем и методы принятия решений: Учебное пособие.-Пенза: Изд-во Пенз. госуд. технол. академии, 2011. - 105-с. 35 ил., библиогр. 8 назв. Рассматриваются методики установления соответствия реальной системе на том или ином уровне некоторого математического описания и исследования его с целью получения оценок характеристик качества исследуемой системы. Среди моделей, позволяющих адекватно описывать и проводить анализ вычислительных систем и сетей с параллельно и асинхронно действующими компонентами, выделены аналитические и имитационные. Рассмотрены математические аппараты для формального описания структуры и процессов функционирования, а также средства и методы их исследования. Теоретический материал иллюстрирован примерами и сопровождается заданиями для самоконтроля. Учебное пособие подготовлено на кафедре «Вычислительные машины и системы» Пензенской государственной технологической академии и предназначено для студентов специальности 230101 «Вычислительные машины, комплексы, системы, сети» направления подготовки «Информатика и вычислительная техника», а также студентов других специальностей, изучающих отдельные разделы моделирования. 1. Общие вопросы моделирования 1.1. Основные понятия и определения теории моделирования Моделированием называется замещение одного объекта, называемого системой, другим объектом, называемым моделью, и проведение экспериментов с моделью (или на модели), исследование свойств модели, опираясь на результаты экспериментов с целью получения информации о системе. Моделирование позволяет исследовать такие системы, прямой эксперимент с которыми: а) трудно выполним; б) экономически невыгоден; в) вообще невозможен. Моделирование - важнейшая сфера применения средств вычислительной техники. В то же время сами средства вычислительной техники являются объектами моделирования на этапе проектирования новых и модернизации старых вычислительных систем, при анализе возможности использования вычислительных систем в различных приложениях. Объектом исследования в теории моделирования является система. Система — это совокупность взаимосвязанных элементов, объединенных в одно целое для достижения некоторой цели, которая определяется назначением системы. При этом элемент — это минимально неделимый объект, рассматриваемый как единое целое. Если система — это совокупность взаимосвязанных элементов, то комплекс — это совокупность взаимосвязанных систем. Элемент, система, комплекс — понятия относительные, т.к. любой элемент, если его расчленить, если его не рассматривать как неделимый объект, то он становится системой, и наоборот любой комплекс становится системой, если входящие в его состав системы рассматривать как элементы.. Для описания системы необходимо определить ее структурную и функциональную организацию. Структурная организация (структура) системы задается перечнем элементов, входящих в состав системы, и конфигурацией связей между ними. Для описания структуры системы используются способы: а) графический — в форме графа, где вершины графа соответствуют элементам системы, а дуги — связям между элементами; б) аналитический, когда задаются количество типов элементов системы, число элементов каждого типа и матрицы связей между ними. Функциональная организация (функции) системы — это правила достижения поставленной цели, правила, описывающие поведение системы на пути к цели её назначения. Способами описания функций системы являются: а) алгоритмический — в виде последовательности шагов, которые должна выполнять система; б) аналитический — в виде математических зависимостей; в) графический — в виде временных диаграмм; г) табличный — в виде таблиц, отображающих основные функциональные зависимости. Понятие состояния системы Свойства системы, значения переменных, описывающих систему, в конкретные моменты времени называются состояниями системы. Процесс функционирования системы можно рассматривать как последовательную смену её состояний во времени, другими словами, процесс функционирования системы — это переход её из одного состояния в другое. Система переходит из одного состояния в другое, если изменяются значения переменных, описывающих состояние системы. Причина изменения переменных состояния, а значит, причина, вызывающая переход системы из состояния в состояние называется событием. Событие является следствием начала или окончания какого-то действия. 1.2. Классификация систем Прежде чем классифицировать системы необходимо определить соответствующие классификационные признаки. Таковыми являются: 1) характер изменения значений переменных системы; 2) характер протекающих в системе процессов; 3) характер функционирования системы во времени; 4) режим функционирования. По первому признаку, т.е. в зависимости от того, как изменяются значения переменных, описывающих состояния системы, все системы делятся на два класса: а) с непрерывными состояниями, для которых характерен плавный переход из состояния в состояние, обусловленный тем, что переменные, описывающие состояния, могут принимать любые значения из некоторого интервала, т.е. переменные являются непрерывными величинами; б) с дискретными состояниями (дискретные системы), для которых характерен скачкообразный переход из состояния в состояние, обусловленный тем, что переменные, описывающие состояния системы, изменяются скачкообразно и принимают значения, которые могут быть пронумерованы, т.е. переменные являются дискретными величинами. По второму признаку, т.е. в зависимости от характера протекающих в системах процессов, все системы делятся на: а) детерминированные системы, в которых отсутствуют всякие случайные воздействия (факторы), а значит, поведение таких систем может быть предсказано заранее; б) стохастические системы, в которых процессы функционирования развиваются под влиянием случайных факторов (внешних или внутренних), т.е. процессы являются случайными. По третьему признаку, т.е. в зависимости от характера функционирования системы во времени, все системы делятся на: а) системы, функционирующие в непрерывном времени, когда переходы между состояниями системы возможны в любые (а, значит, в случайные) моменты времени; б) системы, функционирующие в дискретном времени, когда переходы между состояниями возможны только в определенные (дискретные), заранее известные моменты времени. По четвертому признаку, т.е. в зависимости от режима функционирования, все системы подразделяются на: а) системы с установившимся (стационарным) режимом; б) системы с неустановившимся (нестационарным) режимом; этот режим характерен для переходного этапа или для систем, функционирующих в условиях перегрузки. Проведенная классификация систем приведена ниже на рисунке. Стохастические системы с дискретными состояниями, функционирующие в непрерывном времени, часто еще называют системами массового обслуживания (СМО) или системами с очередями или Q–системами (Queue – очередь). Детерминированные системы с непрерывными состояниями, функционирующие в непрерывном времени, называют динамическими системами или D-системами (Dynamic – динамический). Рисунок 1.1- Классификация систем. Детерминированные системы с дискретными состояниями, функционирующие в дискретном времени называют конечными автоматами или F-системами (Finite – конечный). Стохастические системы с дискретными состояниями, функционирующие в дискретном времени, называют вероятностными автоматами или P-системами (Probability – вероятность). 1.3. Параметры и характеристики системы Количественно любая система описывается совокупностью величин, которые могут быть разбиты на два класса: 1) параметры , описывающие первичные свойства системы и являющиеся исходными данными при исследовании системы; 2) характеристики , описывающие вторичные свойства системы и определяемые как функции параметров системы . Параметры любой системы подразделяются на: а) внутренние, описывающие структурно-функциональную организацию системы; б) внешние, описывающие взаимодействие системы с внешней (по отношению к системе) средой. К внутренним параметрам относятся: а) структурные параметры, описывающие состав элементов системы и саму её структуру; б) функциональные параметры, описывающие функциональную организацию (процесс функционирования) системы. К внешним параметрам относятся параметры нагрузки, показывающие, как часто и в каком объеме используются ресурсы системы. В общем случае — это параметры взаимодействия системы с внешней средой. Характеристики системы делятся на: а) глобальные, показывающие эффективность функционирования системы в целом; б) локальные, описывающие качество функционирования отдельных элементов системы. К глобальным характеристикам системы относятся: а) характеристики производительности, показывающие скорость достижения цели назначения системы; б) временные характеристики, описывающие временные аспекты функционирования системы; в) надежностные характеристики, определяющие надежность функционирования системы; г) экономические характеристики в виде стоимостных показателей, свидетельствующие об экономической целесообразности использования системы. 1.4. Модель Модель — это физический или абстрактный объект, отражающий в той или иной степени процессы в исследуемой системе. Основное требование к модели – это её адекватность , под которым понимается степень соответствия процессов, протекающих в модели, процессам, имеющих место, в системе, и, следовательно, степень соответствия свойств и характеристик модели свойствам и характеристикам системы. Адекватность модели зависит от: а) степени полноты и достоверности сведений об исследуемой системе; б) степени детализации модели; в) корректности параметризации модели, под которой понимается установления соответствия между параметрами системы и модели; г) уровня подготовки и опыта самого исследователя. Классификация моделей Многообразие систем предопределяет использование для их изучения множества различных моделей. В качестве основных признаков, необходимых для классификации моделей, можно рассмотреть: 1) степень адекватности модели; 2) характер исследуемых на модели процессов; 3) способ реализации модели. По первому признаку, т.е. в зависимости от степени адекватности, модели подразделяются на: а) полные (подробные) модели, когда модель в полной мере адекватна изучаемой системе, что характерно для тривиальных систем; б) приближенные модели, когда модель не отражает некоторые аспекты функционирования моделируемой системы, что характерно для большинства моделей. По второму признаку, т.е. в зависимости от характера процессов функционирования системы, все модели могут быть подразделены на: а) непрерывные и дискретные модели — для моделирования процессов с дискретными и непрерывными состояниями; б) детерминированные и стохастические (вероятностные) модели — для моделирования соответствующих процессов функционирования систем; в) статические (структурные) и динамические (функциональные) модели; при этом статические модели используются для изучения поведения системы в отдельные моменты времени, а динамические отображают поведение системы во времени; г) модели с непрерывным и с дискретным временем — в зависимости от характера изменения во времени процессов функционирования системы (такое разделение характерно только для динамических моделей); д) стационарные и нестационарные модели — для моделирования стационарных и нестационарных процессов в соответствующих режимах функционирования системы. Классификация моделей по второму признаку во многом аналогична классификации самих систем, приведенной ранее. По третьему признаку, т.е. в зависимости от способа реализации модели или от способа представления системы, модели подразделяются на: а) физические; б) математические. Физические модели — это "материальные" модели, эквивалентные или подобные в той или иной степени оригиналу. В общем случае физические модели — это модели, процесс функционирования которых такой же, как у оригинала, имеет ту же или подобную физическую природу. Математические модели — это "абстрактные" модели, представляющие собой формализованное описание изучаемой системы с помощью абстрактного языка, в частности, с помощью математических соотношений, отображающих процесс функционирования системы. В дальнейшем при изучении дискретных систем будем рассматривать только математическое моделирование, которое, в зависимости от метода анализа моделей (признак классификации математических моделей), можно разделить на: а) аналитическое моделирование, для которого характерно то, что процессы функционирования, как отдельных элементов, так и системы в целом записываются в виде некоторых математических соотношений (алгебраических, дифференциальных, логических и т.д.); б) имитационное моделирование, когда модель воспроизводит процесс функционирования системы во времени, причем модель имитирует все элементарные составляющие процесса с обязательным сохранением их взаимосвязанности и взаимообусловленности, логической структуры и последовательности протекания по времени; в) комбинированное моделирование, когда процессы функционирования одних элементов системы моделируются аналитически, а процессы функционирования остальных — имитационно. Аналитические модели могут быть исследованы следующими методами: а) аналитическими, когда (путем применения математических правил) для характеристик функционирования системы получены явные аналитические зависимости от параметров системы и параметров внешних воздействий. б) численными, когда для модели, хотя она реализована аналитически (например, в виде системы уравнений), не удается получить в явном виде зависимости характеристик (не удается решить систему уравнений); при этом математические операции заменяются операциями над числами. Основным достоинством аналитического моделирования является возможность детального (полного) анализа характеристик системы в широком диапазоне изменения исходных данных. Однако характерные для аналитического моделирования явные математические соотношения удаются, как правило, получать только для сравнительно простых систем или ценой определенных предположений и допущений, которые "уводят" исходную модель от реальной системы и тут же возникает вопрос об адекватности модели. В тех случаях, когда исследование систем методами аналитического моделирования (даже численными) затруднительно или невозможно, эффективными методами исследования, а зачастую единственными практически доступными, становятся методы имитационного моделирования, базирующееся на теории статистических испытаний. Основное преимущество имитационного моделирования перед аналитическим — это возможность моделирования более сложных систем с учетом таких условий и факторов, которые исключают применение методов аналитического моделирования. Однако существенный недостаток имитационного моделирования — это трудоемкость построения модели и частный характер получаемых результатов. 2. Аналитическое моделирование 2.1. Элементы теории массового обслуживания Исследование ВС предполагает построение математических моделей, отображающих, в зависимости от их назначения, структуру и процессы функционирования. Для современных вычислительных машин и систем характерна работа в режиме решения потока случайных по своим характеристикам задач, поступающих, в общем случае, в случайные моменты времени. Анализ ВС с учетом вероятностного характера протекающих в них процессов возможен методами теории массового обслуживания (МО). Предмет теории МО - системы массового обслуживания (СМО) и сети МО. Под СМО понимают динамическую систему, предназначенную для эффективного обслуживания случайного потока заявок (требований на обслуживание) при ограничениях на ресурсы системы. Рассмотрим схему СМО(рисунок 2.1). Рисунок 2.1- Структурная схема СМО Поступающие на вход СМО однородные заявки (однородное обслуживание) в зависимости от порождающей их причины делятся на типы, интенсивность потока заявок типа . Первопричина заявок - называется источником заявок, а совокупность заявок всех типов - входящим потоком СМО. Обслуживание заявок выполняется совокупностью m, в общем случае, разнотипных каналов, (или приборов обслуживания). Различают универсальные и специализированные каналы обслуживания. Для универсального канала типа j считаются известными функции распределения длительности обслуживания данным каналом j заявок произвольного типа . Для специализированного канала функции распределения длительности обслуживания заявок являются неопределенными, назначение заявок этих типов на данный канал недопустимо. Принимаем к рассмотрению универсальные однотипные каналы обслуживания, т.е. Fji()=Fi(), j= . В произвольный момент времени канал занят обслуживанием только одной заявки, допускается прерывание начатого обслуживания. Если в момент появления заявки на входе СМО есть свободный канал, ее обслуживание начинается немедленно. Если СМО загружена, т.е. каналы все заняты, заявка занимает место в очереди. На число мест в очереди может быть наложено ограничение. При этом возможны конфликтные ситуации, решением которых может быть либо отказ системы принять заявку, либо принятие заявки в систему за счет выталкивания из очереди другой, менее ценной в данный момент времени заявки. В зависимости от числа мест в очереди различают СМО с отказами и без отказов. В СМО с отказами число мест в очереди конечно и, вследствие вероятностного характера как входящего потока, так и процессов обслуживания, существует ненулевая вероятность того, что все каналы заняты обслуживанием и заняты все места в очереди заявками, т.е. заявка получит отказ. В СМО без отказов заявка либо сразу назначается на обслуживание, либо безусловно принимается в очередь. В зависимости от допустимого времени пребывания заявок в системе различают СМО с “нетерпеливыми” и “терпеливыми” заявками. Первая может уйти из очереди и из системы, если ее  превысит некоторое доп., которое в общем случае случайно и характеризуется некоторым распределением. Терпеливая заявка, попав в СМО, дождется конца обслуживания. Процесс продвижения заявок в СМО осуществляется по некоторому закону управления процессами в СМО, который задается дисциплинами ожидания и обслуживания. Дисциплина ожидания определяет порядок приема заявок в систему и размещения их в очереди, а дисциплина обслуживания - порядок выбора заявок из очереди для назначения на обслуживание. Различают СМО с бесприоритетными и приоритетными дисциплинами. В безприоритетных все заявки считаются равноправными, в приоритетных- одни типы заявок имеют более высокий приоритет (более важны с точки зрения критерия эффективности). Совокупность обслуженных и потерянных (не обслуженных и недообслуженных) заявок образуют выходящий поток СМО. В зависимости от структуры выходящего потока различают СМО без потерь (“чистые” СМО) и СМО с потерями (“смешанные”). Для чистых нет ограничений на число мест в очереди и на время пребывания заявки в системе. В зависимости от характера источника заявок различают разомкнутые и замкнутые СМО. В разомкнутых СМО число заявок неограниченно, поведение источника заявок не связано с состоянием СМО ни в данный, ни в какой-либо из предыдущих моментов времени. Для замкнутых СМО характерно конечное число заявок, циркулирующих в системе “источник-СМО”. Обслуженные заявки возвращаются в источник и через некоторое случайное время могут вновь появиться на входе СМО. Поведение источника в замкнутых СМО является некоторой функцией состояния СМО. По числу каналов обслуживания СМО делятся на одноканальные и многоканальные. По типу потока заявок, поступающих в СМО, различают системы с однородным потоком, когда в СМО поступает один поток заявок, и системы с неоднородным потоком, когда поступает М потоков заявок (М>1), характеризующихся разными временами обслуживания. Соответственно формируется одна или несколько очередей. Заявка на решение некоторой задачи, поступающая в ВС, проходит последовательно этапы счета, обращения к внешним устройствам. После выполнения последовательности этапов заявка считается обслуженной и покидает ВС. Таким образом, ВС можно представить как совокупность СМО. Совокупность взаимосвязанных СМО называется сетью массового обслуживания (стохастической сетью). 2.1.1. Параметры и характеристики СМО Первичные свойства СМО, их количественные оценки называются параметрами СМО. Остальные, относящиеся к вторичным, их количественные оценки называются характеристиками СМО. СМО можно характеризовать следующей совокупностью параметров и характеристик: параметрами входящего потока заявок; параметрами структуры СМО; параметрами закона управления процессами в СМО и следующими характеристиками СМО. Введем обозначения и дадим определения основных характеристик качества функционирования СМО 1. Загрузка системы - это отношение интенсивности поступления заявок  к интенсивности обслуживания : (1) Заменив величиной /, получим =, (2) где  -средняя длительность обслуживания единой заявки. Значение загрузки определяет условие существования стационарного режима работы системы. Если , т.е. интенсивность поступления заявок превышает интенсивность их обслуживания, то система работает в режиме перегрузок. Случай =1 является нетривиальным и требует всякий раз особого рассмотрения. В дальнейшем будет всегда предполагать существование стационарного режима. Раскроем физический смысл загрузки. Загрузка характеризует: 1) среднее число заявок, поступающих в систему за среднее время обслуживания одной заявки; 2) долю времени, в течение которого обслуживающий прибор занят обслуживанием заявок; 3) вероятность того, что в произвольный момент времени обслуживающий прибор работает (не простаивает). Первое утверждение вытекает непосредственно из определения загрузки, а справедливость второго утверждения можно доказать простыми рассуждениями. Пусть рассматриваемая система функционирует в течение достаточно большого периода времени Т. Среднее число заявок Т, поступивших в систему за это время будут обслуживаться в среднем в течение времени Т. Тогда доля времени, в течение которого система была занята обслуживанием заявок, . Третье утверждение непосредственно вытекает из второго. Заметим, что второе и третье утверждение справедливы лишь в случае, когда  < 1. Значение определяет вероятность простоя системы и называется коэффициентом простоя. Наиболее полной характеристикой, на основе которой могут быть рассчитаны все остальные характеристики, является вероятность состояния системы. Под состоянием системы будем понимать число заявок, находящихся в системе, которое складывается из числа заявок в очереди и на обслуживании. Вероятность состояния Pk есть вероятность того, что в системе находится ровно k заявок . Качество функционирования системы определяется временем пребывания заявок в системе, равным промежутку времени от момента поступления заявки в систему до момента окончания ее обслуживания. Время пребывания u складывается из времени ожидания , когда заявка находиться в очереди, и времени обслуживания . . (3) В общем случае время ожидания  является суммой двух составляющих: , (4) где н - промежуток времени от момента поступления заявки в систему до момента, когда заявка в первый ряз принимается на обслуживание, п - время ожидания в прерванном состоянии, связанное с прерыванием обслуживания рассматриваемой заявки и ожиданием дальнейшего обслуживания. Если обслуживание заявки не прерывается, то п = 0 и  = н Число заявок в системе m связано с временем прибывания заявок в системе u зависимостью . (5) Это выражение становится очевидным, если учесть, что за время u в среднем поступает u заявок. Выражение (5) называется формулой Литтла [1]. Очевидно, что число заявок в системе складывается из числа заявок, находящихся в очереди и ожидающих обслуживания, и числа заявок, находящихся на обслуживании в приборе. Для системы с неограниченной очередью среднее время ожидания  связано со средним числом заявок в очереди l = , (6) то есть за промежуток времени от момента поступления заявок до момента принятия ее на обслуживание (за время ожидания ) в систему в среднем поступает  заявок. Если теперь в выражение (5) подставить (3) и (6), получим: . Таким образом, среднее число заявок в системе больше средней длины очереди заявок на величину загрузки , которая в данном случае имеет смысл среднего числа заявок, находящихся на обслуживании. На рис.2.2. приведена временная диаграмма работы СМО, позволяющая визуально проследить динамику системы и выделить детали исследуемых вероятностных процессов. Диаграмма дана для обслуживания в порядке поступления и соответствует случаю одного обслуживающего прибора. На диаграмме нижняя ось времени соответствует очереди, а верхняя- прибору обслуживания. Входящие снизу стрелки (как для оси очереди, так и для оси обслуживания указывают на поступление заявки. Стрелки, выходящие сверху, обозначают уход требования из очереди. На диаграмме приняты следующие обозначения: zn - n-я заявка, поступающая в систему; n - время поступления заявки zn ; tn - промежуток времени между zn-1 и zn, ; n - время обслуживания заявки zn ; n - время ожидания в очереди заявки zn.; un - время пребывания в системе Рисунок 2.2. - Временная диаграмма работы СМО Из рисунка 2.2. видно, что заявка поступила в очередь на обслуживание раньше чем заявка освободила обслуживающий прибор. Так как заявка может быть обслужена только лишь после того, как заявка освободит прибор, то в системе происходят одновременно два события: завершается обслуживание заявки и поступает в обслуживающий прибор. Другой пример дает заявка , которая, приходя в систему, застает обслуживающий прибор свободным и обслуживание этой заявки начинается немедленно. На диаграмме видно также время ожидания и время пребывания заявки в системе (заметим, что ). В нестационарном режиме вероятностные характеристики меняются со временем, причем, нестационарность может быть связана с двумя факторами: а) с началом работы системы, когда характеристики функционирования, меняясь со временем, стремятся в пределе к характеристикам стационарного режима; такой режим называется переходным режимом работы системы и длится от момента начала работы системы до момента входа в стационарный режим; б) с перегрузкой системы, когда характеристики функционирования, менялись со временем, растут неограниченно; такой режим называется режимом перегрузок. Условие его существования . Основными характеристиками, определяющими качество функционирования СМО, являются: 1) загрузка системы; 2) вероятность состояния системы; 3) число заявок находящихся в системе; 4) длина очереди заявок; 5) время пребывания заявок в системе; 6) время ожидания заявок. 2.1.2. Системы потоков. Потоки заявок Совокупность событий, распределенных во времени, называется потоком. Если событие заключается в появлении заявок, имеем поток заявок. Описан он может как неубывающий случайный процесс Z(t), принимающий значения 0, 1, 2,...m. Процесс Z(t) есть число заявок, поступивших за промежуток времени (0,t). Пусть t1, t2, ... - моменты поступления заявок и - промежуток времени между двумя последовательными моментами поступления заявок (k-1) и k . Поток, в котором k=const для всех , называется детерминированным, или регулярным. Поток, в котором k представляет собой случайные величины, описываемые законом распределения, называется случайным потоком. Поток, для которого функции распределения случайных величин k () одинаковы, т.е. , для всех , называется рекуррентным потоком. Рекуррентным потоком с запаздыванием называется поток, который может быть описан с помощью двух функций распределения . Характеристикой потока заявок является его интенсивность , которая равна среднему числу заявок, поступающих в единицу времени. Величина , (обратная) определяет средний интервал времени между двумя последовательными заявками. Поток называется стационарным, если интенсивность и закон распределения промежутков времени между заявками не меняются во времени. В противном случае поток нестационарный. Поток называется ординарным, если в каждый момент времени может появиться не более одной заявки. Если в каждый момент появляется более одной заявки, то имеем групповой поток заявок. Поток заявок называется потоком без последействия, если заявки поступают независимо друг от друга, т.е. момент поступления очередной заявки не зависит от того, когда и сколько заявок поступило до этого момента. 2.1.3. Простейший поток Простейший поток обладает следующими свойствами: - стационарностью (вероятностные характеристики не зависят от времени); - отсутствием последействия (заявки поступают в систему независимо друг от друга, и длина интервала t до момента поступления следующей заявки не зависит от того, поступила в начальный момент заявка или нет); - ординарностью (в каждый момент времени в систему может поступить не более одной заявки). Для простейшего потока интервалы времени между двумя последовательными заявками есть независимые случайные величины с функцией распределения ;. Распределение такого вида называется показательным (экспоненциальным) и имеет плотность распределения интервалов времени между заявками (рисунок 2.3) (7) Рисунок 2.3.- График экспоненциального распределения. Математическое ожидание длины интервала времени между последовательными моментами поступления заявок: (8) Дисперсия интервала времени между последовательными моментами поступления заявок (9) Определим вероятность того, что промежуток времени между соседними заявками окажется короче среднего, т.е. (10) Т.е. короткие интервалы более часты, чем длинные, и при простейшем потоке заявки обнаруживают тенденцию к группировке, что создает более тяжелые условия при работе системы. Для простейшего потока число заявок, поступающих в систему за промежуток времени t, распределено по закону Пуассона (рисунок 2.4): (11) где - вероятность того, что за время t в систему поступит k заявок,  - интенсивность потока заявок. Рисунок 2.4.- График распределения Пуассона. (12) (13) Распределение Пуассона дискретно, в то время как распределение интервалов времени в простейшем потоке непрерывно. Если нестационарный поток, интенсивность которого , описывается законом распределения Пуассона, то такой поток называется пуассоновским, но не простейшим, поскольку не выполняется условие стационарности. Простейший поток - это стационарный пуассоновский поток. Особенности простейшего потока 1. Сумма М независимых, ординарных, стационарных потоков заявок с интенсивностями сходится к простейшему потоку с интенсивностью , при условии, что все оказывают более или менее одинаково малое влияние на суммарный поток. Простейший поток обладает устойчивостью, т.е. при сумме независимых простейших получается простейший поток. 2. Для простейшего потока характерно, что поступление заявок через короткие промежутки времени более вероятно, чем через длинные (63%), что создает более тяжелый режим работы системы. Если реальный поток отличен от простейшего, то система будет функционировать не хуже, чем это следует из полученных оценок предельных значений характеристик качества обслуживания. 3. Интервал времени между произвольным моментом t и моментом поступления очередной заявки имеет такое же распределение, что и интервал между двумя последовательными заявками. 2.2. Марковские модели В теории СМО к наиболее изученным и исследованным относятся модели, у которых случайный процесс функционирования относится к классу марковских процессов, т.е. марковские модели. Случайный процесс называется марковским, если вероятность любого состояния системы E в будущем зависит только от состояния в настоящем и не зависит от того, когда и каким образом система пришла в это состояние. Описывающий поведение системы процесс называется цепью Маркова. Описать процесс - значит определить вероятность того, что в момент времени t система находится в том или ином состоянии. Для случайных процессов с дискретным временем изменения состояний происходят только в определенные моменты времени . Переходы описывают вероятностями переходов (Pij). . Для марковских процессов с непрерывным временем промежуток времени между переходами из одного состояния в другое случайно. Вероятность перехода из не может быть задана. Вместо вероятностей вводится параметр, называемый интенсивностью перехода : (предел отношения вероятности перехода из в за промежуток к длине ). Если или постоянны и не зависят от момента времени или (когда начинается), то марковский процесс называется однородным. 2.2.1. Элементы теории процессов гибели и размножения Среди классов марковских процессов с непрерывным временем интерес представляет частный класс процессов размножения и гибели, в которых состояние системы за любой бесконечно малый промежуток времени изменяется не больше, чем на единицу [2]. Обозначим через Ек состояние системы, когда в ней содержится k заявок. И будем рассматривать переход системы лишь в соседние состояния Eк-1 и Ек+1. (рис.2.5). Обозначим через к - интенсивность размножения, она характеризует среднюю скорость рождений (т.е. поступления новых заявок) в состоянии Ек. Аналогично, через к обозначим интенсивность гибели, задающую скорость, с которой происходит гибель (т.е. уход заявок из системы после обслуживания) в состоянии Ек. Заметим, что интенсивности размножения и гибели не зависят от времени, а зависит только от состояния Ек. Более точно, некоторый процесс представляет собой процесс размножения и гибели, если он является однородной цепью Маркова с множеством состояний , если рождение и гибель являются независимыми событиями и если выполняются следующие условия: 1) вероятность того, что в промежутке времени поступит только 1 заявка, в состоянии Ек равна 2) вероятность того, что в промежутки времени закончит обслуживание только 1 заявка, в состоянии Ек равна 3) вероятность того, что в промежутке времени не поступит ни одной заявки, в состоянии Ек равна 4) вероятность того, что в промежутке времени ни одна заявка не закончит обслуживание в состоянии Ек равна Согласно этим условиям можно ввести предположение кратных событий: кратные рождения, кратные гибели и одновременные рождения и гибели в течении малого промежутка времени имеют вероятность бесконечно малую, порядка . Определим вероятность того, что в некоторый момент времени t в системе находится k заявок и обозначим эту величину . Рассмотрим возможные изменения количества заявок в системе в промежутке времени . В момент система будет находится в состоянии Ек, если произошло одно из трех (взаимно исключающих и исчерпывающих все возможности) событий: 1) в момент времени t количество заявок было равно k и в течении времени не произошло изменения состояния; 2) в момент времени t количество заявок было равно k-1 и в течении времени поступила еще одна заявка (рождение); 3) в момент времени t количество заявок было равно k+1 и в течении времени закончила обслуживание одна заявка (гибель). Рисунок 2.5 - Возможные переходы в состояние Ек На рисунке 2.5. представлены эти три возможности. Вероятность первого события равна вероятности того, что в момент времени t процесс находится в состоянии Ек, умноженной на вероятность перехода в течении времени из состояния Ек в состояние Ек (т.е. на вероятность отсутствия на интервале рождения или гибели); Эта возможность описывается первым слагаемым в правый части написанного ниже равенства (14). Второе и третье слагаемые в правой части этого равенства соответствуют остальным двум указанным выше событиям. Переходы в состояние Ек из состояний не являющихся соседними не рассматриваются, т.к. предполагается, что вероятности таких событий в промежутке времени имеют порядок . Таким образом можно записать (14) Эти три вероятности можно складывать, потому что соответствующие события, очевидно взаимно исключают друг друга. Ясно, что равенство (14) имеет смысл только при k  1. Граничное равенство при k=0 имеет, в частности, следующий вид (15) Кроме того, в момент времени t все возможные состояния должны удовлетворять условию: (16) Теперь воспользуемся предположениями А, В, С, Д для вычисления коэффициентов, входящих в систему уравнений (14) - (15). Это приведет рассматриваемую систему к виду + (17) (18) В уравнении (18) использовано следующее предположение: если в системе нет ни одной заявки, то не может произойти гибели (т.е. ), но может произойти рождение Раскрывая скобки в правых частях (17) и (18) получаем: ; Выделяя теперь из обеих частей в обоих равенствах и деля на , приходим к уравнениям: (19) (20) Переходя к пределу при , видим, что левые части в уравнениях (19) и (20) представляют собой производные от по t, а член стремится к нулю. Следовательно, окончательно уравнения записываются в виде: (21) Формулы для определения вероятностей состояний, полученные в результате решения уравнений Колмогорова (21) имеют вид: Эти формулы часто используются при решении задач теории массового обслуживания. Уравнения (21) являются искомой системой дифференциально-разностных уравнений, описывающих динамику рассматриваемого вероятностного процесса. Решение этой системы представляет собой характеристику . На рисунке 2.6. показан граф переходов для процесса размножения и гибели. Рисунок 2.6 - Граф переходов для процесса размножения и гибели Граф позволяет наглядно описать процесс перехода системы из одного состояния в другое. Ребра указывают возможные переходы, а приписанные им числа соответствуют интенсивностям размножения и гибели. 2.2.2. Пуассоновский процесс как процесс чистого размножения Рассмотрим простейший процесс чистого размножения, который определяется как процесс, для которого при всех k. Для упрощения предположим, что для всех k=0,1,2,... . Подставляем эти значения в уравнения (21) получаем (22) Предположим также, что процесс начинается в нулевой момент времени при нуле членов, т.е. (23) Отсюда для получаем решение (24) Подставляя это решение в уравнение (22) при k=1 приходим к уравнению Решение этого дифференциального уравнения, очевидно имеет вид Далее по индукции в качестве решения уравнения (22) находим (25) Распределение вероятностей, задаваемое формулой (25) носит название закона распределения Пуассона, а случайный процесс, управляемый этим распределением - процессом Пуассона. Таким образом процесс чистого размножения с постоянной интенсивностью  приводит к последовательности рождений, образующих Пуассоновский процесс. Условимся рассматривать процесс Пуассона как модель нестационарного потока заявок, поступающих в СМО. Тогда в уравнении (25)  означает интенсивность потока заявок, а величина при начальных условиях (23) означает вероятность появления k заявок в промежутке времени (0, t). На рисунке 2.7 показана форма распределения Пуассона для некоторых частных значений t. Рисунок 2.7 - Распределение Пуассона Математическое ожидание М и дисперсия D распределения Пуассона (26) Среднее значение и дисперсия числа поступающих заявок для распределения Пуассона одинаковы. Формула (24) означает, что в течение промежутка времени длительностью t не появится ни одна заявка. Обозначим через длину промежутка времени, в течение которого не появится ни одной заявки. Тогда вероятность того, что эта длина окажется больше, чем t, равна Р0(t) и тем самым Обозначим - функцию распределения вероятностей. Т.к. является вероятностью того, что время между соседними заявками не превышает t, то (27) Дифференцируя это равенство, находим плотность распределения (28) Приведенные равенства (27) и (28) описывают экспоненциальное или показательное распределение. Графики распределения вероятностей соответствующие различным значениям  приведены на рисунке 2.8 Рисунок 2.8 - Плотность распределения интервалов времени между заявками Равенства (27) и (28) показывают, что для Пуассоновского потока интервалы времени между соседними заявками распределены по экспоненциальному закону; обычно говорят, что пуассоновский поток заявок характеризуется экспоненциальным распределением интервалов времени между заявками. 2.2.3. Анализ характеристик СМО В теории массового обслуживания приняты сокращенные обозначения, в основе которых лежит трехбуквенное обозначение вида ., где A и B описывают соответственно законы распределения промежутков времени между последовательно поступающими заявками и распределение времени их обслуживания, а величина m - число обслуживающих приборов. A и B принимают значения из следующего набора символов: M - показательное распределение; Er - распределение Эрланга порядка r; D - детерминированное распределение ; G - распределение общего вида. Иногда приходится указывать также емкость накопителя системы (которую обозначим через K) или число источников нагрузки (которое обозначим через М). В таком случае будет использоваться пятибуквенное обозначение: А/B/m/K/M. В случае отсутствия одного из последних индексов предполагается, что его значения сколь угодно велико. Например, запись вида D/M/2/20 означает систему с двумя обслуживающими приборами постоянным (детерминированным) временем между двумя последовательно поступающими заявками, показательным распределением длительности обслуживания и накопителем емкостью 20 заявок. 2.2.4. Характеристики СМО типа М/M/1 Система М/M/1 является простейшей. Она представляет собой классический пример, для рассмотрения которого требуется лишь элементарный математический аппарат. Хотя метод рассмотрения системы СМО прост, поведение ее во многих отношениях подобно поведению более сложных СМО. СМО М/M/1 представляет собой систему с одним обслуживающим прибором, пуассоновским входящим потоком и экспоненциальным распределением длительности обслуживания. Таким образом, в такой системе полностью известны распределения вероятностей промежутков времени между последовательными требованиями и распределение вероятностей времени обслуживания. Предположим, что дисциплина обслуживания бесприоритетная, в порядке поступления (FIFO - First Input First Output). Рассматриваемая система может быть представлена, как показано на рисунке 2.9 Рисунок 2.9 - Одноканальная СМО СМО может работать в двух режимах: а) в стационарном б) в нестационарном. При работе в стационарном режиме вероятностные характеристики функционирования системы не зависят от времени. Необходимым условием существования стационарного режима одноканальной СМО является условие , т.е. интенсивность поступления заявок должна быть меньше интенсивности их обслуживания. Рассмотрим процесс размножения и гибели, в котором все интенсивности размножения полагаются постоянными и равными , для и все интенсивности гибели полагаются постоянными и равными при . Этот процесс размножения и гибели с постоянными коэффициентами представляет собой систему типа М/М/1. В этом случае средняя длина промежутка между соседними требованиями равна и среднее время обслуживания равно ; это следует из того, что обе случайные величины t и  распределены по экспоненциальному закону. Таким образом можно записать: На рисунке 2.10 приведен граф переходов для СМО типа М/М/1 Рисунок 2.10 - Граф переходов для СМО типа М/М/1 Из общего уравнения (21) найдем дифференциально-разностные уравнения, соответствующие данному случаю: (29) Таким образом, уравнения (29) представляют собой математическую модель одноканальной СМО типа М/М/1, когда поток и обслуживание являются соответственно пуассоновским и экспоненциальным. Решением системы дифференциальных уравнений (29) являются функции . Для стационарного режима согласно уравнениям (29) имеем следующую систему алгебраических уравнений. (30) c условием, что Решая последовательно уравнения системы (30) при и т.д. получаем: при (31) при (32) Вид равенств (31) и (32) подсказывает, что общее решение системы уравнений (30) нужно искать в виде (33) Для того, чтобы найти P0, подставим выражение (33) в условие нормировки (30) Для системы, работающей в стационарном режиме, т.е. , получим, что сумма в последнем выражении представляет собой сумму членов геометрической прогрессии со знаменателем . Тогда (34) Подставляя (27) в (26) получим (35) Величина при называется загрузкой системы и является основной характеристикой СМО. Согласно (35), распределение вероятностей имеет вид 0,1,2 ... (36) Это распределение называется геометрическим. Важно заметить, что вероятности зависят от  и  только через их отношение . На рис. 2.11. показаны значения вероятностей для рассматриваемой системы, задаваемые формулой (14), в случае, когда Рисунок 2.11 - Стационарные вероятности для СМО типа М/М/1 Продолжая исследование системы М/М/1, найдем средние характеристики обслуживания для рассматриваемой системы. Число заявок в системе определяется соотношением: , где . (37) График среднего числа заявок в системе показан на рисунке 2.12. Рисунок 2.12 - Зависимость среднего числа заявок в системе М/М/1 Длина очереди заявок определяется соотношением: (38) Из выражения (38) следует, что число заявок в системе больше средней длины очереди на величину загрузки: Время пребывания заявок в системе можно определить применяя формулу Литтла из выражения (37). Получаем следующие равенства для среднего времени пребывания заявок в системе. (39) График зависимости среднего времени пребывания заявок в системе от коэффициента загрузки  приведен на рис.2.13. Величина u, соответствующая точке , равна среднему значению времени обслуживания заявки. Иными словами, в этом случае заявка ожидает очереди и обслуживается в среднем единиц времени. Рисунке 2.13 - Зависимость среднего времени пребывания заявки в системе типа М/М/1 Время ожидания заявок в очереди также определяется из формулы Литтла: Используя выражение получаем (40) На рисунке 2.14 приведен график зависимости времени ожидания заявок в системе от загрузки. Рисунок 2.14 - Зависимость времени ожидания от загрузки Из графика видно, что время ожидания растет с увеличением загрузки. При . При малых незначительные колебания загрузки не приводят к значительному увеличению времени ожидания, а при даже незначительные загрузки недопустимы. т.к. приводят к резким изменением времени ожидания. 2.2.5. Характеристики ВС как сложной СМО 1. Многомерный поток. Hа вход СМО поступает многомерный поток заявок типов 1, 2, ..., М с интенсивностями . Пусть каждый будет простейшим. Загрузка прибора потоком i-типа будет - ср. длительность обслуживания заявок типа i Условие существования стационарного режима: . Остальные характеристики обслуживания определяются для каждого i - потока в отдельности по формулам для системы М/M/1. Среднее время ожидания ср и обслуживания uср по одной заявке из суммарного потока в системе связаны со средними количествами заявок в очереди и в системе следующими соотношениями: (41) где ; - вероятность того, что поступившая заявка является заявкой i - типа; lCP - средняя длина очереди заявок всех типов; mCP - среднее число заявок всех типов систем. 2. Многоканальная СМО М/M/n Граф переходов для такой СМО приведён на рисунке 2.15 Рисунке 2.15. Граф переходов для многоканальной СМО М/M/n В такой СМО интенсивности перехода в правое состояние определяются как и у одноканальной СМО. Иначе обратный переход. Переход требует завершения обслуживания в одном из двух каналов, т.е. . Суммарный поток обслуживания k - каналами имеет интенсивность k. При интенсивность обслуживания сохраняется n. Получаем модель размножения и гибели. Делая выкладки, как для одноканальной СМО: (42) 3. СМО с отказами На вход поступает простейший поток заявок с интенсивностью . Поток обслуживания имеет произвольный закон с интенсивностью . Очередная заявка, поступившая в систему, когда все каналы заняты, покидает ее без обслуживания, т.е. очереди в системе отсутствуют. Характеристиками такой системы могут быть пропускная способность, вероятность обслуживания и среднее число занятых каналов. Данная система соответствует модели размножения и гибели. На основании общих формул (решение системы Колмогорова) вероятность того, что в СМО все каналы заняты ; Вероятность того, что заявка будет обслужена ; Пропускная способность: ; (43) Среднее число занятых каналов . (44) 4. Характеристики ВС систем как стохатических сетей. Обычно ВС представляется не одной СМО, а стохаcтической сетью. Для списания ВС в виде сети определяются следующие параметры. 1) число СМО, образующих сеть ; 2) число каналов каждый СМО ; 3) матрица вероятностей передач , где вероятность того, что заявка, покидающая систему Si, поступает в систему Sj . 4) интенсивность 0 источника заявок S0 в разомкнутой сети или число М заявок в замкнутой сети; 5) средние длительности обслуживания заявок 1, 2, ... k в системах S1, S2, ...Sk. Рассмотрим характеристики экспоненциальных сетей с простейшими входными потоками и распределенными по экспоненциальному закону длительностями обслуживания заявок в различных системах сети. В установившемся режиме вероятность передачи заявки из Si в Sj равна доле потока, поступающего из Si в Sj. Если система без потерь, то на входе Si поток с интенсивностью , i=0,1, ...k (45) Из этой системы уравнений находятся соотношения интенсивностей , j=1, 2, ... ,k, (46) где j - коэффициент передачи, который определяет среднее число этапов обслуживания одной заявки в Sj. Для замкнутой сети 0=1. Определяются вероятности состояний, которые характеризуются вероятностью того, что в состоянии Sj находятся М1 заявок, в системе S2 - M2 заявок и т.д. Для разомкнутой сети можно считать, что сеть состоит из совокупности независимых СМО с простейшими входными потоками. Для каждой СМО характеристики определяются отдельно. Существенный недостаток сетевых моделей - трудность учета таких ситуаций, когда заявке требуется одновременно несколько ресурсов а применение аналитического моделирования целесообразно для предварительной оценки характеристик ВС. Вообще говоря, в теории массового обслуживания имеются аналитические формулы для простейших СМО при одномерном и многомерном потоке заявок для одноканальных и многоканальных систем без ограничений и с ограничениями длин очередей, при известных и произвольных как распределениях длительности обслуживания, так и периодов поступления заявок [2]. Существующая теория массового обслуживания к сожалению, дает ответы только в простейших случаях, чаще всего не интересных для практики. Жизнь заставляет создавать значительно более сложные системы массового обслуживания, свойства которых необходимо уметь предвидеть, т. е. отвечать на вопросы о длине очередей в будущей системе, среднем времени ожидания обслуживания и т. д. Именно для этого применяется метод имитационного моделирования. Только он позволяет получить ответы на вопросы, задаваемые разработчиками систем массового обслуживания. 2.3. Тренировочные задания к разделу 1. На вход трехканальной СМО (N = 3) с «чистым» ожиданием поступает простейший паток требований с интенсивностью  = 4 треб/мин. Время обсл обслуживание требований – показательное с параметром Определить, существует ли стационарный установившийся процесс обслуживания требований. Если такой режим существует, то найти вероятности Pk (k = 0, 1, 2, 3) состояний СМО, вероятность Pоч наличия очереди и среднюю ее длину l. Решение. По условию, Тогда загрузка: т.е.стационарный режим существует (условие существования стационарного «установившегося» режима т.е., когда плотность входящего потока не превосходит  плотности потока «обслуживаний». В противном случае, очередь становится не стационарной, СМО «захлебнется» потоком требований. Далее P0 = 0,111 P1 = 0,222 P2 = 0,222 P3 = 0,148 Вероятность наличия очереди треб 2. На АТС, имеющую четыре линии связи, поступает простейший поток вызовов, интенсивность которого равна 3 вызовам в минуту. Возможные повторные вызовы входят в этот поток. Вызов, заставший все линии занятыми, получает отказ. Средняя длительность разговора tобс = 2 мин. Найти: 1) вероятность отказа системы; 2) ср. долю времени, в течении которого АТС не загружена Решение 3. На должность механика по ремонту оборудования претендует 2 человека. Число однотипных технических устройств, которые в случае поломки нужно ремонтировать = 10. Первому из претендентов, способному в течении одного часа отремонтировать 5 устройств платят 3 у.е. в час; второму, который в течении одного часа – 8 устройств – 5 у.е. в час. В предположении, что частота появления неисправных технических устройств подчинена пуассоновскому закону распределения со средним = 4 и продолжительностью обслуживания распределенной экспоненциально. Требуется принять решение – на каком претендентов следует остановить выбор. 3 P0 = 2 P1 + 3 P2 4 P1 = P0 + 3 P3 4 P2 = 2 P0 + 2 P3 4 P3 = 2 P1 + P2 P1 + P2 + P3 + ...P = 1 4. На вход двухпроцессорной ВС поступают заявки, образующие три простейших входящих потока с интенсивностями 1=6 сек-1, 2=15 сек-1, 3=9 сек-1. Процессоры принимаются однотипными со средним быстродействием В=50 тыс. опер/сек. Обслуживание заявки заключается в выполнении на любом из процессоров соответствующей прикладной программы, причем средняя трудоемкость всех трех прикладных программ принимается примерно одинаковая =2,5*103 опер. От заявки к заявке конкретная трудоемкость меняется случайным образом с законом ее распределения экспоненциальным. Для хранения заявок, которые не могут быть немедленно поставлены на обслуживание, выделена буферная зона памяти в 8 ячеек, служебная информация об одной заявке занимает две ячейки памяти. Время пребывания заявки в системе не должно превышать случайной величины доп, распределенной экспоненциально с математическим ожиданием доп=0,1 с. Операционная система реализует бесприоритетные дисциплины ожидания и обслуживания, в ее же функции входит удаление “устаревших” заявок из системы. Критерий эффективности системы имеет вид: где - штраф за отказ СМО принять заявку; - штраф за устаревание заявки за время обработки ее системой (за уход “нетерпеливой” заявки); - штраф за не использование одного канала обслуживания. Необходимо для заданных параметров СМО и заданного критерия эффективности (=3 усл. ед., =2 усл. ед., =10 усл. ед.) определить Е. Сформулируем задачу в терминах теории МО. Рассматривается многоканальная () разомкнутая СМО с потерями, число мест в очереди n=8 яч/2 = 4 яч. Заявки “нетерпеливы”, интенсивность простейшего потока уходов Составляющие входящего потока – простейшие потоки заявок с интенсивностями 1=6 сек-1, 2=15 сек-1, 3=9 сек-1. Поскольку в СМО приняты бесприоритетные дисциплины ожидания и обслуживания, то удобно рассматривать единый входящий поток заявок с суммарной интенсивностью =1+2+3=30 сек-1 . Поток обслуживания для одного канала имеет интенсивность Найти значение критерия эффективности для заданных параметров СМО. 1.Определим предельные вероятности состояний. S0 – в СМО нет ни одной заявки, каналы простаивают; S1 – в СМО 1 заявка, ее обслуживанием занят 1 канал, другой простаивает, очередь отсутствует; S2 – в СМО 2 заявки, каналы заняты, очередь отсутствует; S3 – в СМО 3 заявки, последняя в очереди; Sm+n, когда заняты каналы и места в очереди, СМО не способна принять дополнительно ни одной заявки, т. е. все вновь приходящие заявки получают отказ. Переходы между состояниями будут происходить под действием входящего потока заявок, потоков уходов "“нетерпеливых” заявок из очереди или канала обслуживания, потоков обслуживания. - интенсивность обслуживания “нетерпеливых” заявок. - интенсивность переходов за счет независимых уходов “нетерпеливых” заявок из очереди. Итак: Введя - приведенная интенсивность. - приведенная интенсивность потока уходов из канала обслуживания. - приведенная интенсивность потока уходов из очереди. Р0=? - длина очереди Итак: Предельная вероятность состояния S0 Предельные вероятности других состояний: Р1=0,3534; Р2=0,1767 – очередь отсутствует; Р3=0,0757; Р4=0,0287; Р5=0,0095; Р6=0,0029 – имеет очередь. 2. Среднее число каналов, занятых обслуживанием определяется из закона распределения вероятностей состояний и по связи номера состояния с числом занятых каналов: Загрузка каналов Средняя длина очереди: Среднее число заявок в системе Определим вероятности частных потерь В системе Рn=Pотк+Руб+Ру от возможны потери заявок в форме отказа вследствие переполнения системы, либо в форме ухода “нетерпеливых” заявок из системы Ротк=Р6(Sm+n)=P6=0,0029. Pу=Ру об+Ру ож Вероятность ухода заявки во время обслуживания Ру об = Ру ож= Вследствие совместности этих событий Ру=0,3708. Рn=0,3708+0,0029=0,3737. Вероятность обслуживания т. е. Вероятность появления в потоке обслуженных заявок произвольной заявки из входящего потока Роб=1-Рn=1-0,3737=0,6263 Интенсивность потока обслуженных заявок На основании найденных показателей определим значение критерия эффективности 2.4. Тест по разделу 1. Что характерно для “чистой” СМО? а) отсутствие очереди; б) отсутствие всех ограничений на обслуживание; в) отсутствие приоритетов в обслуживании. 2. Укажите, что является параметрами СМО. а) интенсивности поступления заявок и их обслуживание; б) интенсивности поступления заявок, их обслуживание, структура; в) закон распределения интервалов времени между заявками. 3. Укажите характеристики СМО. а) загрузка, число заявок в системе, длина очереди; б) время обслуживания; в) загрузка, вероятность состояния системы, среднее число заявок в системе, средняя длина очереди, время пребывания заявки в системе, время ожидания. 4. Какой поток из перечисленных является простейшим? а) ординарный, стационарный; б) ординарный, нестационарный; в) неординарный. 5. На входе СМО имеется простейший поток заявок с интенсивностью =4сек-1. В среднем, Через какой интервал времени заявки поступают в систему? а) 4 сек; б) 2 сек; в) 0,25 сек. 6. На входе СМО имеется простейший поток заявок с интенсивностью =2сек-1. В среднем, сколько заявок поступает в систему за единицу времени? а) 1 б) 0,5 в) 2 7. Имеется СМО типа M/M/1. В каком режиме работает система? а) в стационарном; б) в нестационарном; в) это зависит от загрузки. 8. На входе СМО имеется пуассоновский поток заявок с интенсивностью 4 сек-1. Какими свойствами обладает этот поток? а) ординарный; б) нестационарный; в) стационарный. 9. Имеется СМО типа M/M/1. Каким теоретическим распределением описываются интервалы времени между заявками на входе СМО? а) распределением Пуассона; б) распределением экспоненциальным; в) равномерным распределением. 10. Имеется СМО типа M/M/10. Какими состояниями опишется система при отсутствии очереди? а) Р0 б) Р1, Р2, … Р10 в) все возможные состояния. 11. Имеется СМО типа M/G/n. Дайте полную характеристику этой системы. а) СМО с одним обслуживающим прибором; б) многоканальная СМО с простейшим потоком заявок на входе и произвольным законом распределения времени их обслуживания; в) многоканальная СМО. 12. На вход трехканальной СМО с чистым ожиданием поступает простейший поток заданий с интенсивностью =4сек-1. Время обслуживания показательное с параметром =2сек-1. Существует ли стационарный установившийся процесс обслуживания? Перечислить состояния с отсутствием очереди. а) существует: Р0; б) не существует; в) существует: Р0, Р1, Р2, Р3. 3. Моделирование систем и сетей на основе аппарата сетей Петри (N-схем) Важной особенностью функционирования многих систем, и прежде всего систем и сетей массового обслуживания, является параллельный характер протекающих процессов, сопровождающийся сменой дискретных состояний, обеспеченной выполнением тех или иных условий. Для построения адекватных моделей подобных систем эффективно применение сетей Петри (N-схем). Одно из основных достоинств аппарата сетей Петри (СП) заключается в том, что они могут быть представлены как в графической форме (что обеспечивает наглядность), так и в аналитической (это позволяет автоматизировать процесс их анализа). 3.1. Формальное определение сетей ПЕТРИ Представление сети ПЕТРИ основано на двух понятиях: событие и условие. Событие – это действие, имеющее место в системе и которое может осуществляться один раз, много раз, ни разу. Условие – это предикат или логическое состояние системы. Условие может принимать значение “истина” или “ложь”. Возникновением события управляет состояние системы. Состояние системы может быть описано множеством условий. Для того, чтобы событие произошло, необходимо выполнение соответствующих условий. Эти условия называются предусловиями события. Возникновение события может вызвать нарушение предусловий и может привести к выполнению других условий – постусловий. В сети ПЕТРИ каждому событию формально соответствуют переходы Т, а условиям – позиции Р. Связи переходов и позиций задаются входными и выходными функциями. Входная функция I отображает переход в множество позиций, называемых входными позициями перехода. Выходная функция О отображает переход во множество позиций, называемых выходными позициями перехода. Таким образом, сеть ПЕТРИ определяется функциями, переходами и позициями. Например, задана сеть С=(Р,Т,I,О), где Р=(р1,р2,р3,р4,р5); Т=(t1,t2,t3,t4); I(t1)=(p1), I(t2)=(p2,p3,p5), I(t3)=(P3), I(t4)=(p4); O(t1)=(p2,p3,p5), O(t2)=(p5), O(t3)=(p4), O(t4)=(Р2). Определение 1. Сеть ПЕТРИ является четверкой С=(Р,Т,I,O), где Р=(р1,Р2,....,Рn) - конечное множество позиций; n >= 0, n = |Р|. T=(t1,t2,....,tm) - конечное множество переходов, m >= 0, m=|T|, ТР = 0. I:TP - отображение из переходов в множество позиций. О:ТР - отображение из переходов в множество позиций. Справедливо также I:P T ; O:P T . Иначе, сеть ПЕТРИ - это четверка С=(Р,Т,I,О), задающая причинно-следственные связи между событиями и условиями в моделируемой системе [3]. Это формальное определение сетей ПЕТРИ. Более удобно графическое представление сетей ПЕТРИ. Теоретико– графовым представлением сети Петри является двудольный ориентированный мультиграф. Структура сети ПЕТРИ представляет собой совокупность позиций и переходов, связанных входящими и выходящими данными. В соответствии с этим граф обладает двумя типами вершин - позициями и переходами. Ориентированные дуги соединяют позиции и переходы. Дуга направленная от позиции Рi к переходу tj определяет позицию, которая является входом перехода. Кратные входы в переход указываются кратными дугами из входных позиций в переход. Выходная позиция указывается дугой от перехода к позиции. Поэтому сеть ПЕТРИ - это мультиграф. Таким образом, вершины графа можно разбить на два непересекающихся множества вершин Т и Р так, что каждая дуга будет направлена от элемента одного множества к элементу другого множества. Следовательно, такой граф является ориентированным двудольным мультиграфом или просто графом сети ПЕТРИ. Определение 2. Граф сети ПЕТРИ есть двудольный ориентированный мультиграф G=(V,A), где V=(v1,v2,....,vs) - множество вершин; А=(а1,а2,....,аr) - множество дуг, aj=(vj,vk), где vj, vk V. Множество V=PUT, P T=0 и для любой направленной дуги ai A, если ai=(vj,vk), тогда либо vj P и vk T, либо vj T, a vk P. Граф сети ПЕТРИ, эквивалентный заданной структуре имеет вид (рис.3.1.) Рисунок 3.1.- Графическое представление сети Пример. Гибкий производственный модуль (ГПМ) задан следующей структурой: Рисунок 3.2. - Структурная схема ГПМ Для такой системы событиями являются: № События Переходы 1 Магазин поступил в ГПМ t1 2 ОЦ начал обработку t2 3 ОЦ закончил обработку t3 4 Деталь в контейнере t4 а, условиями: № Условия Позиции 1 Заготовка ждет Р1 2 ОЦ свободен Р2 3 Заготовка обработана Р3 4 Деталь получена Р4 Такое представление системы легко моделировать сетью Петри, где условия отображаются позициями, а события – переходами. Входные и выходные функции примут следующий вид: События Предусловия (входная функция I) Постусловие (выходная функция 0) t1 I(t1) = { } O (t1) = {P1} t2 I(t2) = {P1, P2} O (t2) = {P3} t3 I(t3) = {P3} O (t3) = {P2, P4} t4 I(t4) = {P4} O (t4) = { } 3.2. Маркировка сетей ПЕТРИ Маркировка – это присвоение маркеров (фишек) позициям сети ПЕТРИ. Количество и положение их при выполнении сети могут изменяться. Иначе, маркировка – это процедура приписывания соответствующим позициям ёмкости k-го условия, т.е. целого неотрицательного числа (Pk)>=0,которое характеризует степень выполнения k-го условия. Если (Pk)=0, то условие не выполнено, а при (Pk)>0, условие выполнено. Емкость в сети изображается с помощью маркера, который изображается точкой, либо числом, если ёмкость большое число. Маркировка: PN, это функция, отображающая множество позиций P в множество неотрицательных целых чисел. Маркировку можно представить в виде вектора. Маркированная сеть ПЕТРИ это совокупность структуры сети ПЕТРИ и маркировки, т.е. М=(P,T,I,O,). Пример. Опишем сетью Петри работу гибкого производственного модуля (рис. 3.2.) При этом входы перехода I(ti), являются предусловиями соответствующего события; выходы O (ti) постусловиями. Возникновение события равносильно запуску соответствующего перехода. Выполнение условия представляется фишкой в позиции, соответствующему этому условию. Запуск перехода удаляет разрешающие фишки, представляющие выполнения предусловий и образует новые фишки которые представляют выполнение постусловий. СП- модель будет иметь вид: 3.3. Правила выполнения сетей ПЕТРИ 1. Разрешенный переход (возбужденный) - это переход ti, для которого при маркировке выполняется условие: (Pk)>=#(Pk,I(ti)) PkI(ti). Рассматривают только входные позиции (из которых есть стрелка в переход). Для каждой входной позиции выписываем ее емкость и требуем, чтобы емкость была не меньше, чем кратность дуги, выходящей из этой позиции в переход. Физически разрешенный переход обозначает, что событие может произойти. 2. Срабатывание перехода ti - это локальное действие, связанное с изменением количества маркеров во входных и выходных позициях разрешенного перехода ti по следующему правилу: (Pк)= (Pк)-#(Pk,I(ti))+#(Pk,O(ti)) для всех Pk  P. Если позиция Pk не связано с ti переходом, то маркировка останется прежней. Для входных позиций маркировка равна предыдущей минус кратность дуги, идущей в переход. Для выходных позиций новая маркировка равна старой плюс кратность входящей дуги. 3. Функционирование сети ПЕТРИ - это процесс последовательного срабатывания разрешенных переходов, в ходе которого происходит смена маркировки сети до тех пор, пока не будет получена тупиковая маркировка. 3.4. Правила срабатывания переходов 1. Если среди входных функций Pk перехода ti имеется хотя бы одна позиция без маркера, то ti не может сработать. В общем случае, если (Pk)<=(Pk,I(ti)), то переход ti не сработает. 2. Дополнительные маркеры во входных позициях перехода ti не влияют на его запуск. 3. Переход ti может сработать всякий раз, когда он разрешен. При этом срабатывание перехода может произойти через любой конечный промежуток времени после его разрешения, т.е. переход может быть в возбужденном состоянии сколь угодно долго на конечное время, после чего он срабатывает, или возбуждение с него снимается срабатыванием другого перехода. 4. Если два перехода имеют общую входную позицию, которая содержит один маркер, то срабатывает один из них, а эта позиция называется конфликтной. 5. Если имеется несколько попарно независимо-разрешенных переходов, то их срабатывание происходит в любой последовательности или параллельно. Обозначим отношение непосредственного следования после маркировки после срабатывания перехода ti следующим образом: Маркировка , достижимая в результате последовательности переходов из начальной маркировки запишется так: Множество всех маркировок, достижимых в сети из начальной маркировки называется множеством достижимости. Пример. Дана сеть Представим множество достижимости деревом. 3.5. Ординарные сети Петри Вообще, СП моделируют широкий класс дискретных систем, но для некоторых распространенных классов систем удобно применять СП не общего вида, а некоторые их подклассы, более простые и более адекватные рассматриваемым системам. Они получаются в основном путем упрощения топологий (графовой структуры) сетей. В общем случае, для срабатывания перехода t при функционировании сети требуется, чтобы каждая его входная позиция Р имела разметку, не меньшую, чем кратность дуги, соединяющей Р и t, а после срабатывания перехода t разметка любой его выходной позиции Q увеличивается на кратность дуги, соединяющей t и Q. Для срабатывания перехода в ординарной СП требуется, чтобы каждое его входное место содержало хотя бы одну фишку, а после срабатывания перехода каждое его выходное место получает дополнительно по одной фишке. Для теоретического анализа СП удобно ограничиться рассмотрением ординарных сетей Петри. Алгоритм преобразования сети Петри в ординарную. 1.Для всех определяется n (Pk) = 2. 3. Устанавливаются “нормальные” переходы T=(t1,...tm) 4. 5. Для каждого Рк с n (Pk)2 образуется “кольцевая” подсеть 6. Каждый нормальный переход связывается с соответствующими позициями (для n(Pk)=1) и позициями (Pk,1; Pk,2; ... Pk,n(Pk)) (для n(Pk2) согласно тем связям, которые имелись в сети С, лишь бы не возникали ситуации, когда переход ti и позиция Pk,i связаны более, чем одной дугой. 7. Пример. Пусть дана сеть Петри 1. 2. 3. t1, t2, t3 –“нормальные” переходы 4.-5. Кольцевые переходы 6.-7. 3.6. Некоторые свойства сетей Петри Для моделирования систем наибольший интерес представляют временные, стохастические и функциональные сети Петри. Временная сеть Петри характеризуется тем, что вводятся данные задержки при перемещении маркеров. Задержки можно относить к переходам или позициям, они могут быть детерминированными или случайными величинами. Стохастическая сеть Петри характеризуется случайными задержками. В стохастических сетях Петри возможно введение вероятностей срабатывание возбужденных переходов. С помощью стохастических сетей Петри можно получать те же результаты, что и с помощью модель систем массового обслуживания. Функциональная сеть Петри характеризуется тем, что отражает не только последовательность событий (поток управления), но и процессы обработки некоторого потока данных. Для этого в описании каждого перехода добавляется алгоритм обработки данных. С помощью функциональных сетей Петри можно моделировать разнообразные элементы ВС, производить статистическую обработку результатов моделирования, отображать различные алгоритмы функционирования. Цветная сеть Петри используется тогда, когда требуется отличать друг от друга некоторые группы маркеров. Например, при моделировании гибких производственных систем маркеры могут отображать детали разных типов, которые должны направляться в определенные сборочные центры. Для разнотипных деталей вводятся разноцветные маркеры со своими правилами перемещения между позициями. Автоматная сеть Петри – это сеть, в которой каждый переход имеет только один вход и один выход. В автоматной сети число маркеров постоянно. Эти сети по своим возможностям моделирования эквивалентны конечным автоматам. Основное назначение сетей Петри – использование их в качестве имитационных моделей для изучения поведения проектируемых систем при заданных внешних воздействиях. Эти модели используются не только для имитации, но и для исследования некоторых общих свойств систем, не связанных с конкретными внешними воздействиями. 3.7. Представление моделей систем сетью Петри 1. Моделирование простой ВС. События – переходы: t1 – появление задачи не входа ВС; t2 – начало решение задачи; t3 – окончание решения; t4 – выход решенной задачи из ВС. Позиции – условия: Р1 – во входной очереди есть задачи; Р2 – решение окончено; Р3 – процессор свободен; Р4 – в выходной очереди есть задача. Начальная маркировка . Приход задачи в ВС отображается запуском перехода t1 и появлением маркера в Р1. Это влечет срабатывание t2 0,0,1,1 и далее t40,0,1,0 – что приводит ВС в состояние, соответствующее исходной маркировке. 2. Стохастическая сеть Петри для моделирования процессов отказов и устранения неисправностей в технической системе, состоит из 3-х рабочих блоков и одного запасного. Событиям – переходам соответствуют случайные временные задержки: t1 – интервал времени между отказами; t2 – время замены неисправного блока; t3 – время восстановления отказавшего блока. Исходная маркировка Отказ t1 2,1,1,0 Замена блока t2 3,0,0,1 Восстановление блока t3 3,0,1,0 3. Задача о производителе и потребителе. Процесс – производитель создает объекты, которые помещаются в буфер. Потребитель ждет, пока объекты будут помещены в буфер, удаляет оттуда и использует. 3.8. Классификация сетей Петри по динамическим свойствам 1. Безопасная сеть Петри – это маркированная сеть Петри в которой число маркеров в любой из позиций Рi Р никогда не превышает 1. 2. k – ограниченная СП – маркированная сеть, в которой каждая маркировка не превосходит числа k. Замечание 1. 1 – ограниченная - это безопасная СП. 3. Ограниченная СП – это маркированная сеть СП, в которой для любой позиции Рk Р можно найти , для которой она является k ограниченной . 4. Строго сохраняющаяся СП – маркированная сеть СП, в которой в процессе функционирования общее число маркеров остается постоянным: 5. Сохраняющаяся СП – это сеть, для которой существует положительный не нулевой вектор такой, что для него выполняются равенство: Частный случай: это строго сохраняющийся СП. Пример. Сохраняющаяся сеть. Существует такой вектор 6). Живая СП – маркированная сеть, в которой для каждого перехода ti при любой маркировке достижимой из можно получить с помощью совокупности отношений непосредственного следования маркировку при которой переход будет разрешимый Теорема 1. Алгоритм преобразования СП в ординарную СП без потерь сохраняет основные свойства исходной сети ограниченность сохраняет и живость. 3.9. Анализ сетей Петри Основные направления анализа сети Петра следующие: 1. Проблема достижимости: в сети Петри с начальной разметкой требуется определить, достижима ли принципиально некоторая разметка из . С точки зрения исследования моделируемой системы, эта проблема интерпретируется как проблема достижимости (реализуемости) некоторого состояния системы. 2. Анализ модели на сохраняемость позволяет определить свойство сети на невозможность возникновения или уничтожения ресурсов в моделируемом объекте. 3. Свойство живости. Под живостью перехода понимают возможность его срабатывания в данной сети при начальной разметке . Анализ модели на свойство живости позволяет выявить невозможные состояния в моделируемой системе (например, неисполняемые ветви в программе). Анализ живости сети позволяет исследовать отсутствие тупиков, зацикливаний, блокировок в моделируемом процессе, например, в процессе передачи сообщений в вычислительной сети или при выполнении параллельных программ на многопроцессорных системах. 4. Безопасность сети. Безопасной является такая сеть Петри, в которой ни при каких условиях не может появиться более одного маркера в каждой из позиций. Для исследуемой системы это означает возможность функционирования ее в стационарном режиме. На основе анализа данного свойства могут быть определены требования к буферным накопителям в системе. А в общем случае К – ограниченность - это свойство сети Петри, когда число маркеров в любой из ее позиций не превышает К. Ограниченность означает, что число ее состояний конечно. 3.10. Метод анализа сети Петри на основе покрывающего дерева Определения. Покрывающее дерево – это ориентированное корневое дерево, вершинам которого соответствует достижимое из маркировки , а дугами являются разрешенные переходы ti , определяющие отношение непосредственного следования: где и соответственно начало и конец дуги, помеченной символикой ti. Для ограниченных СП покрывающее дерево есть дерево достижимости. 1) Расширенная маркировка. Введем - обозначающая число маркеров и пусть удовлетворяет следующим требованиям: а) nN, >n б) n+=+n=+=-n=-= в) n = n= г) 0 = 0=0 Расширенная маркировка это маркировка, в которой компоненты могут быть либо натуральными числами либо . 2) Корневая вершина – вершина покрывающего дерева, соответствующая начальной маркировке ; 3) Граничная вершина – вершина покрывающего дерева, не обработанная алгоритмом. 4) Терминальная вершина – вершина покрывного дерева, соответствующая тупиковой маркировке. 5) Дублирующая вершина – вершина покрывающего дерева, которая соответствует маркировке , уже ранее встречавшейся. 6) Внутренняя вершина – вершина покрывающего дерева, обработанная алгоритмом и ни является не терминальной, ни дублирующей. Алгоритм построения покрывного дерева 1. Корневая вершина – принимается за граничную вершину X. 2. Пока имеются граничные вершины, они обрабатываются данным алгоритмом, в противном случае – дерево построено. 3. Если - тупиковая маркировка, то соответствующая вершина X – терминальная . 4. Если существует вершина то Х – дублирующая. 5. Если Х – внутренняя вершина, то для каждого разрешенного в перехода ti имеется вершина Z, которая соединяется другой от X к Z и отмечается соответствующим символом ti. 6. Вершине Z соответствует , компоненты которой определяются следующим образом: а) если ; б) если есть вершина У с такая, что то принимаем ; в) если (а) и (б) не имеют места, то для всех позиций Рк, для которых принимаем . 7. Вершина Х переопределяется как внутренняя, а полученная вершина Z становится граничной вершиной Х. 8. Все вычисления повторяются с п.3 Теорема 2. Покрывающее дерево, построенное с помощью алгоритма является конечным. Теорема 3. Процесс построения покрывающего дерева заканчивается за конечное число шагов. Пример. Пусть дана сеть Петри: Ее покрывающее дерево: 3.11. Е – сети Достоинства сетей Петри заключаются в том, что они: 1) позволяют моделировать параллельные процессы всех возможных типов с учетом вероятных кон­фликтов между ними; 2) обладают наглядностью и обеспечивают возможность автоматизирован­ного анализа; 3) позволяют переходить от одного уровня детализации описания системы к другому (за счет раскрытия/закрытия переходов) Вместе с тем, сети Петри имеют ряд недостатков, ограничивающих их возмож­ности. Основной из них — время срабатывания перехода считается равным 0, что не позволяет исследовать с помощью сетей Петри временные характеристики мо­делируемых систем. В результате развития аппарата сетей Петри был разработан ряд расширений. Одно из наиболее мощных — так называемые Е - сети (evaluation — «вычисления», «оценка») — «оценочные сети». В отличие от сетей Петри, в E – сетях: 1) имеются несколько типов вершин-позиций- простые позиции, позиции-оче­реди, разрешающие позиции; 2) фишки (маркеры) могут снабжаться набором признаков (атрибутов); 3) с каждым переходом может быть связана ненулевая задержка и функция пре­образования атрибутов маркеров; 4) введены дополнительные виды вершин-переходов; 5) в любую позицию может входить не более одной дуги и выходить также не более одной. В связи с этим любой переход может быть описан тройкой параметров где S — тип перехода, , — функция задержки, , — функция преобразования атрибутов Базовые переходы следующие. T-переход («исполнение», «простой переход»). Его графическое представление аналогично представлению вершины-перехода сети Петри. Переход срабатывает при наличии маркера во входной позиции. Формально это можно записать так: T-переход позволяет отразить в модели занятость некоторого устройства (под­системы) в течение некоторого времени, определяемого параметром t(d). F-переход («разветвление»). Графическое представление: Срабатывает при тех же условиях, что и T-переход С содержательной точки зрения F-переход отображает разветвление потока информации (транзактов) в системе. J - переход(«объединение»). Графическое представление: Переход срабатывает при наличии маркера в обеих входных позициях- Он моделирует объединение потоков или наличие нескольких условий, опреде­ляющих некоторое событие. Х-переход («переключатель») По сравнению с тремя предыдущими типами переходов он содержит дополни­тельную управляющую («разрешающую») позицию, которая графически обозна­чается обычно либо квадратиком, либо шестиугольником Логика его срабатывания задается следующими соотношениями:b Х-переход изменяет направление потока информации. В общем случае разрешающая процедура может быть сколь угодно сложной, но сущность ее работы заключается в проверке выполнения условий разветвления потока (с точки зрения программиста разрешающая позиция аналогична условному опе­ратору типа if). Y-переход («выбор», «приоритетный выбор»). Этот переход также содержит разрешающую позицию: Логика срабатывания Y-перехода: Y-переход отражает приоритетность одних потоков информации по сравнению с другими. При этом разрешающая процедура может быть опреде­лена различным образом: как операция сравнения фиксированных приоритетов меток; как функция от атрибутов меток (например, чем меньше время обслужи­вания, тем выше приоритет). В некотором смысле он работает аналогично оператору выбора типа case. В Е - сети все переходы обладают свойством безопасности. Это означает, что в выходных позициях (которые в свою очередь могут быть входными для следующе­го перехода) никогда не может быть более одной метки. Вместе с тем, в Е - сетях существуют понятия макроперехода и макропозиции, которые позволяют отображать в модели процессы накопления обслуживаемых объектов в тех или иных узлах системы. Рассмотрим некоторые из них. Макропозиция очередь представляет собой линейную композицию вершин-по­зиций и T-переходов; количество вершин-позиций определяет «емкость» очереди: Макропозиция генератор позволяет представлять в сети источник маркеров (транзактов): Если необходимо задать закон формирования маркеров, то «генератор» может быть дополнен разрешающей позицией. Поскольку в E-сети нельзя «накапливать» маркеров, то вводится макропозиция поглощения: В целях повышения компактности и наглядности сети для обозначения мак­ропозиций используют специальные символы Аналогичным образом путем композиции N однотипных переходов могут быть получены макропереходы всех типов: Рассмотренные особенности сетей существенно расширяют их возможности для моделирования дискретных систем вообще и параллельных процессов в част­ности. Ниже приведен пример описания в виде Е - сети мультипрограммной вычис­лительной системы. Обработка поступающих заданий организована в ней по прин­ципу квантования времени: каждому заданию выделяется равный отрезок (квант) процессорного времени; если задание выполнено, то оно покидает систему, если же времени оказалось недостаточно, то задание встает в очередь и ждет повторного выделения кванта времени. Рисунок 3.3 - Пример описания вычислительной системы в виде Е - сети На рисунке переходы, соответствующие определенным событиям в системе , имеют следующие обозначения.: - постановка задания в очередь; - выполнение задания в течение одного кванта времени; - анализ степени завершенности задания. 3.12. Пример использования аппарата сетей ПЕТРИ при разработке имитационных моделей В заданную систему моделирования входят следующие компоненты: ОП - устройство служащее для хранения информации (данных, программ, промежуточных и конечных результатов обработки), а также для непосредственного использования в процессе выполнения операций в АЛУ и устройстве управления процессора. ЦП - устройство, служащее для непосредственного осуществления процесса обработки данных и программного управления этим процессом. 2 НМД - устройства, предназначенные для хранения дискретной информации типа Винчестер и используются в качестве внешних запоминающих устройств. Исходя из имеющихся данных, формализуем модель системы в виде схемы (рисунок 3.4): Рисунок 3.4 Обозначения: И - источник заявок; Н1, Н2 - накопители для хранения заявок; К1, К2, К3, К4 - каналы обслуживания (ОП,П,В1,В2); L1, L2 - емкость накопителя. Запрос поступает в ОП, где считывается необходимая для работы ЦП информация (команды программы и операнды, над которыми производятся предусмотренные командами операции). Далее запрос поступает в ЦП, который дешифрирует и выполняет команды программы. Затем равновероятно обращение запроса к ОП или НМД, т.е. результаты выполнения операций из ЦП направляются в ОП или НМД1 (НМД2). Прежде, чем записать результаты на "Винчестеры", необходимо вторично обратиться к ЦП, который определяет состояние накопителей и выдает нужную информацию управления. "Винчестеры" могут работать в 3-х режимах: 1)В1 - захвачен, В2 - свободен; 2)В2 - свободен, В1 - захвачен; 3)В1 - захвачен, В2 - захвачен. С помощью сетей ПЕТРИ моделируются процессы, представляемые в виде последовательности событий. Принято считать, что события происходят мгновенно. Каждому из возможных событий соответствует определенный переход. Событие происходит, если выполнены некоторые условия. Каждому из условий в сети ПЕТРИ соответствует определенная позиция. Число состояний в сети ПЕТРИ определяется числом возможных маркировок. Моделирование процессов выражается в перемещении маркеров между позициями. Проектируемая система представлена в виде сети ПЕТРИ (рисунок 3.5.): Рисунок 3.5 Множество событий: События Переходы ЦП работает только с ОП и В1 T1 Обработ. данные из ОП и с В1 пер. на УВ Т2 ЦП работает только с ОП и В2 Т3 Обработ. данные из ОП и с В1 пер. на УВ Т4 ЦП работает только с ОП и с В1, В2 Т5 Обработ. данные из ОП, В1 и В2 пер. на УВ Т6 Множество условий: Условия ОП свободна Р1 В1 свободен Р2 В2 свободен Р3 Позиции Работа на ОП и В1 окончена Р4 Работа на ОП и В2 окончена Р5 Работа на ОП,В1 и В2 окончена Р6 Функционирование сети Петри можно раcсматривать как срабатывание переходов, в ходе которого происходит смена маркеров. Работа ЦП с ОП и В1 отображается запуском перехода t1 (удаление маркеров из Р1, Р2 и появление в Р1, Р4), что влечет за собой срабатывание перехода t2, т.е. передачу данных с ОП и В1 на устройство вывода. Работа ЦП с ОП и В2 отображается запуском перехода t3 (удаление маркеров из Р1 и Р3 и появление в Р1 и Р5), что влечет за собой срабатывание перехода t4, т.е. передачу данных с ОП и В2 на устройство вывода. Работа ЦП с ОП, В1 и В2 отображается запуском перехода t5 (удаление маркеров из Р4 и Р5 и появление в Р6), далее срабатывание перехода t6, и данные из ОП, В1 и В2 передаются на устройство вывода. Состояние устройств восстанавливается при срабатывании: ОП - t1 или t2; В1 - t2 или t6; В2 - t4 или t6. Для получения более полного представления о свойствах моделируемой системы проанализируем полученную сеть ПЕТРИ методом покрывающего дерева (рисунок 3.6.), корневая вершина которого - (1,1,1,0,0,0). Рисунок 3.6. Исследуемая сеть обладает следующими свойствами: 1. Безопасность (число маркеров в любой позиции не превышает 1). Это свойство позволяет осуществлять оппаратную реализацию сети. 2. Одноограниченность (конечность числа состояний), что накладывает ограничения на аппаратную реализацию. 3. Сохраняемость (характеризует невозможность возникновения и удаления ресурсов в моделируемом объекте). 4. Живость (отсуствие зацикливаний и тупиков). Данное свойство сети позволяет сделать важный вывод: в разработанной сети ПЕТРИ отсутствуют зацикливания и тупики и ее можно реализовать аппаратными средствами. Моделирование на ЭВМ поведения систем становится все более эффективным средством исследования различных объектов, позволяющим при минимальных затратах ресурсов и времени получить ответы на вопросы, интересующие проектировщика сложных систем, что способствует интенсификации их создания и повышения качества разработок. 3.13. Тест по разделу 1. Чему соответствует в СП-модели перехода? а) позициям; б) событию; в) условию. 2. Что такое маркировка сети Петри? а) количество маркеров в каждой позиции сети; б) маркер в позиции; в) нумерация позиций и переходов. 3. Условие срабатывания перехода ti. а) б) в) 4. Какая маркировка является тупиковой? а) последняя; б) вновь появившаяся начальная; в) при которой не срабатывает ни один переход. 5. Какое дополнительное влияние оказывают “лишние” маркеры на срабатывание разреженного перехода ti? 6. Дана сеть Петри. Является ли она ординарной? а) является частично; б) является; в) не является. 7. Дана сеть Петри. Сколько позиций будет в эквивалентной ей ординарной сети? (см. п. 6) а) 3 б) 6 в) 4 8. Дана сеть Петри. Является ли она ограниченной и безопасной? а) является ограниченной; б) является безопасной; в) не является. 9. Дана сеть Петри. Какие переходы находятся в возбужденном состоянии и могут сработать? а) t3 б) t1,t3 в) t1 10. Дана сеть Петри. Какие переходы находятся в возбужденном состоянии и могут сработать? а) t4,t1 б) t1,t3 в) t4,t3 11. Дана сеть Петри. Является ли она живой? (см. п. 10). а) является; б) не является; в) не всегда. 12. Дана сеть Петри. Является ли она живой? а) является; б) не является; в) не всегда. 13. Пусть сеть Петри обладает свойствами безопасности и живости. Сохранит ли эти свойства эквивалентная ей ординарная сеть? а) полностью сохранит указанные свойства; б) частично сохранит указанные свойства; в) не сохранит указанные свойства. 4. Имитационное моделирование Метод имитационного моделирования – один из наиболее мощных методов исследования реально существующих и проектируемых объектов самой различной природы и степени сложности. Сущность метода имитационного моделирования заключается в построении имитационных моделей исследуемого объекта и в целенаправленном экспериментировании с такими моделями для получения ответов на поставленные вопросы. При проведении исследования предпочтение конкретному методу может отдаваться в связи с традиционным его использованием и возможности адекватно решать конкретные задачи исследователя. Процесс проектирования модели, проверки ее адекватности, проведения экспериментов и формулирования выводов связан с конкретным назначением модели.. Правильный подход к проектированию модели может существенным образом повлиять на успех. О поведении процесса в целом, часто можно судить на основе поведения его на коротких временных интервалах. При этом в основе моделирования лежит статистический эксперимент, реализация которого невозможна без применения ЭВМ. Прежде чем формально поставить задачу исследования, рассмотрим некоторые статистические методы, которые полезны как при определении, так и при описании соотношений между компонентами и переменными. Имитация означает воспроизведение определенным образом явлений, событий, действий, объектов и т.д. Имитационные модели строят, когда объект моделирования настолько сложен, что описать его поведение, например, математическими уравнениями невозможно или очень затруднительно. В некоторых случаях такой объект моделирования представляют “черным ящиком”, т.е. с неизвестной структурой и, следовательно, с неизвестным поведением при воздействии на него извне и при внутренних изменениях. Суть имитационного моделирования заключается в том, чтобы как можно точнее, полнее, нагляднее отобразить моделируемый объект и динамику его функционирования. Имитационные модели позволяют динамически моделировать различные сценарии развития событий и прогнозировать результат тех, либо иных действий. 4.1. Процедура имитационного моделирования Способ имитационного моделирования заключается в создании логико-аналитической (математической) модели системы и внешних воздействий, в имитации функционирования системы, т.е. в определении временных изменений состояния системы под влиянием внешних воздействий, и в получении выборок значений выходных параметров, по которым определяются их основные вероятностные характеристики. При исследовании детерминированных систем необходимость в последнем отпадает. Научно построенная имитационная модель не только адекватна словесному (содержательному) представлению реальной системы, но и обладает рядом преимуществ. К примеру, такая модель в процессе своего “жизненного” цикла в рамках модельного времени способна “развиваться”, т.е. видоизменяется, как в целом, так и во взаимосвязях элементов ее составляющих. В этом смысле имитационная модель в определенной степени способна отобразить не только специфическую, но и органическую сущность системы. Внедрение информационных технологий и адекватных им методов хранения и обработки информации, отображающей окружающий мир делает насущным движение исследователей систем в направлении использования современных методов имитационного моделирования. Имитационные модели позволяют динамически моделировать различные сценарии развития событий и прогнозировать результат тех, либо иных действий. Модель системы на уровне структуры представляет собой совокупность моделей элементов и их функциональные взаимосвязи. Модель элемента - это набор правил (алгоритмов) поведения устройства по отношению к входным воздействиям (заявкам) и правил изменения состояний элемента. При моделировании на системном уровне элемент отражает функциональное устройство на том или ином уровне детализации. В частности, устройство может быть в работоспособном состоянии и в состоянии отказа. К правилам поведения устройства относятся правила выбора заявок из очереди, реакция устройства на поступление заявки, реакция устройства на возникновение отказа в процессе обслуживания заявки и некоторые другие. Функциональные взаимосвязи устройств определяют возможные пути продвижения заявок по системе от входных устройств к выходным. Они формируют структуру системы. Модель внешних воздействий - это правила определения моментов поступления входных сигналов (заявок) в систему, маршрута заявок в системе по каждому из потоков в соответствии с алгоритмами обработки, приоритетов обслуживания, трудоемкости обслуживания, допустимого времени пребывания заявок в системе. В процессе имитации функционирования системы измеряют те выходные характеристики, которые интересуют исследователя. При изучении стохастических систем измерения производятся многократно, чтобы с достаточной точностью определить вероятностные характеристики. Это такие характеристики системы как время ожидания заявок в очереди, число заявок в системе, длина очередей к устройствам, требуемая емкость памяти. Имитационное моделирование дает возможность учесть надежностные характеристики ВС: моменты возникновения отказов устройств в период моделирования и моменты их восстановления (по известным временам наработки на отказ и восстановления всех входящих в систему устройств). В одной и той же имитационной модели могут фигурировать различные случайные факторы, одни могут быть представлены как случайные события, другие — как случайные величины; более того, если моделируется поведение достаточно сложной системы, то ее функционирование может быть связано с возникновением нескольких типов событий и учетом большого числа случайных величин, распределенных по различным законам. Если же моделирование всех случайных факторов основано на использовании одного датчика, генерирующего одну «общую» последовательность случайных чисел, то с математической точки зрения их нельзя считать независимыми. В связи с этим для моделирования каждого случайной фактора стараются использовать отдельный генератор, или, по крайней мере, обеспечивать создание новой последовательности случайных чисел. Во многих специализированных языках и пакетах моделирования такая возможность предусмотрена. 4.2. Принципы построения моделирующих алгоритмов Имитационный эксперимент представляет собой наблюдение за поведением системы в течение некоторого промежутка времени. В практике существует больше таких задач, в которых оценка эффективности моделируемой системы напрямую связана с временными характеристиками ее функционирования. К ним относятся - задачи по оценке производительности, некоторые задачи по оценке надежности, качества распределения ресурсов, а также все задачи, связанные с исследованием эффективности процессов обслуживания. Характерной особенностью большинства практических задач является то, что скорость протекания рассматриваемых в них процессов значительно ниже скорости реализации модельного эксперимента. С другой стороны, даже те имитационные эксперименты, в которых временные параметры работы системы не учитываются, требуют для своей реализации определенных затрат времени работы компьютера. В связи с этим при разработке практически любой имитационной модели и планировании проведения модельных экспериментов необходимо соотносить между собой три представления времени: - реальное время, в котором происходит функционирование имитируемой системы; - модельное (или, как его еще называют, системное) время, в масштабе которого организуется работа модели; - машинное время, отражающее затраты времени ЭВМ на проведение имитации. Функционирование модели должно протекать в искусственном (не в реальном и не в машинном) времени, обеспечивая появление событий в требуемом логикой работы исследуемой системы порядке и с надлежащими временными интервалами между ними. Нужно учитывать, что элементы реальной системы могут функционировать одновременно, а компоненты машинной модели - последовательно. Для сохранения адекватности причинно-следственных временных связей для одновременно возникших событий, необходимо создать «механизм» задания времени для синхронизации действий элементов модели системы. С помощью механизма модельного времени решаются следующие задачи: 1) отображается переход моделируемой системы из одного состояния в другое; 2) производится синхронизация работы компонент модели; 3) изменяется масштаб времени «жизни» (функционирования) исследуемой системы; 4) производится управление ходом модельного эксперимента. 5) моделируется квазипараллельная реализация событий в модели; Приставка «квази» отражает последовательный характер обработки событий (процессов) в ИМ, которые в реальной системе возникают и протекают одновременно. Известны два подхода к заданию времени: с помощью постоянных и переменных интервалов времени, которым соответствуют два принципа реализации моделирующих алгоритмов, т. е. “принцип ” и “принцип ” (принцип особых состояний) и проиллюстрированы на рис 4.1. Выбор метода реализации механизма модельного времени зависит от назначения модели, ее сложности, характера исследуемых процессов, требуемой точности результатов и т. д. Рисунок 4.1. - Принципы реализации моделирующих алгоритмов Под действием событий Si, имеющих место в системе S изменяются состояния zi модели M. 4.2.1. Метод постоянного шага В модели, построенной по «принципу t» , моменты системного времени будут последовательно принимать значения t1=t, t2=2t, t3=3t, t4=4t. Эти моменты системного времени tj(t) никак не связаны с моментами появления событий Si, которые имитируются в модели системы. Системное время при этом получает постоянное приращение, выбираемое и задаваемое перед началом имитационного эксперимента. В модели, построенной по «принципу z» изменение времени наступает в момент смены состояния системы, и последовательность моментов системного времени имеет вид: t1=tz1, t2=tz2, t3=tz3 t4=tz4= tz5, t5=tz6, т.е. моменты времени tn (z) непосредственно связаны с моментами появления событий в системе Si. При использовании метода постоянного шага отсчет системного времени ведется через фиксированные, выбранные исследователем интервалы времени. События в модели считаются наступившими в момент окончания этого интервала. Погрешность в измерении временных характеристик системы в этом случае зависит от величины шага моделирования . Метод постоянного шага предпочтительнее, если: • события появляются регулярно, их распределение во времени достаточно равномерно; • число событий велико и моменты их появления близки; • невозможно заранее определить моменты появления событий. Данный метод управления модельным временем достаточно просто реализовать в том случае, когда условия появления событий всех типов в модели можно представить как функцию времени. 4.2.2. Метод особых состояний При моделировании по особым состояниям системное время каждый раз изменяется на величину, строго соответствующую интервалу времени до момента наступления очередного события. В этом случае события обрабатываются в порядке их наступления, а одновременно наступившими считаются только те, которые являются одновременными в действительности. Метод моделирования по особым состояниям сложнее в реализации, так как для него требуется разработка специальной процедуры планирования событий (так называемого календаря событий). Моделирование по особым состояниям целесообразно использовать, если: • события распределяются во времени неравномерно или интервалы между ними велики; • предъявляются повышенные требования к точности определения взаимного положения событий во времени; • необходимо реализовать квазипараллельную обработку одновременных событий. Дополнительное достоинство метода заключается в том, что он позволяет экономить машинное время, особенно при моделировании систем периодического действия, в которых события длительное время могут не наступать. Под «особыми состояниями», понимаются всякие, которые должны влиять на изменение модельного времени. На практике обычно вместо состояний рассматривают события, определяющие смену состояний моделируемого процесса. Например, для процесса ввода информации событие — это ввод очередного символа; другими словами, ввод очередного символа «продвигает» модельное время на соответствующий интервал. Таким образом, выбор механизма изменения модельного времени определяет и технологию реализации имитационной модели. Причем, на выбор метода моделирования влияет целый ряд факторов, однако определяющим является тип моделируемой системы. Для дискретных систем, события в которых распределены во времени неравномерно, более удобным является изменение модельного времени по особым состояниям. Если в модели должны быть представлены компоненты реальной системы, работа которых измеряется в разных единицах времени, то они должны быть предварительно приведены к единому масштабу. 4.3. Методы определения характеристик ВС При имитационном моделировании можно измерять значения любых характеристик. Для всей ВС подсчитываются поступившие в систему заявки, полностью обслуженные, не обслуженные по каким-то причинам. Соотношение этих величин характеризуют производительность ВС по определенной рабочей нагрузке. По каждому потоку определяются времена реакции и ожидания, количества потерянных и обслуженных заявок. По каждому устройству определяются время загрузки, число обслуженных заявок, время простоя в результате отказов, длины очередей и занимаемые емкости памяти. При статистическом моделировании большая часть характеристик - это случайные величины. По каждой такой характеристике Y определяется N значений, по которым строится гистограмма относительных частот, вычисляются математические ожидания (М), дисперсии (D), определяются средние по времени и максимальные значения. 4.3.1. Коэффициенты загрузки устройств Коэффициенты загрузки устройств вычисляются как , (4.1) где vк - среднее время обслуживания одной заявки к-устройством; Nок - количество обслуженных им заявок за время Тм. 4.3.2. Расчет математического ожидания и дисперсии выходной характеристики В случае анализа стационарного процесса вычисление М и D характеристики Y производится усреднением не по времени, а по множеству N значений, измеренных по одной реализации процесса достаточной продолжительности. В целях экономии памяти ПЭВМ, на которой производится моделирование, М и D вычисляются в ходе моделирования путем наращивания итогов при появлении очередного измерения случайной характеристики по рекуррентным формулам. Математическое ожидание случайной величины у для ее n-измерения уn: (4.2) где mn-1 - математическое ожидание по предыдущим (n-1) измерениям: (4.3) Начальная d0 = 0. 4.3.3. Расчет среднего по времени значения выходной характеристики При моделировании постоянно ведется подсчет длины очереди к каждому устройству и занимаемой емкости накопителя. (4.4) где i - номер очередного изменения состояния в очереди N - количество изменений; i - интервал времени (i-1,i); li - число заявок в очереди в интервале i; Рисунок 4.2. - Временная диаграмма изменения длины очереди Средняя по времени используемая емкость накопителя: , (4.5) где qi - емкость накопителя, занятая в интервале времени между двумя последовательными обращениями к накопителю. 4.3.4. Построение гистограммы Основное достоинство имитационного моделирования - по любой выходной характеристике может быть построена гистограмма относительных частот, т.е. эмпирическая плотность распределения вероятностей, вне зависимости от сочетаний распределения параметров системы и внешних воздействий. При исследовании стационарной системы гистограмма строится по следующей методике. Перед началом задаются границы изменения характеристики У (ун,ув), указывается число интервалов гистограммы Ng и вычисляется интервал . (4.6) Затем определяется число попаданий измеряемой случайной величины в i-интервал гистограммы Ri и подсчитывается общее число измерений N. По полученным данным вычисляется относительная частота по каждому интервалу: , (4.7) что является достаточным для построения гистограммы относительных частот. Рисунок 4.3. - Гистограмма относительных частот P.S. Площадь гистограммы относительных частот =1, и интеграл от плотности вероятности в пределах (-∞,+∞)=1, т.е. ; , т.е. общее число измерений характеристики у равно сумме чисел попаданий в каждый из интервалов. При необходимости выдвигается гипотеза о том, что полученное эмпирическое распределение согласуется с некоторым теоретическим, имеющим аналитическое выражение для функции или плотности распределения. Далее она проверяется по приемлемому критерию согласие. 4.4. Характеристики нестационарных процессов Для систем с таким процессом функционирования нельзя вычислять вероятностные характеристики по одной реализации процесса. В таком случае случайный процесс У(t) представляется ансамблем реализаций и его характеристики определяются усредненными по ансамблю. Пусть случайный процесс У(t) задан ансамблем реализаций {Уi(t)} (i=1,2,...), а интересующая вероятностная характеристика [У(t)] определяется предельным соотношением: , (2.8) где  - оператор преобразования, лежащий в основе определения характеристики ; Ni - количество реализаций, по которым осуществляется усреднение. Тогда при усреднении , (2.9) 4.5. Алгоритм повторных экспериментов Проводится Ni имитационных экспериментов. При каждом последующем эксперименте параметры системы и нагрузки устанавливаются на исходные значения и в процессе каждого эксперимента остаются неизменными или изменяются по одним и тем же зависимостям. Датчики случайных чисел устанавливаются в начальное состояние только однажды - перед моделированием и до конца моделирования вырабатываются последовательности случайных чисел. Период моделирования T по каждому эксперименту разделяется на Nr сечений. Интервал времени моделирования между двумя сечениями называется прогоном. В каждом эксперименте для фиксированных моментов tr (r=1,2,...,Nr) определяются численные значения выходных характеристик. По каждому i-сечению для всех выходных характеристик может определяться многомерная функция или плотность распределения, оцениваются Мy(tr), Dy(tr) по всей совокупности Ni реализации. Реализация нестационарного случайного процесса показана на рис. 4.4. Рисунок 4.4. - Реализации нестационарного случайного процесса Для обеспечения достоверности необходимо проведение повторных экспериментов (102-104) с последующей обработкой вектора выходных характеристик по нескольким десяткам сечений. Расчет характеристик по методу повторных экспериментов. Математическое ожидание случайного процесса У(t) - это неслучайная функция my(t), которая при каждом значении аргумента tr представляет собой математическое ожидание соответствующего сечения случайной функции: Мy(tr) = M[У(tr)] Dy(tr) = D[У(tr)]. При моделировании вычисления результатов производятся в конце каждого прогона путем наращивания итогов. В частности, количественные вероятностные значения таких выходных характеристик, как длины очередей к каждому устройству, времена реакции по каждому потоку заявок и времена загрузки каждого устройства, определяются по r-му сечению для i-го эксперимента по следующим формулам. Оценка математического ожидания длины очереди к устройству: m[Li] =m[Li-1](i-1) / i + li / i, где [Li-1] – математическое ожидание за предыдущие (i-1) экспериментов; li - длина очереди по r-му сечению для i-го эксперимента. , где D[Li-1]- дисперсия за предыдущие (i-1) экспериментов. По временам реакции и загрузки при достаточно большом количестве сечений, когда процесс можно считать стационарным на протяжении одного прогона, текущие значения математических ожиданий и дисперсии вычисляются по формулам как для стационарных процессов. В специальной литературе приводятся формулы расчета математического ожидания времени загрузки каждого устройства при обслуживании одной заявки, дисперсии времени загрузки каждого устройства на r-м прогоне, оценки математического ожидания и дисперсии времени реакции по каждому потоку в r-м сечении i-го эксперимента[1,5]. 5. Статистические методы исследования систем Применение математических количественных методов для обоснования решений – это основная идея моделирования. При построении модели может быть использован математический аппарат любой сложности. При моделировании сложных систем, которые зависят от большого числа пересекающихся между собой факторов, аналитические модели оказываются неприемлемыми. Для таких систем при исследовании аналитическими методами требуется грубое допущение о Марковском характере процесса, чего в действительности может и не быть. По сравнению с аналитическими, статистические модели более точны и подробны, не требуют грубых допущений, позволяют учесть большое число факторов. Недостатками их является громоздкость, плохая обозримость, большой расход времени при поиске и трудность получения оптимального решения. Теоретической основой статистических методов моделирования являются предельные теоремы теории вероятностей. Они гарантируют высокое качество статистических оценок при числе испытаний и приемлемые результаты могут быть получены и при недостаточно большом числе испытаний. 5.1.Теорема Бернулли: Если проводится независимых испытаний, в каждом из которых некоторое событие происходит с вероятностью , то относительная частота появления события , при сходится по вероятности к . Т.е. при любом предел (- число положительных исходов испытания): Основное распределение математической статистики – это нормальное распределение, и нормально распределённые величины широко применяются на практике. Это вытекает из предельной теоремы Ляпунова: Если случайная величина представляет сумму большого числа взаимно-независимых случайных величин, влияние каждой из которых на всю сумму мало, то случайная величина распределена по закону, близкому к нормальному. Для нормального закона плотность распределения: Характеристика центра распределения – это медиана. Мода – наиболее вероятное значение. Для нормального закона известно, что значений случайной величины, распределённой по нормальному закону попадает в интервал попадает в интервал ; попадает в интервал ; При других распределениях с конечными и вероятность попадания случайной величины в интервал оценивается с помощью неравенства Чебышева. Для и выполняется неравенство: и, согласно этому: 5.2. Метод Монте-Карло Идея метода заключается в «розыгрыше» случайного явления с помощью специально организованной процедуры, включающей в себя случайность и дающей случайный результат. Конкретная реализация случайного процесса каждый раз складывается по-разному и полученное множество реализаций можно использовать как искусственно полученный статистический материал, который может быть обработан методами математической статистики. Метод Монте-Карло используется в случаях: 1. При моделировании сложных комплексных операций, где присутствует много случайных факторов; 2. При проверке применимости простых аналитических методов и выяснении условий их применений; 3. В целях выработки поправок к аналитическим формулам. Результатом метода Монте-Карло является статистическая модель, которая моделирует как бы прошлое (таблица). Она не наглядна и использовать её в качестве модели нерационально. Розыгрыш случайной величины можно проводить не каждый раз, а использовать обширную таблицу, в которой цифры от 0 до 9 встречаются случайным образом, и с одинаковой вероятностью. Такие таблицы называются таблицами случайных чисел. При использовании метода Монте-Карло в таблицу случайных чисел «случайно» входят один раз. Недостатками их является громоздкость, плохая обозримость, большой расход времени при поиске и трудность получения оптимального решения. Теоретической основой статистических методов моделирования являются предельные теоремы теории вероятностей. Они гарантируют высокое качество статистических оценок при числе испытаний и приемлемые результаты могут быть получены и при недостаточно большом числе испытаний. Первоначально был разработан метод статистических испытаний, представляющий собой численный метод, который применялся для моделирования случайных величин и функций, вероятностные характеристики которых совпадали с решениями аналитических задач (процедура Монте-Карло). Затем этот прием стал использоваться для машинной имитации с целью исследования характеристик процессов функционирования систем, подверженных случайным воздействиям, т.е. появился метод статистического моделирования. Подлежащее разыгрыванию распределение вероятностей может быть основано на эмпирических данных, извлекаемых из ранее сформированных записей, или на результатах последнего эксперимента, либо может представлять собой известное теоретическое распределение. Случайные числа используются для получения дискретного ряда случайных переменных, имитирующего результаты, которых можно было бы ожидать в соответствии с разыгрываемым вероятностным распределением. Пусть необходимо определить функцию распределения случайной величины y=y(), где  - случайные величины с известными функциями распределения. Эта процедура реализуется следующими этапами. 1. По каждой величине  производится случайное испытание, в результате которого определяется конкретное iii 2º. Определяется у =f (iii) 3º. Предыдущие операции повторяются N раз, т.е. определяется N значений случайной величины y. 4º. На основные N значений находится эмпирическая функция распределений. Наибольшую пользу этот метод приносит при моделировании вероятностных ситуаций, но применим к некоторым полностью детерминированным задачам, не имеющим аналитического решения. Данные предшествующего опыта вырабатываются искусственно путем использования генератора случайных чисел в сочетании с интегральной функцией распределения вероятностей для исследуемого процесса. (таблица, колесо рулетки, подпрограмма). Для выполнения метода, чтобы получить искусственную случайную выборку из совокупности величин, описываемой некоторой функцией распределения вероятностей следует выполнить следующие процедуры: 1. Построить график или таблицу интегральной функции распределения на основе ряда чисел, отражающего исследуемый процесс, причем значения случайной переменной процесса откладываются по оси абсцисс (x), а значения вероятности (от 0 до 1) - по оси ординат (y), 2. С помощью генератора случайных чисел выбрать случайное десятичное число (СЧ) в пределах от 0 до1 (с требуемым числом разрядов), 3. Провести горизонтальную прямую от точки на оси ординат соответствующий выбранному СЧ до пересечения с кривой распределения вероятностей. 4. Опустить из этой точки перпендикуляр на ось абсцисс. 5. Записать полученное значение x, далее оно принимается как выборочное значение. 6. Повторить шаги 2-5 для всех требуемых случайных переменных, следуя тому порядку, в котором они были записаны. Пример. (Обработка эмпирических данных) [7]. Пусть имеем систему, в которой за каждый 10-минутный период число клиентов, нуждающихся в обслуживании, соответствует распределению, приведенному в таблице: Число клиентов Вероятность Интегральная вероятность 1 2 3 0.40 0.25 0.20 0.15 0.40 0.65 0.85 1.00 Предположим, что проводим эксперимент для 5 периодов времени. Построим график распределения интегральной вероятности. Рисунок 5.1.-График распределения интегральной вероятности Из таблицы случайных чисел берем 5 двузначных чисел и перед каждым ставим десятичную точку. Каждое используем для определения числа клиентов, появляющихся в данном периоде времени 09, 54, 42, 80, 20. Реализация по методу Монте-Карло для распределения выглядят следующим образом: Период времени Случайное число Число клиентов 1 2 3 4 5 0.09 0.54 0.42 0.80 0.20 1 1 2 Если используемые случайные числа распределены равномерно (т.е. имеют одинаковую вероятность появления), то каждое из значений исследуемой величины будет в процессе описываемого эксперимента появляться с такой же относительной частотой, как и в реальном мире, однако исследуемая величина приобретет случайный характер. Таким образом, проводя мысленный эксперимент по определению числа клиентов, нуждающихся в обслуживании в каждые 10 мин. период, мы получаем результаты, типичные для фактического предшествующего поведения исследуемой системы. Метод Монте-Карло предполагает работу с таблицами случайных чисел и задающими распределение. Сначала входят в таблицу в любой точке, а затем вносится в процесс выборки табличных чисел регулярность того или иного рода. При разработке имитационной модели, содержащей стохастические или вероятностные элементы стоит вопрос, следует ли при методе Монте-Карло применять эмпирические данные или же нужно воспользоваться одним из теоретических распределений. При этом нужно учесть, что при использовании эмпирических данных моделируется только прошлое. Закон же остается неизменным во времени, особенности его будут повторяться. Кроме того, теоретическое распределение дает лучшие результаты с точки зрения затрат машинного времени и требуемого объема памяти и гибче при «проигрывании» различных возможных ситуаций. Итак, если есть возможность использовать теоретические распределения, модель получается более полезной. 5.3. Идентификация закона распределения При проведении экспериментов с имитационной моделью в целях сокращения затрат времени бывает целесообразным заменить моделирование работы некоторых ее компонент числовым параметром, либо случайной величиной, распределенной по теоретическому закону. Чтобы такая замена была корректной, необходимо располагать описанием зависимости данного параметра от времени и других факторов. Подбор законов распределений выполняется на основе статистических данных, полученных в ходе эксперимента. В основе процедуры отыскания закона распределения некоторой величины по экспериментальным данным лежит проверка статистических гипотез, как утверждения относительно значений параметров распределения некоторой величины или о самом виде распределения. Совместимость экспериментальных данных с некоторым теоретическим законом распределения, или иначе, соответствие частоты выборочных значений случайной величины той частоте, с которой они должны бы появиться при некотором вероятностно распределении, отвечающем теоретическому закону можно установить. Это также сделать и необходимо, т.к. при определенных законах распределения основных параметров системы и нагрузки появляется возможность создания аналитической модели, а при имитационном моделировании становится проще задание вида закона и статических характеристик, чем представлять случайную величину в виде таблицы. Эта процедура выполняется следующим образом. По совокупности численных значений случайного параметра строится гистограмма относительных частот – эмпирическая плотность распределения. Гистограмма аппроксимируется плавной кривой, которая последовательно сравнивается с кривыми плотности распределения различных теоретических законов распределения. Выбирается один из законов по наилучшему совпадению вида сравниваемых кривых. По эмпирическим значениям вычисляются параметры этого распределения. Затем выполняют количественную оценку степени совпадения эмпирического и теоретического распределения по тому или другому критерию согласия. Если переменная дискретная, то записываем частоты появления каждого из ее возможных значений. Если непрерывная - разбиваем весь диапазон значений на равные интервалы (группы) и записываем частоты появления каждой группы. Тогда относительная частота для каждой группы равна частному от деления наблюдаемого числа событий данной группы на общее число событий. Нужно определить параметры распределения, чтобы подвергнуть их проверке по статистическим критериям. Если предполагаемое распределение является функцией двух параметров, последнее удается оценить на основе выборочного среднего и выборочной дисперсии. Пример. Распределение относительных частот телефонных запросов за одночасовой интервал приведено в таблице. Число запросов N Число одночасовых интервалов с N запросами Относительная частота f 1 2 3 4 5 315 142 40 9 2 1 0.619 0.279 0.078 0.018 0.004 0.002 1.00 Строим гистограмму распределения относительных частот и аппроксимируем ее (рисунок 5.2.) Рисунок 5.2.- Гистограмма относительных частот Аппроксимирующая кривая схожа с кривой закона Пуассона, для которого , x=0,1,2,…N; - параметр Пуассона (интенсивность появления события). При разбивке на группы вычисляется среднее и дисперсия: ; где n – полный объём выборки; k – число групп; Mi – среднее значение i-ого интервала или значение i-ой группы; Fi – частота появления i-ой группы. Вычисление статистических параметров для дискретных данных приведены в таблице . Mi Fi MiFi Mi2Fi 1 2 3 4 5 315 142 40 9 2 1 142 80 27 8 5 142 160 81 32 25 n=509 262 440 Для распределения Пуассона , у нас . Но, когда вероятность некоторого события для одного временного интервала такая же, как и для любого другого, а осуществление события не оказывает влияния на вероятность его повторного появления, имеется веское основание ожидать распределение Пуассона. Кроме того, имеется высокая вероятность появления нулевого числа событий и среднее число событий в каждом временном интервале мало. В этом случае нужно пользоваться средней величиной: . Для статистической оценки гипотезы, о том, что совокупность эмпирических данных незначительно отличается от той, которую можно ожидать при некотором теоретичеcком законе распределения применяются критерии согласия. При проверке гипотез методами математической статистически необходимо иметь в виду, что статистические критерии не могут доказать ни одной гипотезы, они могут только указать на опровержение. 5.3.1. Критерий согласия хи-квадрат Рассматриваются два вида испытаний на соответствие эмпирических или выборочных данных - данным, которые можно ожидать при некотором теоретическом законе. Таким параметром расхождения между ожидаемыми и наблюдаемыми частотами является параметр х² (хи-квадрат). Этот критерий был предложен Пирсоном в 1903 г. и расширен Фишером, который опубликовал в 1924г. соответствующие таблицы критических величин, используемые и в настоящее время [7]. Статистика х² определяется выражением, , где - наблюдаемая частота для каждой группы или интервала, - ожидаемая частота, предсказанная теоретическим распределением сумма по всем группам или интервалам. Если х²=0, то наблюдаемые и теоретически предсказанные значения частот точно совпадают, если х²>0 - совпадения нет, надо сравнить расчетные значения с табличными, чтобы определить на сколько наблюдаемые значения определяются только случайными причинами. В таблице приведены значения хкрит² для различных чисел степеней свободы и уровней доверительной вероятности. При практическом использовании этой статистики высказывается гипотеза о том, что между наблюдаемым и ожидаемым теоретическим распределением расхождений нет. Если х²> х²крит., то на данном уровне доверительной вероятности наблюдаемые частоты значительно отличаются от ожидаемых и тогда гипотезу надо отвергнуть. Для рассмотренного примера проверим данные на доверительном уровне 0.95[7]. Число степени свободы v=k-1-m, где m – число параметров, определяемых опытным путём или на основе выборочных данных. Для примера v=2 (см. ниже). P(x=n) – вероятность поступления n событий; . Подставив n = 0, 1, 2, …, получаем P(n) и заполним таблицу. N P(n) 1 2 3 4 5 0,571 0,319 0,089 0,017 0,003 0,001 291 161 45 9 1 1 315 142 40 9 2 1 1,98 2,47 0,56 0,09 1,00 509 509 5,10 Применяя методику проверки гипотез по критерию x2, нужно учесть, что, во-первых, значения частот для каждой группы или интервала должны быть и в противном случае необходимо объединять смежные группы или интервалы; во-вторых, нельзя пользоваться значениями относительных частот или выраженными в процентах. Поэтому в примере вместо 6 групп образовалось четыре. Этот критерий согласия применим при объёмах выборки n100. = P(n) * 509; ; Правильный выбор числа групп или интервалов имеет существенное значение, т.к. определяет степень свободы и чем больше , тем надежнее критерий различает характер распределения. x2 = 5,10 Подыскивая критическое значение xкрит2 (при 0,95 и v=2) xт2 = 5,99 ,т.к. x2 < xт2, то гипотеза не отбрасывается 5.3.2. Критерий Колмогорова – Смирнова Этот критерий открыт автором в 1939г.[7]. Подобно рассмотренному критерию х2, он может быть использован для сравнения интегральной функции распределения теоретического и эмпирического. Применяется в тех случаях, когда проверяемое распределение непрерывно и известны среднее и дисперсия совокупности. Таблица его критических значений была опубликована в 1949г. Проверка осуществляется путем задания интегральной функции, следующий из теоретического распределения, и ее сравнения с интегральной функцией распределения эмпирических данных. Сравнение основывается на выборочной группе, в которой экспериментальное распределение имеет наибольшее абсолютное отклонение от теоретического. Далее эта разность сопоставляется с критическими значениями с целью определения, может ли такое отклонение быть случайным при данном законе распределения. Для примера, приведённого выше, применим этот критерий согласия (хотя это не корректно). Получаем два интегральных распределения - из наблюдаемых данных и из теоретического распределения и находим абсолютные разности для всех групп значения случайной величины. Заполним этими значениями таблицу. Число запросов (1) Наблюд. част. (2) Наблюд. вероятн. (3) Теорет. вероятн. (4) Интегр. вероятн. (2) (5) Интегр. вероятн. (3) (6) Абсолют. Разность (4-5) 1 2 3 4 5 315 142 40 9 2 1 0,619 0,279 0,078 0,018 0,004 0,002 0,571 0,319 0,089 0,017 0,003 0,001 0,619 0,898 0,976 0,994 0,998 1,000 0,571 0,890 0,979 0,996 0,999 1,000 0,048 0,008 0,003 0,002 0,001 0,000 Максимальное абсолютное отклонение для первой группы равно 0,048. По таблице , при n=509, и =0,05 (=1-) [7]. D крит = 1,36 / = 1,36 / = 0,0603 > 0,048 При использовании этого критерия данные можно как группировать, так и относить каждое наблюдение к отдельной группе. Последнее открывает возможность эффективного анализа при малых выборках. От гипотезы не отказываемся. Этот критерий согласия очень эффективен для выборок n  100.(При n < 10 применяется критерий Крамера - фон Мизенса.) 5.4. Подбор кривых Во многих подсистемах наблюдается функциональная связь между двумя или более переменными, но не всегда очевидна. Для поиска таких математических функциональных или структурных зависимостей между переменными по накопленным экспериментальным данным применяются методы регрессионного и корреляционного анализа. Регрессионный анализ дает возможность построить, исходя из совокупности экспериментальных данных, уравнение, вид которого задается, а корреляционный анализ позволяет судить о том, насколько хорошо экспериментальные точки согласуются с выбранным уравнением («ложатся» на соответствующую кривую). Метод реализуется следующими этапами. 1. Сбор экспериментальных данных. 2. Построение диаграммы разброса, где визуально находится прямая или плавная кривая. 3. Нахождение для аппроксимирующих кривых таких алгебраических уравнений, которые наилучшим образом отображают данную совокупность экспериментальных точек. Аналитик должен выбрать вид кривой, для которой он будет искать аппроксимирующее уравнение. Примеры уравнений кривых: 1. y = a0 + a1k прямая 2. y = a0 + a1k + a2x2 квадратная парабола 3. y = a0 + a1k + a2x2 + a3x3 кубическая парабола 4. y = a0 + a1k + a2x2 + a3x3 + a4x4 парабола 4-ой степени 5. y = a0 + a1k + a2x2 + ... + anxn парабола n-ой степени 6. y = 1 / (a0 + a1k) или y = 1 / y = a0 + a1k гипербола 7. y = a0 bx экспонента 8. y = a0 + a1lg k логарифмическая кривая lg y = a0 + a1 lg k кубическая логарифмическая кривая Наилучшая подгонка кривых для каждого аналитика, естественно своя. Нужен критерий «наилучшего» приближения, который был бы объективен и отвечал понятию приемлемого, а также прост. Для этих целей часто используется метод наименьших квадратов, который формализует процедуру подбора аппроксимирующей кривой на глаз, когда стремятся свести к минимуму отклонения экспериментальных точек от подбираемой кривой (рисунок 5.3.). Рисунок 5.3.-Диаграмма разброса экспериментальных данных Мерой качества приближения кривой к экспериментальным данным является сумма: D1 + D2 + D3 + D4 С математической точки зрения проще эту величину представить суммой квадратов: D12 + D22 + D32 + D42 Мера качества приближения такая же, т.е. кривой наилучшего приближения будет та, для которой сумма D12 + D22 + D32 + D42  min. Так определяется критерий наилучшего приближения по методу наименьших квадратов. 4. Регрессионный анализ. Математический метод, обеспечивающий такую подгонку выбранной кривой, при которой экспериментальные точки ложатся на нее наилучшим образом в смысле критерия наименьших квадратов, называется регрессионным анализом. Аналитик выбирает вид кривой, изучая диаграмму разброса. Используемый математический аппарат должен обеспечивать наилучшее приближение кривой к экспериментальным данным независимо от того, насколько хорошо выбран вид кривой. Под приближением кривой к экспериментальным данным понимается только процесс вычисления значений констант или параметров таким образом, чтобы сумма D i 2 была минимальна (  D i 2 ). Рассмотрим простейший случай. Пусть имеем 4 экспериментальных точки и дадим им линейную аппроксимацию. Линейная аппроксимация экспериментальных данных. x Y x² xy 2 2 3 1 4 3 5 4 4 9 8 6 15 7 13 17 29 Рисунок 5.4.- Диаграмма разброса экспериментальных точек Модель линейного соотношения задается уравнением y = a0 + a1k +  где а0 - начальное значение y, a1 - tg угла наклона прямой,  - случайная ошибка. а0 , a1 ,  - неизвестны. Из совокупности данных можно определить ; ; , . Нужно осознать факт, что наилучшее приближение нашей прямой (или кривой) к экспериментальным данным не означает, что реально существующая физическая зависимость наилучшим образом описывается аппроксимирующим уравнением и соответствует именно этой прямой. Например, пусть диаграмма разброса экспериментальных точек такая, как на рисунке 5.5. Рисунок 5.5. -Диаграмма разброса По критерию наименьших квадратов - прямая, но по экспериментальным данным они не согласуются с линейной зависимостью. 5. Корреляционный анализ Для оценки того, насколько хорошо прямая (кривая) согласуется с экспериментальными данными существует понятие корреляция. Если регрессия определяет предполагаемое соотношение между переменными, то корреляция показывает, насколько хорошо это соотношение отражает действительность. При регрессионном анализе предполагается наличие причинно-следственной связи между зависимой и независимой переменными, а при корреляционном анализе такое допущение не делается. Корреляция говорит лишь о том, насколько тесно экспериментальные точки ложатся на аппроксимирующую кривую. Количественной оценкой такого приближения является коэффициент корреляции r (-1r1). r = -1 - max отрицательная корреляция, с ростом x убывает y и все экспериментальные точки лежат точно на кривой. r = 0 - полное отсутствие корреляции. r = +1 - мax положительная корреляция. Обычно -1 < r < +1 и его надо проверить на статистическую значимость. Для случая простой линейной регрессионной задачи (т.е. для случая, когда имеется одна зависимая и одна независимая переменные, связанные линейно). . Для нашего случая: . Общий разброс у определяется как  ( y - )2, т.е.  квадратов отклонений У от среднего значения . Отношение этой величины разброса, обуславливаемой регрессионным уравнением , к общему наблюдаемому разбросу называется коэффициентом детерминации (смешанной корреляции) и равно r2. r2 = 0,9692 = 0,939 Это значит, что в 93,9 % случаев отклонение У при изменении Х соответствует выведенному уравнению у = 0,947 + 1,316 х. Эти же рассуждения справедливы и для нелинейной зависимости, число зависимых переменных > 1. Эффективное использование процедур статического анализа экспериментальных данных возможно только при наличии соответствующих инструментальных средств. 5.5. Экспертные оценки Когда нет возможности определить значения параметров экспериментально, надо полагаться на субъективные оценки. Желательно воспользоваться мнением коллектива экспертов. Выявление индивидуальных точек зрения и формирование на их основе единого мнения коллектива экспертов осуществляется несколькими методами. Метод Дельфы. Это итерационная процедура, которая позволяет подвергать мнение каждого критике со стороны остальных, не заставляя сталкиваться. Идея метода заключается в создании механизма, обеспечивающих сохранение анонимных точек зрения отдельных лиц. Все взаимодействия регулируются координатором. Групповая оценка вычисляется путем некоторого усреднения. Пример. Определение значения некоторого числа N на основе мнения 12 экспертов. Для этого необходимо: 1. Опросить каждого по оценке N. 2.Расположить ответы по шкале и определить квартили Q, чтобы в каждом отрезке содержалось 1/4 всех оценок и медиану М. Рисунок 5.6.-Распределение собранных данных по шкале 3.Сообщить каждому значения Q1, Q2 и M для пересмотра с обоснованием. Определить новые значения квартилей и медиану. 4.Подсчитать результаты второго тура, сообщить новые Q1, Q2 и дать возможность по желанию изменить предыдущую оценку. 5.Повторить процедуру пока интервал между Q1, Q2 не сузится до некоторой величины. Далее берется медиана M, представляющее групповое мнение. Опрос можно прекратить и в том случае, если дальнейшего изменения дисперсии не предвидится. Цель метода Дельфы - уменьшить психологическое давление, испытываемое при личном контакте. Но метод не всегда надежен, т.к. нельзя учесть влияние на расхождение мнений, движимое желанием приспособиться к общему мнению (эффект «толпы»). Ответственность устремляет экспертов располагать оценки ближе к медиане без аргументации. Метод Дельфы, предполагающий анонимность мнений, итеративную процедуру, управляющую обратную связь, числовые оценки и статистическое определение групповой оценки - ценный инструмент исследования для разработчиков модели. При этом: точность оценки улучшается с ростом числа членов группы и количества итераций и точность падает с увеличением интервала времени между ответами и достигается большее согласие между групповым мнением и мнениями отдельных членов группы, чем при методах, требующих личных контактов. 6. Компьютерное моделирование в среде GPSS World Компьютерные эксперименты отличаются от привычных натурных экспериментов тем, что исследователь экспериментирует не с реальным объектом, а с его компьютерной моделью. Компьютерное моделирование как метод исследования является естественным развитием математического моделирования. В основе компьютерных моделей, по крайней мере тех, о которых речь пойдёт далее, лежат математические модели. Эти модели строятся автоматически по описанию структуры и поведения исследуемой системы, принятому в языке моделирования. Построенные математические модели обычно сводятся к системам уравнений, решение которых редко удаётся найти в замкнутой форме, и их приходится решать численно, с помощью программных реализаций численных методов. Программная реализация математической модели строится автоматически пакетом моделирования. Наконец, при компьютерном моделировании широко используется возможность визуализации как самой модели, так и её поведения. Исследуемая модель предстаёт перед пользователем в виде узнаваемых графических образов, её параметры можно регулировать и ею можно управлять почти так же, как и реальной жизни. В компьютерной модели используемая математическая модель, её программная реализация, системное и математическое программное обеспечение, необходимые для воспроизведения поведения модели, спрятаны за дружеским интерфейсом. Всё это позволяет создавать и исследовать компьютерные модели специалистам, далёким от прикладной математики и информатики. 6.1. Программирование имитационных моделей на языке GPSS Машинное моделирование на языке GPSS GPSS – General Purpose Simulating System – общецелевая моделирующая система, предназначенная для решения задач по моделированию работы всевозможных систем, в том числе - систем массового обслуживания. Система массового обслуживания (СМО) – это система, в которой выполняется ряд операций (действий) по обслуживанию случайного потока заявок (требований на обслуживание). В GPSS заявку называют транзактом. Пример: супермаркет, СТО (станция технического обслуживания), автоколонна, ВС (вычислительная система) и т.п. Сущность машинного моделирования СМО состоит в проведении на ЭВМ эксперимента с моделью этой системы. Машинная модель СМО – это программа, составленная на языке GPSS, которая описывает поведение элементов системы в процессе ее работы. Результатом прогона этой программы на ПЭВМ является статистика – данные о модели, полученные в результате машинных расчетов по составленной и отлаженной программе. Анализ статистики позволяет уточнить исходную программу. Моделирование заканчивается, когда полученная машинная модель адекватна реальной системе массового обслуживания. Этапы решения практической задачи по моделированию: 1. Создание Q-схемы или концептуальной модели СМО (вручную); 2. Построение блок-диаграммы модели (вручную); 3. Составление текста GPSS-программы; 4. Прогон программы на ЭВМ и сбор статистических данных; 5. Анализ статистических данных и уточнение модели. Основные элементы Q-схемы 1. Прибор (канал, линия обслуживания) – элемент СМО, выполняющий реальные операции по обработке заявок (транзактов). Изображается на Q-схемах так: 2. Источник заявок – элемент СМО, выполняющий фиктивную операцию ожидания заявки, которая завершается генерацией (созданием) заявки. Изображается на Q-схемах так: 3. Накопитель – это очередь заявок (транзактов), ожидающих выполнения. Изображается на Q-схемах так: 4. Многоканальное устройство (см. «Виды СМО») Изображается на Q-схемах так: 5. Движение заявок на Q-схеме изображается стрелками: ЗАДАЧА № 1. Интервал прихода клиентов в парикмахерскую с одним парикмахером имеет равномерное распределение 186 мин. Время обслуживания клиентов равномерно распределено в интервале 164 мин. Провести моделирование работы парикмахерской в течение 8 часов. Q-схема задачи № 1 Т = 18(6) е    = 16(4), где Т – средний интервал поступления заявки в систему; е – емкость накопителя (максимальное число заявок, которые могут одновременно находиться в накопителе);  – среднее время обслуживания заявки. Блок-диаграмма задачи № 1 (блоки и карты описаны ниже) Диаграмма состоит из двух сегментов (частей): 1-й сегмент отвечает за моделирование прихода и обслуживания клиентов; так что транзакты, перемещающиеся по модели, – это клиенты парикмахерской; 2-й сегмент – сегмент таймера, моделирует время работы СМО. Единственный транзакт, создаваемый в этом сегменте, представляет собой сообщение о конце рабочего дня. ; Генерация транзактов через каждые 18  6 мин времени (т.е. приход клиентов); ; Клиент встает в очередь перед мастером (условное имя этой очереди - OCH); ; Транзакт занимает прибор PAR (т.е. клиент садится в свободное кресло); ; Клиент покидает очередь OCH; ; Задержка транзакта в приборе PAR на время обслуживания (стрижка клиента); ; Транзакт освобождает прибор PAR (т.е. клиент покидает кресло парикмахера); ; Транзакт удаляется из модели (т.е. клиент уходит из парикмахерской); Сегмент времени: Состоит из двух блоков- GENERATE и TERMINATE. ; Через 480 ед. модельного времени (8 ч * 60 мин) будет создан транзакт – сообщение о конце работы. ; Этот транзакт будет удален и моделирование завершится по времени. GPSS-программа задачи № 1 (позиционный текст, см. ниже) 1 8 19 * 1-й сегмент программы GENERATE 18,6 QUEUE OCH SEIZE PAR DEPART OCH ADVANCE 16,4 RELEASE PAR TERMINATE 0 * 2-й сегмент программы GENERATE 480 TERMINATE 1 START 1 Результаты моделирования Вся статистика, получаемая в результате прогона модели на ЭВМ, делится на две части: 1. Общесистемная статистика; 2. Статистика по отдельным объектам GPSS-модели. Общесистемная статистика включает в себя: • текст модели с номерами всех блоков программы; • установку соответствия между числовым и символическим именем объекта или меткой блока; • статистику по модельному времени (относительному и абсолютному). Статистика по объектам включает в себя характеристики всех элементов СМО, определенных в конкретной задаче. Для задачи № 1: • Статистика по прибору PAR (например, загрузка = 88 %); • Статистика по очереди OCH (например, макс. длина=2 чел.). 6.2. Рекомендации по практическому использованию среды GPSS World В мире информационных технологий имитационное моделирование переживает второе рождение. И это в первую очередь связано с появлением в 2000 году мощного программного продукта фирмы Minuteman Software – GPSS World (GPSSW, General Purpose System Simulation World – Мировая общецелевая система моделирования), разработанного для ОС Windows. В основу системы GPSS World положен язык имитационного моделирования GPSS. С помощью этой системы, например, можно эффективно моделировать как производственные, так и непроизводственные процессы: функционирование торговых заведений, портов, уличное движение, проведение военных действий, работу редакций, учреждений и сети Internet, различных систем массового обслуживания и т.д. Система имеет большой набор команд для управления процессом моделирования, которые можно как использовать в интерактивном режиме, так и включать в модель. Модели в GPSS представляют собой совокупность отдельных элементов, называемых объектами. Существуют 7 категорий и 14 типов объектов GPSS . 6.2.1. Категории и типы объектов языка GPSS Наименование категории Наименование типа объекта Операционная Блоки Динамическая Сообщения Аппаратная Устройства памяти Ключи Вычислительная Арифметические переменные Булевские переменные Функции Статистическая Очереди Таблицы Запоминающая Ячейки Группирующая Группы Списки Все объекты GPSS имеют числовые характеристики, доступные пользователю, называемые стандартными числовыми атрибутами (CЧА). На эти атрибуты можно ссылаться в процессе моделирования. Имя СЧА состоит из двух частей. Первая часть указывает на тип объекта и тип информации о нем, вторая - идентифицирует конкретного члена группы (по номеру или символическому име ни). Например: FC1- число занятий прибора 1 или FC$PRIB - число занятий прибора с именем PRIB. Рассмотрим основные категории объектов системы GPSS: ОПЕРАЦИОННАЯ. К этой категории относится единственный тип объектов - блоки. Разработчик конструирует модель из блоков, как правило, отображая ее в виде блок-схемы. Для удобства графического представления модели каждый блок GPSS имеет принятое стандартное обозначение. Построенная схема является программой на языке GPSS, а каждый блок - подпрограммой в ней. Для ввода ее в ЭВМ необходимо последовательность блоков представить в виде последовательности операций, добавив к названиям блоков требуемые операнды. Каждый блок GPSS имеет входы и выходы, с помощью которых осуществляется их связь в модели. Существуют два особых блока: GENERATE, имеющий только выход, и TERMINATE, имеющий только вход. ДИНАМИЧЕСКАЯ. К этой категории относятся транзакты. Функционирование объекта отображается в модели в виде перемещения транзактов от блока GENERATE в блок TERMINATE через промежуточные блоки. Транзакты (сообщения) являются абстрактными подвижными элементами, которые, перемещаясь между блоками, вызывают и испытывают различные действия. Понятие транзакта уста навливает сам разработчик модели. Например, если мы разрабатываем модель большого универмага, то в понятие транзакта можно вложить "покупатель", который, передвигаясь от отдела к отделу, движется по магазину. Транзакт-"покупатель" движется по модели и может быть поставлен в очередь, задержан, выведен из очереди. Его маршрут может быть изменен и т.д. АППАРАТНАЯ. К этой категории относятся три типа объектов: 1. Одноканальные приборы (в дальнейшем просто устройства). 2. Многоканальные приборы (в дальнейшем - памяти). 3. Ключи. Устройства моделируют объекты, в которых может происходить обработка транзактов. Как правило, она связана с затратами времени. Особенность устройств состоит в том, что каждое из них может быть занято лишь одним транзактом. Памяти же могут обслуживать несколько транзактов одновременно. Ключи могут иметь два состояния: 0 и 1. Транзакты могут устанавливать их в эти состояния или инвертировать их. СТАТИСТИЧЕСКАЯ. К этой категории относятся следующие объекты: 1. Очереди. 2. Таблицы. Транзакты в процессе движения могут задерживаться перед блоками, вход в которые в данных условиях невозможен. В этом случае здесь образуются очереди. Система GPSS позволяет собрать статистику о них. Для сбора данных о других отчетах модели и их представлениях в стандартной табличной форме используются таблицы. В них может быть зафиксировано изменение какого-либо СЧА объекта в процессе моделирования. ЗАПОМИНАЮЩАЯ. Для записи в процессе моделирования текущих записей СЧА используются ячейки, которые имеют различные форматы (слово, полуслово, с плавающей точкой). ВЫЧИСЛИТЕЛЬНАЯ. В процессе моделирования часто возникает необходимость вычисления какого-либо соотношения между различными СЧА (арифметического или логического). Для этой цели и служат объекты этой категории - переменные (арифметические, булевские). Для отображения зависимостей между двумя СЧА служат функции. 6.2.2. Общие сведения о картах описания КАРТЫ ОПИСАНИЯ Карты описания необходимы в системе для того, чтобы описать характеристики различных объектов: емкость памятей, состояние ключей в начальный момент времени, порядок вычисления переменных и т.д. Рассмотрим карты описания по категориям объектов, где они используются. Аппаратная категория. Карта STORAGE служит для описания емкости многоканальных устройств. Формат записи: <имя памяти> STORAGE <емкость>. Имя памяти может быть как числовым, так и символическим. Примеры: 2 STORAGE 10. Память с числовым именем 2 имеет емкость 10 единиц. MKU STORAGE 15. Память с символическим именем MKU имеет емкость 15 единиц. Карта INITIAL служит для установки в начальное состояние логических переключателей (ключей). По умолчанию все ключи находятся в состоянии "0" - "RESET" ("Выключено"). Формат: INITIAL <Ключ1>, <Ключ2>, ... , <Ключ6>. Пример: INITIAL LS$1, LS$KLU, LS$3. Установить в состояние "1" ("Включено") ключи с именами 1, KLU, 3. Запоминающая категория. Карта INITIAL служит для установки в начальное значение ячеек памяти. По умолчанию все ячейки памяти имеют значение 0. Формат: INITIAL <ячейка1>, <значение1>, <ячейка2>, <значение2>, <ячейка3>, <значение3>. Пример: INITIAL XH$1,10,XF$OTN, 3, XH$9, 100. Присвоить полусловной ячейке 1 значение 10, ячейке с именем OTN - значение 3, полусловной ячейке 9 - значение 100. Статистическая категория. Карта TABLE служит для описания таблиц. Формат: <имя таблицы> TABLE A,B,C,D. A, B, C, D, - поля операндов. A - фиксируемый CЧА; B - верхняя граница нижнего интервала; C - ширина интервала; D - число интервалов. Пример: KAR TABLE Q$OTH, 5,1,10 В таблице с именем KAR будет фиксироваться текущее содержимое очереди с именем ОТН. Вычислительная категория. Карта FVARIABLE определяет переменную с плавающей точкой. Формат: <имя переменной> FVARIABLE <выражение>. Допустимые операторы: = - равно <> - не равно < - меньше чем > - больше чем >= - больше или равно <= - меньше или равно 1 - И & - ИЛИ + - сложение - - вычитание / - деление * - умножение @ - деление по модулю () - круглые скобки Для обращения к переменной используется CЧА V$. Пример: 1 FVARIABLE (Q$OTH/3+15)*P$1. Переменная 1 равна (текущее, содержимое очереди с именем OTH+15)* *(значение параметра 1.) Карта VARIABLE определяет целую переменную. Формат: <имя переменной> VARIABLE <выражение>. Список допустимых операторов тот же, что и для карты FVARI- ABLE. Карты различаются лишь тем, что вычисление выражения в карте VARIABLE происходит по правилам целочисленной арифметики. Карта FUNCTION определяет функцию. Формат: <имя функции> FUNCTION <аргумент функции>, <тип функции>, <число точек> // ... /. Аргументом функции может быть любой СЧА. Очень часто бывает необходимо задать какую-либо случайную зависимость. Тогда аргументом функции может выступать значение одного из восьми генераторов случайных чисел. В этом случае аргументом функции будут случайные числа в интервале [0,1]. Форма записи такого СЧА: RN$1. Тип функции задается одной буквой C или D. Буква C означает, что функция является непрерывной, т.е. соседние точечные значения соединяются отрезками и получается ломаная линия. Пример такой функции изображен на рис.6.1. Рис.6.1.-Непрерывная функция Рис.6.2.-Дискретная функция Буква D означает, что функция является дискретной. Пример такой функции дан на рис. 6.2. Число точек, которыми определяется функция, задает точность ее определения. Чем больше точек - тем выше точность задания функции. Ниже основной карты следуют карты описания точек. Они задаются парами Xi,Yi, разделенными между собой знаком "/". Причем точки должны быть заданы следующим образом: X1 < X2 < X3 < < ...< Xi < ... < Xn. Если пары не умещаются на одной строке, то они продолжаются на следующей, но следующая строка должна обязательно начинаться с Xi. В конце строки знак "/" не ставится. Пример: EXP FUNCTION RN$1, C4 .1,4/.2,2/.3,3/.4,1 Функция с именем EXP является непрерывной. Аргументом являются значения генератора случайных чисел с именем 1 и описана она четырьмя точками. Пример: FAN FUNCTION P$1, D4 1,1/2,2/3,3/4,1 Функция с именем FAN является дискретной. Аргументом функции служит значение первого параметра транзакта. Функция описана четырьмя точками. 6.2.3. Основные управляющие карты языка GPSS Управление процессом моделирования осуществляется с помощью специальных управляющих карт. Карта SIMULATE - указание провести моделирование. Эта карта должна быть первой в тексте программы. Ей может лишь предшествовать карта перераспределения памяти REALLOCATE. Карта START - указание о начале и окончании моделирования. Формат: STAPT ,,,. A - счетчик числа завершений; B - подавление вывода на печать статистик (B=NP); C - промежуточный вывод статистики; D - распечатка списков. В поле A указывается начальное число счетчика числа завершений. Транзакт, поступая в блок TERMINATE с непустым полем A, уменьшает это число на значение A блока TERMINATE. При обнулении счетчика управление моделью пере дается следующей карте. Карта END - указание закончить задание. Карта REALLOCATE - определяет максимальное число объектов в модели. Формат: REALLOCATE <объект>, <количество>, <объект>, <количество>, ...,<объект>,<количество>. Эта карта - единственная, которая может предшествовать карте SIMULATE. Она используется для изменения числа объектов в модели, принимаемых по умолчанию. Если задаваемое число объектов меньше принятого по умолчанию, то экономится память. Объекты: FAC - прибор, по умолчанию 20; FSV - полнословная ячейка, по умолчанию 100; FUN - функции, по умолчанию 20; HSV - полусловная ячейка, по умолчанию 100; LOG - логические ключи, по умолчанию 100; QUE - очереди, по умолчанию 35; STO - память, по умолчанию 20; TAB - таблицы, по умолчанию 15; VAR - переменные, по умолчанию 20; XAC - транзакты, по умолчанию 100. Пример: REALLOCATE XAC,500, FAC,3, FUN,1, TAB,1 Карта RESET очищает накопленную статистику. 6.2.4. Описание блоков языка GPSS 6.2.4.1. Блоки, связанные с динамической категорией 1. Группа блоков создания и уничтожения транзактов. Блок GENERATE создает и вводит транзакты в модель. При вводе в модель детерминированного потока транзактов используется операнд A. Запись вида GENERATE 100 означает, что в модель через каждые 100 единиц модельного времени будет вводиться транзакт, причем первый транзакт появится в момент модельного времени, равный 100. При моделировании случайного потока заявок может быть использован операнд B. Запись вида GENERATE 100,40 означает, что поток транзактов имеет равномерное распределение входного интервала в диапазоне значений целых чисел от 60 до 140 включительно. Вероятности появления значений 60, 61, 62, ... , 140 одинаковы и равны 1/121. Операнды А и В могут быть заданы функцией. Например, GENERATE FN$EXP. Эта запись означает, что интервалы поступления транзактов в модель являются значениями функции с именем EXP. Если же функция задана в операнде B, то значение интервала поступления транзактов вычисляется как A*B. Например, запись вида GENERATE 5, FN$EXP означает, что транзакты будут поступать в модель через интервалы времени, равные 5*(значение функции с именем EXP). В блоке GENERATE могут присутствовать и другие операнды. Обратим внимание на один из них: операнд F - число параметров транзакта. Каждый транзакт, двигаясь по модели, может нести с собой информацию, определенную разработчиком модели. Эта информация может быть считана, изменена, уничтожена. Для ее хранения и служат параметры транзакта. Каждый из параметров служит как бы ячейкой памяти в самом транзакте, которая передвигается вместе с транзактом. Таких параметров у транзакта может быть до 1028. Для экономии памяти вводится операнд F, который ограничивает их число. Блок TERMINATE уничтожает транзакты. Выйдя из блока GENERATE и пройдя по модели, транзакт выводится из нее. Его вывод (уничтожение) осуществляет блок TERMINATE, имеющий лишь один операнд A. В нем записывается константа или СЧА. При пустом операнде A его значение принимается равным нулю. При вхождении транзакта в блок TERMINATE происходит уничтожение транзакта, а из специального счетчика числа завершений вычитается значение операнда A. Начальное число этого счетчика указывается в управляющей карте START, которая будет рассмотрена ниже. Блоки SPLIT и ASSEMBLE. Очень часто возникает необходимость моделирования параллельных одновременных процессов обработки одного и того же транзакта. Например, решение одной задачи параллельно на двух ЭВМ одновременно с последующей сверкой результатов. Транзакт "задача" не может быть передан в несколько блоков сразу, поэтому возникает необходимость в создании его копии. Этим и занимается блок SPLIT. Он создает несколько копий транзакта, вошедшего в него, и направляет их в определенный блок. Транзакт и его копии называют ансамблем. Из ансамбля можно снова создать один транзакт. Это осуществляет блок ASSEMBLE. 2. Группа блоков задержки транзактов по заданному времени. Блок ADVANCE задерживает транзакт. Формат: ADVANCE , . A - среднее время задержки; B - разброс относительно среднего значения. Операнды A, B аналогичны операндам блока GENERATE. В блоке ADVANCE они лишь характеризуют время задержки транзакта в данном блоке. Например, ADVANCE 100, 40 означает задержать транзакт на 100, 40; ADVANCE 100, FN$EXP - задержать транзакт на время 100*FN$EXP. 3. Группа блоков, изменяющих параметры и приоритет транзактов. Блок ASSIGN изменяет значение параметра транзакта. Формат: ASSIGN , . A - номер изменяемого параметра; B - новое значение параметра. Блок ASSIGN может работать в трех режимах: фиксации, наращивания и убывания. В режиме фиксации в указанном параметре записывается указанное значение. Примеры: ASSIGN 1,10 - записать в параметр 1 число 10. ASSIGN P$1,FN$DISP - записать в параметр, номер которого указан в первом параметре транзакта, значение функции с именем DISP. В режиме наращивания новое значение прибавляется к старому значению параметра. Пример: ASSIGN 1+,10 - к значению параметра 1 прибавить число 10. В режиме уменьшения новое значение вычитается из старого значения параметра. Пример: ASSIGN 1-,10 - из значения параметра 1 вычесть число 10. Блок PRIORITY изменяет уровень приоритета транзакта. В системе GPSS существуют 128 приоритетов транзактов. Они задаются числами 0 - 127. Чем больше число - тем выше приоритет транзакта. Формат: PRIORITY . А - новый приоритет. 4.Блоки, осуществляющие синхронизацию движения транзактов. Блок MATCH синхронизует движение двух транзактов одного ансамбля. Формат: MATCH . A - имя сопряженного блока MATCH. Первый транзакт, достигнув блока MATCH, задерживается в нем до тех пор, пока другой член ансамбля не достигнет сопряженного с ним другого блока MATCH. Пример: AAA MATCH BBB . . . . . . . . . BBB MATCH AAA Блок GATHER накапливает транзакты одного ансамбля. Формат: GATHER . A - счетчик транзактов, которые должны быть накоплены. Транзакты одного ансамбля задерживаются в блоке GATHER до тех пор, пока их число не станет равным значению поля A. Когда последний транзакт ансамбля войдет в этот блок, все они одновременно выходят из него в том порядке, в котором поступили. 6.2.4.2. Блоки, связанные с аппаратной категорией 1. Группа блоков, описывающих одноканальные устройства. Блок SEIZE занимает устройство. Формат: SEIZE . A - имя занимаемого прибора (числовое или символическое). Транзакт пытается занять устройство, определенное полем A. Если оно уже занято или прервано, транзакт задерживается в предыдущем блоке. Блок RELEASE освобождает устройство. Формат: RELEASE . A - имя освобождаемого устройства (числовое или символическое). Устройство, указанное в поле A, освобождается и становится доступным для других транзактов. Освобождать устройство может лишь тот транзакт, который занимал его. Блок PREEMPT захватывает прибор. Формат: PREEMPT . A - имя прерванного устройства. Транзакт получает в пользование устройство, указанное в поле A, если это устройство не захвачено другим транзактом. Если предыдущий транзакт захватил прибор через блок PREEMPT, текущий транзакт блокируется. Блок RETURN удаляет транзакт из захваченного прибора. Формат: RETURN . A - имя освобождаемого прибора. При входе транзакта в блок RETURN снимается прерывание с прибора, которое было произведено этим транзактом. Если устройство было занято до прерывания, то прерванный транзакт возвращается на дообслуживание после снятия прерывания. 2. Группа блоков, описывающих многоканальные приборы - памяти. Блок ENTER помещает транзакт в память. Формат: ENTER ,. A - имя памяти; B - число занимаемых каналов. Проверяется наличие свободного места в указанной памяти. Если имеется свободная память, то транзакт входит в блок ENTER и занимает указанное число каналов. Если свободной памяти нет, то транзакт задерживается в предыдущем блоке. Пример: ENTER MKU,2 - войти в многоканальное устройство с именем MKU и занять там 2 канала. Блок LEAVE удаляет транзакт из памяти. Формат: LEAVE ,. A - имя памяти; B - число освобождаемых каналов. Пример: LEAVE MKU,3 - освободить в памяти с именем MKU 3 канала. 3. Группа блоков, описывающих логические ключи. Блок LOGIC - логический переключатель. Формат: LOGIC_ X - внутренний операнд; A - имя ключа. X может: I - инвертировать состояние ключа; S - включить; R - выключить. Примеры: LOGIC_R 1 - выключить переключатель 1; LOGIC_I P$3 - инвертировать состояние ключа, имя которого указано в третьем параметре транзакта. 6.2.4.3. Блоки, связанные со статистической категорией 1. Группа блоков, описывающих очереди. Блок QUEUE помещает транзакт в конец очереди. Формат: QUEUE ,. A - имя очереди; B - число добавляемых к очереди элементов (по умолчанию - 1). Увеличивает текущее содержимое очереди, указанной в поле A, на значение в поле B. Транзакт может находиться в двух очередях одновременно. Примеры: QUEUE 1 - стать в очередь 1 и увеличить ее длину на 1; QUEUE P$1,3 - стать в очередь, указанную в первом параметре транзакта, и увеличить ее длину на 3. Блок DEPART удаляет транзакт из очереди. Формат: DEPART ,. A - имя очереди; B - число удаляемых из очереди элементов. Необходимо отметить очень важную деталь. Блоки QUEUE и DEPART служат не для создания очередей. Очереди в системе GPSS будут создаваться и без них. Данные блоки лишь фиксируют поступление или выход транзакта из конкретной очереди. Без них статистика о существующих очередях собираться не будет! 2. Группа блоков, описывающих таблицы. Блок TABULATE заносит значение в таблицу. Формат: TABULATE . A - имя таблицы. Транзакты, входящие в данный блок, осуществляют занесение данных в таблицу, указанную в поле A и описанную картой TABLE. 6.2.4.4. Блоки, связанные с запоминающей категорией Блок SAVEVALUE сохраняет значение. Формат: SAVEVALUE ,,. A - имя ячейки; B - новое значение; C - формат ячейки (XP,XH,XL). Блок SAVEVALUE аналогично блоку ASSIGN может работать в трех режимах: фиксации, наращивания и убывания. В режиме фиксации в ячейку, имя которой указано в поле A, записывается значение, указанное в поле B. Пример: SAVEVALUE 1,10 - в ячейку 1 записывается число 10. В режиме наращивания к содержимому ячейки добавляется новое значение. Пример: SAVEVALUE 1+,10 - к содержимому ячейки 1 добавляется число 10. В режиме уменьшения из содержимого ячейки вычитается новое значение. Пример: SAVEVALUE 1-,10 - из содержимого ячейки 1 вычитается число 10. 6.2.4.5. Блоки, изменяющие маршруты движения транзактов 1. Блоки TRANSFER - блоки перехода. Формат: TRANSFER ,,,. A - режим передачи; B - следующий блок; C - следующий блок; D - значение индекса, используемое в режиме ALL. Транзакт направляется в блок, определяемый в соответствии с режимом передачи, указанным в поле A. Основные режимы передачи: 1. A - пробел: режим безусловного перехода. Транзакт направляется в блок, указанный в поле B. Пример: TRANSFER , MET - транзакт передается в блок с именем (меткой) MET. 2. A - BOTH: транзакт последовательно пытается войти в блок B, затем в блок C, до тех пор, пока один из них станет доступным. Пример: TRANSFER BOTH,MET1,MET2 - транзакт пытается войти в блоки с метками MET1 и MET2. 3. A - ALL: транзакт пытается последовательно перейти в блоки B, B+d, B+2d,..., B+nd, пока не достигнет блока С. Пример: TRANSFER ALL, MET1, METN, 5 - транзакт пытается войти в каждый 5-й блок, начиная с блока MET1, пока не достигнет блока METN. 4. A - ".": статистический режим: в поле A указано десятичное число, выражающее вероятность перехода в блок С: его дополнение до единицы указывает вероятность перехода в блок B. Пример: TRANSFER .4, MET1, MET2 - транзакт с вероятностью 0.4 переходит к блоку MET2 и с вероятностью 0.6 - к блоку MET1. 2. Блок TEST сравнивает 2 стандартных числовых атрибута. Формат: TEST_, ,,. X - внутренний операнд, принимающий значения: E - равно; NE - не равно; L - меньше чем; LE - меньше чем или равно; G - больше чем; GE - больше чем или равно; A - 1-й СЧА; B - 2-й СЧА; C - имя альтернативного блока. Значения СЧА, указанные в полях A и B, сравниваются отношением, определяемым операндом X. Если условие выполняется, транзакт вводится в следующий блок. Если условие не выполняется и определено поле C, транзакт переходит в указанный блок, если же C не задано, транзакт задерживается в предыдущем блоке. Пример: TEST_E P$1,2,MET1 - если значение первого параметра равно 2, то транзакт переходит в следующий блок, иначе - в блок MET1. 3. Блок GATE - блок, проверяющий состояние объектов аппаратной категории: устройств, памятей, ключей. Формат: GATE_ , Внутренний операнд X может принимать значения: U - устройство занято; NU - устройство не занято; I - устройство прервано; NI - устройство не прервано; SF - память заполнена; SNF - память не заполнена; SE - память пустая; SNE - память непустая; LR - ключ включен; LS - ключ не включен. A - имя объекта, состояние которого проверяется; B - блок альтернативного перехода. Если проверяемое условие выполняется, то транзакт переходит в следующий блок. Если же нет и определен блок альтернативного перехода, то транзакт переходит в этот блок. Если же поле B не определено и условие не выполняется, транзакт остается в предыдущем блоке. Пример: GATE_U PRIB, MET - если устройство с именем PRIB занято, то транзакт переходит в следующий блок; иначе - в блок с именем MET. 4. Блок LOOP осуществляет прохождение транзактом цепочки блоков. Формат: LOOP ,. A - номер параметра, определяющего число циклов; B - блок, на который переходит транзакт, если параметр A не равен нулю. Значение параметра поля A уменьшается на единицу. Если оно не равно нулю, транзакт переходит в блок, имя которого указано в поле B. В противном случае транзакт переходит в следующий блок. Пример: LOOP 1,LAB - уменьшает на единицу значение параметра 1 и переходит к блоку с именем LAB, если параметр 1 не равен нулю. 6.2.5. Замена одного или нескольких операторов C помощью GPSS-модели может быть проведено исследование работы систем массового обслуживания при различных уровнях загрузки. Для этого необходимо изменить поля А и В блока GENERATE. Или же можно провести другие исследования, изменив операнды других блоков. Каждое такое изменение предполагает прогон модели заново. Однако средства GPSS позволяют организовать в модели с несколькимим картами START, замену блоков. Для этого каждый из заменяемых блоков должен иметь свое символическое имя. После первого прогона (после первой карты START) вновь указываются заменяемые блоки и обнуляется собранная статистика картой RESET. Затем вновь следует карта START и т.д. ПРИМЕР: Пусть необходимо в модели заменить блоки GENERATE и ADVANCE. Пометим их метками МЕТ1, МЕТ2. Программа имеет вид: SIMULATE MET1 GENERATE 100,40 QUEUE 1 SEIZE 1 DEPART 1 MET2 ADVANCE 20 RELEASE 1 TERMINATE 1 START 100 MET1 GENERATE 90,50 MET2 ADVANCE 30 RESET START 100 MET1 GENERATE 80,30 MET2 ADVANCE 40 RESET START 100 END Данная программа предназначена для трех прогонов модели с различными значениями блоков GENERATE и ADVANCE. 6.2.5.3. Задание определенного времени моделирования Пусть необходимо промоделировать работу какой-либо системы в течение 1000 единиц времени. Это можно сделать, включив в программу следующий сегмент: GENERATE 1000 TERMINATE 1 START 1 END Через 1000 единиц модельного времени из блока GENERATE выйдет транзакт. Он сразу же уничтожится блоком TERMINATE и счетчик числа завершений карты START сбросится в 0. Управление будет передано следующей управляющей карте, а именно - карте END. Моделирование завершится. Ту же самую задачу решает другой сегмент: GENERATE 1 TERMINATE 1 START 1000 END 6.2.6. Тренировочные задания к разделу 1. Имеется один обслуживающий прибор (это могут быть парикмахер, кассир, продавец и т. д.) и поток клиентов на обслуживание (желающих побриться, получить деньги, купить и т. д.). Свойства прибора и потока заданы Прибор обслуживает клиента за время в интервале Т ± D, где Т — среднее время обслуживания, T—D минимальное время обслуживания, а Т + D—максимальное (величины Т и D заданы). Поток клиентов так же описывается интервалом времени между клиентами: t+d, где t — среднее время между появлением клиентов, a [t-d, t+d] интервал возможного изменения этого времени (значения t и d должны быть заданы). Вот и вся исходная информация. А вопросов много; какая будет очередь клиентов, ее среднее значение и максимальное (минимальное, очевидно, равно нулю), какой процент времени обслуживающий прибор будет простаивать? И т. д. Ответы на эти и многие другие вопросы дает моделирование. Процесс моделирования обладает своей спецификой, которая отличает его, и очень существенно например, от вычислительных процессов. Процесс моделирования можно было бы свести к формульным вычислениям, но такое представление было бы не свойственно процессу моделирования и поэтому было бы очень громоздко. Именно поэтому для моделирования разработаны специальные языки высокого уровня. Среди них наибольшей популярностью пользуется язык GPSS.. Всякий процесс моделирования связан с воспроизведением поведения моделируемого объекта. А это поведение характеризуется моментами его изменения. Поэтому надо моделировать те моменты времени, когда в объекте что-то изменяется (приход клиента, начало его обслуживания, конец обслуживания и т. д.). Операторы языка GPSS описывают именно эти моменты. Рассмотрим основные из них. Оператор GENERATE (генерировать) определяет моменты появления клиентов в системе обслуживания. Он характеризуется пятью числами А, В, С, D, Е: GENERATE А, В, С, D, Е. Это означает, что клиенты поступают в среднем через А единиц времени в интервале А В, причем первый клиент придет в случайный момент в интервале С ± В, число таких клиентов равно D, а Е— это приоритет такого рода клиентов. Например: GENERATE 5 обозначает, что клиенты поступают строго через 5 единиц времени, тость в моменты 5, 10, 15,..., причем отсутствие (умалчивание) остальных данных означает, что В=0, С=А', D = оо; Е=0. Как видно, таким способом можно задавать весьма разнообразные по­токи клиентов. Оператор QUEUE А (стать в очередь) присоединяет клиента к очереди А, где А — имя очереди (название или номер). Таких очередей может быть много. Вообще говоря, не для всякого клиента потребуется этот оператор. Так, нетерпеливые клиенты не становятся в очередь, если она велика, т. е. больше какой-то определенной величины. Оператор DEPART В (покинуть очередь) выводит клиента из очереди В при обращении к этому оператору. Оператор SEIZE С (занять) реализует переход клиента на обслуживающий прибор С (это название прибора или его номер), если он свободен. Оператор RELEASE D (освободить) освобождает обслуживающий прибор D. Оператор ADVANCE Е, D (задержать) реализует задержку клиента во время его обслуживания на рабочем месте» указанном выше, и характеризуется средним временем обслуживания Е и полуинтервалом G, таким, что время обслуживания является случайной величиной в интервале Е G. Например, ADVANCE 12, 8 означает, что прибор обслуживает клиента случайное время в интервале 12 8, то есть от 4 до 20 минут. Оператор TERMINATE (завершить) удаляет клиентов из модели. При отсутствии этого оператора они могли бы встать в другую очередь к другому прибору. Оператор SIMULATE (моделировать) отдает команду на моделирование ЭВМ процесса, программа которого написана ниже. При отсутствии этого оператора ЭВМ лишь просмотрит программу на предмет выявления ошибок, но работать по ней не будет. А теперь напишем простейшую программу на GPSS, моделирующую работу салона с одним рабочим местом. Пусть 25 клиентов с одинаковым приоритетом поступают через случайные промежутки времени в интервале 18 6 мин, то есть от 12 до 24 мин, а мастер обслуживает клиента случайное время в интервале 16 ± 4. Интерес к моделированию процесса обслуживания вполне реальный — например, сколько ставить стульев для ожидающих клиентов? А число стульев должно быть равно максимальной длине очереди. Именно эту величину слезет прежде всего определить в результате моделирования. Итак, программа моделирования процесса обслуживания в такого маленького салона имеет вид: Комментарий SIMLTLATE. То есть надо моделировать программу, а не просто просмотреть. GENERATE 18, 6,10, 25. Приход 25 клиентов через случайные интервалы 18 б мин с одинаковым (нулевым) приоритетом, причем первый клиент приходит в интервале 10 ± б мин. QUEUE 1 SEIZЕ A DEPART 1 ADVANCE 16,4 RELEASE A TERMINATE Присоединение клиента к очереди номер 1 (другой здесь не будет). Переход в кресло мастера по имени А (другого здесь нет). Уход из очереди 1. То, что этот оператор стоит позже SEIZE не ошибка, так как кресло могло быть занято, и уход из очереди логично фиксировать после занятия кресла. Этим модель отличается от жизни. Обслуживание клиента у мастера за­нимает случайное время в интервале 164 мин. Освобождение мастера А. Уход клиента из салона. ЭВМ, проделав процедуру моделирования, выдает его результаты в виде характеристик этой системы массового обслуживания. Какие именно характеристики и как их вычислять, указывать не надо. Все это заранее заложено в язык GPSS (он специально ориентирован на такие задачи). Так, прогон указанной выше программы дает следующее: 1. Общее время работы салона 472 мин, то есть 7 часов 52 мин. 2. Мастер был загружен 86% своего рабочего времени. Остальные 14% он ждал клиентов и, следовательно, мог делать какую-то другую работу (уборку помещения и т. д.). 3. Среднее время обслуживания каждого из 25-ти клиентов было 15,88 мин. (а по плану 16 мин.). 4. Очередь не превышала одного человека. Следовательно, если судить по модели одного дня работы салона, достаточно поставить один стул. 5. Средняя дайна очереди 0,16 клиента. 6. Среди 25-ти клиентов 12 не ожидали в очереди, а прошли сразу на свободное кресло. 7. Среднее время ожидания в очереди одного клиента, т. е. включая и тех, кто не ожидал, равно 2,85 мин. 8. Среднее время ожидания в очереди одного ожидающего клиента (их было 13 человек) равно 5,1З мин. и т. д. Эту программу не трудно было бы расширить на определенное время работы салона (например, 480мин=8 час) и тогда определилось бы число обслуженных клиентов (их будет 26 человек). Можно учесть и приоритеты клиентов, т. е. моделировать известное правило, что инвалиды, например, или иные категории клиентов обслуживаются вне очереди, и т. д. 6.2.7. Варианты заданий для самостоятельной работы. Вариант 1 Входной поток имеет равномерное распределение в интервале 100±30 секунд. Время выполнения заданий в вычислительной системе распределено экспоненциально со средним 50 секунд. Исследовать, как изменится нагрузка ВС при изменении среднего значения интервалов поступления ( задать 3 различных значения среднего интервала поступления ). Измерить время нахождения заданий в очереди перед ВС. Промоделировать прохождение через ВС 500 заданий. Вариант 2 Имеется пуассоновский входящий поток заданий со значением интенсивности 12 приходов в час. Время выполнения заданий в вычислительной системе распределено равномерно в интервале 7020 секунд. Исследовать, как изменится нагрузка ВС при изменении среднего времени обслуживания заданий в ВС (задать 3 разных значения среднего). Измерить время нахождения заданий в системе. Промоделировать прохождение через ВС 500 заданий. Вариант 3 Вычислительная система начинает ускоренную обработку заданий, когда общее число заданий в очереди перед ВС больше 10. Входной поток имеет равномерное распределение в интервале 1000400 секунд. Время полной обработки - 800 секунд, ускоренной - 300 секунд. Время выполнения как полное, так и ускоренное постоянно. Исследовать, как изменятся характеристики системы, если распределение интервалов поступления заменить на экспоненциальное с тем же средним. Оценить фактическое среднее время выполнения задания в системе. Промоделировать прохождение через ВС 500 заданий. Вариант 4 Время поступления заданий в систему распределено равномерно в интервале 1000300 секунд. Время выполнения заданий в вычислительной системе распределено равномерно в интервале 800100 секунд. Исследовать, как изменятся характеристики системы, если распределение интервалов поступления заменить на экспоненциальное с тем же средним. Собрать статистику времени нахождения в очереди перед ВС, а также о времени нахождения заданий в системе. Промоделировать прохождение через ВС 500 заданий. Вариант 5 Имеется пуассоновский входящий поток заданий со значением интенсивности 12 приходов в час. Время выполнения заданий в вычислительной системе распределено экспоненциально со средним, которое зависит от длины очереди перед ВС ( см. таблицу ). Исследовать, как изменится нагрузка ВС при изменении среднего времени поступления заданий в ВС ( задать 3 разных значения среднего). Исследовать и оценить фактическое среднее время выполнения заданий в системе. Промоделировать прохождение через ВС 500 заданий. Длина очереди 1-2 3-5 6 и более Среднее время обслуживания, мин 5.5 5.0 4.5 4.0 Вариант 6 Интервалы поступления заданий распределены равномерно в интервале 1000±300 секунд. Время выполнения заданий распределено экспоненциально. Исследовать, как изменятся характеристики системы, если экспоненциальное распределение заменить равномерным. Собрать статистику об очереди заданий к системе и времени нахождения заданий в системе. Промоделировать прохождение через ВС 500 заданий. Вариант 7 Работу пользователей по подготовке запросов за терминалами для ВС следует описать в модели как обслуживание в N-канальной фазе (N=12). Время подготовки запросов распределено равномерно со средним 1000 и размахом 400. Время обслуживания процессора ВС запросов пользователя, посланных с терминалов распределено равномерно со средним 800 и размахом 500. Собрать статистику об очереди запросов пользователя к процессору ВС. Промоделировать работу ВС в течение 10000 единиц модельного времени. Общее число запросов в течение всего интервала моделирования системы остается постоянным. Запросы ВС не покидают, а циркулируют в ней, последовательно изменяя свои состояния в моменты перехода от одной фазы обслуживания к другой. Вариант 8 Вычислительная система состоит из двух независимо функционирующих ЭВМ. Для обработки одних запросов требуется ЭВМ1, для обработки других - ЭВМ2. Выбор ЭВМ происходит случайным образом: с вероятностью, равной 0.351 запрос обрабатывается на ЭВМ1 и с вероятностью 0.649 - на ЭВМ2. Времена обработки запросов на ЭВМ1 и ЭВМ2 распределены равномерно со средними 800 и 1200, размахом 500 и 200 соответственно. Работу пользователей по подготовке запросов за терминалами для ВС следует описать в модели как обслуживание в N- канальной фазе (N=12). Время подготовки запросов распределено равномерно со средним 1000 и размахом 400. Промоделировать работу ВС в течение 10000 единиц модельного времени. Общее число запросов в течение всего интервала моделирования системы остается постоянным. Запросы ВС не покидают, а циркулируют в ней, последовательно изменяя свои состояния в моменты перехода от одной фазы обслуживания к другой. Определить загрузку каждой ЭВМ. Вариант 9 Работу пользователей по подготовке запросов за терминалами для ВС следует описать в модели как обслуживание в N-канальной фазе (N=12). Время подготовки запросов распределено экспоненциально со средним 800. Время обслуживания ВС запросов пользователя постоянно и зависит от числа запросов, находящихся в очереди перед фазой подготовки ( см. таблицу ). Промоделировать работу ВС в течение 10000 единиц модельного времени. Общее число запросов в течение всего интервала моделирования системы остается постоянным. Запросы ВС не покидают, а циркулируют в ней, последовательно изменяя свои состояния в моменты перехода от одной фазы обслуживания к другой. Оценить характеристики ВС. Число запросов до 10 11-15 16-20 21-25 Время обслуживания 300 500 700 1000 Вариант 10 Работу пользователей по подготовке запросов за терминалами для ВС следует описать в модели как обслуживание в N-канальной фазе (N=12). Время подготовки запросов распределено равномерно со средним 1000 и размахом 300. Вычислительная система состоит из двух последовательно функционирующих ЭВМ. Времена обработки запросов на ЭВМ1 и ЭВМ2 распределены экспоненциально со средними 800 и 1200 соответственно. Собрать статистику о времени нахождения запросов в системе. Промоделировать работу ВС в течение 10000 единиц модельного времени. Общее число запросов в течение всего интервала моделирования системы остается постоянным. Запросы ВС не покидают, а циркулируют в ней, последовательно изменяя свои состояния в моменты перехода от одной фазы обслуживания к другой. Вариант 11 Вычислительная система состоит из центрального процессора и канала ввода-вывода. Запрос, посланный пользователем, попадает на обработку в ЦП, предварительно обслужившиеся в канале. Ответное сообщение, в виде обработанного запроса пользователя проделывает обратный путь через канал в/в. Так как сообщение, обработанное в ЦП, будет отличаться от посланного сообщения, то и время работы канала по передаче запроса пользователя будет отличным от времени работы канала по передаче ответного сообщения. Эти времена распределены равномерно со средним 500 и 700 соответственно, размах - 100. Время подготовки запросов распределено экспоненциально со средним 800. Работу пользователей по подготовке запросов за терминалами для ВС следует описать в модели как обслуживание в N-канальной фазе (N=12). Промоделировать работу ВС в течение 10000 единиц модельного времени. Общее число запросов в течение всего интервала моделирования системы остается постоянным. Запросы ВС не покидают, а циркулируют в ней, последовательно изменяя свои состояния в моменты перехода от одной фазы обслуживания к другой. Собрать статистику обо всех очередях перед каждой фазой обслуживания. Вариант 12 Вычислительная система состоит из двух процессоров. Если процессор 1 занят, обработка запросов пользователя производится 2-м процессором. Если и он занят, запросы остаются в очереди перед вторым процессором. Времена обработки запросов пользователя распределены равномерно со средним 1200, 1000 и размахом 300, 200 соответственно. Работу пользователей по подготовке запросов за терминалами для ВС следует описать в модели как обслуживание в N-канальной фазе (N=12). Время подготовки запросов распределено экспоненциально со средним 1000. Промоделировать работу ВС в течение 10000 единиц модельного времени. Общее число запросов в течение всего интервала моделирования системы остается постоянным. Запросы ВС не покидают, а циркулируют в ней, последовательно изменяя свои состояния в моменты перехода от одной фазы обслуживания к другой. Оценить загрузку каждого процессора. Вариант 13 На сборочный участок поступают детали А,В,С. Время поступления деталей распределено равномерно в интервалах : А-[60,120] , В-[50,100] , С-[70,90] минут. Детали поступают на внешнюю приемку к бригаде ОТК , состоящей из 3-х человек. Приемка одной детали А занимает [4,6] минут, В-[2,4] минуты, С - [1,3] минуты. После этого происходит сборка в следующем порядке: 1.сборка деталей А и В ; 2.сборка с С. Время 1-го этапа сборки - [5,9] минут , 2-го - [6,12] минут. Задание а) промоделировать работу участка по сборке 100 узлов ; б) найти оптимальную форму организации труда бригады ОТК из 2-х вариантов: 1. каждый контролер проверяет детали разных типов из общего накопителя; 2. каждый контролер проверяет детали только одного типа из общего накопителя; в) определить необходимую ёмкость этого накопителя. Вариант 14 На обработку в ВС, состоящую из 2-х спецпроцессоров и ОП , поступают задачи А,В,С. Интенсивность поступления задач распределена равномерно в интервалах : А - [1,3] В - [2,4] С - [3,6] задач в минуту. Задачи А поступают в ВС и занимают для решения 1-й процессор и 5 страниц ОП, задачи В - 2-й процессор и 3 страницы ОП, С - оба процессора и 10 страниц ОП. Решение задачи А продолжается [4,6] , В - [5,7] , С - [9,11] секунд. Задачи получают отказ в обслуживании, если во входной очереди уже стоят : а) для А - 5 задач б) для Б - 6 в) для С - 2 . Задание а) промоделировать работу ВС в течение 20000 ед. времени ; б) найти распределение времени решения задач в системе ; в) подсчитать кол-во задач получивших отказ по типам ; г) найти распределение объёма ОП в процессе решения задач . Вариант 15 Станция автотехобслуживания ремонтирует машины 3-х типов: А,В,С. Машины А поступают в интервале [20,50] , В - [15,35] , С - [30,60] минут . На СТО работают 2 бригады слесарей. Ремонт машины А занимает [ 10,20 ] минут , В - [9,19] , С - [10,30] . Стоянка перед СТО имеет 15 мест и каждая бригада имеет свой бокс на 2 машины которые обслуживаются одновременно. Машины не нашедшие места на стоянке ремонтируются в другом месте. Задание а) промоделировать работу СТО в течение суток ; б) найти распределение времени обслуживания автомашин каждого типа ; в) определить необходимое кол-во мест на стоянке для исключения случаев отка- за в обслуживании ; г) найти необходимую емкость боксов для того же. Вариант 16 Вычислительная сеть состоит из 3-х машин. На каждую из них поступает поток заявок с интенсивностью [2,5] заявок в минуту . Половина их решается на месте за время [5,15] секунд.1/4 часть для своего решения требует подключения еще одной машины на время [3,7] секунд , а оставшаяся часть требует все ресурсы сети на то же время. Задачи требующие многомашинной обработки обслуживаются вне очереди и могут прерывать решение простых задач. Причем задачи требующие все ресурсы сети имеют наивысший приоритет и могут прерывать решение всех задач. Задание а) промоделировать работу ВС в течение 8 часов ; б) определить кол-во задач прерванных в процессе решения ; в) исследовать, как изменится это кол-во при снижении доли задач 3-го типа до 1/8 ; г) найти распределение времени решения задач всех типов. Вариант 17 На производственный участок поступают детали. Время их поступления распределено равномерно в интервале [5,15] минут. Сначала они проходят внешнюю приемку у контролера ОТК за [2,4] минуты. 5% из них направляются на доработку, которая занимает [1,3] минуты после чего поступают вновь на приемку на время [1,3] минуты. Детали дважды побывавшие на доработке направляются в брак. После приемки детали поступают на сборку в течение [2,7] минут, а затем на термозакалку на время [8,12] минут. Детали, закаливавшиеся менее 10 минут получают маркировку 2-го сорта, а если кроме этого они были и на доработке - 3-го. Задание а) промоделировать работу участка в течение 8 часов; б) определить : 1.кол-во бракованных деталей 2.кол-во деталей 1-го сорта; 3.кол-во деталей 2-го сорта; 4.кол-во деталей 3-го сорта; в) определить как изменятся эти данные при уменьшении % брака до 2-х ; г) найти распределение времени закалки деталей. 6.2.8. Ошибки при отладке GPSS-моделей 1. Этап трансляции 1.1 < Неизвестный блок > Возможные причины: а) ошибка в написании блока. 1.2 < Неизвестная метка > Возможная причина: а) метка блока не использована. 1.3 < Х не по возрастанию > Возможная причина: а) в карте FUNCTION значения аргумента Х должны располагаться в порядке возрастания. 1.4 < Ошибка в карте FUNCTION > Возможная причина: а) в карте FUNCTION отсутствуют значения X или Y; б) в карте FUNCTION значения (Xi,Yi) находятся на разных строках. 1.5 < Карта REALLOCATE не на месте > Возможная причина: а) карта REALLOCATE в GPSS-модели должна быть самой первой. 2. Этап выполнения GPSS-модели 2.1 < Область транзактов переполнена > Возможные причины: а) в модели задано явно невыполнимое условие в блоках TEST или GATE; б) временные характеристики модели таковы, что в ней одновременно существуют более 100 транзактов. ВНИМАНИЕ !!! Устранить данную ошибку можно использованием карты REALLOCATE ( перераспределение памяти ). 2.2 < Неверный разброс > Возможная причина: а) в блоках GENERATE и ADVANCE значение поля В должно быть меньше значения поля А. 2.3 < Транзакт выходит из очереди, в которую не входил > Возможные причины: а) нарушена логика движения транзактов в GPSS- модели; б) в блоках QUEUE/DEPART указаны имена разных очередей. 2.4 < Транзакт освобождает прибор, который не занимал > Возможные причины: а) нарушена логика движения транзактов в GPSS- модели; б) в блоках SEIZE/RELEASE указаны имена разных приборов. 2.5 < Недопустимый вход в блок GENERATE > Возможная причина: а) нарушена логика движения транзактов в GPSS-модели; 2.6 < Возврат прибора транзактом не захватывающим его > Возможные причины: а) нарушена логика движения транзактов в GPSS-модели; б) в блоках PREEMPT/RETURN указаны имена разных приборов. 2.7 < Вход более чем в 2 очереди > Возможная причина: а) транзакт пытается войти в 3-й блок QUEUE не освободив 2 предыдущих. 2.8 < Транзакт уменьшает содержимое многоканального устройства (МКУ) до отрицательной величины > Возможные причины: а) нарушена логика движения транзактов в GPSS- модели; б) в блоках ENTER/LEAVE указаны имена разных многоканальных устройств. 6.2.9.Стандартные числовые атрибуты Элемент СЧА Краткое определение Блоки N W Счётчик входов Счётчик текущего содержимого Время С1 Элемент относительного времени Генераторы случайных чисел RN При использовании в качестве аргумента функции представляется шестизначной дробью в диапазоне от 0,0000 до 0,999999 включительно; в любом другом случае – целым трёхзначным числом от 0 до 999 включительно Многоканальные устройства R S SA SC SR SM ST Остающаяся ёмкость Текущее содержимое Среднее содержимое (округлённое до целого) Счётчик числа входов Коэффициент использования (в долях тысячи) Максимальное содержимое Среднее время задержки на единицу ёмкости Очереди Q QA QC QM QT QX QZ Текущее содержимое Среднее содержимое (округлено до целого) Счётчик числа входов Максимальное содержимое Среднее время пребывания (на основании QC) (округлено) Среднее время пребывания (на основании QZ) (округлено) Счётчик числа входов (нулевые входы) Переменные BV V Значение булевской переменной Значение арифметической переменной Приборы F FC FR FT Состояние прибора (1 – занят, 0 – свободен) Счётчик числа занятий Коэффициент использования (в долях тысячи) Среднее время задержки на одно занятие (округлено) Сохраняемые величины X XH Значение полнословной сохраняемой величины Значение полусловной сохраняемой величины Таблицы TB TC TD Средняя величина невзвешенных входов (округлено) Количество невзвешенных входов Стандартное отклонение невзвешенных входов (округлено) Транзакты P PR M1 MP Величина параметра Уровень приоритета Время пребывания в модели Время с момента входа в блок MARK Функции FN Значение функции Цепи пользователя CA CC CH CM CT Среднее содержимое (округлено) Общее число входов Текущее содержимое Максимальное содержание Среднее время пребывания на один вход (округлено до целого) 6.2.10.Стандартные логические атрибуты Формулировка условия Мнемоника Устройство занято Устройство не занято Устройство обслуживает прерывание Устройство не обслуживает прерывание Память заполнена Память не заполнена Память пуста Память не пуста Ключ в состоянии «1» Ключ в состоянии «0» FU FNU FI FNI SF SNF SE SNE LS LR 6.2.11.Операторы отношения языка GPSS Формулировка условия Мнемоника Меньше Равно Больше Меньше или равно Не равно Больше или равно L E G LE NE GE Литература 1. Альянх И.Н. Моделирование ВС. – Л.: Машиностроение, 1988. – 223 с. 2. Советов Б.Я., Яковлев С.А. Моделирование систем. Учебник для вузов. – М.: Высшая школа, 2001. – 343 с. 3. Питерсон Д. Теория сетей Петри и моделирование систем. –М.: Мир, 1984.–264 с. 4. Советов Б.Я., Яковлев С.А. Моделирование систем. Практикум: Учебное пособие для вузов 3-е издание. – М.: Высшая школа, 2005. – 295 с. 5. Сирота А.А. Компьютерное моделирование и оценка эффективности сложных систем. – М.: Техносфера, 2006. – 280с. 6. Колесов Ю.Б. , Сениченков Ю.Б. Моделирование систем. Динамические и гибридные системы. Учебное пособие. – СПб.: БХВ – Петербург, 2006. – 224с. 7. Шеннон Р. Имитационное моделирование систем – искусство и наука – М.: Мир, 1978.- 418с. 8. Кудрявцев Е.М. GPSS World. Основы имитационного моделирования различных систем. – М.: ДМК Пресс, 2004. – 317с. Содержание 1.Общие вопросы моделирования 5 1.1. Основные понятия и определения теории моделирования. 5 1.2. Классификация систем. 6 1.3. Параметры и характеристики системы. 7 1.4. Модель 8 2.Аналитическое моделирование 10 2.1. Элементы теории массового обслуживания 10 2.1.1. Параметры и характеристики СМО 12 2.1.2. Системы потоков. Потоки заявок 15 2.2. Марковские модели 18 2.2.1.Элементы теории процессов гибели и размножения 18 2.2.2.Пуассоновский процесс как процесс чистого размножения 21 2.2.3Анализ характеристик СМО 23 2.2.4.Характеристики СМО типа М/M/1 24 2.2.5.Характеристики ВС как сложной СМО 29 2.3 Тренировочные задания к разделу 31 2.4 Тест по разделу 36 3.Моделирование систем и сетей на основе аппарата сетей Петри (N-схем) 38 3.1.Формальное определение сетей ПЕТРИ 38 3.2.Маркировка сетей ПЕТРИ 40 3.3.Правила выполнения сетей ПЕТРИ 41 3.4.Правила срабатывания переходов 41 3.5.Ординарные сети Петри 42 3.6. Некоторые свойства сетей Петри 44 3.7.Представление моделей систем сетью Петри 45 3.8. Классификация сетей Петри по динамическим свойствам 47 3.9. Анализ сетей Петри 48 3.10. Метод анализа сети Петри на основе покрывающего дерева 48 3.11. Е – сети 50 3.12. Пример использования аппарата сетей ПЕТРИ при разработке имитационных моделей 54 3.13. Тест по разделу 57 4.Имитационное моделирование 60 4.1 Процедура имитационного моделирования 60 4.2. Принципы построения моделирующих алгоритмов 62 4.2.1. Метод постоянного шага 63 4.2.2. Метод особых состояний 63 4.3 Методы определения характеристик ВС 64 4.3.1 Коэффициенты загрузки устройств 64 4.3.2 Расчет математического ожидания и дисперсии выходной характеристики 65 4.3.3 Расчет среднего по времени значения выходной характеристики 65 4.3.4 Построение гистограммы 66 4.4 Характеристики нестационарных процессов 67 4.5 Алгоритм повторных экспериментов 67 5.Статистические методы исследования систем 68 5.1.Теорема Бернулли: 69 5.2. Метод Монте-Карло 70 5.3. Идентификация закона распределения 72 5.3.1. Критерий согласия хи-квадрат 75 5.3.2. Критерий Колмогорова – Смирнова 76 5.4. Подбор кривых 77 5.5. Экспертные оценки 80 6.Компьютерное моделирование в среде GPSS World 81 6.1 Программирование имитационных моделей на языке GPSS 81 6.2. Рекомендации по практическому использованию среды GPSS World 84 6.2.1.Категории и типы объектов языка GPSS 85 6.2.2.Общие сведения о картах описания 86 6.2.3.Основные управляющие карты языка GPSS 88 6.2.4.Описание блоков языка GPSS 89 6.2.4.1.Блоки, связанные с динамической категорией 89 6.2.4.2.Блоки, связанные с аппаратной категорией 91 6.2.4.3.Блоки, связанные со статистической категорией 92 6.2.4.4.Блоки, связанные с запоминающей категорией 92 6.2.4.5.Блоки, изменяющие маршруты движения транзактов 93 6.2.5.Замена одного или нескольких операторов 94 6.2.5.3.Задание определенного времени моделирования 95 6.2.6.Тренировочные задания к разделу 96 6.2.7. Варианты заданий для самостоятельной работы. 98 6.2.8.Ошибки при отладке GPSS-моделей 102 6.2.9.Стандартные числовые атрибуты 104 6.2.10.Стандартные логические атрибуты 105 6.2.11.Операторы отношения языка GPSS 105 Литература 105