УДК 004

Алгоритм приоритизации очередей для динамического распределения ресурсов в мультиагентной системе

Семенов Семен Петрович – студент МИРЭА – Российского технологического университета

Жматов Дмитрий Владимирович – кандидат технических наук, доцент кафедры математического обеспечения и стандартизации информационных технологий МИРЭА – Российского технологического университета

Аннотация: В статье рассматривается проблема обработки очередей в мультиагентной системе с большим объемом сообщений и необходимость их параллельной обработки в зависимости от заданного приоритета. Для решения данной задачи был разработан алгоритм приоритизации очередей на основании их весов (приоритетов). В статье дается описание алгоритма приоритизации нескольких очередей посредством их взвешивания. Приведена формула вычисления весов в очередях. Рассматривается практическое применения алгоритма приоритизации нескольких очередей посредством их взвешивания для решения задачи в области ЖКХ, а именно распределения формирования платежных документов ЖКУ между параллельными процессами для снижения времени ожидания документов со стороны агентов. Описан алгоритм, позволяющий динамически переключать ресурсы на обслуживание заполняющихся очередей и высвобождать их по мере необходимости, что приводит к минимизации ожидания конкретного агента выполнения своего задания.

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

Введение

В исследовании рассматривается применение алгоритма справедливого взвешивания очередей в области ЖКХ для обработки возрастающего числа элементов очереди на формирование платежных документов, в мультиагентной системе корпоративной среды. Алгоритм справедливого взвешивания позволяет снизить задержку на ожидание результата [1].

Каждый агент может выставлять в очередь от 1 до более чем 50000 элементов. При единовременном формировании платежных документов всеми агентами по всем существующим лицевым счетам, общий объем очереди может превышать 1000000 документов. Использование одной очереди запросов ведет к длительному ожиданию документов агентами, отправляющими запрос на выставление в очередь небольшого количества элементов. Алгоритм взвешенных очередей позволяет решить эту проблему путем параллельной обработки запросов различного объема и подключения дополнительных обработчиков, что позволяет эффективно использовать возможности современных вычислительных машин.

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

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

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

Одним из наиболее важных вопросов при проектировании сетей с интегрированными услугами является выбор дисциплины пакетного обслуживания в точках очереди в сети. В последнее время большое внимание уделяется дисциплинам, приближающимся к Generalized Processor Sharing (GPS). GPS – это общая форма дисциплины обслуживания совместного использования процессора (PS). В PS существует отдельная очередь FIFO для каждого сеанса, использующего одну и ту же ссылку. В течение любого интервала времени, когда имеется ровно N непустых очередей, сервер обслуживает N пакетов в начале очередей одновременно, каждый со скоростью, равной одной N скорости канала. В то время как сервер PS обслуживает все непустые очереди с одинаковой скоростью, GPS позволяет различным сеансам иметь разные доли обслуживания и обслуживает непустые очереди пропорционально долям обслуживания соответствующих сеансов [2].

Существуют следующие алгоритмы обработки очередей [3]:

1. Традиционный алгоритм FIFO.
2. Приоритетное обслуживание (Priority Queuing), которое также называют «подавляющим».
3. Настраиваемые очереди (Custom Queuing).
4. Взвешенное справедливое обслуживание (Weighted Fair Queuing, WFQ).

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

Взаимодействие дистрибьютера с очередями

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

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

Дистрибьютор циклически просматривает наполненность очередей и подключает/отключает воркеры для конкретной очереди. Максимальное количество создаваемых воркеров (Wor) задано в конфигурации дистрибьютора. Количество воркеров может быть ограничено количеством процессоров вычислительной машины. При этом, может использоваться несколько вычислительных машин, объединенных в распределенную систему.

Постановка элементов в очереди осуществляется на основании следующих правил:

1. Массовое формирование документов более 50000 штук.
2. Массовое формирование документов от 10001 до 50000 штук.
3. Массовое формирование документов от 5001 до 10000 штук.
4. Массовое формирование документов от 101 до 5000 штук.
5. Формирование единичных документов и массовое формирование до 100 штук.

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

Структурная схема работы дистрибьютора с очередями представлена на рисунке 1.

Рисунок 1. Структурная схема работы дистрибьютора с очередями.

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

Дистрибьютор просматривает заполненность каждой из очередей. Если очередь с максимальным приоритетом пустая, то ее приоритет становится равным 0. Соответственно, максимальный приоритет смещается на следующую очередь, приоритеты остальных очередей пересчитываются относительно заполненных очередей.

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

Вес очереди, возрастает экспоненциально и имеет вид:

(1)

где w_i - приоритет очереди

(x_i) – значение весового коэффициента очереди

(φ_i) – заполненность очереди

Приоритет очереди (x_i) возрастает от очереди с меньшим приоритетом к большему и имеет вид:

(2)

где (q) – коэффициент приоритета очередей

(i) – номер очереди

Заполненность очереди () зависит от количества элементов в очереди и имеет вид:

(3)

где – количество элементов в i-ой очереди

(N) – максимальное количество элементов в очереди

Исходя из (2) и (3), вес очереди (1) будет иметь вид:

(4)

Общий вес всех очередей (w):

(5)

где (M) – количество очередей

Так как общий вес всех очередей равен 1, то из (4) и (5) следует, что коэффициент приоритета очередей будет равен:

(6)

Скорость формирования документа (t) ограничена мощностью вычислительной машины.

Количество воркеров (P) на одну очередь вычисляется пропорционально весу очереди и имеет вид:

(7)

Зная t и P_i можно рассчитать скорость обработки одной очереди (V_i):

(8)

Исходя из (7) и (8), V_i будет иметь вид:

(9)

В таком случае, общая скорость обработки очередей (V) будет равна:

(10)

Алгоритм работы дистрибьютора представлен на рисунке 2.

Рисунок 2. Алгоритм работы дистрибьютора.

Декомпозиция алгоритма циклического обхода очередей представлена на рисунке 3.

Рисунок 3. Декомпозиция алгоритма циклического обхода очередей.

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

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

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

Вывод

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

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

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

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

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

1. Analysis and simulation of a fair queueing algorithm, Demers, A.; Keshav, S.; Shenker, S. [Электронный ресурс] – https://people.eecs.berkeley.edu/~sylvia/papers/FQ1989.pdf (Дата обращения05.2023).
2. WF/sup 2/Q: Worst-case fair weighted fair queueing, Bennett, J. C. R.; Hui Zhang [Электронный ресурс] – https://people.cs.pitt.edu/~znati/Courses/WANs/Dir-Rel/RdngMtrl/WF2Q.pdf (Дата обращения05.2023).
3. Алгоритмы управления очередями, Дмитрий Федодеев [Электронный ресурс] – https://www.osp.ru/lan/2007/12/4659316 (Дата обращения 25.05.2023).
4. A fair comparison of message queuing systems, Fu G., Zhang Y., Yu G. [Электронный ресурс] – https://ieeexplore.ieee.org/document/9303425 (Дата обращения05.2023).
5. Simulation-based results of weighted fair queuing algorithms for atm networks, Guillemin Fabrice, Dupuis Alain [Электронный ресурс] – https://www.researchgate.net/publication/220145366_Simulation-based_results_of_weighted_fair_queuing_algorithms_for_ATM_networks (Дата обращения05.2023).