 |
Система массового обслуживания как модель и оригинал
|
|
|
|
Система массового обслуживания (СМО) – одна из основных моделей, используемой инженерами – системотехниками, Заявки (требования) на обслуживание поступают через постоянные или случайные интервалы времени. Приборы (каналы) служат для обслуживания этих заявок. Обслуживание длится некоторое время, постоянное или случайное. Если в момент поступления заявки все приборы заняты, заявка помещается в ячейку буфера и ждет там начала обслуживания. Заявки, находящиеся в буфере, составляют очередь на обслуживание. Если все ячейки буфера заняты, заявка получает отказ в обслуживании и теряется. Вероятность потери заявки (вероятность отказа) - одна из основных характеристик СМО. Другие характеристики: среднее время ожидания начала обслуживания, средняя длина очереди, коэффициент загрузки прибора (доля времени, в течение которого прибор занят обслуживанием) и т.д.
В терминах СМО описываются любые реальные системы, где возможны очереди и (или) отказы в обслуживании.
В вычислительной системе роль обслуживающего прибора играет ЭВМ, роль заявок - решаемые задачи. Источником заявок служат терминалы пользователей. Моментом выдачи заявки является момент нажатия клавиши для подачи директивы о запуске подачи на решение. Операционная системы ЭВМ исполняет роль диспетчера: определяет очередность решения задач. В роли ячеек буфера выступают ячейки памяти ЭВМ, хранящие сведения о задачах, требующих решения.
СМО как модель рассматривается в теории массового обслуживания. При этом оригиналом являются реальные системы: вычислительные, производственные, транспортные и т.д. Целью использования СМО как модели является анализ качества функционирования указанных систем-оригиналов. В относительно простых случаях анализ можно провести аналитическими методами (т.е. по формулам) с помощью теории массового обслуживания. Но в более сложных случаях приходится прибегать к моделированию на ЭВМ, чтобы определить вероятность потери заявки, коэффициент загрузки прибора и другие характеристики СМО.
|
|
|
Имитационная модель СМО - это программа для ЭВМ, воспроизводящая шаг за шагом процесс поступления заявок, взятия их на обслуживание и завершения обслуживания, сопровождающегося освобождением прибора. Эти события имитируются в ЭВМ в том же порядке, в каком они происходят в реальности. Целью имитации процесса функционирования СМО является, как и при теоретическом анализе, определение вероятности потери заявки, коэффициента загрузки прибора и других характеристик. Но при имитационном моделировании СМО выступает в роли оригинала, а моделью является программа имитации или алгоритм, по которому эта программа составлена. Разработку такой программы и прогон ее на ЭВМ с целью нахождения характеристик СМО принято называть имитационным моделированием (в англоязычной литературе -simulation).
Недостатком имитационного моделирования по сравнению с аналитическими методами является численный характер результатов. Моделирование позволяет получить результат в виде числа при конкретных значениях исходных данных, тогда как аналитическое исследование дает общий результат в виде формулы.
Моделирование СМО и других систем, где необходим учет случайных факторов, производится методом статистического моделирования (методом Монте-Карло). Суть этого метода в том, что искомый результат получается путем осреднения большого числа частных результатов, полученных при различных значениях случайных факторов, формируемых в соответствии с их законами распределения. Из-за этого для моделирования требуются большие затраты машинного времени.
|
|
|
При сопоставлении моделирования с аналитическим исследованием надо учитывать также, что аналитическое исследование доступно лишь высококвалифицированному специалисту, владеющему математическими методами, тогда как имитационное моделирование, особенно если оно производится на основе специальных языков и трансляторов, не требует столь высокой квалификации. Разумеется, квалификация предоставляет большие дополнительные возможности, так как и моделирование, и аналитическое исследование дают наибольший эффект при совместном применении, а для совместного их применения требуются особые знания и опыт.
4.2.Иллюстративный пример: моделирование посадки самолетов.
Цель: определение необходимого количества посадочных полос.
Самолеты пребывают в зону и подают заявку на посадку в случайные моменты времени (рис. 4.1).
| t |
| - момент поступления заявки; |
| - момент окончания обслуживания |
| - моменты поступления заявок, получающих отказ. |
– интервал между соседними заявками;
– интервал обслуживания отдельной заявки.
Рис. 4.1. Имитация процесса посадки самолетов
– интервал между соседними заявками задается 
.
Если в момент подачи заявки полоса свободна – начинается процесс посадки, который длится фиксированное время 
. В течение этого времени полоса занята.
Если в момент поступления очередной заявки полоса занята – такая заявка получает отказ. Это нежелательное событие. Если часто отказ – необходима дополнительная полоса. Непосредственная цль моделирования – нахождение (оценивание) вероятности отказа Р.
Процесс смены состояний – дискретный. Время – непрерывное. Особые моменты – моменты поступления заявок и моменты освобождения полосы.
Имитация процесса на ЭВМ: воспроизведение шаг за шагом численных значений особых моментов и значений переменных в эти моменты.
В памяти ЭВМ достаточно отвести одну или несколько ячеек для каждой из характеристик имитируемого процесса и обновлять содержимое этих ячеек, имитируя изменение характеристик во времени.
Перечислим переменные, которые должны хранится и обновляться в памяти ЭВМ для данного примера:
|
|
|
t т – текущий особый момент;
t з – предстоящий момент поступления очередной заявки (ближайший из таких моменов после t т);
t осв – предстоящий момент освобождения полосы;
Z – состояние полося в особый момент (непосредственно перед t т);
n – количество заявок, поступивших к текущему моменту;
к – количество отказов, наблюдавшихся за то же время.
Счетчики n и к накапливают статистики (выборочные данные), по которым определяется оценка 
= 
.
Правило остановки процесса имитации: когда значение n достигнет значения 
(надо задать).
Исходные данные: , (F(x) – специальная подпрограмма). Помимо указанных переменных используются:
-– , , параметры F(x) – постоянные;
–– Вспомогательные переменные: , Е – (event – событие) содержит тип события: 1 – поступление заявки, 0 – освобождение полосы; Z L (Last – прошлое) – представляет предыдущее значение Z.
Как следует из приведенного примера, имитация, как процесс, заключается в организации продвижения системного времени и отображения в нем траектории функционирования оригинала. В данном примере – отображении процессов генерации заявок и их обслуживании. Функционирование отображается сменой состояний оригинала. Ибо смена состояний дает информацию, по которой можно вычислить интересующие исследователя (проектировщика) оценки характеристик оригинала.
Если система (оригинал) стохастическая, то пребывание системы в том или ином состоянии (вектор) и наступление состояний носят вероятностный характер.
Таким образом, имитационное моделирование включает два важнейших аспекта: построение моделирующего алгоритма и разыгрывание состояний системы. Моделирующий алгоритм обеспечивает продвижение системного времени и отображение состояний системы, а реализация случайных факторов и объектов, присущих системе, осуществляется методом статистических испытаний – методом Монте-Карло.
4.3. Концепция статистического моделирования
В основе статистического моделирования лежит процедура, применяемая для моделирования случайных величин и функций и носящая название метода статистических испытаний (метод Монте-Карло).
|
|
|
Общая схема метода Монте-Карло может быть записана в виде
(4.1)
Результат ищется как математическое ожидание некоторой случайной величины Y, которая чаще всего является неслучайной функцией случайной величины X, имеющей распределение р(х). Случайная величина Х имеет распределение р(х) и запись Х ~ р(х) означает, для непрерывной случайной величины, что для непрерывной случайной величины плотность вероятности равна р(х); для дискретной случайной величины функцию р(х) надо понимать как функцию вероятности. Для случайной дискретной величины интеграл (4.1) заменяется суммой Sу(х) р(х), в которой суммирование осуществляется по всем возможным значениям Х. Функция у(х) может иметь несколько аргументов, т.е. зависеть от нескольких случайных величин. В таком случае запись (4.1) остается в силе, только интеграл надо считать многомерным, Х рассматривать как вектор, а р(х) – как многомерную плотность (или функцию) вероятности. Приближенная оценка неизвестного математического ожидания, совпадающая с искомым результатом, находится как среднее арифметическое результатов независимых опытов. Это отражено в правой части (4.1). По закону больших чисел среднее арифметическое сходится к математическому ожиданию.
В каждом опыте разыгрывается реализация х случайной величины Х (в i- м опыте реализация 
) в соответствии с распределением р(х) и вычисляется значение функции в виде у (). Индекс i подчеркивает, что для каждой (i-й) реализации процесса аргументы, составляющие вектор Х, имеют свои случайные значения. Вычисленное очередное значение у () добавляется к накапливаемой сумме S у (). На этом заканчивается очередной опыт. После того как проведено М опытов, вычисляется итоговая оценка в виде правой части выражения (4.1). Опыты повторяются до тех пор, пока дисперсия оценки 
не снизится до требуемой величины, зависящей от допустимой погрешности и коэффициента доверия. Структурная схема эксперимента по имитационному моделированию представлена на рис. 4.2.
|
|
|
