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

Математическое обеспечения и ресурсные возможности современных ЭВМ позволяют провести моделирование различных систем массового обслуживания (СМО). Пусть необходимо моделировать трехфазную СМО, состоящую из источника заявок, 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-ой фазы (увеличивается число заявок в накопителе) и сбрасывается флаг 'поступила заявка'. При отсутствии места в накопителе происходит его переполнение, вследствие чего выдается сообщение о потере заявки, увеличивается число потерянных заявок и сбрасывается флаг 'поступила заявка'.

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

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