3629 МОДЕЛИРОВАНИЕ

Введение

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

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

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

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

Дисциплина “Моделирование” имеет целью обучить студентов современным принципам моделирования в целом и вычислительных систем в частности, ознакомить с основными положениями теории моделирования и их использованием при решении задач проектирования и исследования систем.

1. Цель курсовой работы

Курсовая работа по дисциплине “Моделирование” предназначена для практического усвоения студентами основных разделов теоретической части курса, закрепления и углубления знаний по математическим и программным средствам моделирования, получения навыков комплексного решения задач на базе современных ЭВМ.

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

2. Порядок выполнения курсовой работы

Этапы выполнения курсовой работы те же, что и при моделировании на ЭВМ реальных больших систем в ходе их проектирования и исследования [1,2]. К основным  этапам машинного моделирования  систем относятся:

1)      построение концептуальной модели системы и ее формализация;

2)      алгоритмизация и ее машинная реализация;

3)      получение и интерпретация результатов моделирования.

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

При выполнении  курсовой работы на первом этапе необходимо проанализировать полученное задание, уточнить цели моделирования, уточнить алгоритм функционирования моделируемой системы. Затем следует разработать концептуальную модель - текстовое описание объекта моделирования с числовыми данными, приведенными в задании, описание состава и структуры системы оригинала S0, свойств элементов, связей между элементами, процессов, протекающих в оригинале, внешних воздействий. Концептуальную модель надо проверить на непротиворечивость и полноту описания, для чего следует убедиться, что задание содержит всю необходимую качественную и количественную информацию об объекте. Затем производится формализация концептуальной модели. В качестве аппарата формализации процессов функционирования моделируемых систем в курсовой работе используются Q–схемы – системы массового обслуживания [1]. При формализации концептуальной  модели производится исключение второстепенных элементов и связей, представление моделируемой системы в виде системы массового обслуживания (совокупности источников, заявок, устройств памяти, очередей, логических переключателей и т.д.). Затем в данной курсовой работе проводится аналитический расчет характеристик СМО, что сделано специально для получения практических навыков аналитического  моделирования.

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

Следующим этапом является алгоритмизация процесса функционирования системы моделирования, представленного в виде СМО. Производится переход от формальной модели к её конкретной машинной реализации, ориентированной на использование конкретных программно–технических средств (в курсовой  работе  - это пакет моделирования дискретных систем – ПМДС –GPSS/PC). ПМДС GPSS/РС предназначен для имитационного моделирования сложных производственных, вычислительных и информационных систем. Средства системы GPSS/PC ориентированы  на построение моделей вычислительных систем и проведение машинного эксперимента с целью их анализа только на самом верхнем (системном) этапе проектирования. На этом этапе моделирования принимаются решения о том, какими средствами языка будут описаны объекты реальной  системы в модели, как задаётся маршрут прохождения транзактов по модели, времена обслуживания в отдельных устройствах, условия окончания моделирования и т.д. Этап заканчивается составлением блок–диаграммы модели, представляющей собой логическую схему модели, адаптированную к особенностям  использования для машинной реализации модели ПМДС. При кодировании каждый блок диаграммы заменяется соответствующим оператором языка GPSS. Блок-диаграмма дает  достаточную степень детализации, поддерживаемую средствами ПМДС, для генерации рабочей программы моделирования.

На этапе отладки обнаруживаются и устраняются синтаксические и семантические ошибки. Для тестирования полученной ПМДС–программы может быть использовано специальное средство TRACE [3]. Листинг отлаженной программы выводится на печать.

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

  1. 3. Требования к содержанию и оформлению пояснительной записки

Пояснительная записка должна содержать разделы, отражающие этапы моделирования системы:

  1. Титульный лист.
  2. Введение.
  3. Постановка задачи (подробное задание на проектирование).
  4. Разработка концептуальной модели и её формализация.

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

  1. Аналитический расчет СМО (с описанием введенных переменных, процедуры расчета характеристик СМО, анализом полученных результатов).
  2. Алгоритмизация модели, обоснование принятых решений (необходимо привести блок-диаграмму с подробным описанием процесса функционирования модели).
  3. Кодирование программы. Листинги программы, описание процесса отладки.
  4. Интерпретация и анализ результатов имитационного моделирования.
  5. Сравнение результатов аналитического и имитационного моделирования.
  6. Разработка в соответствии с требованиями ЕСПД программной документации (“Руководство оператора”, “Порядок и методика испытаний”).
  7. Заключение. Выводы.
  8. Библиографический список.
  9. Содержание с указанием номеров страниц.
  10. Приложение. Листинги.

Пояснительная записка должна быть выполнена на бумаге формата 11(А4), схемы алгоритмов – с соблюдением ГОСТа и ЕСПД [4,5].

  1. 4. Аналитическое моделирование

Используются вероятностные и детерминированные аналитические модели. Отличие вероятностных моделей состоит в том, что они естественным образом подходят для представления некоторых  аспектов изменчивости характеристик систем. Рассмотрим вероятностные методы на примере вычислительных систем. Для современных вычислительных машин и систем  характерна работа в режиме решения потока случайных по своим характеристикам задач, поступающих в общем случае в случайные моменты времени. Случайность характерна и для отдельных  подсистем, например подсистемы “процессор – основная память” (случаен поток  команд, выбираемых  устройством управления процессора из памяти), внешних запоминающих устройств (случайно время доступа к хранящемуся в накопителе файлу) и т.д. Анализ и синтез подобных систем с учетом вероятностного характера протекающих в них процессов возможны  методами теории массового обслуживания. Теория массового обслуживания занимается изучением случайных процессов, протекающих в СМО. Аналитическое исследование СМО является наиболее простым, если все потоки событий, переводящие её из состояния в состояние, - простейшие (стационарные пуассоновские). Это значит, что интервалы времени между событиями в потоках имеют показательное распределение с параметром, равным интенсивности соответствующего потока. Для СМО это допущение означает, что как поток заявок, так и поток обслуживаний – простейшие. Вместо “поток обслуживаний простейший” часто говорят “время обслуживания показательное ”. Если все потоки событий простейшие, то процесс, протекающий в СМО, представляет собой марковский случайный процесс с дискретными  состояниями и непрерывным временем.

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

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

Основная задача теории массового обслуживания – задача синтеза оптимальной структуры СМО или сети (ее состава и функциональных связей) при заданных свойствах, ограничениях на параметры входного потока и ресурсы системы. Однако решение этой задачи возможно только после решения задач анализа разнообразных структур СМО. Задача анализа – это определение количественных показателей функционирования систем и сетей массового обслуживания и их зависимости от параметров входящего потока и структуры собственно системы или сети. Решение этой задачи даёт возможность найти “узкие места” системы, определить их влияние на эффективность обслуживания и найти пути их устранения либо при заданных параметрах потока заявок и критериях эффективности обслуживания дать предложения о структуре системы или сети, которая обеспечит решение поставленных задач. Так, для исследования перегруженных вычислительных систем, в которых за обладание ресурсами соревнуются несколько процессов, особенно удобны вероятностные модели, основывающиеся на теории очередей [6]. Существующие математические методы позволяют решить модель только когда она достаточно проста. Для того чтобы модель стала разрешимой, обычно делаются некоторые упрощающие предположения, которые могут оказаться причиной снижения точности модели. Исследователю необходимо учитывать этот факт.

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

Рассмотрим пример аналитического расчета.

Пример. На вход двухпроцессорной центральной управляющей системы (ЦУС) поступают заявки, образующие три простейших входящих потока с интенсивностями  1 = 6 с –1, 2= 15 с –1, 3= 9 с –1. Процессоры принимаются однотипными со средним быстродействием = 50 3 опер./с. Обслуживание заявки заключается в выполнении на любом из процессоров прикладной программы, причем средняя трудоёмкость всех трех прикладных программ принимается примерно одинаковой: = 2,53 операций. От заявки к заявке конкретная трудоёмкость меняется случайным образом. Для простоты будем считать закон её распределения экспоненциальным. Для хранения заявок, которые не могут быть немедленно поставлены на обслуживание, выделена буферная зона памяти емкостью в 8 ячеек, служебная информация об одной заявке занимает 2 ячейки памяти. Время пребывания заявки в системе не должно превышать случайной величины доп, распределенной экспоненциально с математическим ожиданием доп= 0,1 с. Операционная система реализует бесприоритетные дисциплины ожидания и обслуживания, в её же функции входит удаление “устаревших” заявок из системы. Критерий эффективности управляющей системы имеет вид

Е= (откPотк + yPy) + н(m  - ),

где отк - штраф за отказ СМО принять заявку; у – штраф за «устаревание» заявки за время обработки её системой (за уход «нетерпеливой» заявки из СМО); н – штраф за неиспользование одного канала обслуживания.

Необходимо для заданных параметров СМО и заданного критерия эффективности определить Е. Принять следующие значения штрафов: отк= 3 усл. ед. , у= 2 усл. ед. , н= 10 усл. ед. / канал.

Переформулируем предложенную задачу в терминах теории массового обслуживания. В данном случае исследуемую систему можно представить в виде СМО разомкнутого типа, содержащую m (m= 2) однотипных каналов обслуживания, характеризующихся экспоненциальным распределением времени обслуживания со средним значением об или, что эквивалентно, простейшим потоком обслуживаний с интенсивностью = 1/об независимо от типа обслуживаемой заявки. При полностью загруженных каналах заявки могут ждать обслуживания в общей очереди с числом мест n. Дисциплина ожидания – бесприоритетная, заявки ставятся в очередь в порядке поступления, при переполнении очереди вновь поступившая заявка получает отказ. Дисциплина обслуживания также бесприоритетная, при освобождении какого-либо из каналов обслуживания заявка выбирается из начала очереди (дисциплина FIFO). Заявки на входе СМО относятся к одному из М (М= 3) типов, причем заявки i-го типа образуют простейший поток с интенсивностью i (i= ). Так как исследуется бесприоритетная СМО с общей очередью, следует рассматривать объединенный входящий поток, который также будет простейшим с интенсивностью = i. Заявки «нетерпеливы», т.е. они имеют право пробыть в СМО не более доп единиц времени. Если время пребывания заявки в системе tc превышает доп, заявка покидает систему и считается потерянной для нее. «Нетерпеливость» заявок отражает свойство старения информации в вычислительных системах реального времени. Величина доп является случайной с экспоненциальным законом распределения и математическим ожиданием доп= 0,1 с. Уход заявок из СМО будем рассматривать как простейший поток с интенсивностью ν = 1/доп. Уходы заявки возможны либо из очереди, если tож > доп , либо из канала обслуживания, если tож доп. Тогда модель исследуемой системы в виде СМО разомкнутого типа можно представить следующим образом (рис. 1).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 1. СМО разомкнутого типа с двумя однотипными каналами обслуживания

 

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

ож= об= = 1/ доп .

Таким образом, для исследуемой системы имеем число каналов m= 2; число мест в очереди    n= = 4; заявки «нетерпеливы», интенсивность простейшего потока уходов

= = 10 с –1.

Составляющие входящего потока – простейшие потоки заявок с интенсивностями  1 = 6 с –1, 2= 15 с –1, 3= 9 с –1. Единый входящий поток заявок имеет суммарную интенсивность

= 1+ 2+ 3= 6+ 15+ 9= 30 (с -1).

Поток обслуживания для одного канала имеет интенсивность

= =  20 с –1 .

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

S0 – в СМО нет ни одной заявки, каналы обслуживания простаивают, очередь отсутствует;

S1 – в СМО одна заявка, ее обслуживанием занят один из каналов, второй канал простаивает, очередь отсутствует;

Sm= S2 – в СМО две заявки, все каналы обслуживания загружены, очередь отсутствует;

Sm+1= S3 – в СМО три заявки, последняя из пришедших заявок находится в очереди;

Sm+2= S4 – в СМО четыре заявки, две из которых обслуживаются в ОА1 и ОА2, а две находятся в очереди;

Sm+3= S5 – в СМО пять заявок, оба канала обслуживания загружены, три заявки находятся в очереди;

Sm+n= S6 – в СМО m+ n= 2+ 4=6 заявок, оба канала обслуживания загружены, все n= 4 мест в очереди заняты ожидающими обслуживания заявками, СМО в этом состоянии не способна принять дополнительно ни одной заявки, все вновь приходящие заявки получают отказ.

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

S0 S1 S2 S3 S4 S5 S6

 

 

1(+об.)        m (+об.)     m (+об.) +      m (+об.) +      m (+об.) +       m (+об.) +

+ 1           + (n - 2)          + ( n - 1)               + n

 

Рис. 2. Граф переходов

Переходы между состояниями в сторону возрастания индекса состояния возможны лишь под действием входящего потока с интенсивностью = 30 с-1, вследствие ординарности входящего потока переходы возможны лишь между соседними состояниями.

Переходы из состояний Si (i=, m= 2), т.е. S1 и S2, соответствующих отсутствию очереди, в соседние слева состояния, отличающиеся меньшим на единицу числом заявок в системе, происходят под воздействием на заявки, находящиеся в каналах обслуживания, одновременно двух независимых потоков событий: потока обслуживаний с интенсивностью  и потока ухода «нетерпеливых» заявок с интенсивностью об.. Поскольку процессы в различных каналах, занятых обслуживанием, независимы друг от друга , суммарная интенсивность переходов связана с числом занятых каналов и равна i(+об.). Интенсивность переходов из состояний Sm+, =  (m= 2, n= 4), соответствующих  полностью занятым каналам обслуживания и непустой очереди длиной , в соседние слева состояния складывается из двух составляющих:

- одна составляющая соответствует  суммарной интенсивности переходов за счет потоков обслуживаний и потов уходов «нетерпеливых» заявок из каналов обслуживания и равна m(+об)= 2(+об.);

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

Поведение СМО в переходном режиме описывается системой дифференциальных уравнений Колмогорова, решение которой представляет собой совокупность (m+n+1) функций времени, описывающих изменение вероятностей состояний СМО в переходном режиме. В данном случае нас интересует установившийся режим, т.е. режим, соответствующий окончанию переходного режима при t . Граф, приведенный на рис.2, представляет собой типичную схему «гибели и размножения», поэтому для получения предельных вероятностей состояний можно использовать формулу Эрланга [7]:

Pi= , i= ;                                                                  (1)

Pm+= , =                             (2)

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

Pi= ,  i= ;

(3)

Pm+= ,

 

где  - приведенная интенсивность входящего потока, представляющая собой среднее число заявок, поступающих на вход СМО за среднее время обслуживания одной заявки;

об= об/  - приведенная интенсивность потока уходов из канала обслуживания;

ож= ож/  - приведенная интенсивность потока уходов из очереди.

Вероятность P0 определяется из нормирующего условия

P0= .                 (4)

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

ож= об= .

Определим по формуле (4) вероятность состояния S0 :

 

По формулам (3) через вероятность P0 определим вероятности других состояний. Для состояний S1 и S2, когда очередь отсутствует, соответствующие вероятности равны

P1=

P2= .

Состояния S3 – S6 соответствуют случаям наличия очереди в СМО. Вероятности пребывания системы в этих состояниях:

 

 

 

Рассчитав значения вероятностей, найдем показатели эффективности системы и значение критерия эффективности Е.

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

=                                                  (5)

 

Средняя длина очереди  :

= ;                                                          (6)

 

=

Загрузка системы определяется по формуле

=,                                                                                          (7)

=0,9398/2=0,4699.

Определим среднее число заявок в системе:

,                                                                (8)

.

Определим вероятности частных видов потерь. В рассматриваемой СМО потери заявок возможны либо в форме отказа вследствие переполнения системы, либо в форме ухода «нетерпеливых» заявок из системы. Вероятность отказа Pотк можно определить как вероятность нахождения системы в состоянии Sm+n :

Pотк= Pm+n=  ,                                             (9)

Pотк= P6= 0,0029.

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

Pу= Pу.ож+ Pу.об ,                                                                                              (10)

где Pу.ож и Pу.об – вероятности ухода заявки во время ожидания и обслуживания.

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

Pу.об= ,                                                                     (11)

Pу.об= .

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

Pу.ож= ,                                                                     (12)

Pу.ож=.

Тогда вероятность ухода «нетерпеливой» заявки из системы найдем по формуле (10):

Pу=0,3133+ 0,0575=0,3708.

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

Pn= Pотк+ Pу= Pотк+ (Pу.ож+ Pу.об),                              (13)

Pn = 0,0029+ 0,3708= 0,3737.

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

Pоб=1- Pn ,                                                                                                (14)

Pоб=1- 0,3737= 0,6263.

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

=   ,                                                                        (15)

= .

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