double arrow

Уравнения Колмогорова

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

 
 


Рис. 3

При составлении уравнений Колмогорова по графу состояний удобно ввести понятие «потока вероятности». Будем называть потоком вероятности, переводящим систему из состояния в состояние произведение вероятности состояния , из которого исходит стрелка, на интенсивность

потока событий переводящего систему по этой стрелке.

Уравнения Колмогорова (6) составляются по следующему правилу: производная вероятности любого состояния равна сумме потоков вероятности, переводящих систему в это состояние, минус сумма всех потоков вероятности выводящих систему из этого состояния.

Все интенсивности в уравнении (6) можно записать в виде квадратной матрицы:

, (17)

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

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

Зная размеченный граф состояний системы (или матрицу интенсивностей ), можно, воспользовавшись мнемоническим правилом, записать систему дифференциальных уравнений для вероятностей состояний системы (6).

Если все интенсивности потоков не зависят от аргумента t , то марковский процесс называется однородным. Если хотя бы одна из интенсивностей в матрице (17) зависит от времени, то такой марковский процесс называется неоднородным. У однородного марковского процесса коэффициенты в системе дифференциальных уравнений (6) являются постоянными.

Таким образом, для исследования марковского случайного процесса нужно знать: 1) матрицу интенсивностей (17) (или размеченный граф состояний системы ) и 2) начальные условия

, (18)

(19)

Пример. Размеченный граф состояний системы имеет вид, показанный на рис. 4.

 
 


Рис. 4

Написать уравнения Колмогорова для вероятностей состояний и указать, при каких начальных условиях их нужно решать, если в начальный момент времени система S с вероятностью ½ находится в состоянии и с вероятностью ½ - в состоянии

Решение. Уравнения Колмогорова имеют вид

(*)

Любое из этих уравнений может быть отброшено, а соответствующая ему вероятность выражена через остальные с помощью нормировочного условия:

. (**)

Начальные условия, при которых надо будет решать систему дифференциальных уравнений, будут:

(***)

Уравнения (*) как при постоянных, так и переменных интенсивностях (совместно с нормировочным условием (**)), можно решать на ЭВМ при начальных условиях (***) любым из перечисленных методов.


15. МОДЕЛИ ОЧЕРЕДЕЙ В ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ И СЕТЯХ. CТРУКТУРА СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ.

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

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

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

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

Cтруктура системы массового обслуживания

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

Основные элементы системы массового обслуживания (СМО) показаны на рисунке.

 
 


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

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

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



Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: