Новые подходы к моделированию обработки заявок в системах с высокой нагрузкой

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

Новые подходы к моделированию обработки заявок в системах с высокой нагрузкой

Жуков Д.О., Лесько С.А.

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

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

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

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

Отметим, что по имеющимся данным средняя загрузка серверов в существующих информационных системах составляет от 7 до 20 %, и это, наоборот, требуется не столько оптимизации загрузки, сколько ее увеличения. Тем не менее, в определённые моменты времени могут возникать и довольно долго существовать пиковые нагрузки, которые требуют оптимизации, что, например, является важным в том числе и для операционных систем (ОС) реального времени.

При анализе процессов обработки заявок наиболее распространённым математическим аппаратом являются модели теории массового обслуживания [1]. В них, как правило, поступление и обработка заявок рассматриваются не на уровне отдельного сервера (компьютера, узла), а как общий процесс, протекающий в единой информационно-вычислительной сети (ИВС), и моделируют не работу отдельного узла, а всей ИВС.

Теорию нечётких множеств, как правило, применяют с целью более адекватного представления процессов в ИВС уже существующими моделями на базе теории массового обслуживания и теории графов [2]. Теория нечетких множеств (ТНМ) базируется на математическом аппарате теории множеств с допущением о том, что каждый элемент множества входит в него с некоторой вероятностью.

Использование теории нечетких множеств вызвано тем, что при анализе ИВС на основе теории массового обслуживания необходимо априорно формировать дискретные значения длин и интенсивностей входящих пакетов. Если эта информация не известна, то это значительно затрудняет получение конечного результата. Использование вместо группы констант (для описания интенсивностей и длин пакетов) нечеткого множества, характеристическая функция которого описывает вероятность того, что значение данной константы примет данное значение, позволяет строить модели, более адекватно описывающие реально протекающие в ИВС процессы и получать более точный результат [3].

Сравнительно недавно для анализа процессов обработки и передачи данных стал применяться математический аппарат тензорного анализа. Его применение обусловлено неспособностью моделей теории массового обслуживания адекватно описывать близкие к предельным нагрузки [3].

Тензорные модели позволяют геометрически представить процессы в сети [3] и рассматривать их как некоторое преобразование в системе координат. Это упрощает построение моделей сети, однако требует формирования исходных данных и описания объектов ИВС изначально на базе элементов тензорного анализа.

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

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

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

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

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

ПОСТРОЕНИЕ ДИНАМИЧЕСКОЙ МОДЕЛИ ОБРАБОТКИ СТОХАСТИЧЕСКИХ ЗАЯВОК

Допустим, что имеется некоторое множество заявок различных типов, каждый из которых можно обозначить некоторым индексом 1,...k,...j; число заявок одного типа, которые обрабатывает компьютер в данный момент времени, обозначим как (x1, … xk,... xj…).

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

Обозначим через - вероятность того, что на обработке после h шагов работы находится заявок типа K, а через - вероятность того, что находятся - заявок типа K и - вероятность того, что находится заявок. Тогда вероятность (см. рисунок ) того, что на h+1 шаге будет находится заявок типа K будет равна:

= + - .

Рисунок 1 - Схема возможных переходов между состояниями на h+1 шаге

Введем , где t - общее время процесса обработки и получим:

Раскладывая уравнение (1) в ряд Тейлора получим:

.

Учитывая в левой части члены, содержащие не более чем первую производную по t, а в правой не более чем вторую производную по , получим:

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

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

МОДЕЛЬ ПОЛИХРОННЫХ ЗАЯВОК

В этой модели для каждого типа заявок можно задать свой порог Lj и, соответственно, получить набор уравнений вида:

Всего N дифференциальных уравнений II порядка параболического типа со своими граничными условиями вида:

и начальным условием .

Решение этих уравнений позволяет описать динамику поступления и обработки заявок и разработать алгоритм их обработки, который будет учитывать критичность и приоритетность различных заявок. Решение можно произвести аналогично изложенному выше методу и получить уравнения (4) и (5), описывающие динамику каждого типа заявок отдельно:

при x > x0j

при x ? x0j

где соответственно j - определяет тип заявок, проступающих на обработку.

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

Отметим, что состояния могут принимать только целочисленные значения, однако уравнения (4) и (5) задают непрерывные распределения, что, тем не менее, не отвергает возможности их использования, поскольку эти уравнения могут быть дополнены условием, что значимыми являются только значения, полученные для целых величин x.

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

Интеграл P(L,t) вида:

задает вероятность того, что состояние обработки заявок x к моменту времени t будет находиться на отрезке от 0 до L, т.е. не будет находиться в состояния простоя.

Соответственно, вероятность того, что узел обработки заявок окажется к моменту времени t в состоянии простоя, можно определить следующим образом:

.

Возьмем произвольное значение , и (>), например, =50, =15 и =7. На рис. 2 представлена зависимость от времени вероятности того, что к моменту времени t компьютер окажется в состоянии простоя для различных значений критерия простоя L в работе. Кривая 1 для , кривая 2 для , кривая 3 для , кривая 4 для и кривая 5 для .

Рисунок 2 - Зависимости вероятности простоя компьютера от времени для различных значений критерия L

Обратим внимание, что соответствующие вероятности становятся отличными от 0, начиная с некоторого момента времени (см. рис. 2), а сами кривые сдвигаются в сторону больших времен с увеличения L относительно значения . При других значениях , и (>) происходит количественное изменение расположения кривых, однако качественно результат остается неизменным.

Перегруженность узла обработки заявок, связанная с превышением числа заявок выше порога L, связана с тем, что поток входящих заявок превосходит поток исходящих (обработанных) заявок >, что является очевидным.

АЛГОРИТМ ПОЛИХРОННОЙ САМОСОГЛАСОВАННОЙ ОБРАБОТКИ ЗАЯВОК

Предлагаемая в данной работе модель позволяет предложить следующий алгоритм обеспечения бесперебойной работы:

Исходя из аппаратных характеристик и решаемых задач для каждого j-го типа заявок, задаётся пороговое значение критерия - максимально возможного для обработки числа заявок j-го типа.

В течение некоторого интервала времени проводится определение величины параметров (на момент окончания интервала времени).

По уравнениям (6) и (7), учитывая (4) и (5), рассчитывается зависимость и устанавливается предельное значение , которое можно допустить для данного типа заявок, исходя из условий обеспечения надёжности работы.

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

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

Проводится повторение шагов 1-5 в течении всего времени работы.

Литература

1. Клейнок, Л. Теория массового обслуживания [Текст]: [пер. с англ.] / Л. Клейнок; пер. И.И. Грушко; под ред. В.И. Неймана. - М.: Машиностроение,1979. - 432с.

2. Будко, П. А. Выбор пропускных способностей каналов при синтезе сети связи в условиях изменяющейся нагрузки [Текст] / П. А. Будко // Физика волновых процессов и радиотехнические системы,2000. - №3-4. Т.3 - с. 68-72.

3. Пасечников, И. И. Методология анализа и синтеза предельно нагруженных информационных сетей [Текст]: монография / И. И. Пасечников - М.: Машиностроение-1», 2004. - 216 с.

4. Городецкий, А.Я. Информатика. Фрактальные процессы в компьютерных сетях [Текст]: учебное пособие / А.Я. Городецкий, В.С. Заборовский - СПб.: Изд-во СПбГТУ, 2000 - 102 с.

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