시간이 지남에 따라 프로세스를 분산시키는 방법 "충돌"최소값 얻기

임베디드 시스템 용 스케줄러를 개발 중입니다. 이 스케줄러는 X 밀리 초마다 각 프로세스를 호출합니다. 이 시간은 물론 각 프로세스에 대해 개별적으로 구성 할 수 있습니다.시간이 지남에 따라 프로세스를 분산시키는 방법 "충돌"최소값 얻기

모든 것이 코딩되어 있으며 모든 프로세스를 필요에 따라 호출합니다. 내가 직면하고있어 문제는 이것이다 :

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

각각마다 10, 15, 5, 30 밀리 초를 호출 할 내가 4 개 프로세스를 설정 상상

문제는 30ms에 도달하면 모든 프로세스가 같은 순간 (하나씩 차례대로) 호출되고 이로 인해 여기에서 올바른 실행이 지연 될 수 있다는 것입니다.

이 문제는 각 프로세스에 지연을 추가하여 해결할 수 있지만 호출 빈도는 유지되므로 주파수는 서로 배수가되지 않습니다. 내 문제는 각 프로세스에 적용 할 지연을 계산하여 충돌 횟수를 최소화하는 방법을 모른다는 것입니다.

이 알고리즘이나 수학적 지침에 대한 알려진 알고리즘이 있습니까?

감사합니다.

출처

2010-01-16 Raúl Ferràs

간격을 충돌 사이에 두 프로세스 사이에 매개 변수가없는 한 다음, 난 당신이 운이 가지이며, 엄격하게 그들에게 순종해야하는 경우 그들의 간격의 LCM이 될 것입니다. 따라서 모든 간격이 서로 상대적으로 중요 할 때 충돌이 최소화됩니다. –

간격이 주어지면 시작 시간이 일치하는 시간을 찾을 수 있습니다 (오프셋이 없다고 가정). 게시물에 대한 댓글에서 Jason이 언급 한 least common multiple을 찾습니다. 일련의 작업에 대한 간격의 분해를 수행하여 LCM을 찾을 수 있습니다.

그래도 greatest common divisor (또는 가장 큰 공통 요소 인 GCF)이 가장 유용한 숫자 일 수 있습니다. 이 번호는 번이 번 반복되는 간격을 알려줍니다. 예제에서 GCF는 5입니다. GCF가 5 인 경우 시작 시간이 겹치지 않도록 각 작업에 1, 2, 3 등의 초기 오프셋을 추가 할 수 있습니다. 따라서 GCF가 5 인 경우 시작 시간이 중복되지 않는 작업을 최대 5 개까지 가질 수 있습니다. GCF가 20 인 경우 시작 시간이 겹치지 않고 최대 20 개의 작업을 예약 할 수 있습니다.두 개 이상의 작업이 상대적으로 소수 일 경우 (GCF = 1) 간격이 변경되지 않으면 이러한 작업에 어떤 오프셋을 사용하더라도 겹침이 발생합니다.

출처

2010-01-17 14:43:46

5의 배수가 7 인 경우 ? 예 : A = 5, B = 7, C = 20 –

5와 7의 GCF는 1입니다 (상대적으로 소수입니다). 정수 시작 시간이 주어지면 충돌이 발생하지 않고 매 5와 7 번 반복되도록 이러한 두 작업을 예약하는 것은 불가능합니다. 문제의 제약에 대해 더 많이 알지 못한다면 나머지 작업 (이 경우 5 개)의 GCF를 가져 와서 충돌하지 않도록 작업 일정을 계획하는 것이 가장 좋습니다. 그런 다음 간격 띄우기가 0 인 작업 B를 예약하면 최대 2 개의 작업이 동시에 시작됩니다. 정수가 아닌 오프셋을 사용할 수 있다면 작업 B에 0.5ms 오프셋을 주면됩니다. –

완벽한 솔루션이 없기 때문에 때때로 충돌합니다. 사이클 길이에 작은 (0.01-0.1ms) 임의 값을 추가하는 것이 좋습니다. 따라서 장기적으로는 거의 동시에 호출하지 않습니다.

5ms 스케쥴러 세분성이있는 경우 첫 번째 스레드는 항상 X + 1ms, 두 번째 X + 2 등으로 호출되므로 중단없는 실행이 항상 1ms 보장됩니다 (10 개의 스레드가있는 경우 X + 0.5, X + 1, X + 1.5가됩니다). 그러나 이것은 구현하기에 매우 까다로울 수 있습니다.

출처

2010-01-16 15:42:05 BarsMonster

스케줄러의 입도는 1ms입니다. 위의 내용은 문제를 쉽게 보여주기위한 예입니다. –

스케줄러에 무한한 세분성이 없다. sqrt (2)를 첫 번째 프로세스의 기간에 추가 할 수 있습니다. sqrt (3)을 두 번째로, sqrt (5)를 세 번째로 ... :) –

이러한 종류의 문제는 실시간 프로그래밍 및 스케줄링 알고리즘의 영역과 직접 관련됩니다. 나는이 과목을 대학에서 강의했고, 잘 기억한다면 Rate-monotonic scheduling이 당신이 찾고있는 알고리즘의 종류이다.

아이디어는주기에 반비례하는 작업에 우선 순위를 지정한다는 개념입니다. 즉, 기간이 작을수록 우선 순위가 높아집니다. 그러나 작업을 중단하고 나중에 다시 시작할 수 있다면이 방법이 효과적입니다.

EDF (earliest deadline first)과 같은 다른 대안이 있지만 동적 스케줄링 알고리즘 (즉, 실행 중에 우선 순위가 할당 됨)입니다.

출처

2010-01-16 16:59:39 Wookai

쉬운 해결책은 서브 루틴을 호출하는 일정을 변경하는 것입니다. 나는. 5, 10, 15 및 30 밀리 초 대신에 예를 들어 살 수 있습니까? 5, 15, 15, 30? 난 당신이 아이디어를 일반화 할 수 있는지 해요,하지만 작동

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

: (A = 5 밀리 PROC, B, C = 15 밀리 PROC, D = 30 밀리 PROC) : 그럼 당신은 다음과 같은 패턴을 사용할 수 있습니다 정적 간격을 실제로 변경할 수있는 경우에만 가능합니다.

당신은 간격을 변경할 수 없습니다, 또한 당신은 변경 :

출처

2010-01-18 08:56:12

내가 썼던 간격은 단지 예일 뿐이다. 스케줄러가 어느 간격에 직면할지 모릅니다. 아이디어는 스케줄러 자체가 충돌을 최소화하기 위해 지연을 조정할 수 있다는 것입니다. 분명히 시간이 항상 정적 인 경우 수동으로 조정할 수 있지만 어떤 간격을 사용할 지 알 수 없습니다. –

시간이 지남에 따라 프로세스를 분산시키는 방법 "충돌"최소값 얻기

답변

관련 문제