Теорема Джексона

Размещено на http://www.allbest.ru/

Содержание

1. Сети массового обслуживания

2. Анализ однородных открытых СеМО

3. Теорема Джексона

Список литературы

1. Сети массового обслуживания

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

В начале XX века датский ученый А.К. Эрланг, работавший на копенгагенской телефонной станции, поставил и решил ряд новых математическтх задач, позволивших оценивать характеристики телефонных и телеграфных линий связи. Это способствовало возникновению нового направления в теории вероятностей - теории массового обслуживания. На начальной стадии своего развития теория массового обслуживания имела дело с системами массового обслуживания, которые описываются потоками однородных заявок, поступающих в систему, процедурами обслуживания с помощью одного или нескольких каналов, процедурами формирования очередей и способами организации процесса ожидания заявок. Строгое научное описание случайных процессов в теории массового обслуживания и их всестороннее исследование впервые было осуществлено А.Я. Хинчиным. Он исследовал одноканальную систему с ожиданием, простейшим входным потоком и рекуррентным обслуживанием, установив для нее так называемый основной закон стационарной очереди: стационарное распределение числа заявок в системе совпадает с их стационарным распределением в случайные моменты ухода заявок из системы. Большой вклад в развитие теории массового обслуживания внесли Ю.К. Беляев, А.А. Боровков, Б.В. Гнеденко, Н. Джейсуолл, Дж.Р. Джексон, Ф.П. Келли, Дж. Кендалл, Дж.Ф.С. Кингмэн, Л. Клейнрок, Г.П. Климов, И.Н. Коваленко, С. Пальм, Ф. Поллачек, Ю.В. Прохоров, Дж. Риордан, Т. Саати, В.Л. Смит и др.

В 1957 г. Дж.Р. Джексон впервые ввел в рассмотрение понятие открытой сети массового обслуживания ([99]), а в 1967 г. Гордон и Ньюэлл ввели аналогичное понятие замкнутой сети ([91]). В отличие от системы массового обслуживания сеть представляет собой более сложное образование, состоящее из систем массового обслуживания, называемых узлами сети, которые взаимодействуют между собой с помощью некоторого вероятностного механизма. В открытых сетях заявки могут поступать извне, а также уходить из сети. В замкнутых сетях сохраняется постоянное число заявок, которые с помощью случайной маршрутизации могут перемещаться между узлами сети; при этом поступление заявок в сеть и уход заявок из сети невозможны.

Результаты Джексона и Гордона-Ньюэлла не использовались до тех пор, пока в 1971 г. Ф.Р. Мур [115] не обнаружил, что замкнутые сети адекватно описывают вычислительные системы со многими ресурсами. С этого момента теория сетей обслуживания стала быстро развиваться благодаря задачам, связанным с математическим моделированием мультипрограммных вычислительных систем и анализом их производительности, с проектированием и анализом сетей передачи данных и сетей ЭВМ. Дополнительный толчок к дальнейшему развитию теории дала разработка и использование в повсеместной практике различных глобальных и локальных сетей таких, например, как EZERNET, INTERNET и т.д. Значительный вклад в развитие теории сетей внесли Г.П. Башарин, А.А. Боровков, Э. Геленбе, Дж. Джексон, В.А. Ивницкий, Ф.П. Келли, Д. Кениг, Л. Клейнрок, Ю.В. Малинковский, М. Миязава, Б. Меламед, Р. Мюнтц, С.Е.М. Перс, П.К. Поллетт, А.Н. Рыбко, Р. Серфозо, Ю.М. Сухов, П. Тейлор, А.Л. Толмачев, Д. Тоусли, П. Уиттли, Дж. Уолрэнд, Г.И. Фалин, В. Хендерсон, Х. Чао, К. Ченди, Р. Шассбергер и многие другие.

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

2. Анализ однородных открытых СеМО

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

Введем обозначения:

- вектор состояния сети , где - число требований, пребывающих в системе , , ;

- множество всех состояний сети;

- стационарная вероятность пребывания сети в состоянии ;

- стационарная вероятность пребывания системы в состоянии ;

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

- вектор интенсивностей потоков требований, ,

- интенсивность входящего (и выходящего) потока требований в систему ;

- вектор относительных интенсивностей потоков требований, ,

- относительная интенсивность потока требований в систему ;

- коэффициент использования системы .

3. Теорема Джексона

математический массовый обслуживание джексон

Если для однородной открытой сети массового обслуживания выполнены условия:

1) все входящие в сеть потоки пуассоновские;

2) все переходы требований между системами в сети определяются маршрутной матрицей;

3) все длительности обслуживания требований имеют экспоненциальное распределение, причем интенсивность обслуживания может зависеть от числа требований в системе;

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

, , (1)

где

(2)

суть стационарные вероятности состояний систем типа , рассматриваемых как взаимно независимые с пуассоновскими входящими потоками с интенсивностями , а .

Доказательство. Если в момент сеть находится в состоянии , то за интервал времени могут произойти следующие события:

1) не произойдет никаких изменений;

2) в систему поступит требование из источника;

3) после завершения обслуживания в системе требование покинет сеть обслуживания (перейдет в источник);

4) после завершения обслуживания в системе требование поступит в систему .

Вероятность других событий равна .

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

Для упрощения записи уравнений равновесия обозначим

.

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

. (3)

Левая часть уравнения (3) представляет собой стационарную вероятность состояния , умноженную на суммарную интенсивность выхода из этого состояния.

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

Покажем, что подстановка выражений (1) и (2) в уравнение (3) обращает (3) в тождество. Действительно, каждое слагаемое в обеих частях равенства будет содержать множитель , на который можно сократить. Чтобы установить равенство слагаемых в левой и правой частях уравнения (3), выделим в каждом слагаемом в правой части коэффициент . Из соотношений (2) и (3) следует

,

где

.

Следовательно

.

Аналогично

,

.

Подставляя эти выражения в (3) и сократив на , получим

.

Это равенство обращается в тождество, учитывая, что

, .

Таким образом, теорема доказана.

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

,

- математическое ожидание (м.о.) числа требований в очереди системы ,

- м.о. числа занятых приборов системы ,

- м.о. числа требований в системе ,

- м.о. длительности пребывания требований в системе .

Алгоритм, реализующий метод анализа однородных открытых экспоненциальных СеМО:

1) решение системы уравнений с условием нормировки ;

2) вычисление , ;

3) проверка условия существования стационарного режима , ;

4) вычисление стационарных характеристик , , , .

Список литературы

1. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. М.: Наука, 1966. 431с.

2. Ширяев А.Н. Вероятность. М.: Наука, 1980. 575с.

3. Буриков А.Д., Малинковский Ю.В., Маталыцкий М.А. Теория массового обслуживания: Учебное пособие по спецкурсу. Гродно, 1984. 108с. (ГрГу).

4. Феллер В. Введение в теорию вероятностей и её приложения: в 2-х т. М.: Мир, 1967, - т.1,-498с.

5. Кениг Д., Штоян Д. Методы теории массового обслуживания. М.: Радио и связь, 1981. 127с.

Размещено на Allbest.ru