Размещено на http://www.allbest.ru/

Курсовой проект

по курсу «Системный анализ и проектирование систем обработки информации»

Тема: Построение имитационных моделей сложных систем

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

Постановка задачи

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

2. Написать программу, реализующую имитационную дискретно - событийную модель в зависимости от варианта. Вычислить критерии работы системы в соответствии со своей задачей.

3. Программа должна быть написана на языке высокого уровня с применением объектов (С++ или Pascal).

Содержание отчета

1. Постановка задачи (для своего варианта).

2. Краткое теоретическое введение.

3. Функциональная модель системы.

4. Концептуальная модель системы: описание всех допущений, входов, выхода, переменных состояния.

5. Описание связи между элементами системы и ее модели.

6. Алгоритмы реализации модели (в виде блок-схем или псевдокода).

7. Описание программной реализации модели.

8. Листинги программных модулей.

9. Результаты экспериментальных прогонов программной модели.

10. Выводы.

Варианты

Задача 1. Компьютерная система с режимом разделения времени

Постановка задачи

Компания использует компьютерную систему, состоящую из центрального процессора (ЦП) и п терминалов (рис. 1). Оператор каждого терминала затрачивает на «обдумывание» некоторый промежуток времени, который представлен экспоненциально распределенной случайной величиной со средним значением 25 с, затем он направляет ЦП задание, время обслуживания которого распределено экспоненциально со средним значением 0,8 с. Поступающие задания формируют единственную очередь к ЦП с циклической дисциплиной обслуживания, а не с дисциплиной обслуживания FIFO. Это означает, что ЦП выделяет для каждого задания максимальный квант времени обслуживания продолжительностью q = 0,1 с. Если оставшееся время обслуживания задания 5 не превышает q, ЦП тратит время 5 плюс неизменное время подкачки1 (время свопинга) т = 0,015 с, чтобы обработать задание, которое затем возвращается на свой терминал. Однако, если s > q, ЦП затрачивает (q + т) с на обработку задания, которое затем возвращается в конец очереди, а оставшееся время его обслуживания уменьшается на q. Процесс повторяется до тех пор, пока обслуживание задания не будет завершено. После этого задание возвращается на свой терминал, оператор которого начинает очередной период «обдумывания».

Пусть Кi будет временем ответа i-го задания, закончившего обслуживание, которое определяется как время, прошедшее между моментом, когда задание покидает терминал, и моментом, когда ЦП завершает его обработку. Cмоделируем компьютерную систему для выполнения 1000 заданий (то есть с 1000 значений времени ответов) для каждого из случаев, когда п = 10, 20,..., 80, и оценим ожидаемое среднее время ответов для этих заданий, ожидаемое среднее по времени число заданий в очереди, а также ожидаемый средний коэффициент загрузки ЦП. Допустим, что в момент времени 0 все операторы за терминалами обдумывают задания. Компании необходимо установить такое число терминалов, чтобы среднее время ответов на запросы пользователей не превышало 30 с.



Завершенные задания

Рис. 1 Схема компьютерной системы с режимом разделения времени

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

Событие	Тип события
Поступление задания в ЦП от терминала по завершении времени обдумывания	1
Завершение обслуживания задания ЦП, когда выполнение задания либо завершено, либо на него был затрачен квант времени обслуживания q	2
Завершение моделирования	3

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

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

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

Рис. 2. Представление событий с помощью графов для модели компьютерной системы

В модели будут использованы три списка записей: один - для заданий в очереди, другой -- для задания, обрабатываемого ЦП, и еще один -- это список событий.

Рис. 3 Блок-схема событийной функции для поступления задания в ЦП по завершении времени обдумывания для модели компьютерной системы

Рис. 4 Блок-схема несобытийной функции , начинающей выполнение задания ЦП для модели компьютерной системы



Рис. 5 Блок-схема функции для завершения обслуживания задания ЦП для модели компьютерной системы

Выходные данные моделирования и их исследование

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

Отчет с выходными данными (модель компьютерной системы)

Модель компьютерной системы с режимом разделения времени

Число терминалов	10 - 80 по 10
Среднее время обдумывания	25.000 с
Среднее время обслуживания	0.800 с
Время кванта	0.100 с
Время подкачки	0.015 с
Число обработанных заданий	1000

Число	Среднее	Среднее число	Коэффициент использования терминалов время ответа заданий в очереди ЦП
10	1.324	0.156	0.		358
20	2.165	0.929		0.658
30	5.505	4.453		0.914
40	12.698	12.904	0.998
50	24.593	23.871	0.998
60	31.712	32.958	1.000
70	42.310	42.666	0.999
80	47.547	51.158	1.000

Задача 2. Банк с несколькими кассами

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

Постановка задачи

Банк с пятью кассами открывается в 9.00 и закрывается в 17.00, однако кассы продолжают работу до тех пор, пока все клиенты, находившиеся в банке в 17.00, не будут обслужены. Допустим, что интервалы времени между прибытием клиентов представлены экспоненциально распределенными величинами со средним значением 1 мин, а время обслуживания клиентов -- экспоненциально распределенными величинами со средним значением 4,5 мин.

К каждой кассе формируется отдельная очередь. Прибывший клиент присоединяется к наиболее короткой очереди, выбирая крайнюю левую из одинаковых по длине очередей. Пусть пi обозначает общее число клиентов (считая тех, которые в данный момент обслуживаются кассой) в очереди перед кассой i в определенный момент времени. Если по завершении обслуживания клиента кассой i для некой кассы j, пj > пi + 1, тогда клиент, находившийся в конце очереди j, переходит в конец очереди i. (В том случае, если таких клиентов два или больше, то переходит тот, кто находится в крайней левой очереди.) Если касса i свободна, она начинает обслуживание этого клиента (рис. 6).

Рис. 6. Переход клиента из конца очереди j =2 к освободившейся кассе i = 3

Руководство банка интересуют текущие расходы и качество услуг, предоставляемых клиентам, поэтому оно обдумывает возможность изменения числа касс. Требуется cмоделировать банк и оценить ожидаемое среднее по времени совокупное число клиентов в очередях, ожидаемую среднюю задержку в очереди и ожидаемую максимальную задержку в очереди для числа касс п = 4, 5, 6 и 7. Во всех случаях допускаем, что при открытии банка клиентов в нем нет.

В модели банка используются следующие события.

Событие	Тип события
Прибытие клиента в банк	1
Уход клиента из балка по завершении обслуживания	2
Закрытие банка в 17.00	3

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

Рис. 7 Графы событий для модели банка

Модель банка требует 2п + 1 списков записей, где п -- число касс при отдельном прогоне имитационной модели. Списки с 1-го по n-й содержат записи для клиентов, ожидающих обслуживания в соответствующей очереди. Списки с (п + 1)-го по 2n-й используются для определения занятости касс. Если список п + i (в котором i - 1, 2,..., п) содержит одну запись, то касса i занята. Если в нем нет записей, касса i свободна. Как обычно, список 25 предназначен для списка событий. В списках используются следующие атрибуты.

Список	Атрибут 1	Атрибут 2	Атрибут 3
С 1-го по п-й, очереди	Время прибытия в очередь
С (п + 1)-го по 2я-й, кассы
25, список событий	Время возникновения	Тип события	Номер кассы, если тип события -- 2

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

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

Кроме того, надо определить среднее по времени общее число клиентов в очереди. Пусть Q(t) обозначает число клиентов в очереди на момент времени t для г = - 1, 2, ..., п, тогда

будет общим числом клиентов во всех очередях на момент времени t Следовательно, необходимо вычислить

где Т-- время завершения моделирования (оно определяется в соответствии с описанным выше правилом останова). Однако, если мы подставим уравнение в предыдущее уравнение и воспользуемся линейными интегралами, получим следующее уравнение:

Где

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

Рис. 8. Блок-схема функции прибытия клиента в банк.

Рис. 9.Блок-схема функции ухода клиента из банка.

Рис. 2.15. Блок-схема функции перехода клиента в конец одной очереди из конца другой очереди.

Выходные данные моделирования и их исследование

В листинге показаны примерные выходные данные моделирования. Сравнивая возможные варианты с текущей стратегией банка, когда используется пять касс, можно убедиться, что уменьшение числа касс до четырех приведет к ухудшению качества обслуживания клиентов (об этом свидетельствуют задержки в очереди и длина очередей). Увеличение числа касс способствует существенному улучшению обслуживания клиентов и уменьшению средней длины очередей. Является ли такой шаг экономически обоснованным, зависит от того, как руководство соотносит улучшение обслуживания клиентов с затратами на дополнительную кассу. Вряд ли оправдано добавление седьмой кассы, поскольку улучшение обслуживания в этом случае не кажется существенным по сравнению с системой из шести касс. Заметьте, что известно, сколько клиентов обслуживалось в течение дня в каждом варианте системы -- оно соответствует числу зарегистрированных задержек. Это число не очень отличается в различных вариантах системы, поскольку скорость прибытия остается той же, а помещение банка не ограничено.

Листинг 2.21. Отчет с выходными данными (модель банка)

Банк с несколькими кассами и переходом клиентов из одной очереди е другую

Число касс 4-7

Среднее время между прибытиями 1.000 мин

Среднее время обслуживания 4.500 мин Закрытие банка после 8.000 ч

С четырьмя кассами среднее число клиентов в очереди равно 51.319 Задержки в очереди, мин:

Номер

переменной Среднее Число sampst значение значений Максимум Минимум

1 63.2229 501.000 156.363 0.000000

С пятью кассами среднее число клиентов в очереди равно 2.441 Задержки в очереди, мин:

Номер переменной Среднее Число

sampst значение значений Максимум Минимум

1 2.48149 483.000 21.8873 0.000000

С шестью кассами среднее число клиентов в очереди равно 0.718 Задержки в очереди, мин:

Номер

переменной Среднее Число sampst значение значений Максимум Минимум

1 0.763755 467.000 16.5103 0.000000

С семью кассами среднее число клиентов в очереди равно 0.179 Задержки в очереди, мин:

Номер

переменной среднее Число sampst значение значений Максимум Минимум

1 0.176180 493.000 б.97122 0.000000

Задача 3. Производственная система

Постановка задачи

Производственная система состоит из пяти автоматизированных рабочих мест. В настоящий момент места 1, 2,..., 5 включают соответственно 3, 2, 4, 3 и 1 одинаковых станков (рис. 2.16). В сущности система представляет собой сеть из пяти многоканальных систем массового обслуживания. Предположим, что работы поступают в систему с интервалами, представленными независимыми и одинаково экспоненциально распределенными случайными величинами со средним значением 0.25 ч. Существует три типа работ: поступающие работы имеют типы 1, 2 и 3 с соответствующими вероятностями 0,3; 0,5 и 0,2. Для работ типа 1,2 и 3 требуется выполнение четырех, трех и пяти заданий соответственно. Задания должны выполняться на указанных местах в определенном порядке. В различных типах работ используются следующие технологические маршруты.

Тип работы	Рабочие места в соответствии с технологическим маршрутом
1	3, 1,2,5
2	4, 1, 3
3	2, 5, 1, 4, 3

Рис. 2.16. Схема производственной системы с пятью рабочими местами, показывающая маршрут работ типа 1

Так, в работе типа 2 первое задание выполняется на рабочем месте 4, второе -на рабочем месте 1 и последнее -- на рабочем месте 3.

Если работа поступает на определенное рабочее место, а все станки на нем уже заняты, она добавляется в единственную очередь с дисциплиной обслуживания FIFO на этом рабочем месте. Время выполнения задания на определенном станке является независимой случайной величиной с распределением Эрланга 2-го порядка, среднее значение которой зависит от типа работы и от рабочего места, где находится станок. (Если X -- независимая случайная величина с распределением Эрланга 2-го порядка со средним значением г, тогда X = Y1 + Y2 где Y1 и Y2- независимые экспоненциально распределенные величины со средним значением r/2. В качестве альтернативного варианта X может быть случайной величиной, имеющей гамма-распределение с параметром формы 2 и масштабным параметром r/2. Подробнее об этом рассказано в разделе 6.2.2.) Распределение Эрланга 2-го порядка выбрано, чтобы представить время обслуживания, потому, что как показывает опыт, если собирается информация о времени выполнения какого-либо задания, гистограмма этих данных часто имеет такую форму, как у функции плотности вероятностей для распределения Эрланга. Среднее время обслуживания для каждого типа работ и каждого задания приведено в таблице.

Тип работы	Среднее время обслуживания для последовательных заданий, ч
1.	0,50; 0,60; 0,85; 0,50
2.	1,10; 0,80; 0,75
3.	1,20; 0,25; 0,70; 0,90; 1,00

Таким образом, для работы типа 2 требуется среднее время обслуживания 1,10 ч на рабочем месте 4 (там выполняется первое задание для этой работы).

Создадим модель работы системы в течение 365 рабочих дней (при 8-часовом рабочем дне и отсутствии перерывов) и оценим ожидаемую среднюю совокупную задержку в очереди (не включающую времени обслуживания) для каждого типа работ и ожидаемую полную среднюю совокупную задержку для всех типов работ. При вычислении последнего значения используем соответствующие типы работ с вероятностями 0,3; 0,5 и 0,2 как удельный вес. Кроме того, оценим: ожидаемое среднее число работ в очереди, ожидаемый коэффициент использования, ожидаемую среднюю задержку в очереди для каждого рабочего места.

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

События в модели цеха довольно просты.

Представим их следующим образом.

Описание события	Тип события
Поступление работы в систему	1
Уход работы с определенного рабочего места	2
Завершение моделирования	3

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

Рис. 10. Представление событий с помощью графов для модели цеха



Рис. 11. Блок-схема функции, обслуживающей событие поступления новой работы в систему и поступление работы на очередное рабочее место маршрута для модели цеха.

Выходные данные моделирования и их исследование

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

Листинг . Отчет с выходными данными (модель цеха) Модель цеха

Число рабочих мест	5
Число станков на каждом рабочем месте	3 2 4 3 1
Число типов работ	3
Число заданий для каждого типа работ	4 3 5
Функция распределения типов работ	0.300 0.800 1.000
Среднее значение интервала времен/ между	поступлением работ 0.25 ч
Длительность моделируемого периода	365.0 восьмичасовых дней

Тип работы	Рабочие места на маршруте
1	3 12 5
2	4 13
3	2 5 14 3

Тип работы	Среднее время обслуживания, ч, для последовательных заданий
1	0.50 0.60	0.85 0.50
2	1.10 0.80	0.75
3	1.20 0.25 0.70 0.90 1.00

Тип работы	Средняя общая задержка а очереди
1	10.022
2	9.403
3	15.808

Полная средняя общая задержка работ - 10.870

Рабочее	Среднее число	Средний коэффициент	Средняя задержка
место	работ в очереди	загрузки	в очереди
1	12.310	0.969	3.055
2	11.404	0.978	5.677
3	0.711	0.719	0.177
4	17.098	0.961	6.110
5	2.095	0.797	1.043

Статистические данные по рабочим местам показывают затруднения на рабочих местах 1, 2 и 4, хотя степень серьезности проблемы зависит от того, какие именно показатели рассматриваются: среднее число работ в очереди, коэффициент загрузки рабочего места или средняя задержка в очереди. Мы выполнили три дополнительных прогона имитационной модели, добавив станок на каждое из этих рабочих мест (как показало моделирование, рабочие места 3 и 5 практически не испытывают перегрузки, поэтому их работа с новым станком не рассматривалась), чтобы определить, какой тип станка окажет наибольшее влияние на эффективность работы системы. Для полной средней общей задержки работ в качестве единственного показателя производительности в результате трех дополнительных прогонов модели получены данные, приведенные в табл. 2.1. Исходя из этих результатов, станок следует добавить на рабочее место 4, чтобы обеспечить наибольшее уменьшение полной средней общей задержки работ. Как обычно, такой вывод считается ориентировочным, поскольку выполнено всего по одному прогону каждого варианта модели. Сказанное прежде всего относится к данному случаю, так как результаты прогонов трех новых вариантов модели слишком близки.

Таблица 2.1. Оценка ожидаемых полных средних общих задержек работ для текущей и предложенных конфигураций системы

	Полная средняя общая
Число станков на рабочих местах	задержка работ, ч
2, 4, 3, 1 (текущая конфигурация)	10,9
2, 4, 3, 1 (станок добавлен на рабочее место 1)	8,1
3, 3, 4, 3, 1 (станок добавлен на рабочее место 2)	7,6
3, 2, 4, 4, 1 (станок добавлен на рабочее место 4)	7,5

Вариант 1. Возьмем модель компьютерной системы из задачи 1. Предположим, что при обработке заданий в очереди вместо циклической дисциплины обслуживания ЦП выбирает из очереди задания, которые совершили наименьшее количество проходов ЦП. В этом случае, если возникают связи, используется правило FIFO (что эквивалентно применению для разрешения связей времени поступления задания в очередь). Выполните прогон имитационной модели для п = 60 терминалов, пока не будет выполнено1000 заданий.

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

Место в очереди по истечении времени 1	2	3	> 4
Вероятность бегства	0,00	0,25	0,50	1,00

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

Вариант 3. Возьмем модель компьютерной системы из задачи 1. Задания поступают в компьютерное устройство с одним ЦП с интервалами времени, представленными независимыми одинаково экспоненциально распределенными случайными величинами со средним значением 1 мин. Для каждого задания определяется максимальный период времени, необходимый для его обработки; максимальное время для последовательных задании представлено независимыми одинаково экспоненциально распределенными случайными величинами со средним значением 1,1 мин. Однако, если m -- это установленное максимальное время обработки для определенного задания, то действительное время обработки будет равномерно распределено между 0,55 т и 1,05 т. При этом ЦП никогда не обрабатывает задание дольше установленного максимального времени; задание, для которого необходимое время обслуживания превышает указанный максимум, покидает устройство, не завершив обслуживание.

Выполните моделирование компьютерного устройства до момента, пока 1000 заданий не покинут ЦП и задания в очереди обрабатываются в порядке FIFO. Вычислите среднюю и максимальную задержки заданий в очереди, часть заданий, которые испытывают задержку, превышающую 5 мин, и максимальное число заданий в очереди. Используйте поток 1 для времени между поступлениями, поток 2 -- для максимального времени обработки и поток 3 -- для фактического времени обработки.

Вариант 4. Возьмем за основу модель компьютерной системы из задачи 1. Модель следующей системы выполнять по аналогии с задачей 1.

Суда прибывают в гавань, и время между прибытиями, представленное независимыми одинаково экспоненциально распределенными случайными величинами со средним значением, равно 1,25 дня. В гавани имеется док с двумя якорными стоянками и двумя кранами для разгрузки судов. Корабли, прибывшие тогда, когда обе якорные стоянки заняты, становятся в очередь с дисциплиной обслуживания FIFO. Время, необходимое одному крану для разгрузки судна, равномерно распределено между 0,5 и 1,5 дня. Если в гавани всего одно судно, разгрузкой занимаются оба крана, и время разгрузки (оставшееся) уменьшается вдвое. Если в гавани два судна, то каждый из двух кранов работает с каждым судном. Если оба крана разгружают одно судно, то, по прибытии второго судна, один из кранов немедленно начинает его обслуживание, а оставшееся время обслуживания первого судна увеличивается вдвое. Допустив, что в гавани на момент времени 0 нет судов, выполните моделирование работы системы в течение 90 дней и вычислите минимальное, максимальное и среднее время нахождения судов в гавани (включая их время пребывания на якорной стоянке). Оцените также ожидаемый коэффициент загрузки каждой якорной стоянки и кранов. Используйте поток 1 для времени между прибытиями и поток 2 -- для времени разгрузки.

Вариант 5. Возьмем модель компьютерной системы из задачи 1. Задания поступают в компьютерное устройство с одним ЦП с интервалами времени, представленными независимыми одинаково экспоненциально распределенными случайными величинами со средним значением 1 мин. Для каждого задания определяется максимальный период времени, необходимый для его обработки; максимальное время для последовательных задании представлено независимыми одинаково экспоненциально распределенными случайными величинами со средним значением 1,1 мин. Однако, если m -- это установленное максимальное время обработки для определенного задания, то действительное время обработки будет равномерно распределено между 0,55 т и 1,05 т. При этом ЦП никогда не обрабатывает задание дольше установленного максимального времени; задание, для которого необходимое время обслуживания превышает указанный максимум, покидает устройство, не завершив обслуживание.

Выполните моделирование компьютерного устройства до момента, пока 1000 заданий не покинут ЦП и задания в очереди выстраиваются в порядке возрастания установленного для них максимального времени обработки. Вычислите среднюю и максимальную задержки заданий в очереди, часть заданий, которые испытывают задержку, превышающую 2 мин. Используйте поток 1 для времени между поступлениями, поток 2 -- для максимального времени обработки и поток 3 -- для фактического времени обработки.

Вариант 6. За основу возьмите модель компьютерной системы задачу 1.

В карьере грузовики доставляют руду от трех экскаваторов к одной дробилке. Грузовики приписаны к определенным экскаваторам, так что конкретный грузовик всегда возвращается к своему экскаватору, выгрузив руду у дробилки. Используются грузовик двух видов: грузоподъемностью 20 и 50 т. Грузоподъемность влияет на время погрузки машин экскаватором, время переезда к дробилке, время разгрузки и время возвращения к экскаватору (все эти данные указаны в нижеприведенной таблице).

Процесс	20-тонный грузовик	50-тонный грузовик
Погрузка	Экспоненциально	Экспоненциально
распределенные величины	распределенные величины
со средним значением	5 мин со средним значением	10 мин
Переезд	Постоянная величина 2,5 мин	Постоянная величина 3 мин
Разгрузка	Экспоненциально	Экспоненциально
распределенные величины	распределенные величины
со средним значением	2 мин со средним значением	4 мин
Возвращение	Постоянная величина 1,5 мин	Постоянная величина 2 мин

К каждому экскаватору приписаны два грузовика: 20-тонный и 50-тонный. Все очереди к экскаваторам имеют дисциплину обслуживания FIFO, а очередь к дробилке выстраивается в порядке убывания грузоподъемности машин; в случае возникновения связей используется правило FIFO. Допустим, в момент времени 0 все грузовики находятся у своих экскаваторов и только что началась погрузка 50-тонного грузовика. Выполните моделирование работы системы в течение 8 ч и оцените ожидаемое среднее по времени число грузовиков в очереди у каждого экскаватора и у дробилки. Оцените также ожидаемые коэффициенты загрузки всех четырех устройств.

Вариант 7. За основу взять модель компьютерной системы (задача 1).

Вычислительный центр с одним ЦП, выполняющий пакетную обработку заданий, открывается в 7.00 и закрывается в полночь, но продолжает свою работу до тех пор, пока все задания, имеющиеся в нем на 0.00 часов, не будут выполнены. Предположим, что время между поступлениями заданий в центр, представлено экспоненциально распределенными величинами со средним значением 1,91 мин. Задания требуют срочного обслуживания (класс 4), обычного (класс 3), с возможной отсрочкой (класс 2) и по мере возможности (класс 1); эти классы возникают с вероятностями 0,05; 0,50; 0,30 и 0,15 соответственно. Когда ЦП освободится, он будет обрабатывать задание высшего (приоритетного) класса; для заданий одного класса действует дисциплина обслуживания FIFO. Время, необходимое ЦП для обработки заданий класса 4, 3, 2 и 1, представлено случайными величинами с распределением Эрланга 3-го порядка (см. раздел 2.7) с соответствующими средними значениями 0,25; 1,00; 1,50 и 3,00 мин. Создайте модель вычислительного центра если:

А. Обработка задания ЦП не прерывается при поступлении задания более высокого класса.

Оцените для каждого класса ожидаемое среднее по времени число заданий в очереди и ожидаемые средние задержки в очереди. Оцените также ожидаемые доли времени, когда ЦП пребывает в состоянии занятости и когда ЦП занят обработкой каждого класса задания. Заметьте, удобнее использовать отдельный список для очереди заданий каждого класса, а также входной параметр, который устанавливается в 0 для случая А. Используйте поток 1 для времени между поступлениями, поток 2 -- для определения класса заданий и потоки 3, 4, 5 и 6 -- для времени обработки заданий классов соответственно 4, 3, 2, и 1.

Вариант 8. За основу взять модель компьютерной системы (задача 1).

В химчистке выполняется обработка костюмов-двоек. Костюмы поступают в среднем с интервалом 10 мин. Все они сначала проходят обработку у оператора 1, возможно, подождав в очереди с дисциплиной обслуживания FIFO. По завершении обслуживания оператором 1 одна часть костюма (пиджак) поступает к оператору 2, а другая часть костюма (брюки) -- к оператору 3. В ходе обработки пиджака оператором 2 вероятность его повреждения равна 0,05, а вероятность повреждения брюк оператором 3 -- 0,10. Покинув оператора 2, пиджаки поступают в одну очередь к оператору 4; а брюки от оператора 3 -- в другую очередь к оператору 4. Оператор 4 собирает части костюма воедино. Процесс сборки начинается, когда оператор свободен и для него доступны обе части одного костюма. Если обе части собранного костюма не повреждены, костюм возвращается клиенту. Если одна из частей (или обе) повреждена, костюм поступает в отдел работы с клиентами (оператор 5). Допустим, что все интервалы времени являются экспоненциально распределенными с приведенными в таблице средними значениями и для них выделены указанные потоки.

Среднее время	Номер оператора обслуживания, мин	Поток
6	1	1
4	2	2
5	3	3
5 (неповрежденный костюм)	4	4
4	8 (поврежденный костюм)	5
5	12	6

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

Рис. Схема обработки костюмов в химчистке

Вариант 9. В африканском порту танкеры загружаются сырой нефтью. Оборудование в порту позволяет загружать одновременно до трех танкеров. Танкеры, прибывающие в порт каждые (11 ± 7) ч, могут быть трех различных типов. (Все значения времени, приведенные в этой задаче как интервал «±», равномерно распределены в указанном интервале. - RANDOM) Относительная частота появления танкеров различных типов и требования, относящиеся ко времени их погрузки приведены в таблице.

Тип	Относительная	Время
	частота	погрузки, ч
1	0,25	18 ±2
2	0,25	24 ± 4
3	0,50	36 ± 4

В порту имеется один буксир. Ни один тип танкеров не может обойтись без буксира, который отводит танкеры из гавани к причалу, а позднее уводит от причала в гавань. Когда буксир свободен, ему требуется около 1 ч, чтобы отвести танкер к причалу или вывести его в гавань. Если буксир не тянет танкер, ему требуется 0,25 % чтобы преодолеть расстояние от причала до гавани (или наоборот). Когда буксир завершит буксировку к причалу, он приступает к буксировке первого танкера из очереди у причала, если таковая имеется. Если в очереди у причала нет танкеров, буксир отправляется в гавань и приступает к буксировке первого танкера из очереди в гавань. (Если в обеих очередях нет танкеров, свободный буксир остается у причала.) Выполнив буксировку от причала в гавань, буксир берет первый танкер из очереди в гавани, если в ней есть танкеры, а у причала есть свободное место. В противном случае буксир отправится к причалу, и если в очереди у причала есть танкеры, начнет буксировку первого танкера из этой очереди. Если очереди у причала нет, свободный буксир остается у причала.

Ситуация может усложниться из-за того, что в этой зоне часто бывают штормы продолжительностью (4 ± 2) ч. Интервал времени между завершением одного шторма и началом другого представлен экспоненциально распределенной величиной со средним значением 48 ч. Буксир не начнет новую операцию, пока бушует шторм, но всегда завершит уже начатую. (Загрузка танкеров у причала продолжается и во время шторма.) Если на момент начала шторма буксир идет от причала в гавань без танкера, он развернется и возвратится к причалу.

Выполните моделирование этой системы для периода времени, равного 1 году (8760 ч) и оцените ожидаемые:

а) доли времени, когда буксир свободен, перемещается без танкера и выполняет буксировку к причалу или в гавань;

б) доли времени, когда каждое из мест у причала свободно, занято, но загрузка не выполняется, и занято с выполнением загрузки;

в) среднее по времени число танкеров в очереди у причала, а также в очереди в гавани;

г) среднего времени пребывания в порту каждого типа танкеров.

Вариант 10 . За основу взять модель компьютерной системы (задача 1).

Вычислительный центр с одним ЦП, выполняющий пакетную обработку заданий, открывается в 7.00 и закрывается в полночь, но продолжает свою работу до тех пор, пока все задания, имеющиеся в нем на 0.00 часов, не будут выполнены. Предположим, что время между поступлениями заданий в центр, представлено экспоненциально распределенными величинами со средним значением 1,91 мин. Задания требуют срочного обслуживания (класс 4), обычного (класс 3), с возможной отсрочкой (класс 2) и по мере возможности (класс 1); эти классы возникают с вероятностями 0,05; 0,50; 0,30 и 0,15 соответственно. Когда ЦП освободится, он будет обрабатывать задание высшего (приоритетного) класса; для заданий одного класса действует дисциплина обслуживания FIFO. Время, необходимое ЦП для обработки заданий класса 4, 3, 2 и 1, представлено случайными величинами с распределением Эрланга 3-го порядка (см. раздел 2.7) с соответствующими средними значениями 0,25; 1,00; 1,50 и 3,00 мин. Создайте модель вычислительного центра если:

Б. Если обрабатывается задание класса i, когда поступает задание класса j (при этом j > n), обработка задания класса i прерывается. Задание, обработка которого прервалась, поступает в очередь и в своем классе получает наивысший приоритет. В дальнейшем для его обслуживания потребуется только оставшееся время обслуживания.

Оцените для каждого класса ожидаемое среднее по времени число заданий в очереди и ожидаемые средние задержки в очереди. Оцените также ожидаемые доли времени, когда ЦП пребывает в состоянии занятости и когда ЦП занят обработкой каждого класса задания. Заметьте, удобнее использовать отдельный список для очереди заданий каждого класса, а также входной параметр, который устанавливается в в 1 для случая Б.

Вариант 11. Кафе студенческого центра в университете стремится улучшить качество обслуживания. Особенно большой наплыв клиентов наблюдается в обеденное время, с 11.30 до 13.00, когда они прибывают группами по 1,2,3 и 4 чел., с соответствующими вероятностями 0,5; 0,3; 0,1 и 0,05. Интервалы времени между прибытиями групп распределены экспоненциально со средним значением 30 с. Изначально в системе клиенты отсутствуют. Прогон модели должен соответствовать 90 мин работы системы. Каждый клиент, не важно, прибыл он сам по себе или в группе, выбирает один из трех маршрутов по кафетерию:

+ пункт выдачи горячих блюд, пункт выдачи напитков, касса;

+ пункт выдачи холодных закусок, пункт выдачи напитков, касса;

+ пункт выдачи только напитков, касса.

Вероятности выбора таких маршрутов равны 0,80; 0,15 и 0,05 соответственно (см. рис.). На выдаче горячих блюд и холодных закусок клиентов обслуживают по одному (хотя там могут присутствовать один или два работника, о чем речь пойдет дальше). В пункте выдачи напитков организовано самообслуживание; допустим, что здесь никогда не бывает очереди, то есть можно считать, что выдачей напитков занимается бесконечное множество устройств.

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

На рис. ВО -- время обслуживания клиента на выдаче, НВО -- накопляемое (будущее) время оплаты, которое зависит от числа посещений пунктов выдачи, a ~U(a, b) обозначает, что соответствующая величина равномерно распределена между а и Ь, выраженными в секундах. Например, клиент, выбравший первый маршрут, сначала подходит к пункту выдачи горячих блюд, при необходимости становится в очередь, проходит обслуживание, время которого равномерно распределено между 50 и 120 с, для него «накапливается» часть (будущего) времени оплаты, которое равномерно распределено между 20 и 40 с. После этого данный клиент тратит время, равномерно распределенное между 5 и 20 с, на получение напитка и накапливает дополнительную часть (будущего) времени оплаты, равномерно распределенную между 5 и 10 с. Таким образом, время обслуживания этого клиента у кассы будет представлено суммой случайных величин U(20, 40) и U(5, 10), которые отражают время посещения клиентом пункта выдачи горячих блюд и пункта выдачи напитков.



Рис. Схема обслуживания в кафе: ВО -- время обслуживания; НВО -- накопляемое время оплаты

Определите следующие оценки критериев работы системы:

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

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

- среднюю и максимальную общую задержку во всех очередях для каждого из трех типов клиентов (отдельно);

- суммарную среднюю общую задержку для всех клиентов, которая определяется весовыми коэффициентами отдельных средних общих задержек по соответствующим вероятностям их возникновения;

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

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

Вариант 12. Устаревший компьютер работает в мультипрограммном режиме обработки пакетов, то есть одновременно компьютер начинает обработку нескольких (вплоть до установленного максимума к = 4) заданий, но не может начать обработку новых заданий, пока не будет выполнен этот пакет. В пакете каждое задание имеет собственное время выполнения и покидает ЦП по его истечении. В системе существует три класса приоритетов: высший приоритет имеют задания типа 1, средний -- задания типа 2, низший -- задания типа 3. Когда ЦП завершает выполнение последнего задания в пакете, он сначала обращается к заданиям из очереди класса 1 и берет на выполнение как можно больше заданий, вплоть до указанного максимума к. Если в очереди класса 1 было меньше k заданий, ЦП принимает как можно больше заданий из очереди класса 2, чтобы сумма заданий класса 1 и класса 2 составила максимальный размер пакета к. Если в пакете еще остается место, ЦП переходит к очереди класса 3. Если же общее число заданий во всех очередях меньше к, ЦП собирает их все и начинает обработку такого частично заполненного пакета. Процессор не может начать обработку любых поступающих заданий, пока не завершит выполнение всех заданий в текущем пакете. Если в очередях вообще нет заданий, ЦП переходит в состояние незанятости, и при поступлении следующего задания начинает его обработку в пакете размером 1. Обратите внимание, что когда начинается обработка, в одном пакете могут быть задания различных классов.

В рамках очереди данного класса задания могут обслуживаться в порядке FIFO. Установленное время обслуживания задания класса i равномерно распределено между константами a(i) и b(i). Для каждого класса заданий действует отдельный процесс поступления, то есть интервалы времени между поступлениями двух последовательных заданий класса i экспоненциально распределены со средним значением r(i). Таким образом, в любой момент моделирования должно быть задано три отдельных события поступления заданий -- по одному для каждого класса. Если задание поступает, когда ЦП занят, то оно присоединяется к очереди своего класса в месте, определяемом дисциплиной обслуживания (FIFO). Обслуживание задания, поступившего, когда ЦП свободен, начинается незамедлительно, при этом пакет имеет размер 1. Для заданий используются следующие параметры, мин.

i	r(i)	a(i)	b(i)
0,2	0,05	0,11
1,6	0,94	1.83
5,4	4,00	8,00

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

Вариант 13. Кафе студенческого центра в университете стремится улучшить качество обслуживания. Особенно большой наплыв клиентов наблюдается в обеденное время, с 11.30 до 13.00, когда они прибывают группами по 1,2,3 и 4 чел., с соответствующими вероятностями 0,5; 0,3; 0,1 и 0,05. Интервалы времени между прибытиями групп распределены экспоненциально со средним значением 30 с. Изначально в системе клиенты отсутствуют. Прогон модели должен соответствовать 90 мин работы системы. Каждый клиент, не важно, прибыл он сам по себе или в группе, выбирает один из трех маршрутов по кафетерию:

+ пункт выдачи горячих блюд, пункт выдачи напитков, касса;

+ пункт выдачи холодных закусок, пункт выдачи напитков, касса;

+ пункт выдачи только напитков, касса.

Вероятности выбора таких маршрутов равны 0,80; 0,15 и 0,05 соответственно (см. рис.). На выдаче горячих блюд и холодных закусок клиентов обслуживают по одному (хотя там могут присутствовать один или два работника, о чем речь пойдет дальше). В пункте выдачи напитков организовано самообслуживание; допустим, что здесь никогда не бывает очереди, то есть можно считать, что выдачей напитков занимается бесконечное множество устройств.

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

На рис. ВО -- время обслуживания клиента на выдаче, НВО -- накопляемое (будущее) время оплаты, которое зависит от числа посещений пунктов выдачи, a ~U(a, b) обозначает, что соответствующая величина равномерно распределена между а и Ь, выраженными в секундах. Например, клиент, выбравший первый маршрут, сначала подходит к пункту выдачи горячих блюд, при необходимости становится в очередь, проходит обслуживание, время которого равномерно распределено между 50 и 120 с, для него «накапливается» часть (будущего) времени оплаты, которое равномерно распределено между 20 и 40 с. После этого данный клиент тратит время, равномерно распределенное между 5 и 20 с, на получение напитка и накапливает дополнительную часть (будущего) времени оплаты, равномерно распределенную между 5 и 10 с. Таким образом, время обслуживания этого клиента у кассы будет представлено суммой случайных величин U(20, 40) и U(5, 10), которые отражают время посещения клиентом пункта выдачи горячих блюд и пункта выдачи напитков.

Рис. Схема обслуживания в кафе: ВО -- время обслуживания; НВО -- накопляемое время оплаты

Определите следующие оценки критериев работы системы:

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

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

- среднюю и максимальную общую задержку во всех очередях для каждого из трех типов клиентов (отдельно);

- суммарную среднюю общую задержку для всех клиентов, которая определяется весовыми коэффициентами отдельных средних общих задержек по соответствующим вероятностям их возникновения;

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

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

Рассмотрите работу системы с дополнительными работниками:

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

¦ как третий кассир;

+ как помощник при выдаче горячих блюд, при этом клиентов по-прежнему обслуживают по одному, однако время обслуживания сокращается вдвое и равномерно распределено между 25 и 60 с;

+ как помощник при выдаче холодных закусок, при этом клиентов по-прежнему обслуживают по одному, но время обслуживания равномерно распределено между 30 и 90 с.

Вариант 14. Рассмотрим систему массового обслуживания с заданным числом устройств обслуживания п = 5, действующих параллельно и использующих одну общую очередь. Интервалы времени между поступлениями требований экспоненциально распределены со средним значением 5 (все интервалы времени в этой задаче измеряются в минутах). Требование, поступившее, когда в системе есть свободное устройство, немедленно поступает на обслуживание, выбирая крайнее левое устройство, если таковых устройств несколько. Требование, поступившее, когда все устройства заняты, становится в очередь. Когда требование (первый раз) попадает на обслуживание, время его обслуживания равномерно распределено между а = 2 и b = 2,8. Но по завершении первого обслуживания может оказаться, что требование не удовлетворено (вероятность возникновения такой ситуации р - 0,2). Если обслуживание было удовлетворительным, требование покидает систему, в противном случае обслуживание будет продолжаться. Удовлетворено ли требование обслуживанием, следует определять по его завершении. Если требование не удовлетворено завершившимся обслуживанием и в очереди больше нет других требований, начинается повторное обслуживание этого требования на том же устройстве. Если же по завершении неудовлетворительного обслуживания в очереди еще имеются требования, неудовлетворенное требование должно присоединиться к очереди (при этом возможны два нижеописанных варианта развития ситуации), а освободившееся устройство приступает к обслуживанию следующего требования из очереди. С каждым последующим поступлением требования на обслуживание время его обслуживания и вероятность неудовлетворенности обслуживанием уменьшаются. В частности, следующее время обслуживания требования, которое уже i раз обслуживалось неудовлетворительно, будет равномерно распределено между а/(i + 1) и b/(i + 1), а вероятность того, что оно будет не удовлетворено обслуживанием, равна p/(i + 1). Теоретически ограничение на количество обслуживании одного требования отсутствует: требование обслуживается до тех пор, пока не будет удовлетворено.