Как распространять процессы, со временем получая минимальное количество “коллизий”
Я разрабатываю планировщик для встроенной системы. Этот планировщик назовет каждый процесс каждыми X миллисекундами; это время может быть настроено отдельно для каждого процесса, конечно.
Все кодируется и называет каждый процесс, как он должен; проблема, с которой я сталкиваюсь, является этим: Предположите, что я установил 4 процесса, которые назовут каждыми 10, 15, 5 и 30 миллисекунд соответственно:
A: 10ms
B: 15ms
C: 5ms
D: 30ms
Получающийся вызов со временем будет:
A |
A B A B |
C C C C C C C | processes being called
D |
----------------------------------
0 5 10 15 20 25 30 35... ms
Проблема состоит в том, что, когда 30 мс достигнут, все процессы называют одновременно (один за другим), и это может задержать корректное выполнение отсюда.
Это может быть решено путем добавления задержки с каждым процессом (но сохраняя его частоту вызова), таким образом, частоты прекращают быть кратными числами друг друга. Моя проблема состоит в том, что я не знаю, как вычислить задержку для применения к каждому процессу, таким образом, количество коллизий минимизировано.
Там кто-либо - известный алгоритм для этого или некоторое математическое руководство?
Спасибо.
4 ответа
Учитывая набор интервалов, вы можете найти время, в течение которого время начала совпадает (при условии отсутствия смещений), найдя , наименее распространенные несколько , как упомянутое Джейсоном в Комментарий к вашему посту. Вы можете найти LCM, делая главное факторизацию интервалов для набора задач.
Похоже, что, хотя величайший общий делитель (или наибольший общий фактор GCF) может быть наиболее полезным числом для вычисления. Этот номер даст вам интервал, при котором повторяются . В вашем примере GCF составляет 5. С GCF из 5, можно добавить начальное смещение 1, 2, 3 и т. Д. Для каждой задачи, чтобы избежать перекрытия времени начала. Таким образом, с GCF 5, вы можете иметь до 5 задач, которые имеют время начала, которые никогда не перекрываются. С GCF 20, вы можете иметь до 20 задач, запланированных без перекрытия начала. Если два (или более) задача являются относительно простыми (GCF = 1), то перекрытие определенно произойдет, независимо от того, какое смещение вы используете для этих задач, если интервалы никогда не меняются.
Для этого нет идеального решения, они время от времени сталкиваются. Я бы предложил добавить крошечное (0,01-0,1 м) случайное значение для длины цикла, поэтому в долгосрочной перспективе они действительно редко вызываются одновременно.
В качестве альтернативы, если у вас есть 5 мс. Гранулярность планировщика, первый поток всегда вызывается при х + 1 мс, вторая при x + 2 и т. Д., Чтобы всегда было гарантировано 1 мс бесперебойного запуска (если у вас есть 10 потоков, то это будет быть х + 0,5, х + 1, х + 1.5). Но это может быть довольно сложно реализовать.
Эта проблема напрямую относится непосредственно область алгоритмов программирования и планирования в реальном времени. Я взял класс на эту тему в колледже, и если я хорошо помню, скорость - монотонное планирование - это вид алгоритма, который вы ищете.
Идея состоит в том, что вы назначаете приоритеты рабочих мест, которые обратно пропорциональны их периоду, то есть тем меньше, чем выше, тем выше приоритет. Но это работает лучше, если вы можете прерывать вашу работу и возобновить их позже.
Существуют другие альтернативы, хотя, подобные EDF (сначала раннего срока) , но это динамические алгоритмы планирования (т.е. приоритеты присваиваются во время выполнения).
Простое решение состоит в том, чтобы изменить график, в котором вы называете подпрограммы. Я Вместо 5, 10, 15 и 30 мс вы можете жить E.g. С 5, 15, 15 и 30? Затем вы можете использовать следующий рисунок: (A = 5 MS Proc, b, c = 15 ms proc, d = 30 ms proc):
AAAAAAAAAAAAAAAAAAAA ...
B B B B B B B ...
C C C C C C C ...
D D D ...
Я уверен, что вы можете обобщить эту идею, но это работает, только если вы можете на самом деле изменить статические интервалы.
Если вы не можете изменить интервалы, а также вам нужно подчиняться им строго, то я вас повезло, так как нет параметров для изменения:)