Реферат: Моделирование систем массового обслуживания
--PAGE_BREAK--Аналитические модели могут быть исследованы тремя способами:1. Аналитическим. Получение в общем виде зависимости выходных характеристик от исходных.
2. Численным. Нельзя решить сложные уравнения в общем виде. Результаты получают для конкретных начальных данных.
3. Качественным. Нет возможности получения конкретных решений, но можно выделить некоторые свойства объектов или решений уравнений, например, оценить устойчивость решения.
· При имитационном моделирование алгоритм, реализующий модель, воспроизводит процесс функционирования системы во времени. Имитируются элементарные явления, составляющие процесс, с сохранением логической структуры объекта и последовательности протекания процесса во времени. Это позволяет по исходным данным получить сведения о состоянии процесса в определенные моменты времени. Преимуществом имитационного моделирования является возможность решения более сложных задач.
Имитационные модели позволяют достаточно просто учитывать такие факторы, как наличие дискретных и непрерывных элементов, нелинейные характеристики системы, многочисленные случайные воздействия. Когда результаты, полученные имитационной моделью, являются реализацией случайных величин и функций, то для нахождения характеристик процесса функциональной системы необходимо его многократное воспроизведение с последующей статистической обработкой.
· Комбинированное моделирования при анализе сложных систем позволяет объединить достоинства отдельных методов. В нем проводят декомпозицию процесса функционирования сложной системы на подпроцессы и для тех, где можно используют аналитические модели, где нельзя – имитационное моделирование.
Технические средства математического моделирования
Цифровая техника Цифровая техника является дискретной. Основная проблема – быстродействие (не догнать реальное время) слишком сложен механизм.
Аналоговая техника.
В отличие от дискретной техники в основе аналоговой лежит принцип моделирования, а не счета. При использовании в качестве модели некоторой задачи электронных цепей, каждой переменной величине ставится в соответствие определенную переменную величину электрической цепи. При этом основой построения такой модели является изоморфизм — подобие исследуемой задачи и соответствующей электрической модели. При определении критерия подобия используют специальные приемы масштабирования, соответствующие заданным параметрам.
Согласно своим вычислительным возможностям АВМ наиболее приспособлены для исследования объектов, динамика которых описывается обыкновенными дифференциальными уравнениями и уравнениями в частных производных, реже — алгебраическими, следовательно, АВМ можно отнести к классу специальных машин.
В общем случае под АВМ понимаем совокупность электрических элементов, организованных с систему, позволяющих изоморфно моделировать динамику изучаемого объекта. Функциональные блоки АВМ должны реализовывать весь комплекс арифметико-логических операций.
АВМ делятся по мощности (степень дифференциальных уравнений):
· малые ( n £ 10 )
· средние ( 10 £ n £ 20 )
· большие ( n ³ 20 )
<img width=«12» height=«53» src=«dopb306718.zip» v:shapes="_x0000_s1152"> <img width=«420» height=«27» src=«dopb306719.zip» v:shapes="_x0000_s1153 _x0000_s1154 _x0000_s1155"> <img width=«198» height=«173» src=«dopb306720.zip» v:shapes="_x0000_s1157 _x0000_s1162 _x0000_s1161 _x0000_s1160 _x0000_s1159">
Гибридные ВМ Широкий класс ВС, использующий как аналоговый, так и дискретный метод представления и обработки информации.
Подклассы гибридных ВМ:
1. АВМ с цифровыми методами численного анализа
2. АВМ, программируемые с помощью ЦВМ
3. АВМ с цифровым управлением и логикой
4. АВМ с цифровыми элементами (цифровые вольтметры, память)
5. ЦВМ с аналоговыми арифметическими устройствами
6. ЦВМ, допускающие программирование аналогового типа.
В АВМ накладывают и складывают сигналы.
АВМ Û система сопряжения АВМ –ЦВМ.
ЦВМ Û электрическая система согласования
Сравнительная характеристика АВМ и ЦВМ
Основные понятия теории моделирования
Пусть задана сложная дискретная система S.
<shapetype id="_x0000_t13" coordsize=«21600,21600» o:spt=«13» adj=«16200,5400» path=«m@0,l@0@1,0@1,0@2@0@2@0,21600,21600,10800xe»><path o:connecttype=«custom» o:connectlocs="@0,0;0,10800;@0,21600;21600,10800" o:connectangles=«270,180,90,0» textboxrect=«0,@1,@6,@2»><shapetype id="_x0000_t67" coordsize=«21600,21600» o:spt=«67» adj=«16200,5400» path=«m0@0l@1@0@1,0@2,0@2@0,21600@0,10800,21600xe»><path o:connecttype=«custom» o:connectlocs=«10800,0;0,@0;10800,21600;21600,@0» o:connectangles=«270,180,90,0» textboxrect="@1,0,@2,@6"><img width=«220» height=«101» src=«dopb306721.zip» v:shapes="_x0000_s1175 _x0000_s1170 _x0000_s1174 _x0000_s1172 _x0000_s1173 _x0000_s1171 _x0000_s1169">
<shape id="_x0000_i1033" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image024.wmz» o:><img width=«123» height=«29» src=«dopb306722.zip» v:shapes="_x0000_i1033">
<shape id="_x0000_i1034" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image026.wmz» o:><img width=«221» height=«31» src=«dopb306723.zip» v:shapes="_x0000_i1034">
Множество входных параметров
<shape id="_x0000_i1035" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image028.wmz» o:><img width=«129» height=«32» src=«dopb306724.zip» v:shapes="_x0000_i1035">
<shape id="_x0000_i1036" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image030.wmz» o:><img width=«220» height=«31» src=«dopb306725.zip» v:shapes="_x0000_i1036">
Множество внутренних параметров
<shape id="_x0000_i1037" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image032.wmz» o:><img width=«123» height=«29» src=«dopb306726.zip» v:shapes="_x0000_i1037">
<shape id="_x0000_i1038" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image034.wmz» o:><img width=«216» height=«31» src=«dopb306727.zip» v:shapes="_x0000_i1038">
Внешнее воздействие
<shape id="_x0000_i1039" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image036.wmz» o:><img width=«133» height=«29» src=«dopb306728.zip» v:shapes="_x0000_i1039">
<shape id="_x0000_i1040" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image038.wmz» o:><img width=«227» height=«33» src=«dopb306729.zip» v:shapes="_x0000_i1040">
Множество выходных параметров
Закон функционирования некоторой сложной системы в общем виде:
<shape id="_x0000_i1041" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image040.wmz» o:><img width=«149» height=«31» src=«dopb306730.zip» v:shapes="_x0000_i1041">
As – алгоритм функционирования – метод преобразования экзогенных характеристик в эндогенные (независимые в зависимые).
Система также имеет множество состояний в определенные моменты времени:
<shape id="_x0000_i1042" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image042.wmz» o:><img width=«132» height=«29» src=«dopb306731.zip» v:shapes="_x0000_i1042">
<shape id="_x0000_i1043" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image044.wmz» o:><img width=«228» height=«31» src=«dopb306732.zip» v:shapes="_x0000_i1043">
Начальное состояние:
<shape id="_x0000_i1044" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image046.wmz» o:><img width=«231» height=«32» src=«dopb306733.zip» v:shapes="_x0000_i1044">
<shape id="_x0000_i1045" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image048.wmz» o:><img width=«168» height=«32» src=«dopb306734.zip» v:shapes="_x0000_i1045">
<shape id="_x0000_i1046" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image050.wmz» o:><img width=«109» height=«31» src=«dopb306735.zip» v:shapes="_x0000_i1046">
Под математической моделью реальной системы понимается конечной множество переменных x(t), h(t), v(t) вместе с математическими связями между ними и характеристиками выходных параметров системы y(t).
Типовые математические схемы.
В практике моделирования на первоначальных этапах формализации объекта используют так называемые типовые математические схемы, к которым относятся хорошо проработанные и проверенные математические объекты.
процесс функционирования
системы
типовая математическая
схема
обозначение
Непрерывно-детерминированный подход
стандартные ДУ
D-схема
Дискретно-детерминированный подход
конечные автоматы
F-схема
Дискретно-стохастический подход
вероятностные автоматы
P-схема
Непрерывно-стохастический подход
система массового обслуживания
Q-схема
Обобщенные (универсальный)
агрегативная система
A-схема
Сложность возрастает сверху внизу. В агрегативных схемах используется иерархический подход.
Формализация и алгоритмизация процесса функционирования системы
Сущность машинного моделирования некоторой сложной системы состоит в проведении эксперимента с моделью, которая представляет программный комплекс, описывающей формально или алгоритмически поведение элементов системы в процессе её функционирования, т.е. взаимодействия друг с другом и с внешней средой.
Основные требования, предъявляемые к модели:
1. Полнота модели – модель должна предоставлять пользователю возможность получения необходимого набора характеристик, оценок системы с требуемой точностью и достоверностью.
2. Гибкость модели – модель должна давать возможность воспроизводить различные ситуации при варьировании структуры, алгоритмов и параметров модели. Причем, структура должна быть блочной, т.е. допускать возможные замены, добавления и исключения некоторых частей без переделки всей модели.
3. Компьютерная реализация модели должна соответствовать имеющимся технически ресурсам.
Процесс моделирования, включающий разработку и компьютерную реализацию модели, является итерационным. Этот итерационный процесс продолжается до тех пор, пока не будет получена некоторая модель, которую можно считать адекватной в рамках решения поставленной задачи.
Основные этапы моделирования больших систем
1. Построение концептуальной (описательной) модели некоторой системы и её формализация
2. Алгоритмизация модели и её программная реализация
3. Получение и интерпретация результатов моделирования
На первом этапе формулируется модель и строится её формальная схема. Основное назначение данного этапа – переход от содержательного описания объекта к его математической модели. Это наиболее ответственный и наименее формализованный этап. Исходный материал данного этапа – содержательное описание объекта.
1. Проведение границ между системой и внешней средой.
2. Исследование моделируемого объекта с точки зрения выделения основных составляющих процесса функционирования системы (по отношению к целям моделирования)
3. Переход от содержательного описания системы к формализованному описанию свойств процесса функционирования системы, т.е. к концептуальной модели. Переход от содержательного описания системы к её модели в данной ситуации сводится к исключению некоторых второстепенных элементов описания. Предполагается, что они не оказывают существенного влияния на ход процессов, исследуемых в системе с помощью модели.
4. Основные элементы модели группируются в блоки. Блоки I-ой группы представляют собой имитатор воздействия внешней среды. Блоки II-ой групп являются собственно моделью функционирования. Блоки III-ей группы носят вспомогательный характер для реализации I-ой и II-ой групп и для фиксации результатов моделирования.
5. Процесс функционирования системы разбивается на подпроцессы так, чтобы построение отдельных моделей подпроцессов было элементарным и не вызывало трудностей.
На втором этапе моделирования – этапе алгоритмизации модели и её машинной реализации, сформированная на первом этапе математическая модель реализуется в виде программы. Исходный материал – блочная логическая схема.
1. Разработка схемы моделирующего алгоритма.
2. Разработка схемы программы.
3. Выбор технического средства для реализации компьютерной модели.
4. Этап программирования модели (программирование и отладка).
5. Проверка достоверности модели на различных работающих тестовых примерах.
6. Составление технической документации (логические схемы, схемы программ, спецификации)
На третьем этапе (получение и интерпретация результатов) компьютер используется для проведения рабочих расчетов по готовой программе модели. Результат этих расчетов позволяет проанализировать и сделать выводы о характеристиках процесса функционирования моделируемой системы.
1. Планирование машинного эксперимента с моделью системы (активный и пассивный эксперименты). Необходимо составление плана проведения эксперимента с указанием комбинации переменных и параметров, для которых должен проводится эксперимент. Главная задача – дать максимальный объем информации об объекте моделирования при минимальных затратах машинного времени.
2. Проведение рабочих расчетов (контрольная калибровка модели)
3. Статистическая обработка результатов расчетов.
4. Интерпретация результатов моделирования, подведение итогов
5. Составление технической документации.
Различие стратегического и тактического планирования машинных экспериментов заключается в том, что в первом случае ставится задача построения оптимального плана эксперимента для достижения цели, поставленной перед моделированием (оптимизация структуры алгоритмов и параметров системы). Во втором случае, преследуются частные цели оптимальной реализации каждого конкретного эксперимента из множества необходимых экспериментов, заданных при стратегическом планировании.
продолжение
--PAGE_BREAK--Три основных класса ошибок:
1. Ошибка формализации – недостаточно подробное описание модели
2. Ошибка решения – некорректный или слишком упрощенный метод построения модели
3. Ошибка задания параметров.
Проверка адекватности модели.
Проверка адекватности модели заключается в анализе её соразмерности, а также равнозначности системы. Адекватность нарушается из-за идеализации внешних условий и пренебрежения некоторыми случайными факторами.
Считается, что модель адекватна с системой, если вероятность того, что отклонение параметров Dy не превышает некоторой предельной величины d больше допустимой вероятности.
<shape id="_x0000_i1047" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image052.wmz» o:><img width=«129» height=«63» src=«dopb306736.zip» v:shapes="_x0000_i1047">
На практике использование данного критерия невозможно, т.к.:
1. Для проектирования или моделирования системы отсутствует информация о выходной характеристики y.
2. Как правило, система оценивается не по одной, а по множеству характеристик
3. Характеристики могут быть случайными величинами или функциями.
На практике оценка адекватности обычно проводится путем экспертного анализа разумности результатов моделирования.
Выдвигаются следующие виды проверки:
1. Проверка моделируемых элементов
2. Проверка внешних воздействий
3. Проверка концептуальной модели
4. Проверка формализованной математической модели
5. Проверка программной модели
6. Проверка способов измерения и вычисления выходных характеристик
Если модель неадекватна объекту, то выдвигаются следующие типы изменения:
· Глобальные – возникают в случае обнаружения методических ошибок концептуальной или математической модели
· Локальные – связаны с уточнением некоторых параметров и алгоритмов. Выполняются путем замены внешних воздействий на эквивалентные, но более точные.
· Параметрические изменения некоторых специальных параметров, называемые калибровочными.
Завершается данный этап определением и фиксацией области пригодности модели — множество условия, при соблюдении которых точность результатов моделирования находится в допустимых пределах.
Схема взаимодействия технических этапов моделирования
<shapetype id="_x0000_t176" coordsize=«21600,21600» o:spt=«176» adj=«2700» path=«m@0,qx0@0l0@2qy@0,21600l@1,21600qx21600@2l21600@0qy@1,xe»><path gradientshapeok=«t» limo=«10800,10800» o:connecttype=«custom» o:connectlocs="@8,0;0,@9;@8,@7;@6,@9" textboxrect="@3,@3,@4,@5"><img width=«618» height=«726» src=«dopb306737.zip» v:shapes="_x0000_s1253 _x0000_s1248 _x0000_s1252 _x0000_s1251 _x0000_s1250 _x0000_s1240 _x0000_s1239 _x0000_s1249 _x0000_s1247 _x0000_s1246 _x0000_s1245 _x0000_s1242 _x0000_s1243 _x0000_s1244 _x0000_s1238 _x0000_s1241 _x0000_s1235 _x0000_s1237 _x0000_s1231 _x0000_s1236 _x0000_s1229 _x0000_s1227 _x0000_s1234 _x0000_s1230 _x0000_s1233 _x0000_s1232 _x0000_s1228 _x0000_s1226 _x0000_s1225 _x0000_s1224 _x0000_s1223 _x0000_s1222 _x0000_s1221 _x0000_s1220 _x0000_s1219 _x0000_s1218 _x0000_s1217 _x0000_s1216 _x0000_s1215 _x0000_s1214 _x0000_s1213 _x0000_s1212 _x0000_s1211 _x0000_s1210 _x0000_s1209 _x0000_s1208 _x0000_s1207 _x0000_s1206 _x0000_s1205 _x0000_s1204 _x0000_s1202 _x0000_s1203 _x0000_s1201 _x0000_s1200 _x0000_s1199 _x0000_s1198 _x0000_s1194 _x0000_s1193 _x0000_s1195 _x0000_s1197 _x0000_s1196 _x0000_s1191 _x0000_s1192 _x0000_s1184 _x0000_s1189 _x0000_s1190 _x0000_s1187 _x0000_s1177 _x0000_s1185 _x0000_s1186 _x0000_s1183 _x0000_s1179 _x0000_s1182 _x0000_s1188 _x0000_s1181 _x0000_s1180 _x0000_s1178">
Вычислительные системы как объект моделирования
Уровни проектирования:
1. Системное проектирование
Цель – определение производительности. Вычислительная система рассматривается целиком. Отдельные её элементы – ЦП, память и т.д.
ВС := <ЦП, ОП, …><ОС>
2. Функционально-логический уровень проектирования
a. Подуровень регистровых передач.
Исследование команды.
b. Логическое проектирование.
Исследование на уровне логических элементов.
3. Схемотехнический уровень.
Вопросы конкретной реализации (например, как искажается сигнал).
4. Конструкторский уровень.
Оптимизация размещений (например, теплообмен).
Проектирование происходит сверху вниз.
Моделирование на системном уровне.
При моделировании новой или модернизации действующей ВС и сетей необходимо предварительно оценить эффективность их функционирования c учетом различных вариантов структурной организации. Эти варианты могут отличаться составом и характеристиками модулей (моделей устройств), структурой межмодульных связей, режимами работы, алгоритмами управления и т.д. Именно в таких случаях используются модели ВС.
Под Вычислительным Средством понимаем комплекс аппаратных и программных средств, которые в совокупности выполняют определенные обработочные функции.
Операционная Система – набор ручных и автоматических процедур, которые позволяют группе людей эффективно использовать вычислительную установку.
Коллектив пользователей – сообщество таких людей, которые используют ВС для удовлетворения своих нужд по обработке информации.
Входные сигналы (программы, данные, команды), которые создаются коллективом пользователей, называются рабочей нагрузкой.
<img width=«543» height=«143» src=«dopb306738.zip» v:shapes="_x0000_s1262 _x0000_s1259 _x0000_s1255 _x0000_s1260 _x0000_s1254 _x0000_s1261 _x0000_s1258 _x0000_s1257 _x0000_s1256"> <img width=«506» height=«2» src=«dopb306739.zip» v:shapes="_x0000_s1263">
Индекс производительности – описатель, который используется для представления производительности системы. Различают количественные и качественные индексы производительности.
Качественные:
· легкость использования системы
· мощность системы команд
Количественные:
· пропускная способность – объем информации, обрабатываемый в единицу времени.
· время ответа (реакции) – время между предъявлением системе входных данных и появлением соответствующей выходной информации.
· коэффициент использования оборудования – отношение времени использования указанной части оборудования в течение заданного интервала времени к длительности этого интервала.
Концептуальная модель ВС включает сведение о выходных и конструктивных параметрах системы, её структуре, особенностях работы каждого элемента и ресурса, постановка прикладных задач, определение цели моделирования.
Основные задачи:
1. Определение принципов организации ВС.
2. Выбор архитектуры, уточнение функций ВС и их разделение на подфункции, реализация аппаратным и программным путем.
3. Разработка структурной схемы – определение состава устройств и способов их взаимодействий.
4. Определение требований к выходным параметрам устройств и формирования технического задания на разработку устройств для функционально-логического уровня проектирования.
Непрерывно-стохастические модели (Q-схемы).
Особенности непрерывно-стохастического подхода в дальнейшем рассматривается только на примере использования в качестве типовых математическим моделей системы массового обслуживания. Характерным для СМО является случайное появление заявок на обслуживания и завершение обслуживания в случайные моменты времени.
Основные понятия теории массового обслуживания.
Потоком событий называется последовательность событий, происходящих одно за другим в случайные моменты времени.
Поток событий называется однородным, если он характеризуется только моментами поступления этих событий (вызывающими моментами) и задается следующей последовательностью:
<shape id="_x0000_i1048" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image057.wmz» o:><img width=«228» height=«27» src=«dopb306740.zip» v:shapes="_x0000_i1048">,
где tn– момент поступления n-ого события.
Поток событий неоднородный, если он задается не только вызывающими моментами, но и функцией f(n) – набор признаков события (наличие приоритета, принадлежащего к какому-либо типу заявки, класса и т.д.).
Если интервалы времени между событиями независимы между собой и являются случайными величинами, то такой поток называется потоком с ограниченным последействием.
Поток событий называется ординарным, если вероятность того, что на малый интервал времени Dt, примыкающий к моменту времени t, попадает более одного события, пренебрежимо мала по сравнению с вероятностью того, что на этот же интервал времени попадает ровно одно событие.
Поток стационарный, если вероятность появления того или иного события на некотором интервале времени зависит лишь от длины этого интервала и не зависит от того, где на оси времени взят этот интервал.
Для ординарного потока среднее число сообщений за интервал времени Dt равно P1 (t, Dt), тогда
<shape id="_x0000_i1049" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image059.wmz» o:><img width=«119» height=«44» src=«dopb306741.zip» v:shapes="_x0000_i1049"> - интенсивность ординарного потока.
Для стационарного потока интенсивность не зависит от времени и представляет собой постоянное значение равное среднему числу событий, наступивших в единицу времени.
В любом элементарном акте обслуживания можно выделить 2 основные составляющие:
1. собственно, обслуживание
2. ожидание обслуживания заявки
<img width=«472» height=«209» src=«dopb306742.zip» v:shapes="_x0000_s1265 _x0000_s1266 _x0000_s1269 _x0000_s1279 _x0000_s1271 _x0000_s1273 _x0000_s1270 _x0000_s1275 _x0000_s1274 _x0000_s1272 _x0000_s1281 _x0000_s1277 _x0000_s1276 _x0000_s1278 _x0000_s1268 _x0000_s1264 _x0000_s1282 _x0000_s1280 _x0000_s1267">
K – канал, Н – накопитель, П – прибор обслуживания
В i-ом приборе обслуживания имеем:
· wi – поток заявок т.е. интервалы времени между моментами появления заявок (вызывающие моменты) на входе канала Ki.
· ui – поток обслуживания – интервалы времени между началом и окончанием обслуживания заявок.
Заявки, обслуженные каналом, и заявки, покинувшие i-ый прибор не обслуженными, образуют выходной поток Yi, т.е. интервалы времени между моментами выхода заявок.
Процесс функционирования прибора Пi можно представить как процесс изменения состояний его элементов во времени. Переход в новое состояние для прибора означает изменение количества заявок, которые в нем находятся.
<shape id="_x0000_i1050" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image062.wmz» o:><img width=«115» height=«28» src=«dopb306743.zip» v:shapes="_x0000_i1050"> <shape id="_x0000_i1051" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image064.wmz» o:><img width=«103» height=«28» src=«dopb306744.zip» v:shapes="_x0000_i1051"> <shape id="_x0000_i1052" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image066.wmz» o:><img width=«229» height=«59» src=«dopb306745.zip» v:shapes="_x0000_i1052">
где Z – заявка, L – емкость накопителя
В практике моделирование элементарные Q-схемы обычно объединяются. При этом, если каналы различных приборов обслуживания соединены параллельно, то имеет место многоканальное обслуживание, а если последовательно – то многофазное. Следовательно, для задания Q-схемы необходимо использовать некоторый оператор — R-оператор сопряжения, отражающий взаимосвязь элементов структуры между собой.
Различают разомкнутые и замкнутые Q-схемы. В разомкнутых схемах выходной поток не может попасть на вход, а в замкнутых схемах количество заявок постоянно.
Собственными внутренними параметрами Q-схемы будут являться:
· Количество фаз
· Количество каналов в каждой фазе
· Количество накопителей в каждой фазе
· Емкость i-ого накопителя
В зависимости от емкости накопителя в теории массового обслуживания принято:
· Емкость 0 – система с потерями.
· Емкость ® ¥ — система с ожиданием
· Емкость конечна – система смешанного типа
Для задания функционирования Q-схемы также необходимо описать алгоритм её функционирования, который определяет набор правил поведения заявок в различных ситуациях.
продолжение
--PAGE_BREAK--Неоднородность заявок, отражающая реальный процесс учитывается введением классов приоритетов. Следовательно, Q-схема, описывающая процесс функционирования системы массового обслуживания любой сложности, однозначно задается:
Q = (W, U, R, H, Z, A)
1. W — подмножеством входных потоков
2. U — подмножеством потоков обслуживания
3. H — подмножеством собственных параметров
4. R — оператором сопряжения элементов структуры
5. Z — множеством состояний элементов системы
6. A — оператором алгоритмов обслуживания заявок
Для получения соотношений, связывающих характеристики описания функционирования Q-схемы вводятся некоторые допущения относительно входных потоков, функций распределения параметров, длительности обслуживания запросов, дисциплин обслуживания.
Для математического описания функционирования устройств, развивающегося в форме случайного процесса, может быть использован математический аппарат, который носит название Марковского случайного процесса.
Случайный процесс, протекающий в некоторой системе называется Марковским случайным процессом, если он обладает следующим свойством: для каждого момента времени tвероятность любого состояния системы в будущем (при t> t) зависит только от состояния системы в настоящем и не зависит от того, когда и каким образом система пришла в это состояние.
В марковском случайном процессе будущее развитие зависит только от настоящего состояния и не зависит от предыстории. Для марковских случайных процессов определяется вероятности нахождения системы в том или ином состоянии используя уравнения Колмогорова:
<shape id="_x0000_i1053" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image068.wmz» o:><img width=«156» height=«25» src=«dopb306746.zip» v:shapes="_x0000_i1053">,
где p(t) – вероятность попадания в какое-либо состояние
l — множество определенных коэффициентов
Для стационарного потока:
<shape id="_x0000_i1054" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image070.wmz» o:><img width=«140» height=«25» src=«dopb306747.zip» v:shapes="_x0000_i1054">
<shape id="_x0000_i1055" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image072.wmz» o:><img width=«107» height=«25» src=«dopb306748.zip» v:shapes="_x0000_i1055"> - базисная модель
<shape id="_x0000_i1056" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image074.wmz» o:><img width=«128» height=«25» src=«dopb306749.zip» v:shapes="_x0000_i1056"> - интерфейсная модель
Математическая модель некоторой сложной системы строится как совокупность базисной модели и интерфейсной модели, что позволяет использовать одни и те же базисные модели для разных задач проектирования, осуществляя настройку на соответствующую конкретную задачу, посредством изменения только параметров интерфейсной модели.
Математическая модель сложной Q-схемы должна обеспечивать вычисление времени реакции на запрос и производительность системы.
Методика вывода уравнений Колмогорова
<shape id="_x0000_i1057" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image076.wmz» o:><img width=«125» height=«29» src=«dopb306750.zip» v:shapes="_x0000_i1057">
<shape id="_x0000_i1058" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image078.wmz» o:><img width=«73» height=«29» src=«dopb306751.zip» v:shapes="_x0000_i1058">-интенсивность перехода
<shape id="_x0000_i1059" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image080.wmz» o:><img width=«47» height=«27» src=«dopb306752.zip» v:shapes="_x0000_i1059">
1. Найдем вероятность того, что в момент времени t система
находится в состоянии S1. Придадим t малое приращение Dt и
определим, что система в момент времени t+Dt находится в состоянии S1.
<shape id="_x0000_i1060" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image082.wmz» o:><img width=«317» height=«27» src=«dopb306753.zip» v:shapes="_x0000_i1060">
<shape id="_x0000_i1061" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image084.wmz» o:><img width=«348» height=«49» src=«dopb306754.zip» v:shapes="_x0000_i1061">
<shape id="_x0000_i1062" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image086.wmz» o:><img width=«220» height=«27» src=«dopb306755.zip» v:shapes="_x0000_i1062">
2. Найдем вероятность того, что система находится в состоянии S2:
<shape id="_x0000_i1063" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image088.wmz» o:><img width=«480» height=«27» src=«dopb306756.zip» v:shapes="_x0000_i1063">
<shape id="_x0000_i1064" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image090.wmz» o:><img width=«512» height=«49» src=«dopb306757.zip» v:shapes="_x0000_i1064">
<shape id="_x0000_i1065" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image092.wmz» o:><img width=«388» height=«27» src=«dopb306758.zip» v:shapes="_x0000_i1065">
3. Найдем вероятность того, что система находится в состоянии S3:
<shape id="_x0000_i1066" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image094.wmz» o:><img width=«305» height=«27» src=«dopb306759.zip» v:shapes="_x0000_i1066">
4. Найдем вероятность того, что система находится в состоянии S4:
<shape id="_x0000_i1067" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image096.wmz» o:><img width=«308» height=«27» src=«dopb306760.zip» v:shapes="_x0000_i1067">
В результате получаем систему уравнений Колмогорова:
<shape id="_x0000_i1068" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image098.wmz» o:><img width=«288» height=«120» src=«dopb306761.zip» v:shapes="_x0000_i1068">
Интегрирование данной системы даст искомые вероятности состояний, как функций времени. Начальные условия берутся в зависимости от того, какого было начальное состояние системы. Если при t=0 система находится в состоянии S1, то начальные условия будут p1=1, p2= p3= p4=0. Кроме этого, к системе добавляются условия нормировки:
<shape id="_x0000_i1069" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image100.wmz» o:><img width=«69» height=«45» src=«dopb306762.zip» v:shapes="_x0000_i1069">
Все уравнения строятся по определенному правилу:
1. В левой части каждого уравнения стоит производная вероятности состояния, а в правой части содержится столько членов, сколько стрелок связано с этим состоянием.
2. Если стрелка направлена «из» состояния, соответствующий член имеет знак “-“, если «в» состояние, то знак “+”.
3. Каждый член равен произведению плотности вероятности перехода (интенсивность), соответствующий данной стрелке, и вероятности того состояния, из которого выходит стрелка.
Пример.
Рассмотрим многоканальную СМО с отказами. Состояние системы характеризуется по числу занятых каналов, т.е. по числу заявок.
S0 – все каналы свободны
S1 – занят один канал, остальные свободны
Sk – занято k каналов, остальные свободны
Sn – заняты все n каналов.
<img width=«199» height=«55» src=«dopb306763.zip» v:shapes="_x0000_s1299 _x0000_s1298 _x0000_s1297 _x0000_s1295 _x0000_s1294 _x0000_s1293"> <img width=«126» height=«53» src=«dopb306764.zip» v:shapes="_x0000_s1296 _x0000_s1292 _x0000_s1291"> <img width=«76» height=«53» src=«dopb306765.zip» v:shapes="_x0000_s1290 _x0000_s1289"> <img width=«53» height=«20» src=«dopb306766.zip» v:shapes="_x0000_s1305"> <img width=«53» height=«20» src=«dopb306766.zip» v:shapes="_x0000_s1304"> <img width=«53» height=«20» src=«dopb306766.zip» v:shapes="_x0000_s1303"> <img width=«53» height=«20» src=«dopb306766.zip» v:shapes="_x0000_s1302"> <img width=«53» height=«20» src=«dopb306766.zip» v:shapes="_x0000_s1300"> <img width=«53» height=«20» src=«dopb306766.zip» v:shapes="_x0000_s1301">
Разметим граф, т.е. проставим у стрелок интенсивности соответствующих потоков событий. Пусть система находится в состоянии S1. Как только закончится обслуживание заявки, занимающей этот канал, система переходит в состояние S0, интенсивность перехода m. Если занято 2 канала, а не один, то интенсивность перехода составит 2m.
<shape id="_x0000_i1070" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image106.wmz» o:><img width=«332» height=«149» src=«dopb306767.zip» v:shapes="_x0000_i1070">
Предельные вероятности состояний pи pn характеризую установившийся режим работы системы массового обслуживания при t® ¥.
<shape id="_x0000_i1071" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image108.wmz» o:><img width=«311» height=«76» src=«dopb306768.zip» v:shapes="_x0000_i1071">
<shape id="_x0000_i1072" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image110.wmz» o:><img width=«129» height=«51» src=«dopb306769.zip» v:shapes="_x0000_i1072">
<shape id="_x0000_i1073" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image112.wmz» o:><img width=«77» height=«25» src=«dopb306770.zip» v:shapes="_x0000_i1073"> - среднее число заявок, приходящих в систему за среднее время обслуживания одной заявки.
<shape id="_x0000_i1074" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image114.wmz» o:><img width=«235» height=«59» src=«dopb306771.zip» v:shapes="_x0000_i1074">
<shape id="_x0000_i1075" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image116.wmz» o:><img width=«91» height=«51» src=«dopb306772.zip» v:shapes="_x0000_i1075">
Зная все вероятности состояний p, …, pn, можно найти характеристики СМО:
· вероятность отказа – вероятность того, что все n каналов заняты
<shape id="_x0000_i1076" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image118.wmz» o:><img width=«147» height=«51» src=«dopb306773.zip» v:shapes="_x0000_i1076">
· относительная пропускная способность – вероятность того, что заявка будет принята к обслуживанию
<shape id="_x0000_i1077" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image120.wmz» o:><img width=«79» height=«27» src=«dopb306774.zip» v:shapes="_x0000_i1077">
· среднее число заявок, обслуженных в единицу времени
<shape id="_x0000_i1078" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image122.wmz» o:><img width=«60» height=«25» src=«dopb306775.zip» v:shapes="_x0000_i1078">
Полученные соотношения могут рассматриваться как базисная модель оценки характеристик производительности системы. Входящий в эту модель параметр l = 1 / tОБРАБОТКИ, является усредненной характеристикой пользователя. Параметр m является функцией технических характеристик компьютера и решаемых задач.
Эта связь может быть установлена с помощью соотношений, называемых интерфейсной моделью. Если время ввода/вывода информации по каждой задачи мало по сравнению со временем решения задачи, то логично принять, что время решения равно 1 / m и равно отношению среднего числа операций, выполненных процессором при решении одной задачи к среднему быстродействию процессора.
На практике далеко не все случайные процессы являются Марковскими или близкими к ним. В СМО поток заявок не всегда Пуассоновский, ещё реже наблюдается показательное или близкое к нему распределение времени обслуживания.
Для произвольных потоков сообщений, переводящих систему из одного состояния в другое, аналитическое решение получено только для отдельных частных случаев. Когда построение аналитической модели по той или иной причине трудно осуществимо, применяется другой метод моделирования – метод статистических испытаний (Монте-Карло). Широкое распространение метода связано с возможностью его реализации на компьютере.
Идея метода: вместо того, чтобы описывать случайное явление с помощью аналитической зависимости производится «розыгрыш», т.е. происходит моделирование случайного явления с помощью некоторой процедуры, дающей случайный результат. Произведя такой розыгрыш n раз, получаем статистический материал, т.е. множество реализаций случайного явления, которое потом можно обработать обычными методами математической статистики. Метод Монте-Карло предложил Фон-Нейман в 1948 году, как метод численного решения некоторых математических задач.
Суть метода:
1. Вводим в некотором единичном квадрате любую поверхность S.
2. Любым получаем 2 числа xi, yi, подчиняющиеся равномерному закону распределения случайной величины на интервале [0, 1].
3. Полагаем, что одно число определяет координату x, второе – координату y
4. Анализируем принадлежность точки (x, y) фигуре. Если принадлежит, то увеличиваем значение счетчика на 1.
5. Повторяем n раз процедуру генерации 2х случайных чисел с заданным законом распределения и проверку принадлежности точки поверхности S.
6. Определяем площадь фигуры как количество попавших точек, к количеству сгенерированных.
Фон-Нейман доказал, что погрешность <shape id="_x0000_i1079" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image124.wmz» o:><img width=«64» height=«55» src=«dopb306776.zip» v:shapes="_x0000_i1079">.
Преимущества метода статистических испытаний в его универсальности, обуславливающей возможность всестороннего статистического исследования объекта, однако, для реализации этой возможности нужны довольно полные статистические сведения о параметрах элементов.
К недостаткам относится большой объем требуемых вычислений, равный количеству обращений к модели. Поэтому вопрос выбора величины n имеет важнейшее значение. Уменьшая n – повышаем экономичность расчетов, но одновременно ухудшаем их точность.
Способы получения последовательностей случайных чисел
На практике используются 3 основных способа генерации случайных чисел:
1. аппаратный (физический)
2. табличный (файловый)
3. алгоритмический (программный)
Аппаратный способ.
Случайные числа вырабатываются специальной электронной приставкой (генератором случайных чисел). Реализация этого способа не требует дополнительных вычислительных операций по выбору случайных чисел. Необходимо только оперативное обращение к ВУ.
В качестве физического эффекта, лежащего в основе генератора, чаще всего используют шуму в электронных приборах.
Простейшие алгоритмы генерации последовательности псевдослучайных чисел
Одним из первых способов получения является выделение значения дробной части у многочлена первой степени:
<shape id="_x0000_i1080" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image126.wmz» o:><img width=«137» height=«27» src=«dopb306777.zip» v:shapes="_x0000_i1080">
Если n пробегает значения натурального ряда числе, то поведение yn выглядит весьма хаотично.
К. Якоби доказал, что при рациональном коэффициенте a множество y конечно, а при иррациональном – бесконечно и всюду плотно в интервале [0, 1].
Критерий равномерности распределения любой функции: свойство эргамичности – среднее по реализациям псевдослучайное число равно среднему по всему их множеству с вероятностью 1.
1. 1946 год, Фон Нейман.
Каждое последующее случайное число образуется возведением в квадрат предыдущего и отбрасывание цифр с обоих концов. Способ оказался ненадежным.
2. Лемер.
<shape id="_x0000_i1081" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image128.wmz» o:><img width=«180» height=«27» src=«dopb306778.zip» v:shapes="_x0000_i1081">. Для подборов коэффициентов k, c, m были потрачены десятки лет. Подбор почти иррациональных чисел ничего не дает.
3. Разумнее ввести вычисления с целыми числами.
при c = 0 и m = 2n наибольший период достигается при k=3+8i или k=5+8i и при нечетном начальном числе.
Для имитации равномерного распределения на [a, b] используется обратное преобразование функции плотности вероятности.
<shape id="_x0000_i1082" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image130.wmz» o:><img width=«132» height=«80» src=«dopb306779.zip» v:shapes="_x0000_i1082">
где R – равномерно распределенное псевдослучайное число на [0, 1].
В основе построения программы генерации случайной числа с законом распределения, отличным от равномерного, лежит метод преобразования последовательности случайных чисел с равномерным законом распределения в последовательность случайных чисел с заданным законом распределения.
Метод основан на том, что случайная величина x принимает значения, равные корню уравнения
<shape id="_x0000_i1083" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image132.wmz» o:><img width=«167» height=«49» src=«dopb306780.zip» v:shapes="_x0000_i1083">
, имеет плотность распределения f(x). R – случайная величина, равномерно распределенная на [0, 1].
Значение случайной величины, распределенной по показательному закону может быть вычислено из данного уравнения следующим образом:
<shape id="_x0000_i1084" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image134.wmz» o:><img width=«148» height=«81» src=«dopb306781.zip» v:shapes="_x0000_i1084">
Распределение Пуассона относится к числу дискретных (переменная может принимать лишь целочисленные значения, включая 0, с математическим ожиданием и дисперсией l > 0). Для генерации Пуассоновских переменных можно использовать метод точек, в основе которого лежит генерируемое случайное значение Ri, равномерно распределенное на [0, 1], до тех пор, пока не станет справедливым
<shape id="_x0000_i1085" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image136.wmz» o:><img width=«149» height=«45» src=«dopb306782.zip» v:shapes="_x0000_i1085">
При получении случайной величины, функция распределения которой не позволяет найти решение уравнения
<shape id="_x0000_i1086" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image132.wmz» o:><img width=«167» height=«49» src=«dopb306780.zip» v:shapes="_x0000_i1086">
в явной форме, можно произвести кусочно-линейную аппроксимацию, а затем вычислить приближенное значение корня. Кроме того, при получении случайной величины часто используют те или иные свойства распределений.
Воспользуемся этим методом, чтобы сгенерировать случайную величину с законом распределения Эрланга. Распределение Эрланга характеризуется параметрами l и k.
При вычислении случайно величины воспользуемся тем, что поток Эрланга может быть получен путем прорешивания потока Пуассона k раз. Поэтому, достаточно получить k значений случайной величины распределенной по показательному закону и усреднить их.
<shape id="_x0000_i1087" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image138.wmz» o:><img width=«356» height=«49» src=«dopb306783.zip» v:shapes="_x0000_i1087">
Нормальное распределение случайной величины может быть получено как сумма большого числа случайных величин, распределенных по одному и тому же закону распределения с одними и теми же параметрами.
Случайная величина X имеющая нормальное распределение с математическим ожиданием MX и среднеквадратичным отклонением sX может быть получена по следующей формуле:
<shape id="_x0000_i1088" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image140.wmz» o:><img width=«253» height=«55» src=«dopb306784.zip» v:shapes="_x0000_i1088">
Для сокращения вычислений на практике принимаю N=12, что дает вполне относительно хорошее приближение к нормальному распределению.
Немарковские случайные процессы, сводящиеся к марковским
Реальные процессы часто обладают последствием и поэтому не являются марковскими. Иногда при исследовании таких процессов удается воспользоваться методами, разработанными для марковских процессов. Наиболее распространены два способа:
1. Метод разложения случайного процесса на фазы (метод псевдосостояний)
2. Метод вложенных цепей Маркова
Метод псевдосостояний
Суть метода состоит в том, что состояния системы, потоки переходов из которых являются немарковскими, заменяются эквивалентной группой фиктивных состояний, потоки переходов из которых являются марковскими.
Условие статистической эквивалентности реального состояния и соответствующих ему фиктивных состояний в каждом конкретном случае выбирается по-разному. В качестве одного из критериев эквивалентности можно принять следующее условие:
<shape id="_x0000_i1089" type="#_x0000_t75" o:ole=""><imagedata src=«89593.files/image142.wmz» o:><img width=«161» height=«60» src=«dopb306785.zip» v:shapes="_x0000_i1089">
продолжение
--PAGE_BREAK--
еще рефераты
Еще работы по коммуникациям