автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Оптимизация очередей в вычислительных системах

РГБ ОД

К К Яа правах рукописи

Тимофеев Евгений Александрович оптимизация очередей в вычислительных системах Специальность: 05.13.17- Теоретические основы информатики

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

1996

Работа выполнена в Ярославском государственном университете

Официальные оппоненты: доктор физико -математических наук, профессор В.В.Рыков, доктор технических наук, профессор С.Н.Степанов, доктор технических наук, профессор А.М.Цирлш

Ведущая организация - Российский Университет Дружбы Народов

Защита состоится " (> " 1996г. в^^час,

на заседании диссертационного совета Д 200.36.01 при Институт« программных систем Российской академии наук (15214( Ярославская обл. Переславль-Залесский, местечко Ботик, ИПС РАН).

С диссертацией можно ознакомиться в библиотеке ИПС РАН.

Автореферат разослан "3/ » 1996г.

Ученый секретарь диссертационного совета,

кандидат физико -математических наук В.Н.Юмагужин;

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Задача оптимизации' состоит в том» чтобы распределять требования (задания, поступайте в вычислительную систему) так, чтобы оптимизировать некоторый критерий. При этом вычислительную систему представляем следующим образом:

- на вход системы поступают потоки требований (заданий) нескольких типов; ,

- поступившие требования ставятся в неограниченные очереди; . - диспетчер (или планировщик заданий) распределяет

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

- по окончании обслуживания требования на процессоре оно либо покидает систему, либо пороадает новые требования, которые

: поступают в очереди. .

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

задаются рекуррентным, и даже пуассоновским потоком, в длительности обслуживания предполагаются независимыми и одинаково распределенными (для кандого типа). '

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

Подобным задачам теории очередей посвящено довольно большое число статей и монографий (Баварии Т.П., Климов Т.П., Лицеев В.В., Рыков В.В., Боксма 0., Ддайсуол H.R., Клейврок Л. и др.). Рассматриваемые п них задачи можно, охарактеризовать как изучение дисциплин обслуживания. А соответствующая оптимизационная задача сводится к классической постановке - оптимизации функции от нескольких переменных. ,

Однако как классические методы теории очередей, так и новые математические метода (Боровков A.A., Ыалшиев В.А., Боксма 0.,. Шассбергер Р. и др.) анализа систем позволяют . получать решение лишь в специальных случаях. Кроме, того, даже пайдя оптимальное (по некоторому критерию) решениа для рассматриваемой дисциплины остается неясным вопрос о том. является ли это решение оптимальным для всех других дйсцишш.

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

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

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

1) получить решение для более широкого масса вычислительных систем; '

2) получить роиешге, оптямалыгаэ по всем дисциплинам. Полученные результаты по оптимизации средних длин очередей в

вычислительных системах являются актуальными:

1. В алане развития новых подходов к реаешпэ подобных »задач.

2. В плане новых математических моделей вычислительных систем.

3. В плане получения повых алгоритмов' для повышения производительности вычислительных систем.

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

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

Научная новизна и положения, внюсикые на защиту. 1. Описан новый метод оптимизации средних длин очередей. Этот мотод состоит в следующем:

А. Строим множество всевозможных значений средних длин

очередей, называемое далее приоритетным;

Б. Исследуем его комбинаторную структуру и решаем оптимизационную задачу на этом множестве; , '

В. Находим дисциплину обслуживания, реализующую любу» точку приоритетного множег-ва.

2. Предлагаемым методом решены задачи оптимизации функции от средних дшш очередей для ряда'классических систем обслуживания, описываемых в известной символике Кендалла-Башарша как Ыо|Сп|1, 01|Мп|1, С1|Сп|1, Мп|Сп|ю, Ип|(5п|1 с ветвящимися штоками вторичных, требований.

3. Построены эффективные алгоритмы паховдешя решения оптимизационной задачи на приоритетном множестве.

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

Таким образом, теоретические исследования позволили. решить важные и конкретные задачи.

Теоретическая и практическая ценность. Работа теоретическая. . Разработанные методы применимы для достаточно широкого класса систем. Предлагаемые алгоритмы решения, в основном, эффективные. Результаты работы позволяют дать.ответ на практические вопросы о качестве оптимизаций очередей.

Апробация работы. Результаты работы докладывались на ряде . конференций "Проблемы теоретической кибернетики" (Иркутск, 1985)., "Системы обслуживания и сети связи" (Витебск, 1990),' . "Дискретная математика" (МГУ, 1986, ,1989, 1992, 1995), "Интеллектуальные среды" (МГУ,1995); на семинарах институтапроблем управления

- т -

РАН, МГУ, Вычислительного центра РАН, Ярославского государственного университета.

Публикации. Основные результаты диссертации опубликованы в 15 статьях.

Структура и объем работы. Диссертация состоит из введения, семи глав и списка литературы. Изложена на 293 страницах. Библиография - 84 наименования.

содержание работы

Во введения обосновывается необходимость исследований, проводимых в работе, излагается общий метод решения и краткое содержание работы.

В первой главе рассматривается система обслуживания с одним прибором, пуассоиовскш входным и ветвящимися вторичными потоками требований п типов с произвольной длительностью обслуживания. Такая система (предложенная Климовым Г.П., Китаевым М.Ю, Рыковым В.В.) позволяет более точно представлять программу, выполняемую вычислительной системой, как состоящую из некоторого набора подпрограмм, а не единого задания.

Для этой системы найдена дисциплина обслуживания, • при которой достигается минимум (локальный) произвольной функции Р{Ь .), зависящей от средних длин очередей Основными

примерами функций Г являются линейная и максимум из линейных, к которым могут быть добавлены линейные ограничения. Для таких функций.будет найден глобальный минимум. Ранее было известно решение только для линейной функции.,

Положим o - Í1,2...,п> м опишем параметры системы:

а) на вход системы поступает пуассоновский поток требований с интенсивностью х.;

б) поступившее требование с вероятностью эд (leo) поступает в очередь требований 1-го типа (э,* 0, Рп~ 1);

в) в каждый момент времени обслуживается только одно требование; прерывание обслуживания нв допускается;

г) длительности обслуживания требований - независимые случайные величины с функцией распределения Bt(t) (В((0) - 0) для требований 1-го тина (lea); будем предполагать, что

ъ. - / tdB.(t) < ь -'/ tadB.(t) < "о 1 ia о . 1 .

д) после завершения обслуживания требования 1-го тина с -

вероятностью q4 .Jci;ka,:.; ,kn) возникает набор к - (к,.Иг.....1сп)

вторичных требований, которые поступают в очереди требований соответствующего типа; обозначим через Q (в) » Q,(в.,2,,...в-)

1 I 1 3 О

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

aQ a3Q

Чи .< «р. .....V "<•» '

i i *

кроме этого, будем предполагать, что максимальное собственное

значение е матрицы Q » llqájll такое, что е. < 1;

е) после завершения обслукквания по набору (1,...,1 ),

- t Л

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

какое-нибудь требование, если хотя бы одна очередь не пуста;

я) требования одного тина обслуживаются в порядке поступления.

Будем предполагать, что выполнено. условие существования стационарного решгма

п

Р - £ Xßtr,(Q) <1. где г((а) - длительность обслуживания требования i-cco типа и всех поровденннх им требований до выхода их ira системы.

* Через ij обойяачин среднюю длину очереди для требований 1-ого т ла,

. т

L, - Ilm if 1 £t)dt.

1 1 ' •

Т->» 0

Требуется найти дисциплину обслуживания, при которой достигается минимум -функции F(bt,-..,I»n), зависящей от средних длин очередей L(, Для произвольной функции речь идет только о локальном минимуме. Однако основными практическими примерами функций F является линейные и максимум из линейных, к которым могут быть добавлены линейные ограничения. Для таких функций находится глобальпнй минимум. ■

Покажем применение предлагаемого метода для этой задачи 111. Д. Множество ¡1(0) всевозможных значений (L 5

I л

которые будем называть приоритетным многогранником определено в Теорема 2.1. Для любой, дисциплины обслухивакия ияеел. что величины L( - средние длины очередей требований 1-ого вата, i е о, удовлетворяют следугщил огракичениял: " 1^(0) - «{*».

leo

У Ь г.(5) г o(S), v S с а.

íes ' ,

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

*<(S) = JL4.i?ilS)+to»v

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

Б. Комбинаторная структура И(о) и оптимизация функций.

Лемма 2.2. Пусть выполнено условие > о v 1 6 q,

тогда побнокество решений' (1) является гранью разлерносш к у U(q) mazQa и только тогда, когда для него обращайтея в равенство неравенства из (1) для подтохеств St, S , ...,.S ' = о таких, что S с 5 с ... с S = Q.

1 2" пт к

Число граней ¡Г(й) равно 2"-2.- Sí(q) имеет ni вершин, каждую из которых можно задать перестановкой («1,...,яп)• элементов множества а. Вершины й(я) реализуются при относительных приоритетах. "

Для ранее решенной задачи минимизации линейной функции F дано новое геометрическое обоснование алгоритма и построен более эффективный алгоритм, имеющий трудоемкость на порядок (по п) меньшую.'Отметим, что трудоемкость алгоритма такая же как у алгоритма нахождения величин ^(а).

Задача нахождения локального, минимума произвольной функции Р(Ь',••••! ) решена применением метода эллипсоидов, который

основан на эффективном алгоритме решения задачи о' принадлежности точки й(о) (лемма 2.7).

В. Нахождение дисциплины обслуживания, реализующей любую точку if (Я).

В разделе 1.3 описана вероятностно-разделительная дисциплина [3], которая состоит в вероятностном разбиении исходных типов 'на N новых, и применении к новым N типам относительного приоритета. Таким обрезом, зга дисциплина имеет N - п непрерывных параметров и N - дискретных (перестановка, задающая относительный приор.:, ет новых типов). Поскольку размерность И(а) равна .1-1, то N ь 2п-1. Для N = 2п-1 приводится алгоритм нахождения параметров этой дисциплины [41, при которых реализуется любая заданная точка Щй). Этот алгоритм требует находить решение системы ™з п функциональных уравнений от п неизвестных nz .рвз. Для М = Зп-З • описан алгоритм, который требует находить решение системы из 1 функциональных уравнений от 2п-3 неизвестных один раз.

В разделе 1.'4 приведен пример, показывающий, что полученные результаты неверны для рекуррентного входного потока.

Все описанные алгоритмы реализованы на ЭВМ. ,

Во второй глава рассматривается классическая систем MJGJ1 с обслуживанием без прерывания, которая является частным случаем предыдущей (ветвление отсутствует).

Для этой системы твгасе решена задача минимизации (локальной) произвольной функции F(Lt,....Ьп), зависящей от средних длин очередей Ь4.

Воспользуемся предлагаемым методом и для этой задачи [21. А. Приоритетный многогранник й(о) задается следующим образом:

£ Ь1ЬМ = и(0).

(2) 160

2 Ь,ъм ^ <о(Б), *5сС 168

где функция ыСБ) достаточно просто выписывается в явном виде

здесь р1 = - загрузка прибора требованиями 1-ого типа;

У7о - математическое ожидание оставшейся длительности дообслуживания. Идея введения приоритетного многогранника для этой системы принадлежит Бронштейну О.И. и Духовному И.М.

Б. Комбинаторная структура й(а) й оптимизация функций.

Предположения леммы 2.2 (из главы 1) в этой системе всегда выполняются, поэтому ¿/(о) имеет такую же комбинаторную структуру, как в общем случае главы 1, и более того, М(о) является гранью полиматроида (многогранника, введенного и изученного Дк.Эдиоццсом). . '

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

8. Нахождение дисциплины обслуживания, реализующей любую точку М(о).

В разделе 2.3 для вероятностно-разделительной дисциплины, существенно упрощен'алгоритм нахоздения ее параметров по заданной точке, а именно: решение системы из п. функциональных уравнений

(которыэ для этой системы-являются квадратичными) заменено иа п решений квадратных уравнений от одной неизвестной 121.

В разделе 2.4 для введенных Л.Клейнроком приоритетов, зависящих от времени, найдены явные формулы для наховдения парвметров но любой заданной внутренней точке приоритетного многогранника 121.

Теорема 4.1. Пуст величины - удовлетворят (2),

причел неравенствал из (2) ноте сарогш и ^ i ... s Я , тогда параметры di, при. которых приоритеты, зависящие ст врелеш,

ияет средние времена ожидания W..........находятся по

следующему алгоритму. Нолагае я z = 1.

п

Для какЗого J = п, п-1, ..., 1 находил dj, решая уравнение

- n0/(1-p) . о,

запел находил г^ по правшу

z . = z - ой"1, j-» i J j '

п *

где R = Ц р.. ' 1 * ■ j

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

В разделе 2.5' для наиболее простых в применении вероятностных приоритетов доказана теорема о существовании параметров, при которых реализуется любая внутренняя точка М(о), и найдено решение для частной системы М2|Н|1 [53, Для наховдения

стационарных вероятностей нужно решить функциональное уравнение (р^У + р2хуг - (1+р)ху +■ Ч2х + qly). п(х,у) = = (х-у)^2п(х,0) - ц^Ю.У)) + р(1-р)(я1х + цгу - ху). где п(х,у) - неизвестная производящая функция (р - рЛ+ р2< 1, цг*= 1. pq2 & р2). Решение этого уравнения имеет следующий

вид:

Пусть у^х), У2(х) - корни уравнения (у,(1) = 1) р,хгу + р2хуг - (Нр)ху + цгх + - О,

р(1-р)(х-хг)(у1(х)- Уг(х))

а(х) = -'ч.^иь х)(у2{х)-х)—

= у;1 (г).

Тогда

0(0.» - „(НО ч-Д. $ «Щш.

*

г

где -»г - окружность радиуса г с центром в О и 1 < г < р"1. Таким образом, даже в этом простейшем случае решение довольно громоздко, а методы решения подобных уравнений для п * 3 неизвестны.

Все описанные алгоритма реализованы на ЭВМ.

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

величиной кванта. Пусть N - число квантов и я = {1,2,...,Ю.

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

A. Приоритетное множество Р всевозможных значений (Lj, ), с заданной точностью приближается проекцией

п

приоритетного многогранника ,Но).

Б. Задачи оптимизации функций на Р сводятся к оптимизации их на И(я). В частности получаем решение с данной точностью задачи минимизации линейной функции, для которой ранее были известны решения только для специальных случаэв.

B. Нахождение дисциплины обслуживания, реализующей любую точку Р. такие с данной точностью -дается вероятностно-разделительной дисциплиной, реализующей лвСую точку //(«).

Кроме этого, получены описания приоритетного множества Р для некоторых частных случаев. В системе M|G|1 с прерыванием Р является отрезком. Для некоторых классов распределений найдены границы этого отрезка в явном виде. Для системы H2|G2|1 с прерыванием разработанный алгоритм построения Р позволяет найти его для некоторых распределений в явном виде.

В т чтвертой главе рассматривается система GI|MJ1 с прерыванием обслуживания, т.е. на вход системы поступает рекуррентный поток требований с функцией распределения Ait); поступившее требование с вероятностью Э4 поступает в очередь требований 1-го типа 0, рг+...+ pn= 1); длительности обслуживания требований - независимые случайные величины с

-u t

функцией распределения В (t) = 1 - e .

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

A. Множество if (а) всевозможных значений (L ,...,Ь ),

1 п

является многогранником, задаваемым неравенствами (2), но функция u(S) находится как средзее время ожидания в системе GI|HM|1 с обслуживанием в порядке поступления (теорема 1.2). (НМ - гиперэкспоненциальное распределение). Нахождение u(S) сводится к нахождению |S| вещественных корней гладкой функции.

Б. Комбинаторная структура й(я) и оптимизация функций такие же как в системе MJGJ1. Следует отметить, что ранее решение было известно только для частного случая линейной функции и пуэссоновского входного потока.

B. Нэховдение- дисциплины обслуживания, реализующей любую точку «(о).

Вероятностно-разделительная дисциплина обслуживания переносится на систему GI|MJ1 с прерыванием обслуживания, если заменить в ней относительный приоритет новых типов требований на абсолютный.' Описанный в 14] алгоритм нахождения параметров этой дисциплины, при которых реализуется любая заданная точка М(а), справедлив и для этой системы.

В пятой главе рассматривается система GI|Gn|1 с обслуживанием без прерывания, т.е. на вход системы поступает рекуррентный поток требований с функцией распределения A(t); поступившее требование с вероятностью рi поступает в очередь требований 1-го типа (Ps> 0, Рг+...+ р^- 1); длительности

обслуживания требований - независимые случайные величины с функцией распределения В1 (1;).

Рассмотрим возможности применения предлагаемого метода в этой системе для нахоэдения минимума (локального) функции от средних длин очередей Г2,8}.

А. Множество И(о) всевозможных значений (!,...,£), в

I п

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

требования, находящегося на приборе в момент времени 1; может не выполняться равенство

Ни \ } х0(1) (И; - Ига ^ }.Ехо(1;) йХ.

I - > Ю О 1"->Ю о

В разделе 5.1 рассматривается система Б1|В4|1, для которой Это равенство не выполнено. Параметры этой системы следующие: требования поступают с постоянным интервалом длины 3; каждому поступившему требованию с вероятностью' =1/4 приписывается Т1Ш,равный 1 (1 = 1, 2, 3, 4). Длительности обслуживания постоянны для кавдого типа и имеют значения 1, 1, 2, 6. Отметим, что для этой системы 'минимум линейной функции Ь достигается не нри относительном приоритете.

В случае одинаковых распределений длительностей обслуживания кавдого типа М(а) является приоритетным многогранником, задаваемым неравенствами (2) (теорема 2.1), но функция и(Б) находится как среднее время ожидания требований первого типа в системе И|С2|1 с относительным приоритетом первого типа. В общем случае решение для этой системы неизвестно, а найдено

решение для системы GI|HM2|1 (EM - гиперэкспоненциальное

распределение) 18J.

Пусть для этой системы: х - вероятность требования первого

типа (1-х - второго); B(t) - 1- £ q й'"il, где £ q - 1, q * О,

j-i 1 j.i 1 1

N t.»,

(j, < цг < ••-< b - £ q/íijí А О), В (s) - преобразования

Лапласа-Стилтьеса функций Ait), BitÏ. тогда M(S) = W ( I p ), Se (1.....n),

íes

где Wi(x) - функция, определяемая следующим образом

" м г 1 Ьг4 -, q С,

И (х) - I £ ( —-+-í—J -s-J-j- .

1 j.i ..А л.П-rj) (1-rJ)2-' гг (x+rJ-xrj)A*(^i)

Величиин г¡ находятся как корни уравнения

и q (x+r-xr) х D (г)

Г(г) -1-Е -i--^--0;

•t. г-хА*(м.) -С1-х)А*(м.)г

(в п.5.2.1.4 доказано, что это уравнение имеет N вещественных корней).

Функции D^ír) вычисляем по.формуле

n f В (г) , л

Ъ ir) - I ' '— i A*(h (г)) - к"1ц )|. A (i —hj(r) I ' • ¡

где

1 - В (-Ь (г))

е (г) = --г—Ь- ,

J т1(г)в'(-ы1(г))

а 1^(г) - корни уравнения

1 - гВ*(-Ь) = 0.

(в п.5.2.1.3 доказано, что это уравнение имеет ровно Н

вещественных корней).

Величины С1 находим из уравнений (1 = 1.....Ы)

C, S PoA*(tJk) - Go Rn

- » ¿ ---з;--- i

х+г1-хг1 k-1 1 - (1-x)A*(^k) Skl

где

N H f Г

H. , = П П I ----A" iii)

kl i.i j.i V x+r -xr 1

J__4*

x+Vxri

- A*(M

S = П n ÍA*(u) , А*(л,)] [—Ь- - —^-].

1,1 j-i i.iA x+rrxr. x+ri_xri J

№ i¡ii J J

Величину Co находим из уравнения

и и а С.

1 = р + V V • ---¡--- .

° jt, 1 - г г - хА )- (1-х)А*(л )г

j j a a j

Вероятность po отсутствия требований в. системе в момент поступления нового требования определяется как

и

Ро - П Г^1, -к * 1

где гк - корил уравнения

лг.> гг^-ь •

1.1 к

Полученные формулы проверены на ЭВМ как моделированием, так и формальными вычислениями.

Б. Комбинаторная структура Q) и оптимизация функций в случае одинаковых распределений длительностей обслуживания такие лее, как в системе Ц IG |1.

п 1 п 1

В. Нахождение дисциплины обслуживания, реализующей любую точку М(о).

Вероятиестно-разделительная дисциплина для случая одинаковых распределений длительностей обслуживания реализует любую точку

приоритетного многогранника. Описанный в 143 алгоритм нахоадения параметров этой дисциплины, при которых реализуется любая заданная точка ilf(O), справедлив и для этой системы.

г

В шестой главе рассматриваются некоторые задачи для

вычислительных сетей.

Рассмотрены кольцевые локальные сети с маркерным доступом.

Такая сеть состоит из N узлов и в ней задан замкнутый маршрут,

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

Узел осуществляет передачу требований только при наличии маркера.

Длительности передачи требований узлом в соседний узел маршрута -

независимые случайные величины; на каадый узел поступает

пуассоновский поток требований; поступившее на 1-ый узел

требование с вероятностью d должно быть передано ча J-ый

н ' • ' узел, I d( i = 1, du % 0, d( t = 0, i - 1,2.....N;

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

справедливо). Отметим, что ранее было доказано только выполнение

(

закона сохранения - равенства в (1).

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

В разделе 6.2 исследуются длины маршрутов маркера 19,101. Для сети, в которой длины ребер независимы . и одинаково распределены с функцией распределения F(x), найдено среднее значение длины кратчайшей связывающей сети. В ' частности, для

распределений, имеющих непрерывную плотность с значением в нуле

равным 1, показано, что среднее значение длины кратчайшей

«

связывающей сети равно £ к~э+ of1) при N ->®. Решение

основывается на анализе алгоритма Прима построения кратчайшей связывающей сети. Главный результат анализа состоит в получении соотношений между функциями распределения 1-Фп1(х) длин ребер кратчайшей сети (лемма 2.3)

ЕС;;; (i-ptx)),(j-,,»1I1(.J(x) - -№)),0,-,\

1 - 1,2,...,N-1.

Основной результат дап в теореме 2.1.

Теорема 2.1. Пусть функция F(x). задающая распределении дмт ребер сет. удовлетворяет условиял:

.1)6 некоторой правосторонней окрестности 0 существует F'(x) и

F' (х) - ofW"-1 + 0(x1/^'*1*,). 0 s х < е (а > 0); 2) существует яателатнеское оживание длины ребра, тогда 1 - ваша кратчайшей связывающей сети такая, что Ига Г-1Е1 - в-вГ(а+1) У nj-z-"c*"1 ,

еОе г(х) - гаака-фупнция.'

Отметим, что ранеебыли известны только оценки Е1н. Й parчеле 6.3 рассматривается задача, связанная с нвхозденяем надевности сети. Для- нахождения всех минимальных (состоящих из наименьшего числа ребер) разрезов ориентированной сети (111 описан алгоритм, имеющий трудоемкость 0(K3N2). Для неориентированной сети в 112] описан эффективный алгоритм, имеющий трудоемкость 0(кН2), который строит и простую структуру

(с ОШ) вершинами и О(Н) реберные разрезы. Отметим, по порядку роста N.

ребрами), задающую все минимальные что трудоемкость алгоритмов наименьшая

В .седьмой главе рассматривается система обслуживания Мп|Сп|га, в которую поступают пуассоновские потоки требований п различных типов с интенсивностями х . Поступившее требование 1-ого типа с вероятностью х(о размещается на приборе а и обслуживается без прерывания. Длительность обслуживания требования 1-ого типа на приборе а имеет первые два момента Ь И Ъ ПОЛОЖИМ р = X Ь (111 (11, 1* а 1Ш).

I а 1 1 а 2 1 а I I а 1

В этой системе требуется оптимизировать некоторую функцию Р, зависящую от средних времен ожидания « требований 1-ого типа на приборе а; а оптимизация производится как по размещении требований на приборах, так и по дисциплинам обслуживания на них. Покажем применение предлагаемого метода для этой задачи. А. Приоритетное множество и всевозможных значений (ад1,... ) описывается следующим образом.

£ р X < 1, а = 1,2.....ш;

V X = 1 , V 1 е о; , 1« а « 1

(3) Г Р, х, да, =6) (Х,0), а = 1,2,...,ш;

° 1 а 1 а I о а

1.1

£ р х и 4 и (х,Э), у Э с о, а - ' 2.....ш;

1€Я 01

X г О, V 1 е.О, а = 1,2,...,ш;

1а .

где функции и (х.Б) следующие

о (х ,S) - 1£s

- 23 -I pt x, W U )

i a ¡a 0a a

1 - ,!Л«Х-

W (x ) - i x.x ■, /2.

On a " 1 I a i »2

i • t

В. Задача нахождения локального минимума функции F, зависящей от средних времен ожидания wjo, на приоритетном множества I! так зге. как в системе WJGJ1 решается полиномиальным алгоритмом с ' использованием метода эллипсоидов.

В. Любая точка приоритетного множества If реализуется при некотором вероятностном размещении и дисциплине обслуживания.

Однако в этой системе (в отличие от ранее рассмотренных) нахоэдеште глобального минимума представляет трудности даже для простых функций F. Поэтому был изучен и частный случай линейной

п ш

функции F = 2 С(.7/1, где Wt . «= 2 xlew,a ~ среднее время

ожидания требования 1-ого типа. Задача минимизации F сводятся к мщтмпзации нелинейной функции

С х W . (я)

о п ft я, a • Oa

F(x) = I. Z -г.-

a., k.i (1 - RK)(1 - Rk'_1 )

ГДв R - 1 p ■' X (R =0), i.i t "»",

a (iet\... >■ — перестановка чисел 1,2.....n такая, что

С /р г С /р а ... г С' /р ;

л к.« *„ If a It я о

■11 2 2 n п

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

moGä льпого минимума.

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

Приведены результаты моделирования на ЭВМ.

СПИСОК ОСНОВНЫХ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Тимофеев Е.А. Оптимизация средних длин очередей в системе обслуживания с ветвящимися потоками вторичных требований //Авт. и телемеханика. N 3. 1995. С.60-6Т.

2. Тимофеев Е.А. Оптимальные приоритеты в системе GIJGJ1. //Кибернетика. N2. 1991. С.80-85.

3. Тимофеев й.А. Вероятностно-разделительная дисциплина обслуживания и многогранник средних времен ожидания в системе GI|G |1. //Авт. и телемеханика. N 10. 1991. С.121-125.

4. Тимофеев Е.А. Реализация заданных средних времен ожидания в одноканальной системе обслуживания. // Кибернетика и системный анализ. N 6. 1991. С.97-101.

5. Маматов С.А.. Тимофеев Е.А. О системах массового 'обслуживания с вероятностными приоритетами //Авт. и телемеханика. N 9. 1985. С.159-162. .

6. Тимофеев Е.А. Об оптимизации функций от средних времен ожидания в системе массового обслуживания GJ |И|1. //Авт. и телемеханика. N11. 1989. С.100-109.

7. Тимофеев Е.А. Оптимальный выбор средних времен ожидания в системе массового обслуживания GI|Mn|1. //Автоматика и телемеханика. N6. 1991. С.77-&3.

8. Тимофеев Е.А'. О вероятностной смеси абсолютных и относитель-

пых приоритетов в системе GI|H!ln|1. // Кибернетика и системны!! анализ. W 4. 1991. G.T5-B4.

9. Тимофеев Е.А. Случайные минимальные деревья. //Теория вероятностей и ее применения, т.29. Н 1. 1984. 134-141.

10. Тимофеев Е.А. 0 нахождении математического ожидания длины случайного минимального дерева //Теория вероятностей и ее применения. Т.ЗЗ. И 2. 1988. 0,383-387.

11. Тимофеев Е.А. Алгоритм построения минимаксного к-связного ориентированного подграфа. //Кибернетика. N 2. 1982. С. 109-110. 12., Карзапов A.B., Тимофеев Е.А. Эффективный алгоритм наховдения всех реберных разрезов графа. //Кибернетика. Н 2, 1906. С.87-94.