Системы массового обслуживания ограниченной емкости и их приложение к анализу информационно-вычислительных систем тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

В в е д е н и е

Глава I. Однолинейная система массового обслуживания с ненадежным прибором. II

§ I.I Введение . II

§ 1.2 Описание системы и обозначения

§ 1.3 Система с накопителем неограниченной емкости.

§ 1.4 Система с накопителем ограниченной емкости

§ 1.5 Вычислительные алгоритмы.

Глава 2. Системы массового обслуживания с накопителем сложной структуры.

§ 2.1 Постановка задачи.

§ 2.2 Основные типы структур накопителей.

§ 2.3 Стационарное распределение марковского процесса.

§ 2.4 Метод расчета нормирующей константы и вероятности потерь для полнодоступной схеш с индивидуальными потолками.

§ 2.5 Метод расчета стационарных характеристик в общем случае

Глава 3. Анализ некоторых информационно-вычислительных систем.

§ 3.1 Однофазные СМО как модели информационновычислительных систем.

§ 3.2 Анализ структуры буферной памяти.

3 а к л го ч е н и е.

Л и т е р а т у р а.

П р ж л о ж е н и е I.

Теория массового обслуживания (ТМО) широко применяется на этапе проектирования и при анализе функционирования информационно-вычислительных систем (ИБС), которые на современном этапе представляют собой объекты от микро и мини ЭВМ до сетей ЭВМ и сетей передачи данных (ПД). За последнее десятилетие накоплен большой опыт создания и эксплуатации сетей ЭВМ и сетей ГЩ. За это время были выявлены многочисленные случаи возникновения тупиковых ситуаций,раз-личного рода блокировок и ухудшения производительности сетей, не предусмотренные при проектировании. Это объясняется тем, что практика часто опережала теорию и реальные системы создавались прежде, чем достигалось понимание всех нюансов их функционирования.

Исследования в области сетей ЭВМ направлены в основном на выбор топологии сети и пропускной способности каналов ЦЦ, выбор маршрутов передачи информации, анализ производительности узлов коммутации (УК) и структуры буферной памяти (БП), управления потоками и др.[^5";16,<#|Резкое усложнение архитектуры ИВС требует постоянного привлечения все более сложных моделей систем и сетей массового обслуживания (СМО, СеМО) для адекватного описания существенных черт режима функционирования проектируемых комплексов и существующих систем. На этапе проектирования аналитическое и имитационное моделирование является единственным способом оценки производительности создаваемой системы. Моделирование используется для выбора конфигурации ИВС; для оперативного управления функционирования ИВС в реальном времени; при модернизации и расширении системы и пр. Ввиду большой сложности реальных систем, их анализ обычно проводится путем выделения из их структуры компонент, для которых составляются математические модели. Наряду с таким, подходом применяется и комплексное изучение ИБС, учитывающее структуру в целом.Оба подхода развиваются одновременно, однако первый подход получил большее развитие.

Теория ВС еще недостаточно разработана, особенно в части оценки производительности ВС (диалоговых и реального времени) в условиях случайной загрузки. Эти вопросы ставятся и частично решаются в работах Л.Клейнрока , Л.Н.Королева , О.И.Авена и др. Д.Феррари L^l и ряда других советских и зарубежных авторов. В качестве обобщающего труда в области ТМО следует отметить двухтомный справочник, подготовленный коллективом авторов из ГДР и СССР под редакцией Б.В.Гнеденко и Д.Кенига •

Целый ряд задач, который появляется на этапах проектирования и эксплуатации ИБС, связан с исследованием процесса буферизации и определением его оптимальных характеристик. Основной целью таких исследований, является выработка методов защиты системы от перегрузок, для чего необходимо решить вопросы выбора объема буферной памяти (БП), ее оптимальной организации и стратегии ее использования для управления информационными и служебными потоками. При решении задач такого типа и построении соответствующих математических моделей чаще всего используются СМО ограниченной емкости. Для определения вероятности блокировки и требуемого объема БП часто бывает достаточно ограничиться d- -линейной, К -потоковой СМО с ограниченным накопителем и приоритетами разных видов. Для сокращения записи будем кодировать рассматриваемые системы по схеме используя обозначения Кендалла и несколько дополняя их по ходу изложения UjHl . Здесь на месте соответствующих букв приводятся характеристики: А - потока, В - длительности обслуживания,С числа приборов, "Ь - емкости накопителя, £Г - дисциплины обслуживания в СМО. Для нескольких входящих потоков заявок для указания дисциплины обслуживания вводится символ •fj , где нижний индекс указывает дисциплину выбора из очереди на обслуживание, а верхний - дисциплину постановки в очередь, которая имеет смысл только при ограниченной емкости накопителя. При этом означает относительный приоритет (без прерывания обслуживания), абсолютный приоритет (с прерыванием обслуживания). Если jaD , то при заполненном накопителе теряется вновь поступившая заявка,j-2 из накопителя вытесняется заявка меньшего приоритета.

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

Для нужд практики часто при переходе к математической модели приходится отказываться от предположения о марковости системы и при анализе использовать более общие классы случайных процессов такие, как полумарковские, регенерирующие, кусочно-линейные, марковские процессы восстановления и др. Введением в эту проблематику могут служить работы Е.Цинлара , В.С.Королюка и А.Ф.Турбина [З^З , Р.Пайка [бЗ^б^]. Обширная библиография имеется в обзоре [2,6] .С указанными классами процессов тесно связаны также регенерирующие процессы с зависимыми циклами регенерации .

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

GljMl^l^ и работу Дж.Риордана , в которой наряду с другими результатами получено стационарное распределение длины очереди в СМО типа MlGHlt . В этой области отметим также работы [S^CH^iHj^S^], где были использованы некоторые из указанных выше классов случайных процессов. Малоизученными здесь являются приоритетные СМО ограниченной емкости. Укажем на работы [5^0,2,0^3 в которых наряду с другими результатами получены и рекуррентные алгоритмы, например, для СМО типа Несмотря на их сложность, дальнейшие исследования в этой области представляют несомненный интерес, так как приоритетная передача пакетов и сообщений часто применяется в вычислительных системах и сетях Щ.

Актуальным является также вопрос о связи характеристик СМО ограниченной и неограниченной емкости. Первый результат в этой области был получен Г.П.Климовым в (.ZtjbiJ для финального распределения вложенной цепи Маркова СЦМ) для СМО типа MlftHI^- с ненадежным прибором. Обобщение этого результата для ЦМ с квазиверхнетре-угольной матрицей переходных вероятностей содержится в работе [4О* Дальнейшее развитие этот вопрос получил в работах , где показана связь между стационарным распределением длины очереди для СМО ограниченной и неограниченной емкости. В этих работах рассмотрены системы типа и м?в(fi^ii|% (см. § I.I).

В последнее время появился ряд работ, посвященных анализу многопотоковых многолинейных СМО с общим накопителем сложной структуры. В постановочном плане основополагающей здесь является работа Л.Клейнрока и Ф.Камоуна . Работы этого направления предназначены для решения задачи выбора оптимальной структуры БП узла коммутации в сети ЦЦ. Критерием оптимальности здесь является,например, вероятность блокировки УК, которую требуется минимизировать. Подробнее физическая и математическая постановка задачи содержится в § 2.1 и § 2.2. Интересные результаты в этом направлении получены в работах . В них рассматриваются некоторые частные случая, для которых удалось получить простые аналитические результаты в замкнутой форме. Недостатком перечисленных работ является отсутствие унифицированных вычислительных алгоритмов для расчета стационарных характеристик СМО. Такие алгоритмы в указанных работах получены лишь для частных случаев.

Отметим одну особенность рассматриваемых СМО, которая заключается в том, что стационарное распределение марковского процесса, описывающего их функционирование, обладает свойством мультипликативности: ^ р(Ц) = ci П(щ) где К - число входящих потоков; - число заявок потока I в СМО 9 isJjK ; С - нормирующая константа; -некоторые функции. Аналогичным Свойством обладает стационарное распределение числа заявок по узлам экспоненциальной СеМО [^5*5] , 'а для них известен целый ряд эффективных : рекуррентных алгоритмов IjS^djSPjtfj&rl. По равнению с результатами этих работ задача получения алгоритма вычисления стационарных характеристик многопотоковых СМО, является более общей, так как содержит ряд дополнительных параметров. Задача получения вычислительных алгоритмов для рассматриваемого класса систем была решена в работах Г.П.Башарина и К.Е.Самуйлова » где также предложена методика вывода подобных алгоритмов. Далее эта методика была распространена автором на задачи расчета характеристик неоднородных СеМО и применена при анализе структуры БП в УК сети ОД.

Диссертация состоит из трех глав. Первая глава посвящена анализу СМО типа I ^ с ненадежным прибором и одной ее модификации (СМО типа M\B|G.G»(/l|*'||>( ), которая предназначена для использования в качестве математической модели фрагмента специализированной сети ЦЦ. В первом и втором параграфах главы обсуждается постановка задачи и вводятся необходимые понятия и обозначения. В § 1.3 рассматривается случай ос . Получены производящие функции для стационарного распределения длины очереди в произвольный момент времени, а также для финального распределения ЦМ, вложенной как по моментам ухода из системы заявок, так и по моментам окончания восстановления прибора. Эти результаты являются подготовительными по отношению к § 1.4, где формулируется и доказывается основной результат главы, указывающий на связь стационарных распределений длины очереди для случаев t < аа и t-o<? (теорема 1.4).

В § 1.5 получены рекуррентные алгоритмы для расчета стационарного распределения длины очереди в СМО типа М»Б|£,б> \ 4н с ненадежным прибором. В первой главе используются методы вложенных ЦМ и марковских процессов восстановления для СМО типа с ненадежным прибором, а также аппарат линейчатых марковских процессов для СМО типа

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

В последней третьей главе показано применение рассматриваемых моделей и полученных результатов к анализу некоторых ИВС, а также приводится численный анализ. В § 3.1 демонстируется применение СМО типа при анализе функционирования системы сигнализации № 7 МККГТ (Международный консультативный комитет по телеграфии и телефонии). Эта система по своей сути является специализированной системой В § 3.2 на численном примере и с помощью моделей главы 2 показывается, что правильный выбор структуры БП в УК сети ЦЦ дает возможность улучшить пропускную способность узла при больших нагрузках. Кроме того, в этом параграфе предлагается метод анализа структуры БП, основанный на теории неоднородных СеМО. Этот метод дает возможность с высокой степенью детализаций учд*ывать весь процесс обработки пакетов данных в УК. Предложенный здесь вычислительный алгоритм основывается на алгоритмах второй главы. Полученный автором результаты использовались в ЦНИИ связи Минсвязи СССР для оценки качественных характеристик систем сигнализации телефонной сети СССР, что нашло свое отражение в публикациях с участием автора [б, » отчетах , а также подтверждается соответствующим актом о внедрении{Приложение I).

ЗАКЛЮЧЕНИЕ

В заключение сформулируем основные результаты работы:

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

2. Получены рекуррентные алгоритмы для расчета стационарного распределения длины очереди в СМО с ненадежным прибором.

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

4. Получены рекуррентные алгоритмы расчета стационарных характеристик многолинейных марковских СМО с накопителем сложной структуры.

5. Проведен анализ некоторых информационно - вычислительных систем с помощью СМО ограниченной емкости. Разработаны програм-ные средства для реализации на ЭВМ полученных алгоритмов

1. АВЕН О.И., ГУРИН Н.Н., КОГАН Я.А. Оценка качества и оптимизация вычислительных систем. М., Наука, ГРФМЛ, 1982, 468.

2. АНДРОНОВ A.M. Численный метод расчета марковских систем обслуживания. Тр. 3-й Всес. школы по автоматизированным системам массового обслуживания. Изд. ВЦООП, Винница, 1981,

3. АРТАМОНОВ Г.Т., БРЕХОВ О.М. Аналитические и вероятностные модели функционирования ЭВМ. М., Энергия, 1978, 320.

4. БАШАРИН Г.П. О расчете буферной памяти в вычислительных системах с несколькими входящими информационными потоками. Сб. Системы управления и коммутации, М., Наука, 1965, 24 41.

5. БАШАРИН Г.П. Об обслуживании двух потоков с относительным приоритетом на полнодоступной схеме с ограниченным числом мест для ожидания. Изв. АН СССР, Техническая кибернетика, 1967, № 2, 7286.

6. БАШАРИН Г.П. О пуассоновских обслуживающих системах с абсолютным приоритетом и обратной связью. В кн. Массовое обслуживание в системах передачи информации. М., Наука, 1969, 3 20.

7. БАШАРИН Г.П., ГРОМОВ А.И. Матричный метод нахождения стационарного распределения для некоторых нестационарных СМО. Автоматика и телемеханика, 1978, № I, 29 38.

8. БАШАРИН Г.П., ЖАРКОВ М.А., НАУМОВ В.А., САМУЙЛОВ К.Е. Математическая модель системы сигнализации If5 7 при базовом методе защиты от ошибок. Электросвязь, 1983, № II.

9. БАШАРИН Г.П., КУРЕНКОВ Б.Е. Исследование одной СМО с дискретным временем. Изв. АН СССР, Техническая кибернетика, 1983, №6.

10. БАШАРИН Г.П., САМУЙЛОВ К.Е. Об однофазной системе массового обслуживания с двумя типами заявок и относительным приоритетом Изв. АН СССР, Техническая кибернетика, 1983, № 3, 48 56.

11. БАШАРИН Г.П., САМУЙЛОВ К.Е. О двух методах анализа однолинейных систем массового обслуживания с ограниченным накопителем. Тр. У1 Всес. школы-семинара по вычислительным сетям, Москва -Винница, 1981, Часть II, 75 81.

12. БАШАРИН Г.П., САМУЙЛОВ К.Е. Математическая модель одной системы передачи данных с синхронизирующими сообщениями. Тр. 1У Всес. совещания по информационным сетям (ВСИС-1У). М., Наука, 1981, 6-7.

13. БАШАРИН Г.П., САМУЙЛОВ К.Е. Об оптимальной структуре буферной памяти в сетях передачи данных с коммутацией пакетов. Препринт АН СССР, Научный совет по комплексной проблеме "Кибернетика", М., 1982, 70.

14. БАШАРИН Г.П., БОГУСЛАВСКИЙ Л.Б., САМУЙЛОВ К.Е. О методах расчета пропускной способности сетей связи ЭВМ. Электросвязь. Т. 13 (Итоги науки и техники ВИНИТИ АН СССР), М., 1983 , 32 106

15. БАШАРИН Г.П., ХАРКЕВИЧ А.Д., ШНЕПС М.А. Массовое обслуживание в телефонии. М., Наука, 1968, 246.

16. БЕЖЕВ Ю.К. Линейчатые марковские процессы и их приложения к задачам теории надежности. Тр. У1 Всес. совещания по теории ве-вероятностей и мат. стат. Вильнюс, I960. Гос. иэд-во полит, и науч. лит. Лит. ССР, 1962, 309 323.

17. БОЧАРОВ П.П. Об однолинейной обслуживающей системе с ограниченным числом мест для ожидания и приоритетами. Проблемы передачи информации, 1970, № 6, вып. 3, 70-77

18. БОЧАРОВ П.П. Анализ системы M^l^a, Hl*^ с относительными и абсолютными приоритетами. В кн. Численные методы решения задач математической физики и теории систем. М., УДН, 1979.

19. БОЧАРОВ П.П. Анализ бесприоритетной однолинейной системы с ограниченной очередью и заявками нескольких видов. Изв. АН СССР, Техническая кибернетика, 1970, № 6.

20. БОЧАРОВ П.П., НАУМОВ В.А. 0 некоторых системах массового обслуживания конечной емкости. Проблемы передачи информации, 1977, т. ХШ, вып. 4, 96 104.

21. ГНЕДЕНК0 Б.В., КОВАЛЕНКО И.Н. Введение в теорию массового обслуживания. М., Наука, 1966, 368.

22. ПЩЦЕНК0 Б.В., ДАНИЕЛЯВ Э.А. .ДИМИТРОВ Б.Н., КЛИМОВ Г.П., МАТВЕЕВ В.Ф. Приоритетные системы обслуживания. М., изд.МГУ, 1973, 447

23. Gnede.b$o i&.ViA , кон'^Ъ. СИ**!) НьъА^иЛ Лен.

24. BedienungsJ-heob/'e ■ Ba**f 1 (г) . Ьих^/н,aiadtvul* Vet^acj , , (pfc>)

25. КЕНИГ А., РЫКОВ В.В., ШМИДТ Ф. Стационарные системы массового обслуживания с зависимостями. Теория вероятностей. Математическая статистика. Теоретическая кибернетика. Т. 18 (Итоги науки и техники ВИНИТИ АН СССР), М., 1980, 95 186.

26. КЛЕЙНРОК Л. Вычислительные системы с очередями. М., Мир, 1979, 600.

27. КЛИМОВ Г.П. Стохастические системы обслуживания. М., Наука, 1966, 244.

28. КЛИМОВ Г.П. Системы обслуживания с разделением времени. I. Теор. вер. и ее применение. Т. 29, № 3, 1974.

29. КЛИМОВ Г.П. Системы обслуживания с разделением времени. II. Теор. вер. и ее применение. I. 32, № 2, 1978.

30. Bedi€rn<a4gsf>%0ZredSe., A-hcioleWieу/еь&гд . бегв;* >144$.32. fay»cw 6.Р. , AJ<xflaj>e+jah Sm'txmvf S.*• keg£Hezc(+ixLe fiwezszej wrfh Mav/lov-deftekatw/ ejctteJ aud iU/г afa&ea-f/ous . AfaU uual S-bi.j Vet

31. К0Р0ЛЮК B.C., ТУРБИН А.Ф. Полумарковские процессы и их приложения. Киев, Наукова думка, 1976

32. КОРОЛЕВ Л.Н. Структуры ЭВМ и их математическое обеспечение. М., Наука, Г§МЛ, 1978, 352.

33. ЛЫСЕНКОВА В.Т. Анализ многолинейной системы массового обслуживания с ограниченной очередью и приоритетами. В сб. Проблемы распределения информации, М., Наука, 1973, 15 27.

34. НАГАПЕШН Р.Ш. Пакетная обработка заявок в системе Молодой науч. работник ЕГУ, 2(34), 1981

35. НАУМОВ В.А. Об однолинейной системе с ограниченным накопителем и заявками нескольких видов. В сб. Модели систем распределения информации и их анализ. М., Наука, 1982

36. РЙОРДАН Дж. Вероятностные системы обслуживания. М., Связь, 1966, 184.

37. САМУЙЛОВ К.Е. Об одном методе расчета характеристик неоднородных сетей массового обслуживания. Материалы У1 конф. молодых ученых УДН (мат., физ., хим.) ВИНИТИ АН СССР, 1983

38. САМУЙЛОВ К.Е. Сети массового обслуживания с ограничениями и их приложение к анализу структуры буферной памяти. Тр. УШ

39. Всес. школы-семинара по вычислительным сетям.М.,1983

40. САМУЁЯОВ К.Е., МОНТЕНЕГРО В. К расчету вероятности потерь для одной многолинейной многопотоковой системы массового обслуживания с общим конечным накопитнлем. Сб. научн. трудов "Вычислительная математика и информатика". М.,УДН,1983,71-75

41. ТАКАЧ Л/ Некоторые вероятностные задачи в телефонии. Сб. переводов "Математика",4:6,I960,93-144

42. ФЕРРАРИ Д. Оценка производительности вычислительных систем. М.,Мир, 1981, 576

43. ШНЕПС М.А. Системы распределения информации. Методы расчета. Справочное пособие. М., Связь, 1979, 34445. руководящий документ по общегосударственной системе автоматической телефонной связи. (0ГСТФ),М.,Радио и связь,1982,143

44. Разработка и анализ математических моделей сети ОКС. Отчет по научно-исследовательской работе. Л гос.per. 80010704, Шифр темы 8220,М., УДН, 1981

45. Исследование качественных характеристик ЕС ОКС телефонной сети СССР. № roc.per.II82.8048104,Шифр теш 282.,М.,УДН,19834S. HcLsieH A e.+a€£. Open , c&seef аиа/ ntixe a/ h&iu/o'c'is o^ fyu-eues Wrt& c/i^e^euJ a/s^okueis . JT Ass. Coutfiu-f. Mac

46. Зидеь P.T. aT^o&ftn* CtfoS-et/ pu-ecs-e/tcf /ze-^uSotd-? ех-^оь-еи^/о-^ ScbV^s. (?ошшим. ACM , , v. j

47. Btuei? C.j ^oLufiv-Z/eua (f ДЬсу'гащт / ft о SjssJ-eucs sezi&s. /{/съ7% ,

48. Sen VO' Ты/ftc fated d/ns^us/M/^ o^W^/pr

49. Ui daJ-a and ёеш^а^е* /ге-l^t/s. ~ te^o-г^ въ studies, lu C&uo>es-£oe< fyeoy • " 2*jr?/-Swiickiiuj фиг/ Ъа^а Uni^s/^1. Sc'tHs* , к %ybiksъеуиуни/ fa тсмяЬш fre/sso»)^^

50. AuJ tOU^OAA-l- cwifeufv&fes, TzovS.fib r. £e>ta/>. 196-7; v. /Г;

51. Sf. Ji&ctcf Ai. &u//ez /uaua^etueuJ и* лрас1. Л/

52. Ma А* не* St, X, Me*'' К P^v ** ^ ** *teffaeAestS c* tftfs ^ JFfF 7z*«s.1. M . , i/.Ж; .fifes Ы ашхе/*/ М'Я ^^^^J?

53. Scii/cis , ^fata* ■ ef у ^^1. V. ; №6; St7~5b2 j. A/ew/s M.F.j kuncat rf. dti^/Ami £

54. Sphce уаелел f'fo Wet f&u/S • /У&иа^.1. Зычнее , /38/ M^MS*

55. Vazdfl/ rz^^u/atf ^'Zo&zss^s . ■ J1.. 3S-; A/24; W6-/76V. ^/ -ess tf&T1'^fi^dm. АатУ1. U/''Л Mtf t/e^a' :и-/-. Jeuz*.

56. Aes. 2W. , v. /0; AS* 3; -ЛЭ4ed-' ft tt ha ftf/i*^ ^CS-^AU .62. Wiiia^siS; i.и&я-г Off Г

57. U/ijty £ "/ZUC/cczjl . /Т4^ /£#0 ^ is. ^