Как распределить процессы по времени, получив минимальное количество «коллизий»

Question

Я разрабатываю планировщик для встроенной системы. Этот планировщик будет вызывать каждый процесс каждые 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 мс все процессы вызываются в один и тот же момент (один за другим), и это может отсрочить правильное выполнение отсюда.

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

Есть ли какой-нибудь известный алгоритм для этого или какое-то математическое руководство?

Спасибо.

Answer 1

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

Похоже, однако, что наибольший общий делитель (или наибольший общий множитель GCF) может быть наиболее полезным числом для вычисления. Это число даст вам интервал, с которым повторения произойдут . В вашем примере GCF равен 5. С GCF, равным 5, можно добавить начальное смещение 1, 2, 3 и т. Д. К каждой задаче, чтобы избежать наложения времени начала. Таким образом, при GCF, равном 5, вы можете иметь до 5 задач с начальным временем, которое никогда не будет перекрываться. При значении GCF, равном 20, вы можете запланировать до 20 задач без пересекающихся времен запуска. Если две (или более) задачи являются относительно простыми (GCF = 1), то определенно будет иметь место перекрытие независимо от того, какое смещение вы используете для этих задач, если интервалы никогда не меняются.

Answer 2

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

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

Однако существуют и другие альтернативы, например EDF (самый ранний срок - сначала) , но это алгоритмы динамического планирования (т.е.приоритеты назначаются во время исполнения).

Answer 3

Для этого не существует идеального решения, они будут время от времени сталкиваться. Я бы посоветовал добавить к длине цикла крошечное (0,01-0,1 мс) случайное значение, поэтому в долгосрочной перспективе они действительно редко будут вызываться одновременно.

В качестве альтернативы, если у вас есть гранулярность планировщика 5 мс, первый поток всегда вызывается в X + 1 мс, второй в X + 2 и т. Д., Так что всегда гарантируется 1 мс непрерывного запуска (если у вас есть 10 потоков, то он будет быть Х + 0,5, Х + 1, Х + 1,5). Но это может быть довольно сложно реализовать.

Answer 4

Простое решение - изменить расписание, в котором вы вызываете подпрограммы. То есть вместо 5, 10, 15 и 30 мс, вы можете жить, например, с 5, 15, 15 и 30? Затем вы можете использовать следующую схему: (A = 5 мс, proc, B, C = 15 мс, D = 30 мс):

 AAAAAAAAAAAAAAAAAAAA ...
 B  B  B  B  B  B  B  ...
  C  C  C  C  C  C  C ...
   D     D     D      ...

Я уверен, что вы можете обобщить эту идею, но она работает, только если вы действительно можете изменить статические интервалы.

Если вы не можете изменить интервалы, а также вам необходимо строго соблюдать их, то вам не повезло, поскольку нет параметров для изменения:)