Тестовые задания

1) Общее описание моделей. Требования, предъявляемые к моделям.

2) Виды подобия между моделью и фрагментами окружающего мира.

3) Какими принципами руководствуются при построении моделей?

4) Этапы построения математических моделей, их содержание.

5) Моделирование как метод познания. Цели моделирования.

6) Принцип моделируемости и его постулаты

7) Методы моделирования информационных систем.

8) Содержание индукционного моделирования, его назначение.

9) Содержание редукционного моделирования, его назначение

10) Специальные методы моделирования, используемые в прикладной информатике.

Литература

1) Советов Б.Я., Яковлев С.А. Моделирование систем: Учеб. для вузов – 3-е изд. перераб. и доп. – М.: Высш. шк. 2001, -343 с. ISBN 5-06-003860-2

2) Коротков Э.М. Исследование систем управления - М.: 000 Издательско-Консалтинговое Предприятие «ДеКА», 2004. - 336 с. ISBN 5-89645-035-4.

3) Теория систем и системный анализ в управлении организациями: Справочник: Учеб. пособие/Под ред. В.Н. Волковой и А.А. Емельянова. - М.: Финансы и статистика, 2006. - 848 с:. ISBN 5-279-02933-5.

Лекция 16. Моделирование систем и сетей массового обслуживания

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

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

 в ВС поступает слишком мало заявок и теперь уже приходится учитывать потери, вызванные простоем ЭВМ ВС.

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

Так вот, специальный раздел теории систем — теория массового обслуживания, позволяет:

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

 найти оптимальное соотношение между издержками по причине ожидания в очереди и издержками простоя ЭВМ в ВС;

 установить оптимальные стратегии обслуживания.

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

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

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

где р_cj — значение величины рс в j-м испытании.

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

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

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

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

Рисунок 1 - Обобщённая схема системы массового обслуживания

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

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

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

В зависимости от числа мест в очереди различают СМО с отказами и без отказов. В СМО с отказами число мест в очереди конечно.

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

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

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

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

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

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

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

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

, ,

где λ_об – интенсивность потока обслуженных заявок типа i; λ_ni – интенсивность потока потерянных заявок типа i. Очевидно, что λ_об + λ_ni = λ.

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

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

.

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

Вероятность потери p_п – это вероятность того, что произвольно выбранная из входящего потока с интенсивностью λ заявка окажется в потоке потерянных заявок с интенсивностью λ_п:

.

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

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

.

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

Пусть заявка обесценивается пропорционально её задержке в СМО, то есть время пребывания заявки в СМО (иногда учитывают лишь время ожидания в очереди). Тогда эффективность E СМО равна:

,

где e_ci – штраф за единицу времени пребывания заявки i-го типа в СМО; – среднее время пребывания в СМО заявок.

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

,

где e_откi – штраф за отказ СМО принять заявку i-го типа; e_вi – штраф за выталкивание из очереди заявки; e_уi – штраф за уход из СМО нетерпеливой заявки; p_откi, p_вi, p_уi – вероятности соответственно отказа, выталкивания и ухода заявки i-го типа; λ_i – интенсивность входящего потока заявок i-го типа.

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