Оптимизация обработки данных в системах поддержки принятия решений с элементами обслуживания
Введение
Компьютерная система поддержки принятия решений (СППР) выступает в роли вычислительного звена и объекта управления; человек (лицо, принимающее решение, ЛПР) как управляющее звено, задает входные данные, правила и алгоритмы, осуществляет сбор данных из разнородных источников с помощью запросов и оценивает предложенные компьютерной системой решения, основанные на описанных правилах и алгоритмах, и, в случае возникновения риска принятия решения, формирует дополнительные запросы и сценарии. Для улучшения параметров обслуживания запросов в СППР и соответствующих интернет-сервисов (ИТ-сервисов) актуален вопрос оптимизации обработки данных в СППР. Существует множество предложений по оптимизации обработки данных в СППР. В работе [2] предложен алгоритм агрегации простых запросов, позволяющий снизить требования к каналу связи и сократить время на получение и обработку информации в СППР. В работе [3] предложено объединение данных из различных источников, в которых содержится полезная для целей анализа информация, для их унификации с помощью юниверсов (набора объектов, сгруппированных в классы и отражающих предметную область пользователей). В работах [4, 5] предложено снижение времени на обработку данных и требуемого объема дискового пространства с помощью режимов хранения и методов сбора и слияния разнотипных данных. Определению состава и структуры запросов к соответствующей базе моделей посвящены [6, 7] и многие другие работы. Во многих работах рассмотрение СППР производится в том ракурсе, что все параметры её работы заранее известны и не изменяются с течением времени. Однако для реально существующих СППР, т. е. наиболее интересных для пристального изучения, такое предположение не всегда является справедливым. В частности, может не учитываться выход из строя отдельных элементов обслуживания (ЭО) запросов в рассматриваемой системе, либо циклическое изменение (повышение или понижение быстродействия отдельных ЭО в зависимости от текущей нагрузки на систему в целом). В данной ситуации естественно при обслуживании запросов и сценариев пользоваться адаптивным подходом. Таким образом, возникает задача адаптации СППР к изменяющимся условиям внешней и внутренней среды с целью оптимизации функционирования. АНАЛИЗ ПРИНЦИПОВ РАБОТЫСППР С ЭО Системы поддержки принятия решений (ССПР) разработаны на основе интеграции информационно-управляющих систем и систем управления базами данных [8] и включают хранилища данных и инструментальные средства для их обработки, как показано нар рис. 1. В данной работе анализируются методы теории массового обслуживания, базирующиеся на методах теории вероятностей и математической статистики, и средства теории массового обслуживания для задач принятия решений – элементы обслуживания (ЭО). Характерной чертой инструментальных средств для анализа данных СППР (рис. 1) является выполнение заранее определенных запросов или запросов, формируемых дополнительно ЛПР. Обслуживание запросов осуществляется одним, постоянно работающим ЭО. Запрос, поступающий в СППР, при доступности первого (основного) ЭО сразу же занимает его. Если первый ЭО уже занят обслуживанием ранее поступившего запроса, текущий запрос становится в очередь. При превышении заранее установленного максимального количества запросов в очереди число ЭО увеличивается на единицу (в рамках заданного лимита ЭО). Как только число запросов на один ЭО становится равным определённой максимальной величине (с учетом обслуживаемых запросов), или становится меньше её, лишний ЭО убирается (выключается) [9]. После завершения обслуживания производится сбор статистических данных, и обслуженный запрос покидает систему. При отсутствии и незадействованных ЭО, и мест во всех очередях, запрос получает отказ в обслуживании и покидает систему (также после записи статистических данных). Блок-схема алгоритма обслуживания запросов в СППР представлена на рис. 2. Проанализируем начальные условия работы СППР с ЭО. Рассматриваемая система имеет следующие параметры: количество постоянно функционирующих ЭО – 1; количество (лимит) резервных ЭО – 2; максимальное количество (лимит) ЭО Max = 3;
Рис. 1. Типовая структура СППР
Рис. 2. Блок-схема алгоритма обслуживания запросов в СППР
Максимальное количество запросов в каждой из очередей, включая обслуживаемые в настоящее время запросы (при превышении порога включается резервный ЭО) – 3; отказы в обслуживании при отсутствии мест в системе – да; поток входящих запросов – пуассоновский; нагрузка на систему ψ = [0;5]; время моделирования – 720 минут (12 часов); количество осуществляемых прогонов модели – 1000. Рассмотрим граф [10,11], показывающий возможные состояния, в которых может находиться СППР с ЭО (рис. 3).
Рис. 3. Граф состояний адаптивной системы с отказами
Поскольку разрабатываемая система допускает возможность отказов в обслуживании, она имеет конечное число состояний – от 0 p (полное отсутствие запросов в системе) до maxK p (максимально возможное количество запросов в системе). Количество возможных состояний системы может быть вычислено по следующей формуле Q = Max ⋅ K + 1. (1) Используя разрезы графа, можно составить систему уравнений стационарных состояний и выразить все вероятности через 0 p. Формула для расчёта вероятности начального состояния системы может быть получена из исходной формулы [10] путём установки ограничения на максимально возможное количество ЭО в СППР, т. е.
Полученный результат 0 p соответствует такому состоянию системы, когда в ней нет ни одного запроса на обслуживание, т. е. система полностью простаивает.
Методика расчета параметров СППР с ЭО
Реализация методов теории массового облуживания для стохастических задач принятия решений осуществляется с помощью широко распространенных программных средств MathCAD, MatLab. На рис. 4 представлены вероятности полного простоя системы в зависимости от действующей нагрузки ψ при различных значениях параметра K, рассчитанные в среде MathCAD. При K =1 (кривая 1) СППР соответствует варианту системы M/M/3, в которой каждому вновь прибывшему запросу выделяется ЭО (в рамках заданного лимита), и поэтому очередь в системе отсутствует. Очевидно, что система M/M/3 обеспечивает наибольшую вероятность простоя системы. При увеличении значения параметра K вероятность простоя системы снижается, и в пределе становится равной аналогичной вероятности в системе с одним ЭО и практически бесконечной очередью (M/M/1/100), равной, как известно, (1). −ψ Как видно из представленных графиков на рис. 4, адаптивная СППР (кривая 2) обеспечивает большую вероятность простоя, чем система с практически бесконечной очередью M/M/1/100 (кривая 3), но меньшую, чем система без очередей M/M/3.
Рис. 4. Вероятности простоя систем сервиса в зависимости от нагрузки.
Вероятность наличия в системе хотя бы одного запроса может быть определена как 0 p p = −1. (3) Вероятности всех остальных состояний адаптивной системы сервиса могут быть вычислены по формулам, подробно описанным в [12]. Согласно формуле (1), вероятность работы S (в представленном примере – одного, сразу двух и всех трёх) ЭО может быть вычислена как
Графики, представленные на рис. 5, иллюстрирует результаты расчета вероятности работы нескольких ЭО в зависимости от текущей нагрузки ψ. Как видно, максимумы вероятностей работы первого ЭО (кривая 1) и первых двух ЭО (кривая 2) соответствуют значениям текущей нагрузки ψ, т. е. при её увеличении пропорциональное увеличение числа ЭО является наиболее вероятным. Ввиду имеющегося ограничения на общее количество ЭО вероятность одновременной работы всех (в данном случае – трёх) ЭО плавно возрастает (кривая 3), и при отсутствии ограничения на величину ψ приближается к единице, а время простоя ЭО в данном случае, соответственно, стремится к нулю.
Рис. 5. Вероятности одновременной работы нескольких ЭО
Значения коэффициентов использования ЭО могут быть получены по известной ранее формуле [10], с добавлением в неё ограничения на максимально возможное количество ЭО, т. е.
Графики, иллюстрирующие изменения коэффициентов использования ЭО в зависимости от текущей нагрузки представлены на рис. 6.
Рис. 6. Коэффициенты использования ЭО
Рис. 7. Вероятности отказа при различной нагрузке на систему
Как видно из графиков, при достижении ЭО значений коэффициента использования близких к предельным значениям, включается дополнительный ЭО. Очевидно, что у каждого последующего ЭО коэффициент использования меньше, чем у предыдущего. Таким образом, первый ЭО всегда берёт на себя максимальную текущую нагрузку. Представленный вариант системы сервиса допускает возможность отказа в обслуживании. Запросы получают отказ только при одновременном соблюдении двух условий: • все имеющиеся ЭО заняты, • все места в очередях к ЭО заняты. Таким образом, из известной ранее формулы [10] получаем:
Рис. 8. Вероятности попадания запросов в очередь
График функции (6) представлен на рис. 7 и иллюстрирует зависимость вероятности отказа в обслуживании от приведённой нагрузки ψ. Как видно из графиков, адаптивная система сервиса (кривая 2) обеспечивает меньшую вероятность отказа в обслуживании, чем система без очередей M M/ /3 (кривая 1), но большую, чем система с практически бесконечной очередью M M/ /3/100 (кривая 3). Зная финальные вероятности состояний системы, можно определить вероятность образования очереди в ней. Очередь в системе образуется только при соблюдении следующих условий: максимальное число запросов в очереди на один ЭО должно быть больше единицы, т. е. K ≥ 2; система не должна находиться в состояниях 0 p (полное отсутствие запросов) и 1 p (наличие ровно одного запроса). Графики, иллюстрирующие вероятности образования очереди из запросов в системе в зависимости от текущей нагрузки представлены на рис. 8. Как видно из графиков, адаптивная СППР (кривая 2) обеспечивает меньшую вероятность попадания запросов в очередь, чем система с практически бесконечной очередью M M/ /1/100 (кривая 1), но большую, чем система без очередей M M/ /3, в которой эта вероятность равна нулю (кривая 3). Модель адаптивной СППР также может быть использована организациями, занимающимися эффективным управлением жизненным циклом ИТ-сервисов [13].
Заключение
Проведённые исследования показали возможность улучшения параметров обслуживания при использовании адаптивной по отношению к входящему потоку запросов СППР, которая динамически изменяет количество функционирующих ЭО, находясь в рамках заданного лимита, в зависимости от интенсивности потока. Адаптивная СППР представляет собой наиболее сбалансированный вариант системы, в котором дополнительные ЭО включаются только тогда, когда нагрузка на систему возрастает, и выключаются, когда нагрузка на систему снижается, то есть работает в оптимальном режиме, максимально эффективно используя имеющиеся у неё ресурсы.