Дисциплина Моделирование элементов вс

Сетевой метод оценки трудоемкости алгоритмов.

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

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

Оценка средней трудоемкости алгоритмов.

Алгоритм будем представлять в виде графа, состоящего из К операторных вершин и имеющего единственную конечную вершину с номером К=К+1; дуги графа отмечены вероятностями переходов P_ij. Каждой вершине графа поставлено в соответствие среднее значение трудоемкости k_i или l_j. Задача оценки трудоемкости алгоритма сводится к определению среднего числа n₁,n₂,…,n_k обращений к операторам за один прогон алгоритма.

Д
ля применения сетевого подхода к оценке трудоемкости алгоритма, не содержащего циклы, вершины графа алгоритма должны быть пронумерованы в порядке их следования, т.е. так, чтобы любая вершина имела номер, больший любого номера предшествующих ей вершин. Нумерация проводится следующим образом. Начальной вершине присваивается номер 0. Очередной номер i=1,2,… присваивается вершине, в которую входят дуги от уже пронумерованных вершин с номерами, меньшими i. При этом любым двум вершинам должны соответствовать разные номера. Такой порядок нумерации является результативным для любого графа без циклов. Причем конечная вершина графа будет иметь максимальный номер К. Пример корректной нумерации вершин графа(*):

Поскольку граф не содержит циклов, то при прогоне алгоритма вершина 1 будет выполнена точно один раз, то есть n₁ = 1. Среднее число попаданий вычислительного процесса в вершину определяется выражением:

где Р_ji - вероятность перехода из вершины j в вершину i.

При установленном порядке нумерации вершин на момент вычисления n_i значения n₁, n₂,...,n_i_-1 уже определены. Поэтому вычисление значения n_i сводится к суммированию произведений, причем поскольку P_ij = 0 для всех j0, то суммирование следует проводить только для j

Определим среднее число обращений n₁, n₂,...,n_k к операторам алгоритма изображенного графа (предыдущий рисунок)

Рассмотрим случай алгоритма, содержащего циклы:

Н
епосредственное применение описанной методики к таким алгоритмам невозможно и для вычисления значений n₁, n₂,...,n_k необходимо исключить циклы, заменяя их операторами с эквивалентной трудоемкостью.

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

Здесь суммирование проводится по всем вершинам V_j , содержащимся в цикле С.

Пусть известно среднее число повторений цикла n_c, равное числу выполнений тела цикла при одном прогоне алгоритма. Если вероятность перехода по дуге, замыкающей цикл, равна P_kl , то n_C=

В этом случае средняя трудоемкость цикла равна:

и цикл С можно заменить оператором с трудоемкостью k_C.

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

Определим трудоемкость, заданную приведенным выше графом.

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

В
ыделим тела циклов С1 и С2 первого ранга:

Применяя к этим графам рассмотренную ранее методику, определяем среднюю трудоемкость k_C₁ и k_C₂ выполнения тел этих циклов:

Определяем трудоемкость тел этих циклов:

Средняя трудоемкость циклов С1 иС2 вычисляется умножением полученных значений на среднее число повторений этих циклов:

;

Заменяя в исходном графе циклы С1 и С2 операторами С1 и С2 с трудоемкостью k_C₁ и k_C₂, получим граф:

Т
ело цикла С3 имеет вид:

Определим трудоемкость тела цикла С3:

С учетом числа n_C₃ повторений цикла трудоемкость цикла составит:

операций.

Заменив цикл С3 оператором С3 с трудоемкостью k_C₃, получим граф:

Трудоемкость всего алгоритма, представляемого этим графом, равна:

операций.
Оценка минимальной и максимальной трудоемкости алгоритма.

Минимально возможное и максимально возможное значение трудоемкости на момент окончания выполнения оператора V_i обозначим соответственно через A_i и B_i. Имеем A₀=0, B₀=0. Тогда для остальных вершин с номерами i=1,2,...,k:

;;

где (j,i) - дуга, выходящая из вершины j и входящая в вершину i;

D - множество дуг графа программы.

Минимальное min(A_j) и максимальное max(B_j) значения определяются по отношению ко всем вершинам j из которых выходят дуги, входящие в вершину i.

Значения k_imin и k_imax характеризуют минимальную и максимальную трудоемкость оператора V_i.

Для конечной вершины К графа вычисляются значения

;;

характеризующие минимальную и максимальную трудоемкость алгоритма.

Определим минимальную и максимальную трудоемкость алгоритма, не содержащего циклов(*).

Примем, что трудоемкость каждого оператора постоянна и равна 1.

Последовательно применяя , получим:

Таким образом минимальная трудоемкость алгоритма A_k = 5, а максимальная B_k = 7 операций.

Минимальная и максимальная трудоемкость алгоритмов, содержащих циклы, находятся по аналогии с методом определения средней трудоемкости алгоритмов с циклами. При этом выделяются циклы первого ранга. Находятся минимальная А и максимальная В трудоемкость тела цикла. Минимальная и максимальная трудоемкость цикла определяется значениями и , где n_min и n_max - минимальное и максимальное число повторений цикла. Затем цикл заменяется оператором с трудоемкостью k_min= и k_max = и вновь применяется процедура исключения циклов.

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

Сетевые модели вычислительных систем.

Представление ВС в виде стохастической сети.

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

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

Многоканальная СМО содержит К однотипных каналов, среднее время обслуживания заявок V в которых непременно одинаково.

В системе одновременно может обслуживаться до К заявок. Заявки, застающие все каналы занятыми ожидают освобождение каналов в очереди О. Характерная особенность рассматриваемой СМО - полная доступность каналов, при которой любая заявка может быть обслужена любым свободным каналом. Если налагаются ограничения на условия выбора каналов для обслуживания входных заявок, то многоканальная система разбивается на ряд независимых одно- и многоканальных систем. Например, если в системе (*) заявки с вероятностью Р₁ поступают на обслуживание в первые (к-1) полнодоступные каналы и с вероятностью Р₂ = 1 - Р₁ в к-й канал, то исходная система разбивается на две независимые системы, первой из которых является (к-1) - канальная система, а второй - одноканальная система, с интенсивностями входящих потоков заявок Р₁ и Р₂ соответственно.

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

Модель процессора с оперативной памятью.

Подсистема "процессор - оперативная память " рассматривается как однокритериальная СМО. Обслуживающим каналом (прибором) в этой системе является процессов Пр. При работе ВС в мультипрограммном режиме в оперативной памяти размещено несколько программ П₁,П₂,...,П_М.

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

Совокупности готовых к выполнению программ соответствует очередь О заявок в СМО. Программа из очереди, получившая доступ к процессору Пр, переходит в состояние счета. Среднее время непрерываемого счета программы определяет среднюю продолжительность V процесса обслуживания заявки в СМО. Процесс счета, то есть обслуживание программы процессором, прекращается в момент, когда программа обращается к системе ввода-вывода, то есть к устройству ввода-вывода или к ВЗУ. При этом считается, что программа на счет обслужена и покидает систему "процессор - оперативная память". Обслуживание этой заявки, то есть этой программы, будет продолжено другим устройством ВС. Интенсивность  поступления заявок в СМО определяется суммарной интенсивностью пополнения списка готовых к выполнению программ, как за счет поступления новых программ, так и за счет программ, для которых завершен ввод-вывод. Непременное условие готовности программы - наличие ее в оперативной памяти.

Модель мультиплексного канала.

МК обеспечивает параллельную и независимую работу подключенных к нему устройств ввода - вывода (УВВ), различных типов:

- устройств ввода с перфокарт ПК;

- печатающих устройств ПУ;

- накопителей на магнитном диске НМД;

и так далее.

П
оэтому каждое из этих устройств должно рассматриваться как идеальный канал (прибор) СМО. Несколько однотипных устройств ввода - вывода могут рассматриваться как многоканальная СМО с одинаковым среднем временем обслуживания заявок в каждом из каналов.

М
К с подключенными к нему устройствами ввода - вывода представляется в виде совокупности СМО:

В модели система S₁ отображает работу К однотипных устройств ввода - вывода, в каждом из которых заявка на ввод - вывод обслуживается в среднем за время V₁. Интенсивность входящего в эту систему потока равна доле Р₁ от интенсивности  всех заявок, обслуживаемых МК. По аналогии система S_m отображает работу других (n-l) устройств ввода - вывода со средним временем обслуживания заявок V_m и интенсивностью входного потока P_m . Очевидно что должно выполняться равенство .
Модели селекторных каналов.

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

При передаче данных СК обслуживает в каждый момент времени обращение только к одному ВЗУ.

Модель работы СК рассмотрим на примере канала с однотипными ВЗУ.

Модель должна отображать различные этапы в обработке запросов программ на ввод-вывод информации:

- на первом этапе выполняются подготовительные операции;

- на втором этапе осуществляется передача информации между оперативной памятью и одним ВЗУ.

В
результате процесс работы канала и ВЗУ можно представить как процесс последовательного обслуживания запросов в двух СМО, первая из которых отображает этап выполнения подготовительных операций в ВЗУ и вторая - этап передачи данных ПД по каналу.

Продолжительность этих этапов составляет в среднем V₁ и V₂ единиц времени. На вход СК поступает поток заявок с интенсивностью . Заявки, обслуженные в этой системе с вероятностью Р_i , i = 1,2,...,k, направляются в одну из систем ВЗУ_i. Рассматриваемая модель является моделью с блокировкой процессов обслуживания заявок в различных системах. Действительно, ВЗУ_i, завершившее подготовительную операцию, не может начать обслуживание следующей заявки из очередиO_i до тех пор, пока канал, то есть система ПД, не завершит передачу данных из ВЗУ_i. Эффектом блокировки можно пренебречь, если учесть, что задержки при передаче данных значительно меньше времени выполнения подготовительных операций в ВЗУ. Так, среднее время передачи данных V₂ составляет несколько миллисекунд, а среднее время выполнения подготовительных операций V₁ имеет порядок десятков миллисекунд. В связи с этим системы ВЗУ₁ ... ВЗУ_k и ПД могут рассматриваться как независимые СМО.

Эту модель можно еще упростить, если представить ее в виде многоканальной СМО со средним временем обслуживания в каждом из каналов , равным сумме двух временных задержек V₁ и V₂. Как в первом, так и во втором случае время пребывания заявок в модели будет меньше, чем в реальном СК.

В малых ЭВМ может отсутствовать совмещение подготовительных операций в различных ВЗУ, подключенных к одному СК. В таком случае рассматриваемая модель без каких либо погрешностей заменяется одноканальной СМО, в которой среднее время обслуживания заявок равно сумме времен V₁ и V₂.
Стохастическая сетевая модель.

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

В качестве примера определим конфигурацию стохастической сети, которая моделирует вычислительную систему, которая состоит из процессора, оперативной памяти, СК, в каждый момент времени обслуживающего обращение только к одному подключенному к нему ВЗУ, и МК с устройствами ввода - вывода УВВ₁,...,УВВ_k, функционирующими параллельно и независимо друг от друга.

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

И
сходя из сказанного, ВС с заданной структурой и указанным порядком решения задач можно представить как стохастическую сеть следующего вида:

S₁, S₂, S₃ - системы массового обслуживания, отображающие этапы обработки задач в подсистеме "процессор - оперативная память", СК и МК соответственно.

O₁, O₂, O₃ - очереди заявок на обслуживание.

Системы S₁ и S₂- одноканальные СМО, а система S₃ - многоканальная система массового обслуживания в предположении, что к МК в моделируемой ВС подключено К однотипных устройств ввода - вывода. Заявки на решение задач поступают на вход системы с интенсивностью ₀ и воспринимаются системой, моделирующей работу процессора.

Процесс решения задачи в ВС носит многоэтапный характер и складывается из периодов работы процессора, СК и МК. В сетевой модели этот факт отмечается циркуляцией заявок в сети по контурам или , причем переход заявок в системы S₂ и S₃ может осуществляться только из системы S₁, так как заявки на ввод - вывод формируются программами, обрабатываемыми процессором. Выбор направления перехода заявок из системы S₁в системы S₂ и S₃ определяется вероятностями Р₁₂ и Р₁₃ передач заявок. После нескольких циклов обслуживания заявки с вероятностью Р₁₀ покидают сеть. Вероятности Р₁₀, Р₁₂, Р₁₃ зависят от параметров трудоемкости программ, реализуемых ВС. Интенсивность выходящего потока равна _k. Так как ВС работает без потерь заявок, соблюдается равенство _k = ₀.

Разомкнутые и замкнутые стохастические сети.

Для описания ВС используют стохастические модели разомкнутые и замкнутые. Для разомкнутой сети С характерно, что интенсивность источника заявок ₀ не зависит от состояния сети, то есть от числа заявок, поступивших в сеть.

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

Замкнутые сети используются для описания работы ВС, обрабатывающих фиксированное число заявок на решение задач. К таким системам относятся системы оперативной обработки, функционирующие в режиме диалога, когда имеется фиксированное число пользователей и каждый из них не инициирует нового запроса к системе до получения ответа на предшествующий запрос, и система пакетной обработки. В последнем случае количество заявок, циркулирующих в сети, определяется количеством работ, выполняемых в мультипрограммном режиме, то есть коэффициентом мультипрограммирования. Когда выполнение работы заканчивается, тут же инициируется новая работа, выбираемая из выходного пакета. Число заявок, проходящих в замкнутой сети по отмеченной дуге за единицу времени, определяет производительность ₀ системы. Заметим, что величина ₀ не зависит от каких-либо внешних причин, а определяется конфигурацией сети и ее параметрами.
Экспоненциальные стохастические сети

Распределение времени обслуживания заявок в СМО устанавливается исследованием моделей, отображающих отдельные этапы вычислительного процесса. Такими моделями являются модели программ, алгоритмы планирования и функционирования ВЗУ и УВВ. При произвольных распределениях и произвольных входящих потоках получение аналитических зависимостей для исследуемых характеристик ВС в общем случае становится практически невозможным даже при использовании сетевых моделей с упрощенной структурой. Задача будет разрешимой , если предположить. Что входящие потоки - простейшие и распределены по экспоненциальному закону.

Подобные сети называются экспоненциальными стохастическими сетями.

Использование гипотезы о простейших входящих потоках и экспоненциальном распределении времени обработки запросов программ в устройствах ВС приводит к тому, что характеристики системы, определяемые на основе экспоненциальных сетей, оказываются приближенными. Поэтому экспоненциальные сети используются для определения только средних значений характеристик ВС. Причем определяемы таким образом средние характеристики не более чем на 10-15% отличаются от реальных, что вполне приемлемо при инженерных исследованиях. К тому же следует иметь в виду, что чем сложнее структура сети, чем больше связей между составляющими ее системами, тем точнее полученные результаты. Этот факт - следствие приближения суммарных потоков, входящих в каждую из систем сложной сети, к простейшим потокам.

Параметры стохастических сетей.

Стохастическая сеть определяется следующей совокупностью параметров:

1. числом n систем массового обслуживания S₁, S₂,..., S_m образующих сеть;

2. числом каналов (обслуживающих приборов) K₁, K ₂,..., K _m входящих в системы S₁, S₂,..., S_m;

3. матрицей вероятностей передач P = [p_ij], где p_ij - вероятность того, что заявка, покидающая систему S_i, поступит в систему S_j (i,j =1,2,...,n);

4. числом М заявок, циркулирующих в замкнутой сети, или интенсивностью ₀ источника заявок S₀ в разомкнутой сети;

5. средними длительностями обслуживания заявок V₁,..,V_n в системах S₁,...,S_n.

Рассмотрим физический смысл и способы определения перечисленных параметров при построении стохастических сетевых моделей ВС.

Количество систем и каналов

Количество n систем, каналов K₁,...,K_n в системах S₁,...,S_n и связи между этими системами определяют конфигурацию сети. Выбор данных параметров зависит от цели исследования, налагающей соответствующие ограничения на степень детализации моделируемых вычислительных процессов. Обычно число систем сетевой модели равно числу устройств обработки информации, входящих в ВС. К таким устройствам относят процессоры, селекторные (СК) и мультиплексные (МК) каналы. Количество каналов (приборов) в системе массового обслуживания (СМО) определяется числом однотипных устройств ВС. Например, два одинаковых процессора ВС, обслуживающих заявки с одинаковыми характеристиками из общей очереди, представляются двухканальной СМО. Каждый СК с подключенным к нему внешним запоминающим устройством (ВЗУ) рассматривается как одноканальная СМО.

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

Связи между СМО, входящими в сеть, устанавливаются на основе анализа порядка следования этапов обработки заявок в ходе вычислительного процесса. Для отображения связей между СМО сети удобно использовать направленный граф передач, вершины S₁,...,S_n которого соответствуют одноименным СМО, а дуги - связям между ними. Передача заявки в сети из системы S_i в систему S_j после завершения этапа обработки этой заявки в системе S_i отображается на графе дугой, исходящей из S_i и входящей в S_j. В случаях, когда заявка может быть передана из одной СМО в несколько других СМО, возникает неопределенность в выборе направления передачи. Для устранения неопределенности дуги графа передач взвешиваются вероятностями передач P_ij, которые образуют матрицу Р, размерность и элементы которой определяются видом сети.

Разомкнутая сеть содержит n СМО и источник входящего потока S₀, который можно рассматривать как СМО с бесконечным числом заявок и интенсивностью их обслуживания ₀. Замкнутая сеть также содержит n СМО и в ней выделяется фиктивный источник S₀, который можно представить в виде СМО с нулевым временем обслуживания заявок, поступающих на ее вход с интенсивностью ₀.

В результате матрица вероятностей передач разомкнутой и замкнутой сети состоит из (n+1) строк и (n+1) столбцов:

Вероятность передачи заявки из системы S_i в систему S_j равна доле потока, поступающего из системы S_i в систему S_j.Так как в сети заявки не теряются и заявка, выходящая из системы S_i обязательно попадает в некоторую другую систему S_j, то должно выполняться условие:

, i = 0,1,...,n
таким образом, сумма элементов каждой строки матрицы равна единице, то есть эта матрица стохастическая.

Вероятности P_ij определяют порядок циркуляции заявок в сети и имеют следующий смысл. Пусть _ij - среднее количество обращений от устройства, моделируемого системой S_i сети, к устройству, моделируемому системой S_j сети, за время решения одной задачи. Общее количество этапов обслуживания заявок в системе S_i сети:

, i = 0,1,...,n

В таком случае , то есть P_ij - это доля проходящих через систему S_i заявок, которые направляются в систему S_j. Если все заявки, обслуженные системой S_i, поступают в систему S_j, то P_ij=1. Если система S_i не связана по входу с системой S_j, то P_ij=0.

Интенсивности потоков и коэффициенты передач.

Вероятности передач P_ij однозначно определяют соотношения между интенсивностями потоков заявок, циркулирующих в сети и, в частности, поступающих на входы систем S₀,...,S_n сети. Интенсивности ₀,...,_n потоков заявок, поступающих в системы S₁,...,S_n, определяются средним числом заявок, поступающих в единицу времени в эти системы.

Будем рассматривать только установившийся режим. Тогда среднее число заявок, поступивших в систему S_i за некоторый промежуток времени, равно среднему числу заявок, покинувших эту систему, то есть интенсивности входящего и выходящего потоков для системы S_i равны между собой. Интенсивность потока, входящего в любую систему S_i сети, равна сумме интенсивностей потоков , поступающих в нее из других систем S_j (j=0,1,2,...,n). Поскольку заявки из системы S_j поступают в систему S_i с вероятностью P_ji, то интенсивность потока, поступающего из S_j в S_i, равна P_ji_j, где _j - интенсивность выходящего и, следовательно, входящего потока заявок системы S_j. С учетом этого на входе системы S_i имеется поток с интенсивностью:

;(i=0,1,2,...,n).

Эти выражения представляют собой систему алгебраических уравнений (n+1) - го порядка, которым соответствует каноническая форма:

(*)

Из этой системы определяется соотношение интенсивностей потоков _j и ₀ в виде _j=₀_j₀.

Коэффициент ₀_j называется коэффициентом передачи и определяет среднее число этапов обслуживания в системе S_j в расчете на одну заявку, поступающую от источника S₀. В дальнейшем в коэффициенте ₀_j индекс 0 будем опускать: _j.

Тогда _j=₀_j₀.(**), причем ₀=1.

Для разомкнутых стохастических сетей известна интенсивность источника заявок ₀. Поэтому система уравнений (*) имеет единственное решение вида (**), где ₀ - фиксированная величина.

Для замкнутой сети ни одна из интенсивностей ₀,...,_n заранее не известна и в этом случае определитель системы уравнений (*) равен нулю. Поэтому система имеет бесконечное множество решений. Однако из (*) можно определить соотношение интенсивностей потоков _i и ₀, то есть коэффициенты передач _i. Коэффициенты передач ₁,...,_n определяются путем решения системы уравнений (*), в которую подставляется значение ₀=1. В этом случае корни ₁,...,_n системы n-го порядка численно определяют значения ₁,...,_n.

Пример. Определим значения интенсивности _j и коэффициентов передач _j для ранее уже рассмотренной разомкнутой сети:

Г
раф передач этой сети имеет вид:

М
атрица вероятностей передач имеет вид:

Примем: ₀=5 с^-1; Р₁₀=0.1; Р₁₂=0.4; Р₁₃=0.5.

Подставим эти значения в систему уравнений (*):

Получаем: ₁=50; ₂=20; ₃=25.

Находим значения коэффициента передач:

; ;

Пример. Определим значения коэффициентов передач для замкнутой сети следующего вида:

Г
раф передач этой сети имеет вид:

М
атрица вероятностей передач для рассматриваемой сети имеет вид:

Примем: Р₁₀=0.1; Р₁₂=0.4; Р₁₃=0.5; Р₂₁=0.2; Р₂₃=0.8.

Подставим эти значения вероятностей передач в систему уравнений (*):

Получаем: ₁=10₀; ₂=4₀; ₃=8.2₀.

Находим значения коэффициента передач:

; ;

Моделирование элементов автоматики.

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

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

обозначим RC=T–постоянная времени цепи и запишем уравнение в виде: TpU_вых+U_вых=U_вх.

Перепишем уравнение в виде: U_вых(Tp+1)=U_вх.

Передаточная функция звена будет такой: .

Построим модель этого звена. Разобьем ось времени t на малые участки t, как показано на рис:
Будем считать, что при некотором заданном законе изменения U_вх величина U_вых меняется, как показано на рисунке, причем к текущему моменту времени t_n-1 она принимает значение в момент времени t_n. Заменяя в исходном уравнении величину dU_вых/dt приближенно отвечающей ей величиной (U_n-U_n_-1)/t и считая приближенно U_вых=U_n, преобразуем уравнение к виду:

TU_n-TU_n-1+tU_n=tU_вх+(tU_n-1-tU_n-1)

U_n(T+t)=U_n-1(T+t)+t(U_вх-U_n-1)
U_n=U_n_-1+

Обозначим К= если t<

U_n=U_n-1+K(U_вх-U_n-1).

Этот алгоритм легко реализуется программно. При подаче на вход этой модели в заданные моменты времени дискретных значений U_вх при достаточно малых t получается практически такая же характеристика U_вых(t) как и в реальной RC-цепи.

Может возникнуть вопрос, в каких случаях и чем лучше такая программная обработка сигналов, чем аппаратная? Иногда она может быть ненужной, в аналоговых регуляторах проще использовать RC-цепь. Но в цифровых регуляторах она необходима для отфильтровывания высокочастотных шумов в сигналах, поступающих на вход регулятора. Цифровая обработка сигналов может быть полезной и по другим причинам. Например, просто может изменяться коэффициенты К, если в ходе процесса управления меняется величина Т и нужно учитывать это при формировании управляющих воздействий. Или же может оказаться целесообразным для ускорения обработки информации изменять в ходе ее поступления величину t: брать величины t большими при малых изменениях входного сигнала и меньшими, если по времени входной сигнал меняется более резко.

Одним из основных устройств автоматики является регулятор. Построим модель регулятора. Основной принцип регулирования – по отклонению. Это значит, что регулятор вступает в действие после того, как произошло отклонение регулируемой величины X_ист от заданного ее значения X_зад или, как говорят, при наличии рассогласования между заданными и истинными значениями регулируемой величины:

X_вх=X=X_зад-X_ист.

На этом принципе основана работа пропорциональных П-регуляторов, в которых регулирующее воздействие X_вых пропорционально рассогласованию:

X_вых=CX_вх, С – коэффициент пропорциональности.

Может потребоваться достаточно большое рассогласование для того, чтобы регулятор начал ощутимо воздействовать на объект регулирования. Для устранения этого недостатка дополнительно вводят воздействие по производной (ПД-регуляторы).

Пусть рассогласование X_вх(t) меняется как показано на рисунке. На начальном отрезке времени оно мало и пропорциональный канал регулятора может и не включиться в работу, однако его производная X’_вх(t) велика и дифференциальный канал начнет сразу ощутимо воздействовать на объект регулирования, т.е. динамические характеристики процесса регулирования улучшаются. Могут использоваться воздействия не только по X’_вх, но и по X’’_вх, что также может быть полезным. Это регуляторы, работающие с предварением, так как они могут вступать в действие тогда, когда отклонение еще не произошло. В ПД-регуляторах воздействие на исполнительный орган равно:

Х_вых=СХ_вх+Т_дХ`_вх, Т_д - постоянная времени дифференцирующего звена.

Для полного устранения статической погрешности в регулятор вводят гибкую обратную связь и получают изодромные регуляторы (от греческих слов «изос» – постоянный и «дромос» – бег). В таких статических регуляторах по сути дела вводится дополнительное воздействие по интегралу (ПИ-регуляторы) и в них управляющее воздействие равно:

Х_вых=СХ_вх+ T_и - постоянная времени интегрирующего звена.

Для объединения преимуществ этих регуляторов строят ПИД-регуляторы, выходной сигнал которых равен:

Построим модель такого регулятора. Запишем выражение в операторной форме:

x_вых=Cx_вх++T_дpx_вх
Передаточная функция ПИД-регулятора будет такой:

W
(p)=x_вых/x_вх=C+1/T_иp+T_дp

Эта схема может быть основой для программной реализации регулятора. Реализация блоков 1 и 4 проста, а для блоков 2 и 3 необходимо найти соответствующие рекуррентные соотношения. С выхода блока 2 снимаем сигнал: z=, т.е. Т_иpz=x_вх. Дифференциальному уравнению соответствует уравнение в конечных разностях z_n=z_n_-1+x_вх_n_-1.

Выходной сигнал блока 3 равен y=T_дpx_вх, т.е. имеем дифференциальное уравнение: T_д, которому соответствует уравнение в конечных разностях:

y_n_-1=.

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

<< предыдущая страница