Введение к работе
Актуальность работы. Характерной особенностью вычисли-тельных систем, функционирующих в режиме разделения времени, является наличие специальных алгоритмов диспетчеризации, которые позволяют уменьшать время пребывания в системе коротких заданий за счет задержи в очереди перед процессором незавершенных длинных. Анализ характеристик производи-телыюсти вычислительных сетей и систем, сетей связи с пакетной коммутацией, многопроцессорных ЭВМ и ряда других технических систем, функционирующих на основе принципа разделения времени (СРВ), сводится к исследованию систем массового обслуживания (СМО), специальные алгоритмы диспетчеризации в которых моделируются при помощи так называемых дисциплин разделения времени, в частности, дисциплиной обслуживания в обратном порядке с прерываниями.
Существующие в настоящее время методы исследования подобного рода моделей массового обслуживания развиты преимущественно для систем с накопителем неограничеішой емкости при пуассоновском входящем потоке. Однако, в реальных СРВ процесс обработки заданий происходит, как правило, при априорно неизвестных интервалах времени между поступлениями заданий, длительностях их обработки и при реальных ограничениях на объем буферной памяти. В этом случае анализ соответствующих моделей становится сложнее и требует разработки новых методов и подходов. Таким образом, поставленная в диссертации задача исследования поведения характеристик систем массового обслуживания при дисциплинах обслуживания в обратном порядке с прерываниями, принадлежащих к классу дисципліш разделения времени, представляется актуальной как для непосредственного использования получаемых результатов при анализе характеристик производительности СРВ с подобным алгоритмом диспетчеризации, так и с точки зрения их применения для приближенного расчета более сложных моделей вычислительных систем, при тестировании результатов имитационного моделирования, а также для использования таких моделей в качестве оценочных для других моделей СРВ.
Целью диссертационной работы является:
Г. Развитие методов анализа стационарных процессов очередей в однолинейных СМО с ограниченным накопителем, описываемых распределениями фазового типа, при различных дисциплинах обслуживания в обратном порядке с прерываниями.
2. Разработка на основе полученных теоретических результатов комплекса программ для анализа стационарных показателей производительности однолинейных СМО фазового типа с ограниченным накопителем при различных дисциплинах обслуживания в обратном порядке с прерываниями.
Результаты, выносимые на защиту, определяются поставленной целью и состоят в следующем:
1. Для анализа очередей в однолинейных СМО конечной
емкости, описываемых распределениями фазового типа, при дис
циплине LCFS с прерываниями, учитывающей различные варианты
обслуживания прерванных заявок, развиты методы, на основе
которых выведены рекуррентные матричные формулы для расчета
стационарного распределения очередей, разработан вычисли
тельный алгоритм получения начальных моментов времени пре
бывания заявок в системах, получены выражения для стацио
нарной функции распределения интервалов между выходами
заявок из СМО, а также ряд показателей производительности
системы.
-
Для анализа стационарных характеристик однолинейной СМО конечной емкости с распределениями фазового типа при дисциплине обслуживания LCPS с прерываниями входящего потока и обслуживания разработаны методы ее анализа и получено геометрическое представление распределения очереди, а также выведены выражения для основных показателей производительности СМО.
-
На основе полученных теоретических результатов разработаны комплексы программ для расчета показателей производительности однолинейных СМО конечной емкости при дисциплинах ЬСРЗ с прерываниями.
Методы исследования. Методы, применяемые в диссертаци-онной работе, базируются в основном на использовании теории случайных процессов, теории массового обслуживания и численных методах.
Обоснованность научных положений. Полученные в диссер-тации"результаты полностью обоснованы строгими математическими доказательствами и проведенным численным анализом.
Научная новизна работы заключается в развитии методов и разработке вычислительных алгоритмов для анализа очередей в однолинейных СМО конечной емкости с распределениями фазового типа при инверсионном обслуживании с прерываниями. В диссертационной работе впервые
при анализе стационарных характеристик однолинейных СМО конечной емкости при инверсионном обслуживании с прерываниями за счет использования распределений фазового типа учтена априорная неизвестность интервалов меиду поступлениями заявок в систему и длительностей их обслуживания;
получены аналитические выражения для основных показателей производительности однолинейных СМО конечной емкости с распределениями фазового типа и дисциплиной обслуживания в обратном порядке с прерываниями при повторном обслуживании прерванной заявки и при ее дооОслуживании;
проведено исследование стационарных характеристик однолинейной СМО конечной емкости, описываемой распределениями фазового типа, с дисциплиной обслуживания в обратном порядке с прерываниями входящего потока и обслуживания.
Выводы второй главы для случая дисциплины LCFS с прерываниями и дообслуживанием прерванной заявки обобщают ранее известные результаты, все остальные результаты являются новыми.
Практическая ценность работы. Полученные в диссертации результаты могут быть использованы при аналитическом моделировании вычислительных сетей и систем, узлов сетей связи с пакетной коммутацией, многопроцессорных ЭВМ и других технических систем, в основе функционирования которых лежит принцип разделения времени. Результаты, полученные для систем с распределениями фазового типа, позволяют унифицировать вычислительные алгоритмы и учитывать большую информацию об исходных распределениях. Расчетные алгоритмы, разработанные в диссертации, доведены до програш!, которые включены з комплекс программ по расчету систем и сетей массового обслуживания, разрабатываемый в Российском уюшерсите-
те дружбы народов.
Реализация результатов работы. Исследование систем массового обслуживания с распределениями фазового типа при дисциплинах обслуживания в обратном порядке с прерываниями проводилось в рамках НИР "Разработка математических методов и алгоритмов анализа мультипроцессорных вычислительных систем, локальных и интегральных информационно-вычислительных сетей" (государственный регистрационный номер 01.9.10 033110), которая выполнялась в соответствии с координационными планами АН СССР.
Апробация работы. Материалы диссертационной работы докладывались на IV Международном семинаре но теории телетрафика и компьютерному моделированию (Москва, 1993), Всесоюзной научно-технической конференции: Микросистема-92 (Томск, 1992), IV Всесоюзном совещании по распределенным вычислительным системам массового обслуживания (Душанбе, 1991), VII, VIII, IX Белорусской зимней школе-семинаре по теории массового обслуживания (Гродно, 1ЭЭ1; Брест, 1992; Минск, 1993), XXVI, XXVII, XXVIII научных конференциях факультета физико-математических и естественных наук Российского университета дружбы народов (РУДН) (Москва, 1991, 1992, 1993), а также на научном семинаре кафедры теории вероятностей и математической статистики РУДН.
Публикации. По материалам диссертационной работы опуб-ликовано 9 работ, из них 2 в центральной печати.
Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы и приложения. Содержит 150 страниц текста и список литературы из Є? наименований .
