Способ распределенной обработки нестационарного потока заявок реального времени в условиях дефицита ресурсов гетерогенной вычислительной системы
Владельцы патента RU 2628432:
Федеральное государственное казенное военное образовательное учреждение высшего образования "Академия Федеральной службы охраны Российской Федерации" (Академия ФСО России) (RU)
Изобретение относится к способу распределенной обработки нестационарного потока заявок реального времени. Технический результат заключается в повышении вероятности обслуживания запросов в условиях дефицита ресурсов вычислительной системы и наличия отказов в обслуживании заявок за счет сглаживания потока поступающих заявок с помощью изменения параметров качества обслуживания запросов. Из прошлого уровня техники были использованы процедуры кластерного анализа и определения классов запросов, расчета ресурсоемкости запроса, назначения запроса на обработку. После введения новых процедур установки уровня качества обслуживания, определения вычислительной сложности запроса, упорядочивания запросов согласно своевременности стало возможным осуществлять функционирование гетерогенной вычислительной системы в случае ее перегрузки. 8 ил., 1 табл.
Изобретение относится к области вычислительной техники, а именно к вычислительным системам, и, в частности, может быть использовано в распределенных вычислительных системах. Оно предназначено для организации функционирования распределенной вычислительной системы в условиях дефицита ресурсов, с установленным уровнем качества обслуживания.
Известны способы распределения запросов пользователей в вычислительных системах (см., например, патент Японии №2-30534, кл. G06F 15/16; а.с. СССР №1624473, кл. G06F 15/20, 1991; а.с. СССР №1730626 А1, кл. G06F 9/46, 1992), суть которых заключается в распределении заданий процессорами в многопроцессорной вычислительной системе при вертикальном распараллеливании программ. При освобождении любого процессора очередное задание распределяется сразу еще до окончания текущего задания. Перечисленные аналоги имеют следующие недостатки:
- низкая вероятность обслуживания запросов в условиях дефицита ресурсов вычислительной системы и наличия отказов в обслуживании заявок;
- низкая эффективность использования вычислительных ресурсов системы, т.е. невысокие коэффициенты использования вычислительных ресурсов системы, определяемых отношением времени работы вычислительного ресурса в заданном временном интервале к указанному интервалу;
- возможность применения только в сосредоточенных вычислительных системах;
- высокая ресурсоемкость получения информации состояния ресурсов в распределенной вычислительной системе.
Наиболее близким по технической сущности к заявленному способу распределения запросов пользователей в вычислительной системе является способ, предложенный в патенте РФ №2406124, кл. G06F 15/16, 2009. В данном прототипе способ заключается в том, что принимаются запросы пользователей, определяют их класс, рассчитывают ресурсные требования запросов, выделяются первоочередные запросы и передаются в соответствующие исполнительные узлы вычислительной системы на исполнение.
Этот способ по сравнению с вышеназванными способами-аналогами распределения ресурсов вычислительной системы обеспечивает высокую эффективность при использовании в распределенных вычислительных системах при значительной вариации значений параметров потока запросов; приемлемость использования способа в системах с динамически изменяющимся составом исполнительных узлов.
Указанный способ-прототип имеет недостаток: низкая вероятность обслуживания запросов в условиях дефицита ресурсов вычислительной системы и наличия отказов в обслуживании заявок;
Предлагаемый способ расширяет функциональные возможности способа-прототипа за счет введения дополнительных процедур и частичного изменения связей в логике работы предыдущего уровня техники.
Задачей изобретения является создание способа распределенной обработки нестационарного потока заявок реального времени в условиях дефицита ресурсов гетерогенной вычислительной системы, позволяющего достичь технический результат: повышение вероятности обслуживания заявок в условиях дефицита ресурсов вычислительной системы и наличия отказов в обслуживании заявок, за счет сглаживания потока поступающих заявок с помощью изменения параметров качества их обслуживания.
Эта задача решается тем, что принимают запросы на обслуживание, множество запросов пользователей классифицируют, группируют запросы по классам, определяют функцию расчета ресурсоемкости запроса для каждого класса. Запросы переклассифицируют при изменении параметров потока запросов, запросы пользователей идентифицируют и соотносят с одним из классов запросов, определяют ресурсоемкость запроса, формируют схему требований запроса к вычислительным ресурсам, направляют в очередь соответствующей группы однотипных вычислительных узлов. Однотипные исполнительные узлы объединяют в группы однотипных исполнительных узлов, для каждой группы исполнительных узлов вычислительной системы создают очередь обработки запросов. При поступлении в очередь к группе однотипных исполнительных узлов определяют схему исполнения запросов, перераспределяют запросы в соответствии со схемой исполнения запросов, выделяют первоочередные запросы пользователей и передают их в соответствующие группы однотипных исполнительных узлов вычислительной системы на исполнение. Выделение первоочередных запросов пользователей осуществляют путем одновременного опроса входных очередей по сформированным схемам опроса входных очередей, одновременно с поступлением запросов пользователей в соответствующую группу исполнительных узлов вычислительной системы для каждой из них корректируют схему опроса входных очередей, а после выполнения запроса пользователя в соответствующем узле группы вычислительных узлов повторяют действия, начиная с опроса входных очередей для каждой группы исполнительных узлов вычислительной системы, способ согласно изобретению дополнен тем, что множество запросов пользователей группируют по классам вычислительной сложности, устанавливают приемлемое значение качества обслуживания каждому запросу для расчета их ресурсоемкости, универсальные исполнительные узлы объединяют в группы универсальных узлов по параметрам их вычислительной мощности. По результатам исполнения запроса устанавливают весовую функцию для запросов этого сервисного класса, одновременно с изменением весовой функции класса заявки корректируют схему исполнения запросов, производят выделение первоочередных запросов пользователей с учетом времени нахождения запроса в вычислительной системе. Для запросов, получивших отказ в обработке, повторяют действия, начиная с установки качества обслуживания, повторения указанных действий совершают до полного исполнения всех запросов, получивших отказ в обработке.
Проведенный анализ уровня техники позволил установить, что аналоги, характеризующиеся совокупностью признаков, тождественных всем признакам заявленного технического решения, отсутствуют, что указывает на соответствие изобретения условию патентоспособности «новизна». Результаты поиска известных решений в данной и смежных областях техники с целью выявления признаков, совпадающих с отличительными от прототипа признаками заявленного объекта, показали, что они не следуют явным образом из уровня техники. Из уровня техники также не выявлена известность влияния предусматриваемых существенными признаками заявленного изобретения преобразований на достижение указанного технического результата. Следовательно, заявленное изобретение соответствует условию патентоспособности «изобретательский уровень».
Заявленное техническое решение поясняется чертежами, на которых представлено:
фиг. 1 - алгоритм кластерного анализа и определения классов запросов;
фиг. 2 - алгоритм определения ресурсоемкости запроса пользователя;
фиг. 3 - алгоритм назначения запроса пользователя для обработки на вычислительный узел;
фиг. 4 - блок-схема алгоритма, реализующая заявленный способ распределенной обработки нестационарного потока заявок в случае перегрузки гетерогенной вычислительной системы;
фиг. 5 - вариант распределенной вычислительной системы с территориально распределенными ресурсами территориально распределенными пользователями, созданной на базе ассоциации локальных вычислительных сетей, вычислительных кластеров, сайтов grid-систем;
фиг. 6 - экспериментальная модель вычислительной системы;
фиг. 7 - результаты эксперимента по оценке эффективности;
фиг. 8 - схема организации обработки запросов пользователей в распределенной вычислительной системе.
Возможность реализации заявленного способа распределенной обработки нестационарного потока заявок реального времени в условиях дефицита ресурсов гетерогенной вычислительной системы объясняется следующим образом.
Способ предназначен для планирования обработки запросов пользователей в гетерогенной распределенной вычислительной системе (ГРВС), создаваемой на базе ассоциации локальных вычислительных сетей, вычислительных кластеров, сайтов grid-систем, отдельных пользовательских компьютеров. Подобная система представляет собой вычислительную систему с территориально распределенными ресурсами, в качестве которых выступают вычислительные узлы различной производительности и архитектуры, объединенные в сеть коммуникационным оборудованием. Вычислительные узлы предоставляют свои ресурсы с целью обработки запросов пользователей. Вариант такой системы представлен на фиг. 5.
Заявленный способ может быть реализован в виде распределенного устройства, осуществляющего организации функционирования распределенной вычислительной системы в условиях дефицита ресурсов, с установленным уровнем качества обслуживания (фиг. 8).
Функционирование процесса управления обслуживанием запросов пользователей начинается с запуска и первоначальной настройки вычислительной системы. Вычислительные узлы, входящие в состав РВС, измеряют с помощью «блока оценки производительности». Измеренную информацию производительности согласно фиг. 8 передают на «блок классификации ресурсов». В «блоке классификации ресурсов» определяют классы производительности вычислительных узлов и их свойства. Информацию производительности от «блока оценки производительности» передают в «блок определения класса производительности узла». В «блоке определения класса производительности узлов» вычислительный узел соотносят с одним из классов производительности вычислительных узлов. Все вычислительные узлы одного класса производительности объединяют в виртуальный вычислительный ресурс определенной вычислительной мощности, о чем вносят соответствующую запись в «блок сопровождения очереди класса узла». К каждому виртуальному вычислительному ресурсу образуют очередь запросов соответствующей вычислительной сложности. Обслуживание запросов из очереди организуют в «блоке сопровождения очереди сервисного класса узла», в котором назначают и переназначают вычислительные узлы для обработки запросов соответствующей вычислительной сложности. При добавлении в ГРВС нового вычислительного узла его соотносят с тем или иным классом производительности и добавляют в виртуальных вычислительный ресурс. При отказе вычислительного узла запись о нем в «блоке сопровождения очереди сервисного класса узлов» удаляют, присваивают отказавшему узлу новый класс производительности в «блок определения класса производительности узла». Необработанные запросы, находящиеся в очереди класса узла, передаются на «блок приема запросов». Минимальное количество «блоков сопровождения очереди класса узлов» равно количеству классов производительности вычислительных устройств. При значительном удалении вычислительных узлов одного класса производительности друг от друга и низкой пропускной способности коммуникационной системы возможно образование нескольких «блоков сопровождения очереди класса узлов» для одного производительного класса.
В каждом «блоке сопровождения очереди класса узлов» все сгруппированные вычислительные узлы упорядочивают по убыванию производительности.
Процесс обслуживания начинается, когда пользователь формирует запрос на обслуживание. Запрос на обслуживание формируют в блоке «источник запросов». Через «блок связи» запросы передают на «блок приема запросов». С «блока приема запросов» запрос передают на «блок сервисной классификации запросов». В «блоке сервисной классификации запросов» накапливают информацию о свойствах, параметрах качества обслуживания (вначале процесса обслуживания выбирается максимальное допустимое значение параметров качества), множества полученных запросов и множества необработанных запросов от отказавших узлов, получают значение весовой функции для каждого сервисного класса из «блока оценки производительности» и информацию о результатах обработки запросов из «блока сопровождения классов узлов. В «блоке сервисной классификации запросов» множество запросов разбивают на несколько классов вычислительной сложности, соответствующих классам производительности вычислительных узлов, определяют условия принадлежности запроса каждому классу и вычисляют функцию прогнозирования ресурсных требований для запросов из каждого класса, учитывая требования к их качеству обслуживания и их весовую функцию согласно известного алгоритма на фиг 1. При изменении свойств потока запросов, весовой функции сервисного класса запросов, количества отказов в обработке запроса определенного сервисного класса изменяют параметры качества обслуживания этого сервисного класса и адаптируют алгоритм прогнозирования ресурсных требований запроса согласно алгоритма на фиг. 4.
Условия принадлежности запроса определенному классу вычислительной сложности с значением весовой функции, полученным из «блока оценки производительности», передают из «блока сервисной классификации запросов» в «блок определения сервисного класса запроса», а функцию прогнозирования ресурсных требований запроса - в «блок расчета ресурсоемкости». Известный алгоритм прогнозирования ресурсных требований запроса представлен на фиг. 2.
Каждый запрос пользователя из «блока приема запросов» передают на «блок определения сервисного класса запроса», в котором на основании условий принадлежности определяют класс вычислительной сложности запроса. Далее запрос пользователя и информацию о нем передают на «блок расчета ресурсоемкости», в котором на основании класса сложности и функции прогнозирования ресурсных требований запроса вычисляют ресурсные требования запроса.
Запрос пользователя, принятый на обслуживание вычислительных узлов, перенаправляют на вычислительный узел. В вычислительном узле запрос пользователя обслуживают. Результаты обслуживания запроса пользователя передают на «источник запросов» через «блок связи». В случае отказа в обслуживании запрос возвращают в «блок приема запросов». Информацию о результатах обслуживания передают на «блок сопровождения очереди сервисного класса узлов» и «блок сервисной классификации», причем на «блок сервисной классификации» передается информация о необработанных заявках, для определения уровня качества обслуживания соответствующего сервисного класса и корректировки функции прогнозирования. При получении информации о завершении обслуживания запроса информацию о нем в «блоке сопровождения очереди сервисного класса узлов» удаляют. По завершении обслуживания запроса на основании веса обслуженного запроса корректируют функцию прогнозирования ресурсных требования запроса в «блоке сервисной классификации запросов». В «блоке определения очередности запросов» через оптимальный промежуток времени переупорядочивают запросы согласно их своевременности. Своевременность обслуживания запроса рассчитывают на основе прогнозных ресурсных требований запроса и времени нахождения запроса в системе обслуживания, передаваемых из «блока оценки производительности».
В условиях отсутствия отказов запрос назначают на обработку на вычислительный узел согласно известному алгоритму, приведенному на фиг. 3.
Таким образом, благодаря новой совокупности существенных признаков, за счет введения новых процедур и связей между ними появляется возможность организации функционирования распределенной вычислительной системы в условиях дефицита ресурсов, с заранее оговоренным качеством обслуживания. Предлагаемый способ может быть использован в подсистемах и звеньях управления технологическими процессами в информационно-вычислительных сетях.
Для оценивания эффективность технического результата была проверена путем имитационного моделирования вычислительной системы при помощи программной среды «MathCad 14».
Эксперимент по оцениванию эффективности проводился в два этапа:
1 этап - без корректировки качества обслуживания заявок;
2 этап - с корректировкой качества обслуживания заявок.
Модель вычислительной системы включала три сервера различных классов вычислительной мощности, с соответствующими параметрами максимальной мощности Q=50, 60 и 70. Причем за каждым сервером было закреплено одинаковое количество запросов соответствующей им вычислительной сложности с их значениями коэффициента q, определяющего требования к качеству обслуживания, которые поступали от источников нагрузки (фиг. 6).
В модели было предусмотрено параллельное выполнение трех независимых друг от друга процессов:
процесса, моделирующего фон задач, решаемых сервером помимо обслуживания запросов (имитирован потоком внешних воздействий (λвв) на обслуживающий прибор);
процесса, моделирующего загрузку сервера запросами на обслуживание;
процесса, моделирующего функционирование сервера по обслуживанию разноприоритетных запросов пользователей вычислительной системы.
Процесс, моделирующий загрузку сервера запросами на обслуживание, имитирован входящим потоком запросов на обслуживание, имеющим следующие характеристики:
интенсивность поступления запросов - λ, изменяющаяся во времени;
закон распределения времени поступления запросов ƒ(Δt) принят экспоненциальным, т.к. создает наиболее тяжелый режим при обслуживании
запросов, что приводит к дефициту ресурсов вычислительной системы, а при большом числе источников запросов, что соответствует реальной вычислительной системе, суммарный поток стремится к простейшему, имеющему экспоненциальное распределение, независимо от законов распределения отдельных источников (см. Иванов Е.В. Имитационное моделирование средств и комплексов связи и автоматизации. - СПб.: ВАС, 1992. - 206 с.).
Процесс, моделирующий функционирование сервера, имитирован работой универсального обслуживающего прибора - устройства или группой устройств одного класса вычислительной мощности, выполняющих операции по обслуживанию запросов различных сервисных классов соответствующей вычислительной сложности, причем выставлялся максимальный начальный уровень обслуживания qmax для всех сервисных классов в соответствии с их требованиями. Обслуживающий прибор характеризуется числом каналов обслуживания; интенсивностью обслуживания (μ пакетов/с); законом распределения времени обслуживания F(t0).
Выходными параметрами обслуживающего прибора являются поток запросов, обслуженных прибором λобс; поток запросов, потерянных в результате недостаточной производительности сервера λпп.
С учетом входных параметров и характеристик полученной системы массового обслуживания необходимо так регулировать уровни качества обслуживания и распределять запросы на обслуживание при заданных вычислительных ресурсах серверов, чтобы уменьшить поток запросов, потерянных в результате недостаточной производительности сервера λпп в часы пиковой нагрузки, жертвуя качеством обслуживания.
Результаты моделирования приведены в таблице 1 и в виде гистограммы на фиг. 7, из которых видно, что суммарный поток запросов, обслуженных с применением разработанного технического решения, превышает результат, полученный в варианте обработки без корректировки качества обслуживания, на 20% при максимальной загрузке, на 13% при средней и на 0,88% при минимальной загрузке сервера.
На основании этих результатов можно сделать вывод о том, что разработанный способ позволяет наиболее эффективно, т.е. более своевременно, обслуживать запросы пользователей с гарантированным качеством обслуживания даже для варианта «минимальной» загрузки.
Способ распределенной обработки нестационарного потока заявок реального времени в условиях дефицита ресурсов гетерогенной вычислительной системы, заключающийся в том, что принимают запросы на обслуживание, множество запросов пользователей классифицируют, группируют запросы по классам, определяют функцию расчета ресурсоемкости запроса для каждого класса, запросы переклассифицируют при изменении параметров потока запросов, запросы пользователей идентифицируют и соотносят с одним из классов запросов, определяют ресурсоемкость запроса, формируют схему требований запроса к вычислительным ресурсам, направляют в очередь соответствующей группы однотипных вычислительных узлов, однотипные исполнительные узлы объединяют в группы однотипных исполнительных узлов, для каждой группы исполнительных узлов вычислительной системы создают очередь обработки запросов при поступлении в очередь к группе однотипных исполнительных узлов, определяют схему исполнения запросов, перераспределяют запросы в соответствии со схемой исполнения запросов, выделяют первоочередные запросы пользователей и передают их в соответствующие группы однотипных исполнительных узлов вычислительной системы на исполнение, после приема запросов пользователей на обслуживание формируют данные о свободных ресурсах вычислительной системы в виде исполнительных узлов для выполнения запросов пользователей, по данным сетеметрии формируют для каждой группы однотипных исполнительных узлов схему опроса входных очередей, а выделение первоочередных запросов пользователей осуществляется путем одновременного опроса входных очередей по сформированным схемам опроса входных очередей, причем одновременно с поступлением запросов пользователей в соответствующую группу исполнительных узлов вычислительной системы для каждой из них корректируют схему опроса входных очередей, а после выполнения запроса пользователя в соответствующем узле группы вычислительных узлов повторяют действия, начиная с опроса входных очередей для каждой группы исполнительных узлов вычислительной системы, причем повторение указанных действий совершают до полного исполнения всех запросов пользователей во всех очередях, охватываемых схемой опроса данной группы исполнительных узлов вычислительной системы, отличающийся тем, что множество запросов пользователей относят к сервисным классам, устанавливают приемлемое значение качества обслуживания каждому сервисному классу, группируют по классам вычислительной сложности для расчета их ресурсоемкости, универсальные исполнительные узлы объединяют в группы универсальных узлов по параметрам их вычислительной мощности, по результатам исполнения запроса устанавливают уровень качества обслуживания для запросов этого сервисного класса, одновременно с изменением весовой функции класса заявки корректируют схему исполнения запросов, выделяют первоочередные запросы пользователей учитывая, время нахождения запроса в вычислительной системе, для запросов, получивших отказ в обработке, повторяют действия, начиная с установки качества обслуживания, повторение указанных действий совершают до полного исполнения всех запросов, получивших отказ в обработке.
