Расписание отправки сообщений потребителям с разной скоростью

Question

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

Пример. Предположим, у нас есть данные от D1 до Dn.D1 для отправки многим потребителям C1 каждые 5 мс, C2 каждые 19 мс, C3 каждые 30 мс, Cn каждые Rn мс.Dn для отправки на C1 каждые 10 мс, C2 каждые 31 мс, Cn каждые 50 мс

Каков наилучший алгоритм, который планирует эти действия с наилучшей производительностью (CPU, Memory, IO)?

С уважением

Answer 1

Как описано в Helium_1s2, существует второй способ, основанный на том, что я назвал таблицей расписания, и это то, что я использовал сейчас, но у этого решения есть свои ограничения.

Предположим, что у нас есть одна информация для отправки идва потребителя C1 и C2:

Как вы можете видеть, мы должны извлечь нашу таблицу расписания, и мы должны идентифицировать повторяющийся цикл передачи и значение IDLE MINIMUM PERIOD.На самом деле, бесполезно выполнять цикл с наименьшим интервалом времени, например, 1 мс, 1 нс, 1 мин или 1 ч (в зависимости от случая), НО это не всегда лучший период, и мы можем оптимизировать этот цикл следующим образом.

например, один (C1 в 6 и C2 в 9), мы отмечаем, что есть цикл, который повторяется от 0 до 18. с минимальной разностью двух последовательных событий отправки, равной 3. так:

HCF(6,9) = 3 = IDLE MINIMUM PERIOD
LCM(6,9) = 18 = transmission cycle length
LCM/HCF = 6 = size of our schedule table

И таблица расписания:

и цикл отправки выглядит следующим образом:

while(1) {
  sleep(IDLE_MINIMUM_PERIOD); // free CPU for idle min period
  i++; // initialized at 0
  send(ScheduleTable[i]);
  if (i == sizeof(ScheduleTable)) i=0;
}

Проблема с этим методомчто этот массив будет расти при увеличении LCM, что имеет место, если у нас плохая комбинация, например, с rate = простое число и т. д.

Answer 2

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

Вариант 1. Выполните следующие единицы измерения каждый раз (в вашем примере, миллисекунды)

func callEachMs
    time = getCurrentTime()
    for each datum
        for each customer
            if time % datum.customer.rate == 0
                sendMsg()

Это имеет преимуществоне требуя постоянно хранимой памяти - вы просто проверяете каждую единицу времени, следует ли отправлять сообщениеЭто также может относиться к сообщениям, которые не были отправлены в time == 0 - просто сохраните время, когда сообщение было первоначально отправлено по модулю скорости, и замените условное на if time % datum.customer.rate == data.customer.firstMsgTimeMod.

Недостаток этого методаэто полностью зависит от того, всегда ли вызывается со скоростью 1 мс.Если существует задержка, вызванная другим процессом на ЦП, и он пропускает цикл, вы можете пропустить отправку сообщения вообще (в отличие от отправки с небольшим опозданием).

Вариант 2: Поддерживать список списков кортежейгде каждая запись представляет задачи, которые необходимо выполнить за эту миллисекунду.Составьте свой список, по крайней мере, до тех пор, пока самая большая скорость делится на единицу времени (если ваша самая большая скорость составляет 50 мс, а вы переходите на мс, ваш список должен быть не менее 50 мс).Когда вы запустите свою программу, поместите сообщение в первый раз в очередь.И затем каждый раз, когда вы отправляете сообщение, обновляйте его в следующий раз, когда вы отправите его в этом списке.

func buildList(&list)
    for each datum
        for each customer
            if list.size < datum.customer.rate
                list.resize(datum.customer.rate+1)
            list[customer.rate].push_back(tuple(datum.name, customer.name))

func callEachMs(&list)
    for each (datum.name, customer.name) in list[0]
        sendMsg()
        list[customer.rate].push_back((datum.name, customer.name))
    list.pop_front()
    list.push_back(empty list)

Преимущество этого состоит в том, что вы избегаете многих ненужных опций вычисления модуля 1, требуемых.Однако это связано с увеличением использования памяти.Эта реализация также не будет эффективной, если существует большое несоответствие в скорости ваших различных сообщений (хотя вы можете изменить это для более эффективной работы с алгоритмами с более длинными скоростями).И его по-прежнему нужно вызывать каждую миллисекунду.

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

.

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