Multi-agent method to improving adaptive real-time management of computing resources

Full Text

Введение

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

В процессе роста сложности и динамики таких систем централизованные методы и алгоритмы управления стали встречать серьёзные трудности:

• с увеличением размерности решаемых задач традиционные методы оказываются малоприменимыми из-за комбинаторного роста числа вариантов и резкого увеличения объёма вычислений;
• требуется всё чаще учитывать не только интересы центра, но и отдельных узлов ВС, а также индивидуальные особенности поступающих задач;
• высокая неопределённость и динамика бизнес-процессов приближают их к границе «хаоса», а принятые ранее решения в любой момент могут изменяться;
• жёсткая привязка ресурсов к единому диспетчеру не обеспечивает необходимой масштабируемости и отказоустойчивости – ключевых требований для современных вычислительных и производственных сред.

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

1 Обзор существующих решений

Недостатки централизованных ВС обусловили потребность в разработке распределённых и самоорганизующихся систем, управляемых коллективом автономных роботов, программных агентов, способных принимать согласованные локальные решения, находясь в коммуникации с другими агентами ВС [3, 4]. Такие ВС показывают превосходство в производительности, позволяя принимать решения в реальном времени [5], и обладают более высокой отказоустойчивостью [6].

Рассматриваемое направление получило развитие в Самарской школе мультиагентных (МА) систем [7]. На основе МА моделей сети потребностей и возможностей (ПВ-сетей) и метода компенсаций при взаимных уступках агентов сформулирована концепция эмерджентного интеллекта – коллективного искусственного интеллекта (ИИ), возникающего в открытых самоорганизующихся системах с использованием онтологий и МА технологий. Решение сложной задачи при таком подходе строится как процесс самоорганизации программных агентов с конфликтными интересами, которые выявляют и разрешают конфликты в ходе непрерывной конкуренции и кооперации на виртуальном рынке ВС. Разрешение конфликтов осуществляется за счёт переговоров агентов, сопровождающихся взаимными уступками, регулируемыми индивидуальными функциями удовлетворённости, и бонусов-штрафов агентов до достижения состояния консенсуса, отражающего «конкурентное равновесие» агентов (когда ни один из агентов не может улучшить своё состояние). Разработанный подход показал свою эффективность при решении ряда задач управления ресурсами в транспорте, промышленном производстве, цепочках поставок и других применениях [8].

Задача эффективного управления ВР стала особенно актуальной в связи с растущей сложностью решаемых задач, развитием суперкомпьютеров, методов и средств ИИ. В [9] предложена модель суперкомпьютерного кластера, развивающая методы систем массового обслуживания для повышения эффективности вычислений. В этой области разработан и применяется ряд решений на основе МА технологий. В [10] заложена теоретическая основа и проведён ряд исследований децентрализованного управления самоорганизующимися ВС. Однако предложенные в ней модели и методы имеют ограничение, связанное с невозможностью обеспечить максимальную адаптивность в реальном времени.

Известны решения, нацеленные на оптимизацию расписания в реальном времени. В [11] описан алгоритм оптимизации расписания задач NDFS (Nearest Deadline First Scheduled), исходя из заданного срока их выполнения с учётом их приоритетов. В [12] эта модель дополнена динамическим ранжированием ресурсов и резервным копированием задач на следующий по рангу ресурс, что повышает устойчивость системы к внештатному выходу ресурса из строя. В [13] описан подход к оптимизации расписания FCFS-LRH (First Come First Served –Left-Right Hole), нацеленный на минимизацию незаполненных промежутков в расписании.

Примеры решения задач динамического планирования в вычислительных средах приведены в [14-19], варианты применения МА систем для управления ресурсами и их расписаниями – в [20]. Большинство описанных в этих работах алгоритмов опирается лишь на общий приоритет задач и на временное окно, когда бронирование ресурса для задачи имеет смысл, и рассматривается только наиболее позднее возможное планирование задачи. При возникновении локального конфликта происходит полное перепланирование расписания или его участка, что может приводить к излишним и произвольным перестановкам в расписании.

Цель настоящей работы – переработать подход к заданию правил планирования задач и обеспечить более высокую адаптивность.

2 Формализация задачи

2.1 Элементы вычислительной системы и их основные параметры

Моделируемая ВС состоит из двух основных типов сущностей: ресурсов, которые выполняют работу, и задач, которые необходимо выполнить. Эти сущности представляются следующими наборами:

• набор ресурсов $R=\left\{r_j\right\}$, $\text{j}=\overline{\mathrm{1,}J}$, где J – количество ресурсов;
• набор задач $O=\left\{o_i\right\}$, $\overline{\mathrm{1,}I}$, где I – количество задач.

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

2.2 Описание задач

Каждая задача o_i из набора O характеризуется длительностью выполнения и моделью функции удовлетворённости. Модель функции удовлетворённости s_i представляет собой набор точек $\left(t,s_i\left(t\right)\right)$, где $s_i\left(t\right)$ – показатель удовлетворённости задачи в случае её выполнения в момент времени t (см. рисунок 1). Функция удовлетворённости может принимать значения в диапазоне $s_i\left(t\right)\in \left[\mathrm{0,1}\right]$. Временная ось не имеет ограничений. Для удобства восприятия графической информации в данной работе используется упрощённое представление – в секундах, от 0 до 10 включительно.

Рисунок 1 – Пример моделифункции удовлетворённости

2.3 Постановка задачи

Необходимо для имеющихся групп ресурсов R и задач O максимизировать целевую функцию S, представляющую собой показатель общей удовлетворённости системы (ПОУС), который включает все задачи и ресурсы: $S={\sum }_{i=1}^I{s}_i\left(t_i\right)$, где t_i – время выполнения задачи o_i (в случае, если для задачи o_i не забронирован ресурс, то считать s_i =0).

2.4 Модель функции удовлетворённости

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

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

Рисунок 2 – Изображение задачи на графике и её функции удовлетворённости

3 Традиционный подход к решению задачи

3.1 Описание алгоритма

В числе традиционных алгоритмов планирования и оптимизации выполнения задач [1, 2] лежит принцип: «первый пришёл – первый исполнился». Для МА системы такой принцип часто применяется, и в алгоритмы не включается взаимодействие с другими агентами задач – агент нового заказа анализирует расписание на предмет свободных мест и выбирает наиболее подходящее место, согласно собственной функции удовлетворённости так, чтобы не затронуть другие задачи.

Пример 1 – наиболее благоприятный для этого алгоритма, когда задача o_new может свободно разместиться и выполниться в момент времени t_peak, совпадающий с пиком собственной функции удовлетворённости. На рисунке 3 видно, что свободное пространство, находящееся в диапазоне ненулевого значения функции удовлетворённости, представляет отрезок времени $t \in \left[\mathrm{2,} 7\right]$ секунд. С учётом длительности выполнения задачи o_new возможное время выполнения задачи находится в пределах $t \in \left[\mathrm{4,} 7\right]$ секунд (рисунок 4). Алгоритм ограничивает функцию удовлетворённости этим промежутком и выбирает наилучшую из возможных позиций для бронирования ресурса. Здесь функция удовлетворённости принимает наибольшее значение в момент времени 5 секунд. Следовательно, агент задачи забронирует ресурс в промежутке времени $t \in \left[\mathrm{3,} 5\right]$ секунд (рисунок 5).

Рисунок 3 – Пример 1, исходная функция удовлетворённости задачи o_new

Рисунок 4 – Пример 1, функция удовлетворённости задачи o_new после её ограничения

Примере 2 – ограниченная функция удовлетворённости имеет область ненулевых значений $t \in \left[\mathrm{6,} 7\right]$ секунд (рисунок 6). Функция удовлетворённости принимает максимальное значение в момент времени 6 секунд. Следовательно, агент задачи забронирует промежуток времени $t \in \left[\mathrm{4,6}\right]$ секунд (рисунок 7).

Рисунок 5 – Пример 1, результат размещениязадачи o_new

Рисунок 6 – Пример 2, функция удовлетворённости задачи o_new после её ограничения

Рисунок 7 – Пример 2, результат размещения задачи o_new

3. 2 Недостаток традиционного алгоритма

 В Примере 3 (рисунок 8) одна из задач (o₁) из последней конфигурации модели смещена вправо на 0.5 секунды. Это изменение в ВС приводит к резкому ухудшению работы алгоритма. На рисунке 8 можно видеть три свободных промежутка времени. Первые два – $t\in \left[\mathrm{0,} 1.5\right]$ и $t\in \left[\mathrm{3.5,} 5\right]$ секунд – имеют продолжительность 1.5 секунды и не могут вместить задачу продолжительностью 2 секунды. Последний промежуток времени (в конце расписания) не имеет ограничения длительности, но на нём невозможно расположить задачу o_new так, чтобы она выполнилась в момент времени, соответствующий ненулевому значению функции удовлетворённости.

В примере 3 возможно сместить задачи o₁ и o₂ за счёт частичного снижения их показателя удовлетворённости так, чтобы между ними образовалось пространство в 2 секунды. Это позволит вместить новую задачу o_new и повысить ПОУС, но для этого нужны переговоры, чтобы учесть индивидуальные особенности каждого участника и его предпочтения.

Рисунок 8 – Пример 3, агент задачи  o_new  не может забронировать ресурс

4 Адаптивное формирование расписаний выполнения заданий на вычислительных ресурсах

4.1 Описание предлагаемого метода

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

Вводятся два дополнительно термина.

• Модификация mod – атомарное изменение существующего расписания: добавление задачи, сдвиг задачи, вытеснение задачи, перераспределение на другой ресурс и т.д. Модификации не носят контекстуальный характер, они являются лишь составляющими конечного плана изменения расписания – патча.
• Патч patch – конечный последовательный набор модификаций. Патч носит контекстуальный характер и всегда относится к конкретному ресурсу, он используется как универсальный пакет передачи информации об изменениях расписания конкретного ресурса как между агентами задач в процессе утверждения патча, так и при отправке утверждённого патча агенту ресурса.

Каждая модификация $mo{d}_{n,m}$ патча $patc{h}_m$ ( $n=\overline{\mathrm{1,}{N}_m}$, $m=\overline{\mathrm{1,}M}$, $N_m$ – количество модификаций в патче $patc{h}_m$, M – количество патчей) вносит изменение в расположение задачи в расписании и влияет на её показатель удовлетворённости. Изменение показателя удовлетворённости задачи при применении к ней модификации $mo{d}_{m,n}$ составляет $\text{Δ}{s}_{n,m}$. Изменение ПОУС при применении патча $patc{h}_m$ составляет $\text{Δ}{S}_{\text{patch}}^m$ и равно сумме всех изменений показателей удовлетворённостей задач, вызванных применением модификаций этого патча $\text{Δ}{S}_{\text{patch}}^m={\sum }_{n=1}^{N_m}\text{Δ}{s}_{n,m}$. Процесс формирования патча состоит из следующих этапов.

• Агент задачи самостоятельно анализирует состояние расписания ресурса и вычисляет наиболее выгодный для системы патч. Здесь «наиболее выгодный» – это такой патч $patc{h}_m$, который имеет наибольшее значение прироста ПОУС $\text{Δ}{S}_{\text{patch}}^m$ среди всех доступных патчей.
• Агент задачи передает патч другим агентам задач, затронутых этим патчем. Другие агенты задач могут принять патч или принять решение о смене ресурса и сообщить об этом агенту задачи, передавшему патч. При принятии решения о смене ресурса агент задачи, рассчитавший патч, рассчитывает его заново и сообщает об изменениях другим агентам задач. Этот цикл длится до тех пор, пока все агенты задач, затронутых патчем, не будут удовлетворены актуальным патчем либо сообщат о смене ресурса.
• Агент задачи, рассчитавший патч, передаёт утверждённый патч агенту ресурса.
• Агент ресурса применяет патч, и, в случае успешного применения, уведомляет всех затронутых агентов задач об успешном применении патча. В случае неудачи агент ресурса сообщает агенту задачи причину ошибки применения патча. Ошибки в применении патча могут возникать по различным причинам, например, устаревшая информация о расписании у агента задачи. Агент задачи может либо принять меры по разрешению проблемы, если такая возможность есть, либо перейти к рассмотрению другого ресурса.
• Алгоритм расчёта наиболее выгодного патча

4.2.1 Формализация задачи

В контекст задачи входят:

• ресурс r и его расписание schedule;
• набор задач O=o_i, $\overline{\mathrm{1,}I}$, уже находящихся в расписании schedule, где I – количество задач в расписании;
• задача o_new, не находящаяся в расписании schedule, которую необходимо разместить.

Новую задачу можно разместить между любыми двумя задачами или по краям расписания. При этом можно сместить любую из размещённых в расписании задач так, чтобы забронированные ими временные участки не пересекались. Всего вариантов размещения новой задачи относительно находящихся в расписании задач I+1, где I – количество задач, уже размещённых в расписании. Для каждого варианта размещения рассматривается до K вариантов сдвига других задач: $K=\left(I+1\right)\cdot {\sum }_{i=1}^I{T}_i,$ где Ti – количество опорных временных точек модели функции удовлетворённости s_i задачи o_i. Область возможных решений представляет гиперповерхность в пространстве размерности I+2, где:

• ось $axi{s}_i,i=\overline{\mathrm{1,}I}$ задаёт время t_i, к которому выполнится задача o_i;
• ось $axi{s}_{I+1}$ задаёт время t_new, в которое выполнится размещаемая задача o_new;
• ось $axi{s}_{I+2}$ отражает приращение ПОУС $\text{Δ}{S}_{\text{patch}}^m$ при расположении задач в расписании в соответствии со значениями остальных осей.

Изображение гиперповерхности для I=1 представлено на рисунке 9. Проекция гиперповерхности на гиперплоскость ΔS=0 (заштриховано) представляет область допустимых вариантов размещения задач в расписании.

Рисунок 9 – Гиперповерхность возможных решений при I=1

Задача алгоритма сводится к поиску патча с максимальным¹ приращением ПОУС. На рисунке 9 максимальному приращению ПОУС соответствует патч, устанавливающий время выполнения размещённой задачи t_i=1 секунда, а новой задачи t_new=4 секунды.

Если нет ни одного варианта, для которого $\text{Δ}{S}_{\text{patch}}^m>0$, то добавление задачи o_new в расписание считается невозможным.

4.2.2 Описание алгоритма

Входными данными являются: состояние расписания ресурса; параметры новой задачи; параметры задач, размещённых в расписании. Результат работы алгоритма – патч с наибольшим приращением ПОУС среди всех возможных патчей.

Для каждого варианта размещения новой задачи в расписании итеративно применяются следующие этапы алгоритма.

• Для выбранного размещения рассчитывается модель сдвига окружающих задач.
• Из полученной модели сдвига задач и их функций удовлетворённости рассчитывается функция стоимости сдвига, отражающая зависимость потери в ПОУС от величины сдвига.
• Рассчитывается функция приращения ПОУС как разница функции удовлетворённости новой задачи и функции стоимости сдвига.
• Составляется патч, включающий добавление новой задачи и сдвиг окружающих задач в соответствии с максимальным значением функции приращения ПОУС.

Затем, из всех рассчитанных патчей выбирается один – с наибольшим значением приращения ПОУС.

Схема алгоритма представлена на рисунке 10.

Сдвиг задач, начиная с задачи o_n вперёд – это такое изменении времени бронирования $\text{Δ}{t}_n^{\text{begin}}>0$ задачи o_n, при котором время бронирования $t_m^{\text{begin}}$ каждой последующий задачи $o_m,m>n$ в расписании изменяется на минимально возможное значение для выполнения условия $t_m^{\text{begin}}>t_{m-1}^{\text{end}}$, где $t_{m-1}^{\text{end}}$ – это момент времени, в который выполнится задача o_m-1, предшествующая задаче o_m, если она будет принята к исполнению в момент времени $o_{m-1}^{\text{begin}}$.

Условия сдвигов назад и вперёд представлены формулами 1 и 2 соответственно.

Рисунок 10 – Схема алгоритма расчёта и выбора наилучшего патча

4.2.3 Расчёт функции стоимости сдвига

В Примере 4 (рисунок 11) представлена работа алгоритма расчёта функции стоимости сдвига для задач o₁ и o₂, где s₁ – функция удовлетворённости задачи o₁, s₂ – функция удовлетворённости задачи o₂. Обе задачи находятся в оптимальном положении. Задачи сдвигаются в сторону увеличения времени их брони (вправо), освобождая пространство перед задачей o₁.

Рисунок 11 – Пример 4, функцииудовлетворённости задач

Согласно изначальному расписанию задача o₁ должна начать обрабатываться в момент времени 1 секунда. Если новую задачу o_new возможно разместить так, чтобы она выполнилась в этот же момент времени, то задача o₁ не сдвигается и стоимость этого нулевого сдвига составит $\text{Δ}{S}_{shift}\left(1\right)=s_1\left(3\right)-s_1\left(3\right)=1-1=0$.

Отрезок времени $t\in \left[\mathrm{1,} 2\right]$ секунд можно освободить, переместив только задачу o₁. При этом она встанет вплотную к задаче o₂. Стоимость сдвига составит $\text{Δ}{S}_{shift}\left(2\right)=s_1\left(3\right)-s_1\left(4\right)=1-0.5=0.5$. Функция стоимости сдвига (рисунок 12) заштрихована под углом 135 градусов. Чтобы освободить участок tϵ[2, 3] секунд, понадобится сдвигать обе задачи (см. условия сдвига (1) и (2) в разделе 4.2.2). Функция стоимости сдвига равна сумме изменений их показателей удовлетворённости $\text{Δ}{S}_{shift}\left(3\right)=\left(s_1\left(3\right)-s_1\left(5\right)\right)+\left(s_2\left(6\right)-s_2\left(7\right)\right)=\left(1-0\right)+\left(1-0.5\right)=1.5$ (рисунок 13). При дальнейшем смещении задачи o₁ функция удовлетворённости s₁ не будет оказывать влияния на результирующую, т.к. значение её функции удовлетворённости будет неизменно равно нулю (рисунок 14). Здесь $\text{Δ}{S}_{shift}\left(4\right)=\left(s_1\left(3\right)-s_1\left(6\right)\right)+\left(s_2\left(6\right)-s_2\left(8\right)\right)=\left(1-0\right)+\left(1-0\right)=2$. Дальнейшее смещение не повлияет на значение функции стоимости сдвига, т.к. значения обеих функций удовлетворённости неизменно будут равны нулю (рисунок 15).

Рисунок 12 – Пример 4, функциястоимости сдвига для tϵ[1, 2]

Рисунок 13 – Пример 4, функциястоимости сдвига для tϵ[1, 3]

Рисунок 14 – Пример 4, функциястоимости сдвига для tϵ[1, 4]

Рисунок 15 – Пример 4, полностьюрассчитанная функция стоимости сдвига

4.2.4 Расчёт функции приращения ПОУС

Разница между функцией удовлетворённости s_new новой задачи o_new и функцией стоимости сдвига задач ΔS_shift, находящихся в расписании, покажет приращение ПОУС ΔS_patch при применении патча, содержащего модификации добавления новой задачи и смещения размещённых.

Если в расписании присутствуют задачи по обе стороны от вставки, то функция стоимости сдвига ΔS_shift рассчитывается из двух компонент: левосторонней $\text{Δ}{S}_{shift}^{\text{left}}$ и правосторонней $\text{Δ}{S}_{shift}^{\text{right}}$. Работа алгоритма расчёта приращения ПОУС представлена на примере 5 с одним отличием от примера 4: задача o_new размещается между задачами o₁ и o₂ (рисунок 16). Результат вычисления обеих компонент функции стоимости сдвига представлен на рисунке 17. Правосторонняя функция стоимости сдвига отражает потерю в ПОУС при сдвиге времени начала обработки задачи o₂. Начало обработки задачи o₂ будет совпадать с временем окончания обработки добавляемой задачи o_new. Функция удовлетворённости также привязана к времени окончания обработки задачи. При рассмотрении правосторонней функции стоимости сдвига разница между s_new и s₂ будет отражать приращение ПОУС в зависимости от расположения задач o_new и o₂.

Рисунок 16 – Пример 5, функции удовлетворённости задач

Рисунок 17 – Пример 5, подготовленные к объединению функции стоимости сдвига

В отличие от правосторонней функции стоимости сдвига левосторонняя отражает потерю в ПОУС при сдвиге времени окончания обработки задачи o₁ и выбранном начале времени обработки задачи o_new. Чтобы две функции стоимости сдвига можно было сложить, необходимо предварительно сместить левостороннюю компоненту вперёд на промежуток, равный длительности новой задачи o_new (рисунок 18). Результат сложения обеих частей функции стоимости сдвига и функция удовлетворённости s_new представлены на рисунке 19.

Рисунок 18 – Пример 5, компоненты функциистоимости сдвига для обоих направлений

Рисунок 19 – Пример 5, функция стоимости сдвига (штриховка 135°) и функция удовлетворённости s_new новой задачи o_new (штриховка 45º)

Рисунок 20 – Пример 5, результат размещения новой задачи

На данном этапе становится видно, как выглядит разница s_new и функции стоимости сдвига. Задача o_new размещается в соответствии с максимальным значением их разности (рисунок 20).

5 Прототип системы управления вычислительными ресурсами

Акторная система реализована на языке Python 3.13 с использованием библиотек:

• thespian – реализация модели акторов для создания распределённых и многопоточных систем;
• pydantic – валидация данных и генерация конструкторов классов;
• loguru – журналирование работы системы;
• pytest – модульное тестирование;
• pickle – сериализация сообщений между агентами.

5.1 Архитектура мультиагентной системы

Роль управления агентами полностью делегирована от центрального объекта акторной системы специальному агенту-менеджеру, который, в отличие от объекта акторной системы, находится в потоке, не связанном с системной оболочкой, что позволяет ему обрабатывать входящие сообщения, не блокируя интерфейс программы. Акторная система выполняет две задачи: инициализация агента-менеджера при запуске модели и чтение стандартного потока ввода. При вводе команд в стандартный поток акторная система отправляет сообщение с текстом команды актору-менеджеру и переходит в режим ожидания следующей команды. Это позволяет вносить изменения в ВС параллельно с протекающим в ней активным процессом, используя единый интерфейс взаимодействия с ВС (консоль программы, объединяющая стандартные потоки ввода и вывода), что упрощает проведение экспериментов.

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

Основные агенты модели – это агенты задач и агенты ресурсов. Схема иерархии агентов представлена на рисунке 21.

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

Рисунок 21 – Схема иерархии агентов

Агент задачи хранит свойства задачи, текущее состояние бронирования ресурса и информацию о всех доступных ресурсах. В рамках проведения эксперимента использованы две модели поведения агента задачи – пассивная и активная, алгоритмы поведения которых рассмотрены в подразделах 3.1 и 4.2.

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

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

Рисунок 22 – Процесс восстановления состояния акторной системы по заданной конфигурации

5.2 Протокол взаимодействия агентов

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

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

Рисунок 23 – Процесс выполненияпользовательской команды

Рисунок 24 – Процесс формированияи принятия патча

 Взаимодействие МА системы с пользователем также выполняется через агента–менеджера (см. рисунок 23).

5.3 Формирование и применение патча

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

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

После корректировки патча агент-инициатор отправляет его на просмотр другим включённым в патч агентам задач. После принятия патча, агент-инициатор снова отправляет патч агенту ресурса. Если агент ресурса определит патч валидным, то он применит этот патч на собственном расписании и уведомит всех затронутых агентов задач об изменении их положения в расписании.

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

Существует два сценария, ведущих к цикличности в переговорах: отказ агента задачи от предлагаемого патча и отказ агента ресурса от применения патча.

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

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

Применение патча – синхронный и атомарный процесс: в каждый момент времени только один агент задачи может успешно применить изменения к расписанию ресурса. Это означает, что в случае поступления нескольких конкурирующих патчей будет гарантировано, что один из них будет применён первым, а остальные получат информацию об изменившемся состоянии ресурса. Благодаря этому агенты, получив обновлённые данные, гарантированно смогут применить патч на ресурсе.

6 Вычислительный эксперимент

Сравнение двух методов между собой производилось путём тестирования, которое выполнял специальный агент. Ему передавалась информация о варьируемых элементах конфигурации ВС: пределы варьирования, шаг варьирования или заранее заданные варианты:

• тип поведения агента задачи – активный или пассивный (пассивное поведение соответствовало следованию традиционному алгоритму, активное – предлагаемому);
• количество задач (от 5 до 25 задач с шагом 5);
• длительность задач (от 2 до 6 часов с шагом 1 час):
• продолжительность модели функции удовлетворённости задач (для всех задач модель функции удовлетворённости имела форму равнобедренного треугольника: длина основания треугольника является продолжительностью модели функции удовлетворённости задачи и варьировалась в промежутке от 3 до 12 часов с шагом 3).

Агент-популятор поочерёдно воспроизводил состояние системы для каждой из возможных комбинаций параметров, все задачи имели одинаковые исходные данные за исключением благоприятного времени выполнения задачи. После завершения переговоров между агентами задач и ресурсов агент-популятор запрашивал их показатели удовлетворённости, на этой основе получал информацию о количестве задач, успешно зарегистрировавших ресурс, и рассчитывал ПОУС.

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

На рисунке 25 показано распределение ПОУС, где видно, что мода распределения у предлагаемого (активный тип поведения агентов задач) алгоритма выше, чем у традиционного (пассивный тип поведения агентов задач).

Рисунок 25 – Распределение ПОУС для активного и пассивного типов поведения агентов задач

На рисунках 26 – 28 показаны зависимости ключевых показателей ВС – ПОУС и количество агентов задач, успешно забронировавших ресурс от варьируемых параметров системы.

На приведённых графиках видно, что адаптивный метод показывает на 25–30% лучший результат по сравнению с традиционным. Это объясняется большей гибкостью предлагаемого алгоритма, который способен найти способ вместить в расписание задачу и повысить ПОУС, в то время как традиционный алгоритм сочтёт невозможным добавление новой задачи в расписание.

Рисунок 26 – Зависимость ключевых показателей от количества задач в системе

Рисунок 27 – Зависимость ключевых показателей от длительности задач

Рисунок 28 – Зависимость ключевых показателей от продолжительности модели функции удовлетворённости

Заключение

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

• высокая адаптивность, т.к. допускается изменять любые ранее принятые решения по включению и сдвигам заказов в расписания ВР;
• коллективное принятие решений, при котором агенты задач анализируют расписание не только с позиции собственных интересов, но и потенциально учитывают влияние изменений на показатель общей удовлетворённости системы;
• гибкость и масштабируемость, достигаемые за счёт децентрализованного взаимодействия агентов;
• подтверждённое вычислительным экспериментом повышение ПОУС на 25–30% за счёт применения адаптивных патчей по сравнению с традиционным методом.

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

¹ Благодаря тому, что результирующая функция кусочно задана, она имеет конечное множество точек, где может быть найден максимум. Добавляя в алгоритм различные «фильтры», снижается количество вариантов перебора и повышается скорость работы алгоритма.

About the authors

F. M. Kiriakov

Author for correspondence.
Email: kiriakov.f.m@gmail.com
ORCID iD: 0009-0000-1585-9852

Master's student at the Institute of Automation and Computer Engineering

P. O. Skobelev

Email: petr.skobelev@gmail.com
ORCID iD: 0000-0003-2199-9557

Candidate of Technical Sciences, Doctor of Technical Sciences, Chief Researcher, Professor at the Department of Computer Science and Computing Systems

References

Supplementary files

Supplementary Files

Action

1. JATS XML

Download

2. Figure 1 – Example of a satisfaction function model

Download (65KB)

Indexing metadata

3. Figure 2 – Graphic representation of the task and its satisfaction function

Download (156KB)

Indexing metadata

4. Figure 3 – Example 1, original task satisfaction function onew

Download (200KB)

Indexing metadata

5. Figure 4 – Example 1, the satisfaction function of task onew after its constraint

Download (150KB)

Indexing metadata

6. Figure 5 – Example 1, result of placing the onew task

Download (138KB)

Indexing metadata

7. Figure 6 – Example 2, the satisfaction function of task onew after its constraint

Download (87KB)

Indexing metadata

8. Figure 7 – Example 2, result of placing task onew

Download (84KB)

Indexing metadata

9. Figure 8 – Example 3, task agent onew cannot book a resource

Download (61KB)

Indexing metadata

10. Figure 9 – Hypersurface of possible solutions for I=1

Download (292KB)

Indexing metadata

11. Figure 10 – Scheme of the algorithm for calculating and selecting the best patch

Download (825KB)

Indexing metadata

12. Figure 11 – Example 4, task satisfaction functions

Download (129KB)

Indexing metadata

13. Figure 12 – Example 4, shift cost function for tϵ[1,2]

Download (94KB)

Indexing metadata

14. Figure 13 – Example 4, shift cost function for tϵ[1,3]

Download (86KB)

Indexing metadata

15. Figure 14 – Example 4, shift cost function for tϵ[1,4]

Download (112KB)

Indexing metadata

16. Figure 15 – Example 4, fully calculated shift cost function

Download (173KB)

Indexing metadata

17. Figure 16 – Example 5, task satisfaction functions

Download (147KB)

Indexing metadata

18. Figure 17 – Example 5, prepared for merging shift cost functions

Download (183KB)

Indexing metadata

19. Figure 18 – Example 5, components of the shift cost function for both directions

Download (208KB)

Indexing metadata

20. Figure 19 – Example 5, shift cost function (135° shading) and satisfaction function snew of the new task onew (45º shading)

Download (230KB)

Indexing metadata

21. Figure 20 – Example 5, result of placing a new task

Download (204KB)

Indexing metadata

22. Figure 21 – Agent hierarchy diagram

Download (145KB)

Indexing metadata

23. Figure 22 – The process of restoring the state of an actor system according to a given configuration

Download (158KB)

Indexing metadata

24. Figure 23 – The process of executing a user command

Download (138KB)

Indexing metadata

25. Figure 24 – The process of forming and accepting a patch

Download (372KB)

Indexing metadata

26. Figure 25 – Distribution of the POUS for active and passive types of task agent behavior

Download (116KB)

Indexing metadata

27. Figure 26 – Dependence of key indicators on the number of tasks in the system

Download (236KB)

Indexing metadata

28. Figure 27 – Dependence of key indicators on task duration

Download (223KB)

Indexing metadata

29. Figure 28 – Dependence of key indicators on the duration of the satisfaction function model

Download (209KB)

Indexing metadata