Страницы

Поиск по вопросам

четверг, 11 июля 2019 г.

Как сглаживать пики периодических задач на оси времени?

Есть сотни тыс. периодических заданий, где каждое должно выполняться со своим собственным периодом повтора: раз в 12 часов, у других раз в 15 минут, например.
Помимо периода P, у задания ещё два параметра: время T, когда его уже можно начать выполнять (не раньше), и коэффициент срочности K, который означает, как быстро с момента T линейно растёт приоритет этого задания. При прочих равных K = 1/Period
Рабочий процесс дискретный, запускается «шагами» раз в 5 минут по крону. Каждый раз берет охапку заданий, из тех, что уже можно исполнять, ориентируясь на приоритеты на данный момент этих заданий, и не больше, чем своя «ёмкость», которая ограничена.
Ситуация: в один момент времени внезапно пришла сразу 1000 новых заданий. При ёмкости в 300 задач за один шаг такой пик вызовет лавину задержек у всех задач. Поэтому эту 1000 заданий надо постепенно раскидать, чтобы они шли не в единый момент, а +-. Но «разъехались» они по этим новым своим позициям не мгновенно, а в течение какого-то времени. Напр. можно ограничивать скорость «сползания» каждой задачи в % от её периода.
Вопрос: как корректировать фазу периодических заданий, чтобы пики нагрузки «размазывались» по времени? При этом надо, чтобы если какое-то задание и сдвигалось, оно делало это постепенно, маленькими шагами. Тут важно, чтобы интервал выполнения каждого задания был максимально приближен к целевому – у кого-то это 12 часов, у кого-то 15 минут.
По аналогии с физическим миром, как я себе представляю, это похоже на насыпание частиц (кристаллов песка) на поверхность. Чтобы песчинки в итоге распределились более ли менее равномерно, надо поверхность встряхивать, снова и снова. Каждый раз частицы стремятся удалиться от соседей. И это постепенно приводит к равномерному распределению.
Может, есть известный алгоритм, описывающий такую модель?


Ответ

Можно организовать приоритетную очередь заданий. Постараюсь объяснить. Допустим у Вас есть 1000 заданий, каждое со своей периодичностью. Т.е. Вы знаете, в какие моменты времени каждая из этих задач должна в следующий раз запуститься. В таком случае при наступлении некоторого момента времени, когда должна запуститься одна или несколько задач, Вы их не запускаете, а ставите в очередь определенным образом. Например, ёмкость рабочего процесса 300 задач. В некоторый момент времени должно запуститься 450 задач. 300 из них Вы запускаете на выполнение (задержка 0*T), остальные остаются в очереди. Через 5 минут Вы должны запустить еще 170 задач. Вы эти 170 ставите в начало очереди, так что бы рабочий процесс забрал сначала их (задержка 0*T), затем он доберёт до свой емкости из прошлых задач еще 130 (задержка 1*T). Через следующие 5 минут все повторится. При этом есть вероятность, общее количество заданий превысит физический предел обработки 24 часа * 12 задач в час * 300 заданий в обработке. В этом случае часть заданий, которая превышает это число, вообще не будет обрабатываться. Однако и от этого можно избавиться, достаточно для каждого задания отслеживать, сколько оно находится в очереди. Если это значение превысило некоторый порог (необходимо будет рассчитать или определить опытным путём), то повышать приоритет задания, сдвигая его в начало очереди, т.е. запускать "принудительно". Если у Вас задания нескольких разных типов, можно ввести более развитую приоритетную систему.

Комментариев нет:

Отправить комментарий