Математическая модель одноконтурной управляющей вычислительной системы и анализ систем обмена информации с помощью стохастических графов

АННОТАЦИЯ

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

ABSTRACT

The article is devoted to the development of well-known and the development of new analytical methods for the study of information exchange between the control computer system and subscribers. The complexity of the analysis of information exchange systems is due to the complexity of the exchange process. The model of the information exchange system in a single-circuit control computer system (UVS) and the construction of its mathematical model, taking into account some simplifications. These models are at the stage of synthesis of the functional lead and to estimate the performance of processors during the implementation of model programs (work), to analyze the flows in the system, compare different options for building functional assemblies and methods of information exchange between the aircraft and external parties, to identify possible errors.

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

Keywords: computer system, information exchange, Queuing system, stochastic graphs, Poisson intensity flow, matrix.

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

В статье рассмотрена система обмена информацией в одноконтурной управляющей вычислительной системе (УВС) и построение ее математической модели с учетом некоторых упрощений.

Построена и исследована математическая модель процесса обмена информации с помощью стохастических графов. Получить аналитические выражения для определения вероятности дискретной Марковской цепи можно, воспользовавшись теоремой Медведева Г.А. [1] для анализа стохастических графов, позволяющей получить простые рекуррентные формулы их вычисления.

Вывод уравнений. Отличительной чертой оптимального подхода к проблемам построения сложных управляющих ВС является исследование взаимосвязи между этапами сбора, накопления, обработка информации и техническими параметрами системы. Возможность аналитического решения указанной задачи стала реальной благодаря предложенным методам описания модели ВС как системы массового обслуживания (СМО) и разработке методов теории Марковской цепей. Формальной моделью описанной выше ВС служит двух узловая двухфазная СМО [2,3] у которой узел (процессорные устройство) содержит один обслуживающий прибор А и является первой фазой для внешнего потока заявок и второй – для внутреннего потока, генерируемого внешним запоминающим устройством (узлом С) (рис1). Полагаем, что ширина полосы пропускания памяти больше или равна ширине полосы процессоров, а поэтому на выходе С всегда содержатся заявки внутреннего потока, требующие второй фазы обслуживания. На вход системы поступает внешний пуассоновский поток интенсивности λ.

Прибор А должен обслуживать заявки внутреннего и внешнего, обладающего относительным приоритетом, потока. Следовательно, заявки внешнего потока не прерывают уже начатого обслуживания заявки внутреннего потока, а поступают в очередь r накопителя (БН) и ждут окончания обслуживания. Если же в очереди r нет заявок, а в узле С всегда имеются заявки внутреннего потока (предположение о неограниченности программ), то прибор А по окончании обслуживания одной заявки из узла С немедленно приступает к обслуживанию другой и т. д. до прихода заявок внешнего потока.

Рисунок 1. Двух узловая двухфазная СМО

Сделав допущение о том, что время обслуживания имеет экспоненциальное распределение с параметром μ для внешнего потока и μ₁ для внутреннего, тогда СМО может быть описана однородной Марковской цепью, для которой определим фазовой вектор

где  –вероятность пребывания системы в момент   времени t в состоянии

Чтобы определить Марковский процесс, необходимо задаться матрицей плотностей переходов. Это удобно делать, построив стохастический граф процесса [1, 2], так как между матрицей плотностей перехода и матрицей смежности В графа  существует взаимно однозначное соответствие [1]. Графом  называется пара, состоящая из множества  и отображения  множества Х в подмножество  по закону, когда каждому элементу  ставится в соответствие некоторое подмножество . При этом возможны подмножества Ø. Каждый элемент множества Х (множество элементарных состояний системы) представляет вершину графа, а упорядоченная пара элементов (X,У), где , является дугой графа.

Квадратная матрица  называется матрицей смежности графа G, где , если из Х_α в вершину Х_β идет дуга, и – в противном случае. Чтобы получить из матрицы В матрицу А, нужно единичные элементы матрицы B заменить соответствующими плотностями переходов.

Построим граф возможных переходов [3], за время ∆t  между состояниями множества Х. Для этого элементы Х состояния изобразим в виде точек (или малых кружков), называемых узлами графа, расположив в ряд все состояния х  Х () в порядке возрастания (слева направо) количества заявок в системе. Возможные переходы из одного состояния в другое указываются стрелками, соединяющими эти состояния. Осуществляются же переходы в результате принятия на обслуживание новой заявки (переход направо) или окончания обслуживания (переход налево). Линия, соединяющая два узла, называется ветвью графа. Каждая ветвь (х, у) характеризуется величиной, называемой передачей ветви Р_ху, а для нашей системы передача принимает смысл вероятности перехода из состояния х в состояние у.

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

Для пуассоновского процесса коэффициент передачи (вероятность перехода) прямых ветвей, вычисленный с точностью до 0(∆t), одинаков и равен   где  – длина очереди, а для обратных ветвей  . Передачу петли найдем следующим образом:

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

Рисунок 2.  Граф переходов обслуживающей системы

Коэффициентами передачи ветвей данного графа будут:

,  ,

.  ,

                                             (1)

В соответствии с графом составляем систему линейных дифференциальных уравнений первого порядка

                     (2)

При  уравнения (2а) и (2г) очевидно отсутствует.

Так как то переходные вероятности также больше нуля,

  а поэтому данная цепь является неприводимой и апериодической. Тогда, согласно теореме Маркова [1,4], существуют предельные вероятности   что является единственным решением системы уравнений (3), полученным путем предельного перехода по t (при  )

                                   (3),

Решая данную систему с условием нормировки

                                                                             (4)

получим единственное распределение стационарных вероятностей системы.

РЕШЕНИЕ ЗАДАЧИ. Определить вероятности состояний дискретной Марковской цепи можно, воспользовавшись теоремой Медведева Г.А. [1,4] для анализа стохастических графов, позволяющей получить простые рекуррентные формулы их вычисления. Суть теоремы состоит в следующем: выделяются сечения  ветвей в графе , которые превращают его при удалении S в на не связанных между собой связанных графа:  и . Связным называется граф, в котором каждая пара вершин может быть соединена некоторой цепью. Несвязный граф может быть разбит на конечное число связных подграфов, называемых компонентами, или частями.  Любой несвязный граф является совокупностью связных графов. Причем сечение  можно представить в виде суммы двух сечений  S = S₁S₂ ,  где   S₁S₂   = 0 и если (α,β) S₁, то α X₁ ,  β X₂ .

Аналогично, если (α,β) S₂, то α X₂, β X₁. Тогда справедлива следующая теорема

                                                                    (5)

Граф, представленный на рис 2. и описывающий поведение управляющей ВС при описанных допущениях о потоках и дисциплине обслуживания, может иметь следующие сечении:

1.. В этом случае с помощью теоремы (5) получим соотношение  

2.Сечение 2: ; В этом случае получаем

;                                                          (6).

Учитывая (6), найдем

                                                                              (7)

3.  для из которого с помощью (5) получаем 

 где                                                          (8)

4. Сечение дает выражение, аналогичное S₂ для произвольного , в чем легко можно убедиться, для чего применим к   теорему (5)

                                                                   (9)

 и, подставив в последнее выражение , полученное из (8), значение после преобразований находим  где (9) применяя последовательно  – раз, получим  или

                                                                                    (10)

где 

Применяя же к-раз (8) с учетом (6), (7) и  (10), находим

                                                       (11)

где  

 .

Подставив значение  и  в условии нормировки, после преобразований находим

                                                                             (12)

Подставив (12)  в  (10) и (11) окончательно получим

,  

, .

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

                                                                     (13)

При r = ∞ получим следующее выражение для  

 где .                                                                  (14)

Подставив его в  найдем

,                                                              (15)

Если время обслуживания заявок внутреннего потока равно нулю, т.е.  (это равносильно тому, что нет заявок внутреннего потока), то , а потому получим , , т.е. согласно формулам приведенным [1-3] для вычислений времени ожидания начала обслуживания и средней длины очереди, если на вход обслуживающего прибора поступает один пуассоновский поток и имеет место дисциплина выбора из очереди « первый пришел - первый обслуживается». Прибор не все время обслуживает заявки внутреннего потока, часть времени (производительной мощности) расходуется на обслуживание заявок внешнего потока, а потому среднее время обслуживания одной заявки внутреннего потока , будет отличаться от величины . Определим через вероятность занятости, прибора обслуживания заявок внутреннего потока интенсивность их обслуживания:

.

Коэффициент снижения производительность η процессора (производительность будем понимать в ранее определенном смысле) вычисляется следующим образом:

                                                                                      (16)

Подставив в  и η значения  Р_ok  (k = 0, 1, 2,…, r), получим после упрощений = 1 / μ₁(1-ρ) ,     η = ρ.

Учитывая ограниченность длины очереди, выражение для P₀₀ будем искать в виде

                                                                  (17)

При r = 0 мы получим. Это значит, что если очередь для накоплений заявок внешнего потока отсутствует, то обслуживаться всегда будут заявки внутреннего потока. Отметим довольно простые выражения для  при ;

;                                             (18)

которые помогут при построении графика (рис.3.) зависимости Р₀₀ от длины очереди и интенсивности потока требований, поступающих от внешнего источника. Среднее время обслуживания заявок внутреннего потока при этом равно 

Тогда относительное снижение производительности обслуживания прибора будет

                                                                     (19)

Выводы:

Нa рис.3 и рис. 4 показана зависимость времени ожидания от величины ρ при фиксированных значениях отношения ψ = μ / μ₁  и сравниваются кривые при дисциплинах обслуживания: относительных и абсолютных приоритетах.

График изменения  и η =η (λ, μ, μ₁, r), показанные на рис.4 для r=1, 2 и r=∞ при фиксированных значениях отношений ψ = μ / μ₁, равных 0,1 и ∞, позволяют сделать ряд выводов:

1. При увеличении емкости внешнего накопителя уменьшается степень загрузки процессора вычислительными операциями и вероятность потери информации.

2. При r → ∞ относительное снижение производительности стремится к величине загрузки процессора обслуживаниям внешних заявок, т.е. η → ρ.

Список литературы:
1. Медведев. Г.А. Анализ стохастических графов, описывающих поведения шаговых систем автоматического поиска // Автоматика и вычислительная техника, 1978, - N 4 – с 15-24
2. Гнеденко. Б.В., Коваленко. И.Н. Введение в теорию массового обслуживания. -2-е изд.-М: наука, 1987. -336 с.
3. Алгоритмы и программы решения задач на графах и сетях. / Нечепуренко. М.И., Попков. В.И. и др.- Новосибирск: Наука. Сиб. от-ние, 1990. -515 с.
4. Кендалл. Д. Стохастические процессы, встречающиеся в теории очередей и их анализ методом вложенных цепей Маркова: Математика. –М: ИЛ, 1969 г. с 3-22 (сб. переводов).