Моделирование систем массового обслуживания (стр. 1 )

,Министерство образования и науки Российской Федерации

Иркутский государственный технический университет

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

систем массового обслуживания

Учебное пособие для студентов, обучающихся по специальностям:

«Информационные системы в машиностроении»

«Вычислительные системы, комплексы и сети»

Издательство

Иркутского государственного технического университета

2007

УДК 004.94

ББК 32.973.26-018.2

Рецензент: старший научный сотрудник ИСЭМ СО РАН, к. т.н.,

Хрусталев систем массового обслуживания:

учеб. пособие. – Иркутск: Изд-во ИрГТУ, 2с.

Редактор

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

Приведены задания на лабораторные работы по курсу «Моделирование» (пять работ) и базовые варианты заданий на курсовые работы. Каждому из базовых заданий могут соответствовать три – четыре варианта, различающихся законами распределения случайных величин и параметрами этих законов.

Для студентов специальностей «Информационные системы в машиностроении» и «Вычислительные машины, комплексы, системы и сети».

© , 2007

© Иркутский государственный

технический университет, 2007

ОГЛАВЛЕНИЕ

1. Системы массового обслуживания и их применение

при моделировании средств вычислительной техники … 4

2. Аналитические методы моделирования систем

массового обслуживания … 14

3. Имитационное моделирование систем массового

обслуживания. … 28

4. Система имитационного моделирования

GPSS World. … 32

5. Некоторые приемы программирования в системе GPSS,

используемые при выполнении курсовых и лабораторных

работ. … 79

Лабораторные работы по курсу «Моделирование» … 103

Задания по курсовым работам … 108

Тесты для самоподготовки … 112

Библиографический список … 117

1. Системы массового обслуживания и их применение при моделировании средств вычислительной техники

1.1 Моделирование в вычислительной технике

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

В вычислительной технике различают четыре уровня моделирования.

1. На системном уровне объектом моделирования являются вычислительные системы.

2. На алгоритмическом или архитектурном уровне рассматриваются архитектурные свойства системы. При этом объектом моделирования является вычислительный процесс.

3. На функциональном (микрооперационном) уровне или уровне регистровых передач объектами моделирования являются устройства ЭВМ.

4. На уровне логического моделирования рассматривается функционирование логических схем: больших и сверхбольших интегральных схем (БИС и СБИС), типовых элементов замены – ТЭЗов и т. д.

Основной задачей данного курса является изучение методов моделирования систем. Под системой S будем понимать целенаправленное множество взаимосвязанных элементов любой природы [1]. При моделировании систем применяется так называемый системный подход, в основе которого лежит последовательный переход от общего к частному, когда в основе рассмотрения лежит цель. Исследуемый объект при системном подходе выделяется из окружающей (внешней) среды. Под внешней средой Е понимается множество существующих вне системы элементов любой природы, оказывающих влияние на систему или находящихся под ее воздействием. Состав элементов, входящих в модель, зависит от цели моделирования. Совокупность связей между элементами системы определяет ее структуру.

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

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

1.2. Математические схемы моделирования систем

Математическая схема – средство формулирования понятий[1]. Математическую схему можно определить как звено при переходе от содержательного описания процесса функционирования системы к формальному. Формальная модель системы S – это множество величин, описывающих процесс функционирования системы:

- совокупность входных воздействий на систему ;

- воздействия внешней среды ;

- внутренние параметры системы ;

- выходные характеристики .

Различают следующие типовые математические схемы:

- дифференциальные уравнения;

- конечные и вероятностные автоматы;

- системы массового обслуживания;

- сети Петри;

- агрегативные модели.

Данным математическим схемам соответствуют следующие классы моделей.

1)  Непрерывно – детерминированные модели (D-схемы). Эти модели представляются дифференциальными уравнениями (обыкновенными или в частных производных).

2)  Дискретно – детерминированные модели (F-схемы). Представляются конечными автоматами.

3)  Дискретно – стохастические модели (P-схемы). Представляются вероятностными автоматами.

4)  Непрерывно – стохастические модели (Q-схемы). Системы с очередями (системы массового обслуживания).

5)  Сетевые модели (сети Петри или N-схемы).

6)  Комбинированные модели (агрегативные модели или А-схемы).

В настоящем пособии рассматриваются системы массового обслуживания,

поскольку функционирование многих средств вычислительной техники и вычислительных систем можно адекватно описать с помощью Q – схем.

1.3. Системы массового обслуживания

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

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

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

- задача анализа, т. е. определение количественных характеристик СМО при заданной структуре и заданных параметрах элементов структуры;

- задача синтеза оптимальной структуры СМО при заданных характеристиках и ограничениях на параметры элементы структуры.

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

Рассмотрим структурную схему СМО [2] (рис. 1.1)

Рис. 1.1. Структурная схема системы массового обслуживания

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

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

Параметры – это количественные оценки первичных свойств системы.

Характеристики – количественные оценки вторичных свойств системы, получаемые в процессе моделирования.

Параметры систем массового обслуживания

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

Простейший поток заявок обладает следующими свойствами: стационарности, ординарности и отсутствием последействия.

Поток называется стационарным, если его вероятностные характеристики не изменяются со временем.

Поток называется ординарным, если события в нем происходят по одиночке.

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

Основным параметром входящего потока заявок является его интенсивность.

Интенсивностью или плотностью потоканазывается среднее число событий в ед. времени. Для стационарного потока λ =const.

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

tср = 1/λ..

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

.

Привлекательность простейшего потока объясняется рядом обстоятельств:

1. Допущение о простейшем потоке заявок позволяет получать аналитические зависимости характеристик СМО от параметров входящего потока, что затруднительно для других видов потока заявок.

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

3. Если СМО обеспечивает желаемую эффективность функционирования системы при простейшем потоке заявок на входе, то обслуживание системой других случайных потоков заявок с одинаковой интенсивностью будет выполняться не хуже. Это обстоятельство связано со следующим свойством экспоненциального распределения: 63% заявок поступают чаще, чем среднее время между заявками, а 37% заявок поступают значительно реже среднего времени. Кроме того, коэффициент вариации, равный отношению среднего квадратичного отклонения к математическому ожиданию, для экспоненциального распределения равен 1 (для большинства других законов эта величина меньше единицы). Поэтому простейший поток заявок создает самый тяжелый режим работы для системы массового обслуживания.

Если простейший входящий поток представляет собой совокупность m потоков различных типов с интенсивностями (i=), то его можно характеризовать суммарной интенсивностью

.

Степень важности заявок может быть различной, по этому признаку заявки делят на классы. Каждому классу присваивается приоритет k (k=).

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

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

Параметры структуры СМО

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

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

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

Если в момент появления заявки на входе СМО хотя бы один канал свободен от обслуживания, ее обслуживание может быть начато немедленно, без задержки. Однако вполне вероятна ситуация, когда заявка застает СМО полностью загруженной, т. е. когда все m каналов обслуживания заняты. В этом случае начало обслуживания задерживается, заявка может занять место в соответствующей очереди. Таким образом, вторым важным компонентом структуры СМО является очередь, параметром которой является число мест в очереди n. В приоритетных системах общая очередь может быть разделена на несколько очередей по числу различаемых системой приоритетов, для каждой из которых должно быть указано число мест ni, (i=). На число мест в очереди может быть наложено ограничение. Это может быть сделано как для каждой очереди в отдельности, так и для всей совокупности очередей в целом. При этом возможны конфликтные ситуации, решением которых может быть отказ системы принять заявку.

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

Параметры закона управления процессами в СМО

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

Дисциплина ожидания определяет порядок приема заявок в систему и размещения их в очереди:

- Заявка принимается в общую очередь. При переполнении очереди заявка

получает отказ.

- Заявка принимается в общую очередь в порядке поступления. При

переполнении очереди вновь прибывающая заявка выталкивает из очереди

заявку дольше всех находящуюся в очереди.

- Заявка принимается на свободное место, оставшееся после назначения

заявок на обслуживание по случайному правилу. При отсутствии

свободного места заявка получает отказ.

Дисциплина обслуживания – определяет правило выборки заявок из очереди для назначения на обслуживание.

В зависимости от принятых в СМО дисциплин ожидания и обслуживания различают СМО с бесприоритетными и приоритетными дисциплинами.

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

- выбирается первая в очереди заявка-дисциплина «первым пришел – первым вышел» (FIFO - First Input First Output);

выбирается последняя в очереди заявка-дисциплина «последним пришел - первым вышел» (LIFO - Last Input First Output);

- заявка выбирается из очереди случайным образом.

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

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

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

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

Совокупность обслуженных и потерянных заявок образует выходящий поток СМО.

В зависимости от структуры выходящего потока различают СМО без потерь («чистые» СМО) и СМО с потерями («смешанные» СМО).

Для «чистых СМО характерно отсутствие ограничений на число мест в очереди (бесконечная очередь) и на время пребывания заявки в системе («терпеливые» заявки). По этой причине выходящий поток будет состоять лишь из обслуженных заявок.

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

Если входящий поток содержит заявки m типов с интенсивностями потока заявок типа i(i=), выходящий поток можно характеризовать суммарной интенсивностью потока обслуженных заявок

,

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

,

где - интенсивность потока потерянных заявок типа i. Очевидно, что

+=.

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

Проиллюстрируем обобщенную структуру СМО примером однопроцессорной цифровой управляющей системы (ЦУС), входящей в состав автоматизированной системы управления технологическим процессом (АСУ ТП) [2]. Помимо аппаратных средств (процессор, память, устройство прерывания, периферийные устройства) в состав ЦУС входят программные средства, содержащие прикладные и системные управляющие программы. Прикладные управляющие программы реализуют алгоритмы управления технологическим процессом, их исполнение процессором рассматривается как обслуживание заявок, поступающих в ЦУС от технологического процесса. Системные управляющие программы осуществляют управление прохождением заявок через ЦУС (диспетчирование) и исполняются тем же процессором. Обычно выделяют две основные системные управляющие программы: ДИСПЕТЧЕР1 (D1) и ДИСПЕТЧЕР2 (D2), реализующие, соответственно, дисциплины ожидания и обслуживания.

Заявки С1, С2, ..., СМ в виде сигналов прерывания от датчиков состояния технологического процесса поступают в устройство прерывания, входящее в состав процессора. Появление сигнала прерывания (заявки) С инициирует в процессоре операцию прерывания, в результате выполнения которой процессор переключается на выполнение программы D1. D1, распознает приоритет поступившей заявки и ставит ее в соответствующую очередь, реализованную в специально зарезервированной области памяти, причем для хранения информации об одной заявке может потребоваться несколько ячеек памяти. D2 анализирует состояние очередей O1, O2, ..., ON, выбирает заявку Сk, имеющую преимущественное право на обслуживание, и инициирует соответствующую прикладную программу. Инициирование программы D2 происходит в моменты окончания исполнения прикладных программ и программы D1.

Характеристики и показатели эффективности СМО

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

1) Характеристика выходящего потока заявок , т. е. интенсивность входящего потока

=.

2) Вероятность обслуживания характеризует вероятность того, что произвольно выбранная из входящего потока с интенсивностью заявка будет обслужена, т. е. окажется в потоке обслуженных заявок с интенсивностью

=/.

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

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

,

,

.

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

Среднее время ожидания tож в общем случае является суммой двух

составляющих:

=,

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

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

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

=+.

6) Средняя длина очереди представляет собой математическое ожидание числа заявок, находящихся в очереди, т. е. длины очереди .

.

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

,

где m - общее число каналов.