Анализ нестационарных и стационарных характеристик в модели Клейнрока

Актуальность работы. Развитие информационно-вычислительных систем диктует необходимость построения и изучения их математических моделей.

По мнению известного специалиста по вычислительным системам Л. Клейнрока «применения теории очередей для анализа распределения ресурсов и решения задач о потоках данных в вычислительных системах является, по-видимому, единственным доступным специалистам по вычислительной технике методом, позволяющим понять сложные связи в таких системах» .

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

Модель МгСг1оо. В одноканальную систему обслуживания с ожиданием поступают независимые пуассоновские потоки 1 -вызовов, ., гвызовов с параметрами аъ—-, аг соответственно. Длительности обслуживания вызовов независимы, не зависят от процесса поступления и для к-вызовов,, имеют функцию распределения Вк (х), Вк (+0) = 0.

Теория модели МГСЩ со с классическими приоритетными дисциплинами глубоко разработана (Климов, Гнеденко, Даниелян, Джейсуол, Прабху, Ушаков н др. 2,4,8,14,20,29,33]).

Параметрическую дисциплину строят так, чтобы её «крайними» случаями были: дисциплина относительных или абсолютных приоритетов и FIFO (first input — first output) или LIFO (last input — first output). Непрерывное изменение параметров позволяет регулировать меру предоставляемого преимущества различным потокам.

В рамках модели Mr|Gr|l|co предложены различные параметрические дисциплины (Клейнрок, Прабху, Духовный, Климов, Даниелян, Малинковский и др. 1,8,18,19,21,22,24,25,35]).

Интересна дисциплина с линейно зависящами от времени приоритетами. Поступивший в момент т>0 в модель квызов, к =, г, в момент t > т получает приоритет bk (t — т) + ск, bk, ск е (-°°,+оо).

Прерывания обслуживания не допускаются. В момент завершения обслуживания из очереди на прибор выбирается вызов с наибольшим приоритетом.

Главная характеристика — виртуальное время ожидания wk (t) к-вызова в момент t, к =, г, являющаяся аналогом «времени реакции» в вычислительных системах.

Задача нахождения функции распределения величины wk (t), k =, r, в модели Mr|Gr|l|co с линейно зависящими от времени приоритетами — нерешенная проблема!

Для разработчика важно, чтобы неравенства wl (t)<—- 0, имели место при всех значениях параметров. Это верно лишь в случае bk>b!c+h ck>ck+l, к = 1, г-1,сохраняющем «богатство» дисциплины. В данном случае, по-видимому, упростится и аппарат анализа. «Богатство» дисциплины сохраняется и при допущении q = • • • = сг = 0, которое принято ниже.

Существенно различны подслучаи > • • • > br > 0 и.

—->br .

В первом из них «крайними» случаями служат дисциплины FIFO и относительных приоритетов с дисциплиной FIFO внутри потоков, во втором — LIFO и относительных приоритетов с дисциплиной LIFO внутри потоков.

При bx >—->br >0:

1. Л. Клейнрок получил рекуррентные уравнения, определяющие средние стационарные времена ожидания А—вызовов, к = 1, г ([19],.

1976 г.);

2. Э. А. Даниелян нашел стационарное распределение времени ожидания г-вызова ([5], 1980 г.);

3. Э. А. Даниелян и Ф. Лизе получили систему уравнений для распределений величин wk (t), k =, r, t>0 (([34], 1991 г.). Однако в них содержится ошибка.

При 0>bx>—->br Г. Джун ([35], 1970 г.) провел аналогичное Л. Клейнроку исследование.

Упомянутые подслучаи в модели MrGrl со мы называем моделями Клейнрока и Джуна.

Дальнейшие исследования по модели Клейнрока ничего существенно нового не добавило к результатам Л. Клейнрока [32,36].

Отметим также предшествующие исследования по модели Клейнрока в частном случае экспоненциально распределённых времён обслуживания [18].

Здесь мы не касаемся вопроса оптимизации по модели Клейнрока, по которому имеется несколько публикаций.

Что же касается исследований по другим параметрическим дисциплинам, то мы процитируем лишь некоторые из них [3,6,7,8,12,13,26,27].

Таким образом, упомянутая выше проблема не решена и для моделей Клейнрока и Джуна.

С величиной к =, г, о0, тесно связан период занятости.

Тк (и) с задержкой и, со скоростью роста приоритета Ьк+]. Тк (и) начинается с задержки и, в начале которой вызовы в модели отсутствуют и за которую вызовы накапливаются, но не обслуживаются.

Он определяется следующим образом.

Пусть: Vслучайное число обслуженных вызовов за общий период занятости модели с задержкой и — внутри него и = (0 -последовательные моменты окончаний задержки и обслуживаний вызовов.

Полагаем Тк{и)=1п, п> О, если при /я=0,я-1 (0,-1-пусто) в моменты (т+0 и + 0 в модели имеются и отсутствуют вызовы с приоритетом соответственно больше Ьк+и Ьк+^п.

Изучение характеристик моделей Клейнрока и Джуна, в частности, вышеупомянутых актуально. Этим вопросам и посвящена диссертационная работа.

Объектом исследования являются величины м/к (?) и Тк (и), к =, г ^>0, и> 0, в моделях Клейнрока и Джуна.

Цели работы. Намечены следующие цели. В случае модели Клейнрока найти:

1. Функции распределения величин (7), к = 1, г, Г > 0;

2. Функции распределения векторов (^(О^+иСО^-'^г^СО), к =, г, Г>0, где ] =к +, г, есть суммарное время обслуживания 7 -вызовов находящихся в очереди в момент I, которые будут обслужены после момента г + (/);

3. Стационарные функции распределения при Г —" величин и векторов в 1. и 2. соответственно;

4. Изучить цепи Маркова, вложенные в вектор-процесс роста приоритетов вызовов разных потоков.

В случае модели Джуна провести предварительный анализ величин к —, г ^ >0.

Научная новизна. В диссертационной работе для модели Клейнрока впервые:

1. Найдены две различные системы уравнений, обе содержащие полную информацию о функциях распределения величин м>к{1), к = Ь},(>0;

2. Найдены две различные системы уравнений, обе содержащие полную информацию о функциях распределения векторов (Щ (0>Щ+1,к (*)>-•-Яг ' к =, г, t>0, в частности, вектора.

7),.м>г (()) с г = 2 в модели Клейнрока и с г > 2 в модели Л/г|Сг|1|оо с относительными приоритетами;

3. Найдена функция распределения вектора (Т1(и1)г., Тг1(иг1)) при 0<�щ<.<�иг1;

4. Найдены рекуррентные уравнения, определяющие стационарные функции распределения величин векторов к =, г, при и рекуррентные уравнения для стационарных средних времен ожидания;

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

— 8 В модели Джуна изучены Т^и), к =, г, и>О, и стационарное время ожидания 1-вызова.

Методы анализа. Для изучения и (щ (0'-,'Пк+1,к (?)>~-:>'Пгк (*У) > к = 1, г,? > 0, развит метод вероятностной интерпретации интегрального уравнения Такача и предложен новый метод, основанный на приеме введения дополнительных событий.

Разработан метод сведения вектора (Г1(м1),., Гг1(мА.1)), О <�щ<.<�иг1, к той же характеристике при дисциплине относительных приоритетов со специфическим ростом интенсивностей потоков, позволяющий использовать известные методы.

Предложен способ предельного перехода в уравнениях для м>к{1) и (ч>к (0>т1к+, к (0т—'1Г1гк (0) > к = 1, г, использующий приемы математического анализа.

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

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

Вид результатов обеспечивает их практическую реализацию на.

ЭВМ.

Структура, объем. Работа изложена на 114 страницах. Состоит из трех глав, приложения, списка литературы из 36 наименований, содержит 7 рисунков.

Нумерация параграфов и формул в каждой главе своя, рисунковсквозная.

§ 2. Содержание работы.

Вводная глава состоит из четырех параграфов. В § 1 обоснована актуальность тематики, отмечены новизна и ценность работы. Основные результаты сформулированы в § 2. В § 3 изложены методы анализа м>к (7), к = Ц-,? > О, при дисциплине относительных приоритетов. В § 4 методы предыдущего параграфа развиты для изучения вектор-процессов к = и, ^ — 0> при дисциплине относительных приоритетов.

1. Бронштейн О. И., Духовный И. М. Модели приоритетного обслуживания в информационно-вычислительных системах. — М.: Наука, 1976, 220 с.

2. Гнеденко Б. В., Даниелян Э. А. и др. Приоритетные системы обслуживания. -М.: МГУ, 1973,279 с.

3. Григорян Г. С. Многомерные предельные теоремы в стуктурно-сложных приоритетных моделях. Дисс. на соиск. уч. степени канд. физ. — мат. наук., М.: МИЭМ, 1982, 113 с.

4. Даниелян Э. А. Приоритетные задачи в системах обслуживания одним прибором. М.: МГУ, Серия: стат. и стох. сист., вып. 13, 1971, 120 с.

5. Даниелян Э. А. об одной системе с динамическими приоритетами. -Ученые записки ЕГУ, 1980, № 3, с. 19−25.

6. Даниелян Э. А. О классе дисциплин относительных динамических приоритетов в системе МГ|СГ (1|°°. Изв. АН Узб. ССР, серия физ. — мат. наук, 1980, № 6, с. 17−26.

7. Даниелян Э. А. Время ожидания в модели с категорийными во времени приоритетами. Кибернетика, Киев, 1980, № 6, с. 127−133.

8. Даниелян Э. А. Математическая теория приоритетных моделей МГ|СГ|1|°°.-Дисс. на соиск. уч. степени докт. физ.-мат. наук, М.: МГУ, 1981, 257 с.

9. Даниелян И. Э., Киселева Л. Г. Стационарные времена ожидания в модели Клейнрока. Обозрение прикл. и промышл. матем., 2001, т. 8, вып.2, с.

10. Даниелян Э. А., Иванов В. Длина очереди однолинейных систем обслуживания с приоритетом. Изв. АН Арм.ССР, Математика, XI, № 2, 1976, с.99−112.

11. Даниелян Э. А., Хачикян Х. З. Тенденции в изучении модели МГ|СГ|1|°° теории очередей. Ученые записки ЕГУ, 2001, № 1, с. 1−19.

12. Даниелян Э. А., Хостикян П. Т. Предельные теоремы в моделях Afr|Gr|l|°°с категорийными во времени абсолютными и относительными приоритетами при фиксированных загрузках. Ереван, Межвузовский сб. «Математика», 1982, вып. 1., с. 132−162.

13. Даниелян Э. А., Хостикян П. Т. Виртуальное время ожидания в модели с категорийными во времени абсолютными приоритетами. Препринт ВЦ АН Арм. ССР, Ереван, 1983, 40 с.

14. Джейсуол Н. К. Очереди с приоритетами. М.: Мир, 1973, 279 с.

15. Киселева Л. Г. О параметрической модели Джуна. Материалы 2-й Всероссийской научно практической конференции «Проблемы, инновационные подходы и перспективы развития курортно-рекреационного комплекса России». Сочи, 15−18 апреля 2001 г., с.323−342.

16. Киселева Л. Г. Вложенные цепы Маркова в Модели Клейнрока. Майкоп, 2001 г. 20с.П.Киселева Л. Г., Симонян, А Р. О периодах занятости в модели Клейнрока. Сб. «Проблемы теории и практики обучения математике», Санкт-Петербург, РГПУ, 2001, с. 152−153.

17. Клейнрок Л. Коммуникационные сети. Стохастичекие потоки и задержки сообщений. Наука, 1970, 255 с.

18. Клейнрок Л. Вычислительные системы с очередями. М.: Мир, 1979, 600 с.

19. Климов Г. П. Стохастические системы обслуживания. М.: Наука, 1966, 243 с.

20. Климов Г. П. Системы обслуживания с разделением времени. I. «Теор. вер. и её прим.», 1974, т. XIX, № 3.

21. Климов Г. П. Системы обслуживания с разделением времени. II. -«Теор. вер. и её прим.», 1978, т. XXIII, № 2.

22. Королюк B.C. Граничные задачи для сложных пуассоновских процесов. Киев: Наукова Думка, 1975, 139 с.-113.

23. Малинковский Ю. В. Стационарное функционирование приоритетных систем массового обслуживания. Дисс. на соиск. уч. степени канд. физ. — мат. наук, Вильнюс, 1980, 133 с.

24. Прабху Н. У. Стохастические процессы теории запасов. М.: Мир, 1984, 184 с.

25. Сандрян С. Н. Анализ модели Прабху. Дисс. на соиск. уч. степени канд. физ. — мат. наук, Ереван, 1991, 136 с.

26. Симонян А. Р. Предельные теоремы в модели Прабху при фиксированных загрузках. Дисс. на соиск. уч. степени канд. физ. — мат. наук, Ереван, 1991, 119 с.

27. Соколов И. А. Совместное распределение времени ожидания вызовами различных приоритетов. Изв. АН СССР, Техн.киберн., № 2, 1978, с. 104−110.

28. Ушаков В. Г. Аналитические методы исследования приоритетных систем обслуживания. Дисс. На соиск. Уч. степени доктора физ.-мат. Наук, М.: МГУ, 1995', 2£$с.

29. Феллер В.

Введение

в теорию вероятностей и её применения. Т.2. М.: Мир, 1984, 751 с.

30. Фихтенгольц Г. М. Курс дифференциального и интегрального исчисления. I (изд. 6) — И (изд. 6) — III (изд. 4). М.: Наука, 1966.

31. Bagchi U., Sullivan R.S. Dynamic Non-Preemptive Queues with General Linearly Increasing Priority Function. Oper. Res., v. 35, 1985, p. 1278 -1298.