Method and system for scheduling periodic processes

1. Method of scheduling periodic processes for execution in an electronic system, including in a network, in a data processor, or in a communication device, wherein said electronic system includes a controller for performing said scheduling, wherein a number of N processes P i are already scheduled with each process P i having an individual service interval SI i , and wherein an additional process P N+1 is to be scheduled with a service interval SI N+1 , said method comprising the steps of

scheduling, at each of plural scheduling stages, said additional process P N+1 to maximize a minimum time lag between the execution times of said additional process P N+1 being currently scheduled and the execution times of said number of N already scheduled processes P i by assigning an appropriate initial execution time t ie to said additional process P N+1 being currently scheduled,

wherein said controller calculates the minimum time lag between the execution times of said additional process P N+1 to be currently scheduled and the execution times of each of said number of N already scheduled processes P i , and expresses each calculated minimum time lag as a function of said initial execution time t ie to be assigned to said additional process P N+1 , and

wherein a minimum of all individual minimum time lags between said additional process P N+1 to be currently scheduled and each of said number of N already scheduled processes P i defines an absolute minimum time lag which is maximized by computing a period T of a function that represents the absolute minimum time lag as a function of the initial execution time t ie of the additional process P N+1 to be currently scheduled, and

wherein said initial execution time t ie of said additional process P N+1 to be scheduled is determined by way of breaking an N-flows problem into a number of N different 2-flow problems.

2. Method according to claim 1 , wherein said process is a task, a flow or an operation.

3. Method according to claim 2 , wherein, when plural processes arrive concurrently at said controller, an algorithm is provided that orders said processes for sequential scheduling according to predefined policies.

4. Method according to claim 1 , wherein, in case several processes arrive concurrently at said controller, an algorithm is provided that orders said processes for sequential scheduling according to predefined policies.

5. Method according to claim 1 , wherein the N-flows problem is broken into a number of N different 2-flow problems by calculating the minimum time lag between the execution times of said additional process P N+1 to be currently scheduled and the execution times of said number of N already scheduled processes P i .

6. Method according to claim 5 , wherein said minimum time lag between the execution times of said additional process P N+1 to be currently scheduled and the execution times of said number of N already scheduled processes P i is expressed as a function of said initial execution time t ie to be assigned to said additional process P N+1 to be currently scheduled.

7. Method according to claim 1 , wherein the scheduling mechanism is applied to frequency intervals, to spatial intervals, or to timing intervals.

8. Method of scheduling periodic processes for execution in an electronic system, including in a network, in a data processor, or in a communication device, wherein said electronic system includes a controller for performing said scheduling, wherein a number of N processes P i are already scheduled with each process P i having an individual service interval SI i , and wherein an additional process P N+1 is to be scheduled with a service interval SI N+1 , said method comprising the steps of

scheduling, at each of plural scheduling stages, said additional process P N+1 to maximize a minimum time lag between the execution times of said additional process P N+1 being currently scheduled and the execution times of said number of N already scheduled processes P i by assigning an appropriate initial execution time t ie to said additional process P N+1 being currently scheduled,

wherein said controller calculates the minimum time lag between the execution times of said additional process P N+1 to be currently scheduled and the execution times of each of said number of N already scheduled processes P i , and expresses each calculated minimum time lag as a function of said initial execution time t ie to be assigned to said additional process P N+1 , and

wherein a minimum of all individual minimum time lags between said additional process P N+1 to be currently scheduled and each of said number of N already scheduled processes P i defines an absolute minimum time lag which is maximized by computing a period T of a function that represents the absolute minimum time lag as a function of the initial execution time t ie of the additional process P N+1 to be currently scheduled, and

wherein the period T of the function that represents said absolute minimum time lag is computed as the Least Common Multiple of the Greatest Common Divisors between the service interval SI N+1 of said additional process P N+1 to be currently scheduled and the service intervals SI i of each of said number of N already scheduled processes Pi.

9. Method according to claim 8 , wherein for each of said number of N already scheduled processes P i all “zeros”, defined as multiples of the Greatest Common Divisor between the service interval SI N+1 of said additional process P N+1 to be currently scheduled and the service intervals SI i of each of said number of N already scheduled processes P i , contained within said period T of said absolute minimum distance are generated, wherein each said “zero” of the function of said initial execution time t ie is an input value that produces an output of zero.

10. Method according to claim 9 , wherein a list of said “zeros” is generated containing said “zeros” in a sorted order.

11. Method according to claim 10 , comprising the step of locating, within said list of sorted “zeros, the largest gap between two consecutive “zeros”.

12. Method according to claim 11 , wherein the center of said largest gap is selected as said initial execution time t ie .

13. Method according to claim 9 , wherein for each of said number of N already scheduled processes P i all “zeros” includes shifted multiples of the Greatest Common Divisor of the Greatest Common Divisor between the service interval SI N+1 of said additional process P N+1 to be currently scheduled and the service intervals SI i of each of said number of N already scheduled processes P i , contained within said period T of said absolute minimum distance are generated.

14. A computerized system comprising a computer processor that schedules periodic processes for execution in an electronic system, including in a network, in a data processor or in a communication device, said computerized system comprising a controller that is scheduling a number of N processes P i with each process P i having an individual service interval SI i and that is configured to schedule an additional process P N+1 with a service interval SI N+1 ,

said controller scheduling, at each of plural scheduling stages, said additional process P N+1 to maximize a minimum time lag between the execution times of said additional process P N+1 being currently scheduled and the execution times of said number of N already scheduled processes P i by assigning an appropriate initial execution time t ie to said additional process P N+1 being currently scheduled,

wherein said controller calculates the minimum time lag between the execution times of said additional process P N+1 to be currently scheduled and the execution times of each of said number of N already scheduled processes P i , and expresses each calculated minimum time lag as a function of said initial execution time t ie to be assigned to said additional process P N+1 , and

wherein a minimum of all individual minimum time lags between said additional process P N+1 to be currently scheduled and each of said number of N already scheduled processes P i defines an absolute minimum time lag which is maximized by computing a period T of a function that represents the absolute minimum time lag as a function of the initial execution time t ie of the additional process P N+1 to be currently scheduled, and

wherein said initial execution time tie of said additional process P N+1 to be scheduled is determined by way of breaking an N-flows problem into a number of N different 2-flow problems.