# Patent

## Title
Extensible scheduling of tasks in time-triggered distributed embedded systems

## Abstract

A scheduling algorithm for scheduling processor tasks and message transmissions in distributed real-time time-triggered embedded system. The algorithm identifies the earliest starting transmission time and the latest ending transmission time for each message to be transmitted on a bus to define message transmission time-windows. The algorithm then identifies a task execution time-window for each task to be performed in each processor in terms of the message transmission time-windows. The algorithm then optimizes the message transmission time-window by minimizing a peak usage request and an average usage request for each processor. The optimized transmission time-windows allows each processor to be separately scheduled.

## Background
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to a process for scheduling tasks in a distributed time-triggered embedded system and, more particularly, to a process for scheduling processor tasks and message tasks in a distributed real-time time-triggered embedded system using a common communications bus, where the several processors in the system are decoupled from each other to provide scheduling extensibility.
2. Discussion of the Related Art
Embedded systems are known in the art that include a plurality of distributed processors that transmit digital messages between each other on a time-triggered communications bus. The system employs software tasks allocated to each individual processor. The tasks executed by the processors transmit messages between the processors on the communications bus. Because the bus is time-triggered, only one message is transmitted on the bus at a time. The tasks are periodic and have hard deadlines that may produce catastrophic results if not met. For example, in an automotive steer-by-wire embedded system, it is necessary that the outputs from the various processors in the system have strict deadlines. There are also precedent constraints for the tasks where one task may need to be executed before another task is executed, possibly within a single execution period. Therefore, it is necessary that the system properly schedule the execution of the tasks in each processor and the transmission of the task messages on the bus so that all of the deadlines are met and all of the constraints are satisfied.
It is desirable that the scheduling employed in an embedded system be extensible so that if changes are needed or upgrades are developed after the initial implementation of the system, such as adding or removing processors and/or adding or removing tasks, the original schedule is not affected. For example, if a task set is changed at one processor or a new processor is added to the system, then it is desirable that this change not affect the schedules for the tasks and message transmissions of the other processors. If the new messages can be transmitted on the bus without affecting the transmission of the existing messages, then no change is needed for the scheduling of the other processors already in use. Otherwise, it may be necessary to reprogram the bus schedule at great expense.
SUMMARY OF THE INVENTION
In accordance with the teachings of the present invention, a scheduling algorithm is disclosed for scheduling processor tasks and messages in a distributed real-time time-triggered embedded system. The scheduling algorithm first identifies the earliest starting transmission time and the latest ending transmission time for each message to be transmitted on a communications bus during one transmission cycle to determine a message transmission time-window. The algorithm then identifies a task execution time-window for each task to be performed in each processor based on the transmission time-window for each message. Based on the task execution time-windows, the algorithm then derives a usage request function for each processor in the system, where the usage request function is the addition of usage requests for each task to be executed by the processor. From the usage request function for each processor, the algorithm computes a peak usage request for each processor and an average usage request for each processor. The algorithm then optimizes the message transmission time-windows by minimizing the peak usage request and the average usage request for each processor. From the optimized message transmission time-windows, the algorithm then provides independent scheduling for the tasks executed by each individual processor and the messages transmitted on the bus, where the processors are decoupled from each other and the bus.
Once the optimized message transmission time-window for each message is determined on the communications bus, the algorithm can make the scheduling even more accommodating for later upgrades by selectively assigning time slots within the time-window for the messages so that future messages can be added to time slots between the messages in the transmission cycle. In this embodiment, the algorithm first determines an initial message schedule where the messages are assigned a certain time slot within their transmission time-window, using, for example, an earliest-deadline-first scheduling process, based on a known scheduling technique. The algorithm then reallocates the messages as evenly as possible within the transmission cycle, but still maintaining the messages within a time slot in their transmission time-window. Reallocating the messages within the time windows may include solving for a quadratic optimization problem that provides an optimization model. The real numbers of the solution of the quadratic optimization problem are rounded down to the nearest integer so that the messages are positioned within a time slot in their assigned time-window to allow unused time slots to be available between the messages to provide the future extensibility.
Additional advantages and features of the present invention will become apparent from the following description and appended claims, taken in conjunction with the accompanying drawings.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a diagram of an embedded system including a plurality of processors connected to a communications bus;
FIG. 2 is a flow chart diagram showing an operation for scheduling messages and tasks in the system shown in FIG. 1, according to an embodiment of the present invention;
FIG. 3 is a diagram showing a usage request function for a processor in scheduling the system shown in FIG. 1;
FIG. 4 is a flow chart diagram showing a process for scheduling messages in time slots within a transmission cycle on a time-triggered bus for the system shown in FIG. 1, according to another embodiment of the present invention; and
FIG. 5 is a diagram showing a technique for assigning messages to time slot for a scheduling algorithm of the invention.



DETAILED DESCRIPTION OF THE EMBODIMENTS
The following discussion of the embodiments of the invention directed to a process for scheduling processor tasks and message transmissions on a communications bus in an embedded system to increase system schedulability and extensibility is merely exemplary in nature, and is in no way intended to the limit the invention or its applications or uses.
FIG. 1 is a plan view of an embedded system 10 of the type discussed above that includes a plurality of processors 12 and 14 that are programmed to perform a plurality of tasks 16. In one example, each processor 12 and 14 receives signals from an appropriate sensor 18 and 20, respectively, for a particular application. Additionally, the processors 12 and 14 control an actuator 22 and 24, respectively, for the particular application. The results of the various tasks 16 executed by the processors 12 and 14 are transmitted between the processors 12 and 14 on a time-triggered communications bus 26 as messages 28.
In this example, task t11 in the processor 12 receives signals from the sensor 18 and sends a message m11-21 on the bus 26 to task t21 in the processor 14, which issues a command to the actuator 24. Likewise, task t22 in the processor 14 receives signals from the sensor 20 and sends a message m22-12 on the bus 26 to the task t12, which issues a command to the actuator 22. There are end-to-end deadlines for the data sensing and the command issuing. According to the invention, the task executions for the processors 12 and 14 and the message transmissions on the bus 26 are scheduled so that all of the deadlines are met, all the precedent constraints are satisfied, such as t11→m11-21→t21, and the schedules generated are extensible for later upgrades.
The known scheduling techniques for the type of embedded system discussed above have scheduling and extensibility limitations because the task scheduling in the processors are coupled, i.e., all of the processor tasks are scheduled together. This coupling is a result of the precedence relationship between the tasks 16 in the processors 12 and 14. The present invention proposes decoupling the processors 12 and 14 in the embedded system 10 to provide the task scheduling and the message scheduling by enforcing the precedence relations through time-slicing, i.e., assigning specific time-windows for the transmission of the messages 28 on the bus 26, so that the scheduling of the tasks 16 in the processors 12 and 14 can be performed independently from each other. In other words, the scheduling algorithm first identifies an optimized time-window for the messages 28 to be transmitted on the bus 26 between the processors 12 and 14, and then based on when the messages 28 will be transmitted, determines when the tasks 16 need to be executed to generate the messages 28. This distributed scheduling as a result of decoupling the processors 12 and 14 allows for single processor scheduling that can be solved effectively.
The time-window for the message transmissions to provide the system schedulability and extensibility is determined while satisfying the timing requirements and the precedent constraints. The time-window determination is an optimization problem that includes minimizing an objective function, but satisfying precedent constraints, which can be solved by many existing algorithms. The main challenge is how to obtain the objective function for schedulability and extensibility. According to one embodiment of the invention, the schedulability and the extensibility are related to peak processor usage request and average processor usage request.
For the calculations discussed below, there are m processors and N tasks, where the tasks 16 are already allocated to the processors 12 and 14. The task set is defined by (tij, i=1, . . . , m,j=1, . . . , ni), where the tasks (tij, j=1, . . . , ni) are allocated to the processor pi and Σi=1mni=N. For each task tij, Aij is its arrival time, Cij is its worst case execution time, Dij is its deadline, and Tij is its period. The order of performing the tasks 16 has a known precedent. The precedent relationships are represented as “tij precedes tkl” (also denoted as tij→tkl), which means that the task tij must be executed before the task tkl within one period. It is necessary to schedule the task executions for each processor 12, 14 so that all of the deadlines are met, all of the precedent constraints are satisfied and the derived schedules are extensible for later upgrades.
The task and message scheduling of the invention is based on the assumptions that there is no communication delay between the tasks 16, i.e., the output of a task tij can be transmitted to another task tkl as an input without delay, and all of the tasks 16 have the same period, i.e., Tij=T for all i and j. The first assumption results from the fact that the communications bus 26 can be modeled as a special processor and the messages 28 transmitted on the bus 26 can be viewed as tasks to be executed on the bus processor. For example, if the task tij needs to send a message mij-kl to task tkl on the bus 26 because of the precedence relation “tij proceeds tkl,” then the bus 26 can be viewed as a processor pb and the message mij-kl as a task to be executed on pb. Its arrival time can be the same as the arrival time of tij, its execution time can be equal to its transmission time, its deadline can be the same as the deadline of tkl and its period can be the same as the period of tij. Also, the precedence relationship “tij precedes tkl” is replaced by “tij precedes mij-kl” and “mij-kl precedes tkl.”
The second assumption is provided because tasks with different periods can always be transformed to tasks with the same period. If the tasks have different periods, only the scheduling for the time interval that is equal to the least common multiple of the periods of all tasks needs to be solved. Therefore, every invocation of each task within the interval can be treated as a new task, and all of the new tasks will have the same period that is equal to the least common multiple of the periods of all of the old tasks. Then, instead of solving the scheduling for the set of old tasks with different periods, the scheduling can be solved with a set of new tasks with the same period.
To solve for the above described extensible distributed scheduling, a time-slicing approach is employed to decouple the scheduling for the processors 12 and 14. In the decoupling approach, for each message mij-kl on the bus 26, a message time-window [bij-kl, eij-kl] is assigned for its transmission so that all of the precedent constraints among the processors 12 and 14 are satisfied by the time-window assignments, and all of the necessary timing requirements are satisfied. Particularly, the following constraints are defined:




  
    
      
        
          b
          
            ij
            -
            kl
          
        
        ≥
        
          B
          
            ij
            -
            kl
          
        
      
    
    
      
        (
        1
        )
      
    
  
  
    
      
        
          
            e
            
              ij
              -
              kl
            
          
          -
          
            b
            
              ij
              -
              kl
            
          
        
        ≥
        
          C
          
            ij
            -
            kl
          
        
      
    
    
      
        (
        2
        )
      
    
  
  
    
      
        
          e
          
            ij
            -
            kl
          
        
        ≤
        
          E
          
            ij
            -
            kl
          
        
      
    
    
      
        (
        3
        )
      
    
  
  
    
      
        
          
            b
            
              ij
              -
              ku
            
          
          -
          
            e
            
              hv
              -
              il
            
          
        
        ≥
        
          
            max
            q
          
          ⁢
          
            
              ∑
              
                
                  t
                  ip
                
                ∈
                
                  chain
                  ⁢
                  
                    
                      
                        q
                      
                    
                    
                      
                        
                          il
                          -
                          ij
                        
                      
                    
                  
                
              
              
                
              
            
            ⁢
            
              
            
            ⁢
            
              
                C
                ip
              
              ⁢
              
                
              
              ⁢
              for
              ⁢
              
                
              
              ⁢
              all
              ⁢
              
                
                  
                
                ⁢
                
                  
                
              
              ⁢
              k
            
          
        
        ≠
        
          i
          ⁢
          
            
          
          ⁢
          and
          ⁢
          
            
          
          ⁢
          h
        
        ≠
        i
      
    
    
      
        (
        4
        )
      
    
  




In equations (1)-(4), Bij-kl and Eij-kl are the earliest starting time and the latest ending time, respectively, for the transmission of the message mij-kl. Bij-kl and Eij-kl are obtained by an algorithm discussed below that ensures that all of the tasks in the dependency chain preceding mij-kl are completed before Bij-kl, and after the messages arrival, and all of the tasks in the dependency chain succeeding mij-kl are completed after Eij-kl, and before the messages deadline. Cij-kl is the transmission time for the message mij-kl. Equation (2) states that the time-window [bij-kl, eij-kl] is longer than Cij-kl so that the message mij-kl is transmitted within the time-window. chainil-ijq is the qth task chain in the processor pi between til and tij, chainil-ijq={til,tiq1, . . . ,tiqr,tij|til→tiq1→ . . . →tiqr→tij}. Equation (4) states that the tasks in the processor pi between the messages mhv-il and mij-ku, according to the dependency relationship, are completed within the time-window [ehv-il, bij-ku] between the time-windows of mhv-il and mij-ku. Note that bij-kl and eij-kl are not the exact starting time and finishing time of the transmission for mij-kl, and [bij-kl, eij-kl] is only a time-window within which the transmission of the message mij-kl is scheduled, so bij-kl and eij-kl can be viewed as a new arrival time and a new deadline of the message mij-kl.
FIG. 2 is a flow chart diagram 50 showing the operation of the algorithm for determining the scheduling of the various messages 28 and tasks 16 for the embedded system 10, according to the invention. The algorithm first identifies the earliest starting transmission time Bij and the latest ending transmission time Eij for each message that is to be transmitted on the bus 26 at box 52. The following algorithm can be used to obtain the earliest starting time Bij and the latest ending time Eij for each task 16 and each message 28 that ensures that all of the preceding tasks in the dependency chain are able to be completed before time Bij and after their arrival time, and all of the succeeding tasks in the dependency chain are able to be completed after time Eij and before their deadlines. In this algorithm, the bus 26 is viewed as a processor and the messages mij are viewed as tasks.
Starting from the tasks having no successor and processing on every step those tasks whose successors have been processed:




  
    
      
        
          E
          ij
        
        =
        
          min
          ⁢
          
            {
            
              
                D
                ij
              
              ,
              
                
                  
                    
                      min
                    
                  
                  
                    
                      
                        
                          t
                          ij
                        
                        ->
                        
                          
                            
                              t
                              
                                kl
                                ,
                              
                            
                            ⁢
                            k
                          
                          ≠
                          i
                        
                      
                    
                  
                
                ⁢
                
                  {
                  
                    
                      E
                      kl
                    
                    -
                    
                      C
                      kl
                    
                  
                  }
                
              
              ,
              
                G
                ij
              
            
            }
          
        
      
    
    
      
        (
        5
        )
      
    
  




Let EKij={til|tij→ . . . →til}, i.e., the set of successor tasks of tij on the processor pi. Suppose there are h different latest ending times for the tasks in EKij, denoted as E1>E2> . . . >Eh. Then, Gij is computed by the following procedure:





  
    
      
        
          
            S
            1
          
          =
          
            
              ∑
              
                
                  
                    t
                    ip
                  
                  ∈
                  
                    
                      EK
                      
                        ij
                        ,
                      
                    
                    ⁢
                    
                      E
                      ip
                    
                  
                
                =
                
                  E
                  1
                
              
              
                
              
            
            ⁢
            
              
            
            ⁢
            
              C
              ip
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              
                F
                ⁢
                or
              
              ⁢
              
                
              
              ⁢
              k
            
            =
            
              
                2
                ⁢
                
                  
                
                ⁢
                to
                ⁢
                
                  
                
                ⁢
                k
              
              =
              h
            
          
          ,
          
            
          
          ⁢
          
            
              S
              k
            
            =
            
              
                ∑
                
                  
                    
                      t
                      ip
                    
                    ∈
                    
                      
                        EK
                        
                          ij
                          ,
                        
                      
                      ⁢
                      
                        E
                        ip
                      
                    
                  
                  =
                  
                    E
                    k
                  
                
                
                  
                
              
              ⁢
              
                
              
              ⁢
              
                C
                ip
              
            
          
        
        ⁢
        
          

        
        ⁢
        If
        ⁢
        
          
        
        ⁢
        
          
            
              E
              k
            
            >
            
              
                E
                
                  
                    k
                    -
                    1
                  
                  ,
                
              
              ⁢
              
                
              
              ⁢
              then
              ⁢
              
                
              
              ⁢
              
                S
                k
              
            
          
          =
          
            
              S
              k
            
            +
            
              E
              k
            
            -
            
              (
              
                
                  E
                  
                    k
                    -
                    1
                  
                
                -
                
                  S
                  
                    k
                    -
                    1
                  
                
              
              )
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            G
            ij
          
          =
          
            
              E
              h
            
            -
            
              
                S
                h
              
              .
            
          
        
      
    
    
      
        (
        6
        )
      
    
  




Starting from the tasks 16 having no predecessor and processing on every step those tasks whose predecessors have been processed:




  
    
      
        
          B
          ij
        
        =
        
          max
          ⁢
          
            {
            
              
                A
                ij
              
              ,
              
                
                  
                    
                      min
                    
                  
                  
                    
                      
                        
                          
                            t
                            kl
                          
                          ->
                          
                            t
                            ij
                          
                        
                        ,
                        
                          k
                          ≠
                          i
                        
                      
                    
                  
                
                ⁢
                
                  {
                  
                    
                      B
                      kl
                    
                    +
                    
                      C
                      kl
                    
                  
                  }
                
              
              ,
              
                F
                ij
              
            
            }
          
        
      
    
    
      
        (
        7
        )
      
    
  




Let BKij={til|tij→ . . . →tij}, i.e., the set of predecessor tasks of tij on the processor pi. Suppose there are h different earliest starting times for the tasks in BKij, denoted as B1<B2< . . . <Bh. Then, Fij is computed by the following procedure:





  
    
      
        
          
            S
            1
          
          =
          
            
              ∑
              
                
                  
                    t
                    ip
                  
                  ∈
                  
                    
                      BK
                      
                        ij
                        ,
                      
                    
                    ⁢
                    
                      B
                      ip
                    
                  
                
                =
                
                  B
                  1
                
              
              
                
              
            
            ⁢
            
              
            
            ⁢
            
              C
              ip
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              for
              ⁢
              
                
              
              ⁢
              k
            
            =
            
              
                2
                ⁢
                
                  
                
                ⁢
                to
                ⁢
                
                  
                
                ⁢
                k
              
              =
              h
            
          
          ,
          
            
          
          ⁢
          
            
              S
              k
            
            =
            
              
                ∑
                
                  
                    
                      t
                      ip
                    
                    ∈
                    
                      
                        BK
                        
                          ij
                          ,
                        
                      
                      ⁢
                      
                        B
                        ip
                      
                    
                  
                  =
                  
                    B
                    k
                  
                
                
                  
                
              
              ⁢
              
                
              
              ⁢
              
                C
                ip
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            
              If
              ⁢
              
                
              
              ⁢
              
                B
                k
              
            
            <
            
              
                +
                
                  S
                  
                    
                      k
                      -
                      1
                    
                    ,
                  
                
              
              ⁢
              
                
              
              ⁢
              then
              ⁢
              
                
              
              ⁢
              
                S
                k
              
            
          
          =
          
            
              S
              k
            
            +
            
              (
              
                
                  B
                  
                    k
                    -
                    1
                  
                
                +
                
                  S
                  
                    k
                    -
                    1
                  
                
              
              )
            
            -
            
              B
              k
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            F
            ij
          
          =
          
            
              B
              h
            
            +
            
              
                S
                h
              
              .
            
          
        
      
    
    
      
        (
        8
        )
      
    
  




In the above algorithm for obtaining the earliest starting time and the latest ending time for each task 16 and message 28, Gij is determined to make sure that every successor task tij for the processor pi is able to be completed and meet its own latest ending time. Because there may be partial order among the successor tasks, special attention must be given to the fact that those tasks are executed in the same processor 12 or 14 when computing Gij. For example, suppose there are two successor tasks ti1 and ti2 of the task tij, and there is no dependency between ti1 and ti2. Let E1=4 and E2=3 be the latest ending time of ti1 and ti2, respectively, and Ci1=2 and Ci2=1 be their respective worst case execution time. By letting Gij=min (E1-Ci1, E2-Ci2)=2, then it is incorrect. Because the total execution time for the two tasks is three and the time-window is E1-Gij=2, it is clear that starting from the time Gij=2, ti1 and ti2 cannot both be finished before their ending time on the same processor 12 or 14. The procedure given in the above algorithm for Gij is correct when considering that those tasks are executed by the same processor 12 or 14. It is easy to determine that by following the procedure, Gij=0 for the above example is correct. A similar procedure is also provided for Fij in the above algorithm.
The algorithm then identifies an execution time-window for each task 16 for each processor 12, 14 whose message is to be transmitted on the bus 26, based on the transmission time-windows of the messages 28 at box 54. In one embodiment, the following algorithm calculates the time-window for performing the individual tasks in the processors 12 and 14 based on the message transmission time-windows for the results of the tasks 16, particularly wbij and weij. For message tasks mij-kl on the bus 26, wbij-kl=bij-kl and weij-kl=eij-kl, and for tasks tij on each non-bus processor pi, starting from the tasks 16 having no successor on the processor pi and processing on every step those tasks 16 whose successors on pi have been processed.




  
    
      
        
          we
          ij
        
        =
        
          {
          
            
              
                
                  
                    
                      min
                      ⁢
                      
                        {
                        
                          
                            E
                            
                              ij
                              ,
                            
                          
                          ⁢
                          
                            
                              min
                              
                                
                                  l
                                  ⁢
                                  
                                    :
                                  
                                  ⁢
                                  
                                    t
                                    ij
                                  
                                
                                ->
                                
                                  t
                                  il
                                
                              
                            
                            ⁢
                            
                              we
                              il
                            
                          
                        
                        }
                      
                      ⁢
                      
                        
                          
                            
                              
                            
                          
                        
                        
                          
                            
                              
                            
                          
                        
                      
                    
                  
                
                
                  
                    
                      min
                      ⁢
                      
                        {
                        
                          
                            E
                            
                              ij
                              ,
                            
                          
                          ⁢
                          
                            
                              min
                              
                                (
                                
                                  q
                                  ,
                                  r
                                
                                )
                              
                            
                            ⁢
                            
                              
                                wb
                                
                                  
                                    il
                                    -
                                    qr
                                  
                                  ,
                                
                              
                              ⁢
                              Y
                            
                          
                        
                        }
                      
                    
                  
                
              
              ⁢
              
                
                  
                    
                      
                                                ⁢
                        
                          (
                          
                            q
                            ,
                            r
                          
                          )
                        
                        ⁢
                        
                          :
                        
                        ⁢
                        
                          T
                          ij
                        
                      
                      ->
                      
                        m
                        
                          ij
                          -
                          qr
                        
                      
                    
                  
                
                
                  
                    otherwise
                  
                
              
              ⁢
              
                

              
              ⁢
              Where
              ⁢
              
                
              
              ⁢
              Y
            
            =
            
              
                min
                
                  
                    
                      (
                      
                        u
                        ,
                        v
                      
                      )
                    
                    ⁢
                    
                      :
                    
                    ⁢
                    
                      t
                      ij
                    
                  
                  ->
                  
                    
                      t
                      
                        ir
                        1
                      
                    
                    ->
                    
                      
                    
                    ⁢
                    
                      
                        ...
                        ⁢
                        
                          
                        
                        ⁢
                        
                          t
                          irk
                        
                      
                      ⁢
                      
                        
                      
                      ->
                      
                        m
                        
                          
                            ir
                            k
                          
                          -
                          uv
                        
                      
                    
                  
                
              
              ⁢
              
                
                  (
                  
                    
                      wb
                      
                        
                          ir
                          k
                        
                        -
                        uv
                      
                    
                    -
                    
                      
                        ∑
                        
                          h
                          =
                          1
                        
                        k
                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                        C
                        
                          ir
                          h
                        
                      
                    
                  
                  )
                
                .
              
            
          
        
      
    
    
      
        (
        9
        )
      
    
  




For tasks tij on each non-bus processor pi, starting from the tasks 16 having no predecessor on the processor pi and processing on every step those tasks 16 whose predecessors on the processor pi have been processed:




  
    
      
        
          we
          ij
        
        =
        
          {
          
            
              
                
                  
                    
                      max
                      ⁢
                      
                        {
                        
                          
                            B
                            
                              ij
                              ,
                            
                          
                          ⁢
                          
                            
                              max
                              
                                
                                  l
                                  ⁢
                                  
                                    :
                                  
                                  ⁢
                                  
                                    t
                                    ij
                                  
                                
                                ->
                                
                                  t
                                  il
                                
                              
                            
                            ⁢
                            
                              we
                              il
                            
                          
                        
                        }
                      
                    
                  
                  
                    
                      
                                                ⁢
                        
                          (
                          
                            q
                            ,
                            r
                          
                          )
                        
                        ⁢
                        
                          :
                        
                        ⁢
                        
                          s
                          .
                          t
                          .
                          
                            m
                            
                              qr
                              -
                              ij
                            
                          
                        
                      
                      ->
                      
                        t
                        ij
                      
                    
                  
                
                
                  
                    
                      max
                      ⁢
                      
                        {
                        
                          
                            B
                            
                              ij
                              ,
                            
                          
                          ⁢
                          
                            
                              max
                              
                                (
                                
                                  q
                                  ,
                                  r
                                
                                )
                              
                            
                            ⁢
                            
                              
                                we
                                
                                  
                                    qr
                                    -
                                    ij
                                  
                                  ,
                                
                              
                              ⁢
                              Z
                            
                          
                        
                      
                    
                  
                  
                    otherwise
                  
                
              
              ⁢
              
                

              
              ⁢
              Where
              ⁢
              
                
              
              ⁢
              Z
            
            =
            
              
                max
                
                  
                    
                      (
                      
                        u
                        ,
                        v
                      
                      )
                    
                    ⁢
                    
                      :
                    
                    ⁢
                    
                      m
                      
                        uv
                        -
                        
                          ir
                          1
                        
                      
                    
                  
                  ->
                  
                    
                      t
                      
                        ir
                        1
                      
                    
                    ->
                    
                      
                        ...
                        ⁢
                        
                          
                        
                        ⁢
                        
                          t
                          
                            ir
                            k
                          
                        
                      
                      ->
                      
                        t
                        ij
                      
                    
                  
                
              
              ⁢
              
                
                  (
                  
                    
                      we
                      
                        uv
                        -
                        
                          ir
                          1
                        
                      
                    
                    +
                    
                      
                        ∑
                        
                          h
                          =
                          1
                        
                        k
                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                        C
                        ih
                      
                    
                  
                  )
                
                .
              
            
          
        
      
    
    
      
        (
        10
        )
      
    
  




In the above computation of weij, when the task tij does not have any immediate successor on other processors 12, 14, ∃/(q,r): tij→mij-qr, weij=min{Eij, min1:tij→til(weil-Cil)} can also be used instead of what is used in the algorithm. The intent of this decision in the algorithm is that when the task tij does not have any immediate successor on other processors 12 and 14, the task tij is combined with its successors on the same processor 12 or 14, i.e., the task til, as one super-task for a computation of a usage request function, which is provided by trying to assign the same usage window for the two tasks. Because the main purpose is to identify the time-windows for the message on the bus 26 so that the scheduling on each processor 12, 14 can be decoupled, each individual task 16 is not scheduled at this time. The task scheduling on each individual processor 12, 14 is performed after the time-windows for the messages are optimized. Here, the determination of the processor usage window for each task 16 will lead to the computation of the usage request function, which will be used later for the determination of the optimized time-windows for the messages on the bus 26.
Because the task tij has no immediate successor on other processors 12, 14, implying that it has no direct impact on the time-windows of the messages on the bus 26, it naturally follows that it is desirable to combine tij with its successor for the computation of the usage request function by trying to assign the same usage window for tij and its successors, which would eventually help to simplify the determination of the optimized time-windows for the messages on the bus 26. This also applies to the decision in the algorithm for the computation of wbij when the task tij does not have any immediate predecessor on the other processors 12, 14.
The question then remains as to how to determine bij-kl and eij-kl for the desired schedulability and the extensibility, i.e., how to determine bij-kl and eij-kl so that it is more feasible to schedule the tasks 16 on each processor 12, 14 and the schedules derived are more extensible to accommodate changes for later upgrades. In other words, determining the time-window is a constrained optimization problem, where the constraints are provided by equations (1)-(4), and the objectives for optimization are schedulability and extensibility.
According to the invention, an objective function for schedulability and extensibility is defined that includes a peak usage request and an average processor usage request for each processor 12 and 14. Particularly, from the identified task execution time-windows, the algorithm derives a usage request function for each processor 12 and 14, and then computes the peak usage request and the average usage requests for each processor 12 and 14 at box 56. First, the usage request function for each task tij, ƒij(t):[0,T]→R is defined as:




  
    
      
        
          
            f
            ij
          
          ⁡
          
            (
            t
            )
          
        
        =
        
          {
          
            
              
                
                  
                    C
                    ij
                  
                  
                    
                      we
                      ij
                    
                    -
                    
                      wb
                      ij
                    
                  
                
              
              
                
                  t
                  ∈
                  
                    [
                    
                      
                        wb
                        ij
                      
                      ,
                      
                        we
                        ij
                      
                    
                    ]
                  
                
              
            
            
              
                0
              
              
                otherwise
              
            
          
        
      
    
    
      
        (
        11
        )
      
    
  




Where T is the common period, R is the set of real numbers, Cij is the worst case execution time of tij, and [wbij, weij] is the processor usage window requested by tij that is determined from the message transmission windows.

From the usage request function for each task 16, the usage request function for each processor pi, gi(t):[0,T]→R, is defined as:




  
    
      
        
          
            g
            i
          
          ⁡
          
            (
            t
            )
          
        
        =
        
          
            ∑
            
              j
              =
              1
            
            
              n
              i
            
          
          ⁢
          
            
          
          ⁢
          
            
              f
              ij
            
            ⁡
            
              (
              t
              )
            
          
        
      
    
    
      
        (
        12
        )
      
    
  




Then, the peak usage request for each processor 12, 14 is determined as:




  
    
      
        
          PU
          i
        
        =
        
          
            max
            
              t
              ∈
              
                [
                
                  0
                  ,
                  T
                
                ]
              
            
          
          ⁢
          
            
              g
              i
            
            ⁡
            
              (
              t
              )
            
          
        
      
    
    
      
        (
        13
        )
      
    
  




From equations (11) and (12):





  
    
      
        
          PU
          i
        
        =
        
          
            max
            
              t
              ∈
              
                {
                
                  
                    
                      
                        wb
                        
                          ij
                          ,
                        
                      
                      ⁢
                      j
                    
                    =
                    1
                  
                  ,
                  ⋯
                  ⁢
                  
                    
                  
                  ,
                  
                    n
                    i
                  
                
                }
              
            
          
          ⁢
          
            
              g
              i
            
            ⁡
            
              (
              t
              )
            
          
        
      
    
    
      
        (
        14
        )
      
    
  




The average usage request for each processor 12, 14 is defined as:




  
    
      
        
          
            AU
            i
          
          =
          
            
              
                ∫
                0
                T
              
              ⁢
              
                
                  
                    g
                    i
                    2
                  
                  ⁡
                  
                    (
                    t
                    )
                  
                
                ⁢
                
                  
                
                ⁢
                
                  d
                  t
                
              
            
            
              
                ∫
                0
                T
              
              ⁢
              
                
                  
                    g
                    i
                  
                  ⁡
                  
                    (
                    t
                    )
                  
                
                ⁢
                
                  
                
                ⁢
                
                  d
                  t
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          
            Since
            ⁢
            
              
            
            ⁢
            
              
                ∫
                0
                T
              
              ⁢
              
                
                  
                    f
                    ij
                  
                  ⁡
                  
                    (
                    t
                    )
                  
                
                ⁢
                
                  
                
                ⁢
                
                  d
                  t
                
              
            
          
          =
          
            
              C
              
                ij
                ,
              
            
            ⁢
            then
            ⁢
            
              :
            
          
        
      
    
    
      
        (
        15
        )
      
    
  
  
    
      
        
          AU
          i
        
        =
        
          
            
              ∫
              0
              T
            
            ⁢
            
              
                
                  g
                  i
                  2
                
                ⁡
                
                  (
                  t
                  )
                
              
              ⁢
              
                
              
              ⁢
              
                d
                t
              
            
          
          
            
              ∑
              
                j
                =
                1
              
              
                n
                i
              
            
            ⁢
            
              
            
            ⁢
            
              C
              ij
            
          
        
      
    
    
      
        (
        16
        )
      
    
  




The algorithm then optimizes the message transmission time-windows within their earliest starting time and latest ending time based on the objective function for minimizing the peak and average processor usage requests at box 58 to provide the desired schedulability and extensibility. In one embodiment, the objective function for the message time-window optimization is defined as:




  
    
      
        
          O
          ⁡
          
            (
            
              
                b
                
                  
                    ij
                    -
                    kl
                  
                  ,
                
              
              ⁢
              
                e
                
                  ij
                  -
                  kl
                
              
            
            )
          
        
        =
        
          
            ∑
            
              i
              =
              1
            
            m
          
          ⁢
          
            
          
          ⁢
          
            
              α
              i
            
            ⁡
            
              (
              
                
                  PU
                  i
                  2
                
                +
                
                  AU
                  i
                  2
                
              
              )
            
          
        
      
    
    
      
        (
        17
        )
      
    
  




Where Σi=1mαi=1, αi is the weight for the processor pi and is determined by the system designer. In general αi=1/m. If the schedulability and extensibility of a processor is more important, then the corresponding weight for the processor can be increased. The objective function gives the peak usage request and the average usage request for all of the processors 12, 14 in the system 10.

The reason that the usage request is used to determine the objective function is that the value of the resource usage request represents the level of contention for the resources. If the usage request can be balanced among all of the resources, and over the whole execution period, then the contention for the resources can be reduced on each processor/bus and at each time over the whole execution period, which will make each individual processor/bus scheduling much easier. Because the contention for the resources is reduced, it would be easier to add tasks/processors within the existing schedule without changing the schedule. Thus, the above objective function captures both the desired schedulability and extensibility.
The time-window optimization can now be formulated as an optimization with linear constraints and non-linear objective functions subject to the constraints of equations (1)-(4) as:




  
    
      
        
          min
          
            
              b
              
                
                  ij
                  -
                  kl
                
                ,
              
            
            ⁢
            
              e
              
                ij
                -
                kl
              
            
          
        
        ⁢
        
          O
          ⁡
          
            (
            
              
                b
                
                  ij
                  -
                  kl
                
              
              ⁢
              
                e
                
                  ij
                  -
                  kl
                
              
            
            )
          
        
      
    
    
      
        (
        18
        )
      
    
  




FIG. 3 is a diagram illustrating how the usage request function of equation (12) is defined for a processor and how the objective function of equation (17) is defined. Tasks t11 and t12, whose execution time-windows overlap, are to be executed by processor p1 and task t21 is to be executed by processor p2. Because task t11 must be performed before task t21, the message time-window m11-12 is defined between the execution time-windows for task t11 and task t21. From this the usage request function of the processor p1 is shown in the graph from which the objective function is calculated as discussed above.
Based on the optimized message transmission time-window, the algorithm then performs independent task scheduling for each processor 12, 14 and the bus 26 by using any suitable known uni-processor scheduling technique at box 60. Particularly, after the message time-windows are optimized for all of the messages 28, the scheduling for the tasks 16 in each processor 12, 14 can be solved independently by using max (Aij, max(q,r):tqr→tij,q≠i(eqr-ij)) and min(Dij, min(k,l):tij→tkl,k≠i(bij-kl)) as the new arrival time and the new deadline, respectively, of the task tij for the processor pi, i=1, . . . m, and j=1 . . . ni, because the dependency among tqr, mqr-ij, tij, mij-kl, and tkl are enforced by the new arrival time and the new deadline. Any of the several and existing suitable single processor scheduling methods can be used for scheduling the tasks 16 in each individual processor 12 and 14. Note that the dependencies among the tasks 16 for the same processor are not enforced by the new arrival times and the new deadlines. Further, only the dependencies among the tasks 16 in the processors 12 and 14 are enforced by the new arrival times and the new deadlines. In other words, in the uni-processor scheduling process, the task dependencies in the same processor still need to be considered.
Once the optimized time-window for each message is determined for each message as discussed above at the box 58, another embodiment of the present invention determines which time slot in the optimized time-window the message 28 will actually be sent on the bus 26 so that the messages are spaced apart in time to allow other messages to be inserted into the schedule at a later date if desired to further increase the schedulability. It is stressed that the above described process shown in the flow chart diagram 50 does not need to use the following time slot reallocation procedure in that other time slot allocation procedures can be used. Also, the following described time slot reallocation procedure does not need to be used in the process described above for decoupling the processors 12 and 14.
The scheduling technique of this embodiment of the invention can further be described as follows. Suppose the transmission cycle of a time-triggered communications bus consists of N slots, where there are m messages to be scheduled in the N slots for transmission. For each message m, Am, Dm and Cm are its arrival time, deadline and transmission time, respectively. Note that Am, Dm and Cm are all integers, and are measured by the number of the time slots. There are also precedence relationships among the messages m, which are represented in the form of “message i precedes message j,” or in short “i precedes j.” The messages 28 need to be transmitted in the time slots, i.e., to determine what time slot to use to transmit what message m, so that all the deadlines are met and all the precedence relationships are satisfied. It is also desirable that the schedule be extensible, i.e., if some changes are needed after the implementation of the system 10, such as adding or removing processors or adding or removing tasks for the purpose of upgrading, the schedule for the remaining messages m on the bus 26 would not be affected. For example, if the task set is changed at one processor 12, 14 or a new processor is added to the system 10, then it is necessary that this change not impact the schedule for the remaining messages 28 on the bus 26. If the new messages m can be transmitted on the bus 26 without affecting the transmission of the existing messages, then no change is needed for the schedule of the existing messages m, which means that the task schedules for those corresponding processors 12, 14 remain unchanged. Otherwise, it may be necessary to rebuild the schedule for the whole system, which may be very costly.
To provide the above described extensible scheduling for messages on a time-triggered bus, according to this embodiment of the invention, a two step process is performed. FIG. 4 is a flow chart diagram 62 showing a process for reallocating the time slots for the messages to provide extensibility. First the algorithm derives the initial message schedule for the time-triggered bus 26 within the optimized message time-window using a suitable algorithm at box 64. In other words, the algorithm determines a schedule for the message transmission on the time-triggered bus 26 to schedule the messages in the time slots so that all deadlines and precedence constraints are satisfied in the manner as discussed above. Suitable algorithms are known in the art to derive a schedule for a set of tasks with precedence relationships and different arrival times. For example, the article J. Blazewicz, “Scheduling Dependent Tasks with Different Arrival Times to Meet Deadlines,” E.Gelenbe, Ed., Modeling and Performance Evaluation of Computer Systems, North-Holland Publishing Company (1976) discloses one such example. In this article, the arrival times and deadlines of the tasks 16 that are involved in precedence relationships are revised so that the precedence relationships are enforced by the revised arrival times and deadlines.
Next, an earliest-deadline-first (EDF) scheduling approach is used for the set of tasks with revised arrival times and deadlines without precedence relationships. The revision of the arrival times and the deadlines is performed by starting from the tasks 16 having no successor and processing on every step those tasks whose successors have been processed to revise the deadlines. This step is shown in the following equation.

Dk*=min(Dk,min{Dj*−Cj; for all j with “k precedes j”})  (19)

Starting from the tasks having no predecessor and processing on every step those tasks whose predecessors have been processed, the arrival times are revised as:

Ak*=max(Ak,max{Aj*+Cj; for all j with “j precedes k”})  (20)

Equations (19) and (20) identify the order of when the messages 28 will be transmitted in the transmission cycle. For example, FIG. 5 shows a time cycle 70 including ten time slots 72 where each message m1, m2 and m3 is transmitted during the time cycle 70. The time cycle 70 repeats itself in that the messages m1-m3 are sent during each time cycle 70. In this example, based on the discussion above, the message m1 must be sent within the time-window including the time slots 2 and 3, the message m2 must be sent within time-window including the time slots 3-5 and the message m3 must be sent within time window including the time slots 4-8 to meet the deadlines and precedent constraints discussed above. The length of the time-windows for the messages m1-m3 is different because of different types of messages and the priorities of the messages m1-m3. For the time cycle 70, the message m1 is assigned the time slot 2, the message m2 is assigned the time slot 3 and the message m3 is assigned the time slot 4, which fulfills their time requirements at the beginning of each time-window period, but does not allow for future messages based on other precedence and constraints to be provided between the message m1 and m2, the message m1 and m3 and the message m2 and m3.
In the second step, the algorithm then redistributes the messages 28 within the transmission cycle 70 without violating the message order in the original schedule so that the precedent constraints are still satisfied, and without violating the message deadlines, so that the messages 28 are allocated as uniformly as possible within the transmission cycle 70. The purpose of the second step is for the extensibility. Because the arrival times and the deadlines for future messages are unknown, it is assumed that the arrivals of the later added messages are uniformly distributed over the transmission cycle 70. If the existing messages are distributed as uniformly as possible within the transmission cycle 70, then it is more likely to find appropriate unoccupied time slots 72 for later added messages for the upgrade. Therefore, there is less of a chance that the schedule for the remaining messages will have to be changed.
It is assumed that the transmission order of the messages m in the schedule is (1, 2, . . . , M) and the slot assignments are k1<k2< . . . <kM, i.e., the message j is scheduled into the slot kj. To provide the extensibility, it is necessary to reallocate the messages 28 as evenly as possible within the transmission cycle 70 without violating the message deadline and without violating the message transmission order determined by the initial schedule.
The process of reallocating the messages can be provided by an optimization model as follows. Let X [j] be the slot number that the message j is allocated to after the reallocation. The reallocation is then formulated as:

Minimize └Σj=1 to M−1(X[j+1]−X[j]−1)2+(N+X[1]−X[M]−1)2┘  (21)

Subject to Aj≦X[j]≦Djƒo j=1, 2, . . . ,M and X[j]+1≦X[j+1]ƒ or j=1, 2, . . . ,(M−1)

If X[j] is required to be an integer for every j, then equation (21) becomes an integer programming problem. For the optimization, X[j] is allowed to be a real number, and the optimization then becomes a quadratic programming problem that can be solved more effectively by existing algorithms. The algorithm solves the quadratic programming problem for the initial message schedule based on equation (21) for the reallocation of the messages at box 66. The algorithm then rounds the real numbers of the solution down to the nearest integer and returns the solution as the extensible message schedule at box 68.
Referring back to FIG. 5, a second time cycle 78 including time slots 80 shows how the messages m1-m3 are reallocated in the transmission cycle 78 by equation (21). Particularly, message m1 is still allocated to time slot 2, but message m2 is allocated to time slot 5 and message m3 is allocated to time slot 8. In this reallocation, all of the messages m1-m3 are transmitted during their assigned time-window, but the time slots 3 and 4 are left open between the time slots 2 and 5, the time slots 6 and 7 are left open between the time slots 5 and 8 and the time slots 9, 10 and 1 are left open between the time slots 8 and 2, thus allowing for other messages to be inserted into these open time slots later without changing the scheduling of the messages m1-m3.
The foregoing discussion discloses and describes merely exemplary embodiments of the present invention. One skilled in the art will readily recognize from such discussion and from the accompanying drawings and claims that various changes, modifications and variations can be made therein without departing from the spirit and scope of the invention as defined in the following claims.

## Claims

1. A method for scheduling messages on a communications bus and scheduling tasks to be performed by a plurality of processors in an embedded system, said method comprising:
identifying an earliest starting transmission time and a latest ending transmission time for each message to be transmitted on a communications bus to define a message transmission time-window for each message;
identifying a task execution time-window for each task to be performed by each processor in the system based on the message transmission time-windows, wherein identifying an earliest starting transmission time and a latest ending transmission time and identifying a task execution time-window includes determining that all precedent constraints for the tasks are satisfied and all timing requirements for the messages are satisfied;
determining a usage request function for the processors based on the task execution time-windows;
determining a peak usage request and an average usage request for each processor based on the usage request function;
optimizing the message transmission time-windows for each message within the earliest starting transmission time and the latest ending transmission time of each message by minimizing the peak usage request and the average usage request; and
independently scheduling the tasks for each processor based on the optimized message transmission time-windows.

2. The method according to claim 1 wherein identifying an earliest starting transmission time and a latest ending transmission time includes a process that starts with a task that does not have a successor task and processing on a step-by-step basis those tasks whose successor tasks have already been processed.

3. The method according to claim 1 wherein the precedent constraints and the timing requirements are defined by the following equations:



  
    
      b
      
        ij
        -
        kl
      
    
    ≥
    
      B
      
        
          ij
          -
          k
        
        ,
        l
        ,
      
    
  




  
    
      
        e
        
          ij
          -
          kl
        
      
      -
      
        b
        
          ij
          -
          kl
        
      
    
    ≥
    
      C
      
        
          ij
          -
          kl
        
        ,
      
    
  




  
    
      e
      
        ij
        -
        kl
      
    
    ≤
    
      E
      
        
          ij
          -
          kl
        
        ,
      
    
  




  
    
      
        
          b
          
            ij
            -
            ku
          
        
        -
        
          e
          
            hv
            -
            il
          
        
      
      ≥
      
        
          max
          q
        
        ⁢
        
          
            ∑
            
              
                t
                ip
              
              ∈
              
                chain
                ⁢
                
                  
                    
                      q
                    
                  
                  
                    
                      
                        il
                        -
                        ij
                      
                    
                  
                
              
            
          
          ⁢
          
            
              C
              ip
            
            ⁢
            
              
            
            ⁢
            for
            ⁢
            
              
            
            ⁢
            all
            ⁢
            
              
            
            ⁢
            k
          
        
      
      ≠
      
        i
        ⁢
        
          
        
        ⁢
        and
        ⁢
        
          
        
        ⁢
        h
      
      ≠
      i
    
    ,
  



where Bij-kl is the earliest starting time of the message, Eij-kl is the latest ending time of the message, bij-kl and eij-kl define the beginning starting time and the ending time of the message transmission time-window, respectively, and Cij-kl is the transmission time for the message.

4. The method according to claim 1 wherein determining a usage request function for the processors includes determining a usage request function for each task and each processor.

5. The method according to claim 4 wherein determining a usage request function for the processors includes determining a usage request function fij(t) for each task by the equation:




  
    
      f
      ij
    
    ⁡
    
      (
      t
      )
    
  
  =
  
    {
    
      
        
          
            
              C
              ij
            
            
              
                we
                ij
              
              -
              
                wb
                ij
              
            
          
        
        
          
            
              t
              ∈
              
                [
                
                  
                    wb
                    
                      ij
                      ,
                    
                  
                  ⁢
                  
                    we
                    ij
                  
                
                ]
              
            
            ,
          
        
      
      
        
          0
        
        
          otherwise
        
      
    
  




where Cij is a worst case execution time of the task tij , wbij is an earliest execution time of the task tij , and weij is a latest ending time of the task tij.

6. The method according to claim 5 wherein determining a usage request function for each processor includes using the equation:




  
    
      
        g
        i
      
      ⁡
      
        (
        t
        )
      
    
    =
    
      
        ∑
        
          j
          =
          1
        
        
          n
          i
        
      
      ⁢
      
        
      
      ⁢
      
        
          f
          ij
        
        ⁡
        
          (
          t
          )
        
      
    
  
  ,




where gi(t) is the usage request function for each processor and fij(t) is the usage request function for each task.

7. The method according to claim 1 wherein determining a peak usage request (PU) includes using the equation:




  
    
      PU
      i
    
    =
    
      
        max
        
          t
          ∈
          
            {
            
              
                
                  
                    wb
                    
                      ij
                      ,
                    
                  
                  ⁢
                  j
                
                =
                1
              
              ,
              ⋯
              ⁢
              
                
              
              ,
              
                n
                i
              
            
            }
          
        
      
      ⁢
      
        
          g
          i
        
        ⁡
        
          (
          t
          )
        
      
    
  
  ,




and determining an average usage request (AU) includes using the equation:




  
    
      AU
      i
    
    =
    
      
        
          ∫
          0
          T
        
        ⁢
        
          
            
              g
              i
              2
            
            ⁡
            
              (
              t
              )
            
          
          ⁢
          
            
          
          ⁢
          
            d
            t
          
        
      
      
        
          ∑
          
            j
            =
            1
          
          
            n
            i
          
        
        ⁢
        
          
        
        ⁢
        
          C
          ij
        
      
    
  
  ,




where gi(t) is the usage request function for each processor, wbij is an earliest execution time of the task, and Cij is a worst case execution time of the task.

8. The method according to claim 1 wherein optimizing the message transmission time-windows includes using the equation:




  
    
      O
      ⁡
      
        (
        
          
            b
            
              
                ij
                -
                kl
              
              ,
            
          
          ⁢
          
            e
            
              ij
              -
              kl
            
          
        
        )
      
    
    =
    
      
        ∑
        
          i
          =
          1
        
        m
      
      ⁢
      
        
      
      ⁢
      
        
          α
          i
        
        ⁡
        
          (
          
            
              PU
              i
              2
            
            +
            
              AU
              i
              2
            
          
          )
        
      
    
  
  ,




where b is the starting time of the message time-window, e is the ending time of the message time window, αi is a weight for the processor, PUi is the peak usage request for the processor time window and AUi is the average user request for the processor.

9. The method according to claim 1 further comprising determining an initial message schedule for assigning the messages to time slots in the optimized message time-window, and reallocating the messages in the time slots to provide unused time slots between the messages.

10. The method according to claim 9 wherein reallocating the messages in the time slots includes substantially evenly spacing the messages in the message time-window.

11. A method for scheduling messages on a communications bus and scheduling tasks to be performed by a plurality of processors in an embedded system, said method comprising:
identifying an earliest starting transmission time and a latest ending transmission time for each message to be transmitted on a communications bus to define a message transmission time-window for each message;
identifying a task execution time-window for each task to be performed by each processor in the system based on the message transmission time-windows, wherein identifying an earliest starting transmission time and a latest ending transmission time and identifying a task execution time-window includes determining that all precedent constraints for the tasks are satisfied and all timing requirements for the messages are satisfied;
optimizing the message transmission time-windows for each message within the earliest starting transmission time and the latest ending transmission time of each message so as to decouple the scheduling of the processors from each other;
determining a usage request function for the processors based on the task execution time-windows and determining a peak usage request and an average usage request for each processor based on the usage request function, wherein optimizing the message transmission time-windows includes minimizing the peak usage request and the average usage request; and

independently scheduling the tasks for each processor based on the optimized message transmission time-windows.

12. The method according to claim 11 further comprising determining an initial message schedule for assigning the messages to time slots in the optimized message time-window, and reallocating the messages in the time slots to provide unused time slots between the messages.

13. An apparatus having a computing device configured to schedule messages on a communications bus and schedule tasks to be performed by a plurality of processors in an embedded system, said apparatus comprising:
means for identifying an earliest starting transmission time and a latest ending transmission time for each message to be transmitted on a communications bus to define a message transmission time-window for each message;
means for identifying a task execution time-window for each task to be performed by each processor in the system based on the message transmission time-windows, wherein the means for identifying an earliest starting transmission time and a latest ending transmission time and the means for identifying a task execution time-window both include means for determining that all precedent constraints for the tasks are satisfied and all timing requirements for the messages are satisfied;
means for determining a usage request function for the processors based on the task execution time-windows;
means for determining a peak usage request and an average usage request for each processor based on the usage request function;
means for optimizing the message transmission time-windows for each message within the earliest starting transmission time and the latest ending transmission time of the message by minimizing the peak usage request and the average usage request; and
means for independently scheduling the tasks for each processor based on the optimized message transmission time-windows.

14. The apparatus according to claim 13 wherein the means for identifying an earliest starting transmission time and a latest ending transmission time and the means for identifying a task execution time-window include means for starting with a task that does not have a successor task and processing on a step-by-step basis those tasks whose successors tasks have already been processed.

15. The apparatus according to claim 13 wherein the means for determining a usage request function includes means for determining a usage request function for each task and each processor.

16. The apparatus according to claim 13 further comprising means for determining an initial message schedule for assigning the messages to time slots on the bus, and means for reallocating the messages in the time slots to provide unused time slots between the messages.

17. A method for scheduling messages on a communications bus and scheduling tasks to be performed by a plurality of processors in an embedded system, said method comprising:
identifying an earliest starting transmission time and a latest ending transmission time for each message to be transmitted on a communications bus to define a message transmission time-window for each message;
identifying a task execution time-window for each task to be performed by each processor in the system based on the message transmission time-windows,
determining a usage request function for the processors based on the task execution time-windows;
determining a peak usage request and an average usage request for each processor based on the usage request function;
optimizing the message transmission time-windows for each message within the earliest starting transmission time and the latest ending transmission time of each message by minimizing the peak usage request and the average usage request;
determining an initial message schedule for assigning the messages to time slots in the optimized message time-window, and reallocating the messages in the time slots to provide unused time slots between the messages; and
independently scheduling the tasks for each processor based on the optimized message transmission time-windows.