Материал: Моделирование, анализ и оценка надежности информационных систем и технологий. Некравцева Т.А., Толстых Т.О

65

4.3. Дискретно-стохастические модели

Рассмотрим особенности построения математических схем при дис- кретно-стохастическом подходе к формализации процесса функционирования исследуемой системы S. Так как сущность дискретизации времени при этом подходе остается аналогичной рассмотренным конечным автоматам, то влияние фактора стохастичности проследим также на разновидности таких автоматов, а именно на вероятностных (стохастических) автоматах.

Основные соотношения. В общем виде вероятностный автомат

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

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

Введем математическое понятие Р-автомата, используя понятия, введенные для F-автомата. Рассмотрим множество G, элементами которого являются всевозможные пары (xi,zs), где xi и zs, — элементы входного подмножества Х и подмножества состояний Z соответственно. Если существуют две такие функции и , то с их помощью осуществляются отображения G Z и G У, то говорят, что F= <Z, X, Y, , > определяет автомат детермини-

рованного типа.

Пусть bkj= 1, где bkj — вероятности перехода автомата в состояние zk и появления на выходе сигнала yj если он был в состоянии zs, и на его вход в этот момент времени поступил сигнал хi. Число таких распределений, представленных в виде таблиц, равно числу элементов множества G. Обозначим множество этих таблиц через В. Тогда четверка элементов P=(Z, X, Y, B) на-

зывается вероятностным автоматом (Р - автоматом).

Если справедливы следующие соотношения:

zk=1 , qk=1, qkzi=bkj

где zk и qk – вероятности перехода Р-автомата в состояние zk и появлении выходного сигнала yk при условии, что Р-автомат находился в состоянии zs и на его вход поступил входной сигнал xi , то такой Р –автомат называется

66

автоматом Мили. Это требование означает выполнения условия независимости распределений для нового состояния Р-автомата и его выходного сигнала.

4.4. Непрерывно-стохастические модели

Особенности непрерывно-стохастического подхода рассмотрим на примере использования в качестве типовых математических схем систем массового обслуживания, которые будем называть Q-схемами. Системы массового обслуживания | представляют собой класс математических схем, разработанных в теории массового обслуживания и различных приложениях для формализации процессов функционирования систем, которые по своей сути являются процессами обслуживания.

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

В любом элементарном акте обслуживания можно выделить две основные составляющие: ожидание обслуживания заявкой и собственно обслуживание заявки. Это можно изобразить в виде некоторого i-го прибора обслуживания Пi (рис.2.2), состоящего из накопителя заявок Нi, в котором может одновременно находиться li, = О, LiH заявок, где LiH — емкость i-го накопителя, и канала обслуживания заявок (или просто канала) Кi. На каждый элемент прибора обслуживания Пi поступают потоки событий: в накопитель Нi — поток заявок wi, на канал Кi, — поток обслуживаний ui.

67

Рис.4.2. Прибор обслуживания заявок

Потоком событий называется последовательность событий, проис-

ходящих одно за другим в какие-то случайные моменты времени. Раз-

личают потоки однородных и неоднородных событий. Поток событий на-

зывается однородным, если он характеризуется только моментами поступления этих событий (вызывающими моментами) и задается последовательностью {tn}, где tn—момент наступления n-го события — неотрицательное вещественное число.

Потоком неоднородных событий называется последовательность {tn, fn}, где tn – вызывающие моменты, а fn – набор признаков события. Например, применительно к процессу обслуживания для неоднородного потока заявок могут быть заданы принадлежность к тому или иному источнику заявок, наличие приоритета, возможность обслуживания тем или иным типом канала и т. п.

Обычно в приложениях при моделировании различных систем применительно к элементарному каналу обслуживания К, можно считать, что поток заявок wi W, т. е. Интервалы времени между моментами появления заявок (вызывающие моменты) на входе Кi, образует подмножество неуправляемых переменных, а поток обслуживания ui U, т. е. Интервалы времени между началом и окончанием обслуживания заявки, образует под-

множество управляемых переменных.

Заявки, обслуженные каналом Кi, и заявки, покинувшие прибор Пi, по различным причинам необслуженными (например, из-за переполнения накопителя Нi), образуют выходной поток уi Y, т. е. Интервалы времени между моментами выхода заявок образуют подмножество выходных переменных.

Процесс функционирования прибора обслуживания Пi можно представить как процесс изменения состояний его элементов во времени zi(t).

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