Geum.ru

В. А. Федоров московский инженерно-физический институт (государственный университет) постановка и решение

Вид материалаРешение
Подобный материал:

УДК 004.4(06) Технологии разработки программных систем


А.И. ГОВОРОВ, А.В. КРЯНЕВ, Г.В. ЛУКИН, В.А. ФЕДОРОВ

Московский инженерно-физический институт (государственный университет)


ПОСТАНОВКА И РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ СИСТЕМ ОБСЛУЖИВАНИЯ С ОГРАНИЧЕНИЕМ ДЛИНЫ ОЧЕРЕДИ


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


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

Устройство обслуживания может находиться только в двух состояниях: свободно или занято. Различия появляются именно тогда, когда поступившая заявка застает все устройства обслуживания занятыми. Выделяют следующие виды систем обслуживания: с отказами, с ожиданием и смешанного типа. В системах с отказами заявка, заставшая в момент своего поступления все устройства обслуживания занятыми, получает отказ в обслуживании и в дальнейшем система работает так, как будто эта заявка вообще не поступала. В системах с ожиданием подобная заявка становится в очередь на обслуживание. Заявки, находящиеся в очереди, удовлетворяются по мере освобождения устройств обслуживания. В системах смешанного типа заявка, заставшая в момент своего поступления все устройства обслуживания занятыми, становится в очередь на обслуживание при условии, что количество заявок, уже стоящих в очереди, меньше некоторого числа, в противном случае эта заявка утрачивается системой [2,3].

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

При расчете последовательно фиксируются только реперные моменты времени tk , соответствующие либо моментам поступления заявок на обслуживание, либо моментам окончания обслуживания очередной заявки. Обозначим через ∆tk, k=2,…,N – время между (k-1)-й и k-й заявками. Последовательность ∆tk для модельных задач можно воспроизвести с помощью датчика случайных величин согласно заданному закону распределения на основе метода Монте-Карло [4], либо эта последовательность соответствует реальному потоку заявок на обслуживание.

Выходными значениями алгоритма являются:
  • число обслуженных заявок L;
  • число отказов от обслуживания K*;
  • время холостого простоя Web-системы T0;
  • вероятность отказа в обслуживании prisk = K*/N;
  • процент холостого простоя Tпростоя = (T0/∑∆tk) * 100%;
  • время обслуживания, включая ожидание в очереди.

Решение задачи оптимизации заключается в определении такого числа mopt обслуживающих устройств, что для m=mopt выполняется неравенство prisk ≤ p*risk, а для m=mopt-1 неравенство prisk > p*risk. Оптимальное количество устройств обслуживания определяется итерационным методом, начиная со значения mopt=1.

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


Список литературы:

  1. Менаске Д. Производительность Web-служб. Анализ, оценка и планирование. – СПб.: ООО «ДиаСофтЮП», 2003.
  2. Аникина Л.И., Визгалов Е.И., Говоров А.И., Крянев А.В., Лукин Г.В.. Постановка и решение задач оптимизации грид-систем. Сборник научных трудов научной сессии МИФИ-2007.
  3. Крянев А.В., Лукин Г.В., Федоров В.А., Визгалов Е.И., Говоров А.И. Постановка и решение задач оптимизации конфигурации программного обеспечения для интеграции корпоративных приложений. М.: МИФИ, Препринт №006-2007., 2007.
  4. Agrawal S. Metamodeling: A Study of Approximation in Queuing Models. MIT Press, Cambridge, 1985.




ISBN 978-5-7262-0883-1. НАУЧНАЯ СЕССИЯ МИФИ-2008. Том 11