Лабораторная работа №4. Построение и исследование имитационной модели массового обслуживания на основе сетей Петри.

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

Методические указания

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

Работу трехфазной системы массового обслуживания рассмотрим по ее сети Петри, представленной на рисунке 18.5. По истечении времени T0 на вход СМО (в позицию P2) поступает заявка, а генератор заявок (позиция P1) загружается снова. Если накопителе 1-ой фазы есть место (есть маркеры в позиции P4), заявка поступает в накопитель (в позицию P5), в противном случае заявка теряется и увеличивается число потерянных заявок (число маркеров в позиции P3). Если в накопителе 1-ой фазы есть заявки и один из ее каналов свободен (есть маркеры в позициях P6 или P9), свободный канал загружается работой на соответствующее время T11 или T12 (маркер помещается в позицию P7 или P8 на это время, позиция P6 или P9 освобождается), а число свободных мест в накопителе увеличивается. Когда один из загруженных каналов выполнит свою работу, то в том случае, если в накопителе 2-ой фазы есть место (есть маркеры в позиции P10), заявка покидает канал (позиция P7 или P8 освобождается) и помещается в накопитель (в позицию P11), а канал освобождается (маркер возвращается в позицию P6 или P9). Если в накопителе 2-ой фазы есть заявки и один из ее каналов свободен (есть маркеры в позициях P12 или P15), свободный канал загружается работой на соответствующее время T21 или T22 (маркер помещается в позицию P13 или P14 на это время, позиция P12 или P15 освобождается), а число свободных мест в накопителе увеличивается. Когда один из загруженных каналов выполнит свою работу, то в том случае, если канал 3-ей фазы свободен (есть маркер в позиции P17), заявка покидает канал 2-ой фазы (позиция P13 или P14 освобождается) и загружается в канал 3-ей фазы на время T31 (в позицию P16), а канал освобождается (маркер возвращается в позицию P12 или P15). Когда загруженный канал 3-ей фазы выполнит свою работу (время T31 истечет), он освобождается (маркер покидает позицию P16 и помещается в позицию P17), при этом увеличивается число обслуженных заявок (число маркеров в позиции P18).

 

Рис. 18.5. Сеть Петри системы

Процедура генерации и обслуживания заявок

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

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

Реализация моделирующего алгоритма СМО

Алгоритм строим по принципу "дельта t", предполагающему постоянный шаг изменения системного времени. После ввода исходных данных, установки начальных условий, в том числе и для источника заявок, проверяем условие окончания моделирования. Если условие выполняется и время моделирования истекло переходим к обработке и выводу результатов моделирования, в противном случае переходим к изменению системного времени: уменьшаем на фиксированную величину время до конца обслуживания заявок каналами, время до поступления заявки из источника, время до окончания моделирования. Затем, начиная с конца, моделируем работу сети Петри трехфазной СМО, а именно: моделируем обслуживание заявки каналом 3-й фазы, переход заявки из 2-й в 3-ю фазу, обслуживание заявки каналом 2-ой фазы, переход заявки из 1-й фазы в накопитель 2-й фазы, обслуживание заявки каналом 1-й фазы, поступление заявки на вход. После завершения моделирования работы сети Петри трехфазной СМО возвращаемся к проверке условия окончания моделирования. Моделирование работы сети Петри с конца позволяет продвинуть все обслуженные заявки за один "тик" системного времени, а также загрузить на их место новые заявки из накопителей.

Обслуживание заявки каналом 3-й фазы

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

Обслуживание заявок каналами 2-ой фазы и переход заявки из 2-й в 3-ю фазу

Далее проводится последовательный просмотр каналов 2-ой фазы. Определяем, имеется ли в каналах 2-й фазы заявки, ожидающие обслуживания в канале 3-ей фазы. Если в данный момент времени имеются такие заявки, обслуживание которых в канале 2-ей фазы завершено, и канал 3-ей фазы свободен, то выбирается в соответствии с дисциплиной обслуживания одна из заявок и имитируется ее обслуживание каналом 3-ей фазы, фиксируется занятость канала 3-й фазы и освобождение канала 2-й фазы. Если канал 3-ей фазы занят, то осуществляется блокировка канала 2-й фазы.

Переход заявки из накопителя 2-й фазы в каналы 2-ой фазы

Снова проводится последовательный просмотр каналов 2-ой фазы. Если в данный момент времени в накопителе 2-ой фазы имеются заявки, а просматриваемый канал 2-й фазы свободен, то вычисляется время обслуживания заявки свободным каналом, фиксируется занятие канала, а место в накопителе освобождается (уменьшается число заявок в накопителе).

Обслуживание заявок каналами 1-ой фазы и переход заявки из 1-й фазы в накопитель 2-й фазы

Далее проводится последовательный просмотр каналов 1-ой фазы. Определяем, имеется ли в каналах 1-й фазы заявки, ожидающие обслуживания в канале 2-ей фазы. Если в данный момент времени имеются такие заявки, обслуживание которых в канале 1-ей фазы завершено (истекло время обслуживания), и в накопителе 2-ой фазы имеются свободные места, то производится запись заявки в накопитель и освобождение конкретного канала 1-й фазы. Если свободных мест в накопителе нет, то фиксируется блокировка канала 1-й фазы.

Переход заявки из накопителя 1-й фазы в каналы 1-ой фазы

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

Переход заявки в накопитель 1-й фазы

Если установлен флаг 'поступила заявка' (на вход системы поступила заявка из источника), то при наличии свободного места в накопителе 1-ой фазы выдается сообщение о поступлении заявки, заявка ставится в очередь на обслуживание каналами 1-ой фазы (увеличивается число заявок в накопителе) и сбрасывается флаг 'поступила заявка'. При отсутствии места в накопителе происходит его переполнение, вследствие чего выдается сообщение о потере заявки, увеличивается число потерянных заявок и сбрасывается флаг 'поступила заявка'.

Поступление заявки на вход системы

После этого проверяем, истекло ли время до поступления очередной заявки из источника. Если время истекло, устанавливаем флаг 'поступила заявка', определяем время до поступления следующей заявки из источника и увеличиваем число поступивших заявок.

Задание на лабораторную работу

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

Варианты

1. Четыре ЭВМ объединены в сеть со случайным доступом. Первая ЭВМ передает данные каждые 10+-4с в течение 15+-10с. Вторая ЭВМ - каждые 12+-4с в течение 5+-3с, третья ЭВМ - каждые 20+-5с в течение 8+-6с, четвертая -каждые 20+-4с в течение 11+-3с. Скорость передачи по сети 10 Мбит/с. Смоделировать систему. Определить число отказов для каждой ЭВМ. Экспериментальным путем определить требуемую скорость передачи по сети.

2. Для обработки данных по некоторому алгоритму требуется с вероятностью 0.2 – одна итерация, с вероятностью 0.5 – 2 итерации, с вероятностью 0.3 – 3 итерации. Длительность каждой итерации 15+-5с. При этом в первом случае вероятность ошибки равна 0.1, во втором – 0.05, в третьем 0.01. При ошибке данные теряются. Смоделировать процесс обработки 10000 заданий. Подсчитать количество заданий, для которых потребовалось одна, две и три итерации. Подсчитать количество потерянных заданий. Определить время обработки.

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

4. В вычислительной системе две ЭВМ: основная и резервная. Пакеты на обработку поступают каждые 10+-5с. Обработка занимает 9+-3с. Примерно 10% заявок для обработки требуют подключения резервной ЭВМ. Если ЭВМ занята, то пришедшая заявка отправляется в буфер. Заявки из буфера обладают низшим приоритетом и обрабатываются в последнюю очередь. Смоделировать обработку 1000 заявок. Определить время работы и простоя основной и резервной ЭВМ, число заявок в буфере.

5. В вычислительной системе две ЭВМ: основная и резервная. Пакеты на обработку поступают каждые 12+-6с. Обработка занимает 10+-3с. Примерно 15% заявок для обработки требуют подключения резервной ЭВМ. Если ЭВМ занята, то пришедшая заявка отправляется в буфер. Заявки из буфера обладают высшим приоритетом и обрабатываются в первую очередь, как только ЭВМ освобождается. Смоделировать обработку 1000 заявок. Определить время работы и простоя основной и резервной ЭВМ, число заявок в буфере.

6. На обработку поступают пять видов заявок с вероятностями, соответственно, 0.1, 0.2, 0.3, 0.2, 0.2. Их обработка занимает 2+-1с, 3+-1с, 5+-2с, 3+-2с, 4+-2с. Смоделировать обработку 10000 заявок. Подсчитать число заявок каждого вида, время их обработки, общее время работы системы.

7. Пакеты данных передаются из пункта А в пункт В по основному каналу связи за 10+-4с, по резервному каналу за 15+-8с. Вероятность ошибки при передаче – по основному каналу 0.05, по резервному 0.1. Пакеты поступают каждые 9+-3 с. Если оба канала заняты, пакет идет в буфер. Если при передаче возникает ошибка – пакет теряется. Смоделировать поступление 10000 пакетов. Подсчитать время занятости обоих каналов, число заданий попавших в буфер и число потерянных заданий.

8. Вычислительная система состоит из 4 ЭВМ. Задания приходят на обработку каждые 10+-2с. Если первая ЭВМ занята, задание обрабатывается на второй и т.д. Время обработки на первой ЭВМ 30+-10с, на второй 35+-5с, на третьей 40+-5с, на четвертой 50+-15с. Оценить время загрузки и время простоя каждой ЭВМ при обработке 10000 заданий, вероятности того, что пакет будет обработан каждой из ЭВМ.

9. Запросы к базе данных поступают каждые 3+-1 с. Примерно в половине случаев пользователь при запросе указывает все идентификационные данные и запись находится за 2+-1с. При неполных данных время поиска 3+-2 с. Если система занята, заявки ставятся в очередь. Смоделировать работу системы за 6 часов.

10. Данные по каналу связи передаются пакетами, в каждом из которых от 2 до 8 блоков. Вероятность ошибки при передаче одного блока составляет 0,05. Если при передаче пакета возникает ошибка хотя бы в одном блоке, теряется весь пакет. Смоделировать передачу 10000 пакетов. Подсчитать число потерянных пакетов, среднюю длину каждого пакета, вероятность прохождения пакета по каналу.

Содержание отчета по лабораторной работе

1. Титульный лист.

2. Тема лабораторной работы.

3. Цель лабораторной работы.

4. Отражение хода лабораторной работы.

5. Вывод.

Курсовое проектирование