Method of scheduling successive tasks5826080Abstract A method of scheduling tasks subject to timing and succession constraints essentially comprises grouping the tasks in layers according to succession constraints and scheduling the tasks layer by layer in increasing layer order up to the last layer, if possible, and then deciding that the resulting scheduling succeeds. If the scheduling achieved in a layer other than the first layer does not satisfy one or more constraints applying to a task belonging to the current layer, the method reschedules a layer containing a predecessor task corresponding to an unsatisfied constraint, schedules or reschedules all the other layers higher than the layer of the predecessor task, up to the last layer, if possible, and then decides that the resulting scheduling succeeds. Applications include scheduling of transmission of information on an industrial data bus. Claims There is claimed: Description BACKGROUND OF THE INVENTION
______________________________________
TA1 ›t.sub.min, t.sub.max !=
›0, 4 ms! modulo 10 ms
TA2 ›10, 13 ms! modulo 20 ms
TA3 ›20, 23 ms! modulo 30 ms
TA4 ›30, 32 ms! modulo 40 ms
TA5 ›40, 41 ms! modulo 50 ms
TA6 ›20, 22 ms! modulo 40 ms
______________________________________
These tasks have a macrocycle equal to the lowest common multiple of their combined periods, which is 600 ms. A macrocycle can be divided into 60 microcycles each of 10 ms. Two repetitive tasks can be in conflict if they have to be executed during the same microcycle. For example, the tasks TA1, TA3 and TA6 must be executed during the same microcycle ›20 ms, 30 ms! then ›140 ms, 150 ms!, etc. To determine a schedule that suits the worst case scenario, it is sufficient to consider a microcycle in which all tasks without exception must be executed once. In practise, the tasks do not all occur in the same microcycle. An imaginary case in which this event occurs is considered below. Time shifting can shift the execution time of each task into the interval of the same microcycle ›0, 10 ms!. It is defined by the formula: t.sub.st.sup.Kimag =t.sub.st.sup.K -k.PGCD where t.sub.st.sup.Kimag is the imaginary, or theoretical, execution start time of a task K; t.sub.st.sup.K is the real execution start time of the task K; PGCD is the duration of a microcycle, i.e. the highest common denominator of the periods; and k is an integer such that the imaginary execution start time t.sub.st.sup.Kimag of the task K is shifted into the required microcycle, in this instance the microcycle ›0, 10 ms!. The interval ›t.sup.K.sub.min, t.sup.K.sub.max ! defined by all the constraints applying to the task K is therefore also shifted by -k.PGCD. The scheduling method of the invention is then applied in this interval ›0, 10 ms!. When a permutation satisfying all the constraints has been determined, the actual execution times t.sup.K.sub.st are deduced from the imaginary execution start times using the formula: t.sub.st.sup.K =t.sub.st.sup.Kimag +k.PGCD modulo the period of the task K. FIG. 5 shows the resulting scheduling of the tasks over the interval 0 to 100 ms, the interval 100 ms to 600 ms not being shown but being scheduled in a similar way. Each execution interval is shown in black. Consider, for example, the interval 20 ms to 30 ms in which there can be conflict between the tasks TA1, TA3 and TA6. The task TA1 is executed in the interval 24 ms to 25 ms. The task TA3 is executed in the interval 22 ms to 23 ms. The task TA6 is executed in the interval 21 ms to 22 ms. Thus TA1 and TA3 or TA6 are never executed simultaneously, regardless of the microcycle in question, which is one of the 60 microcycles constituting the macrocycle ›0, 600 ms!. In an application in which some tasks can be executed simultaneously, this preliminary step further consists in grouping the tasks into a plurality of independent graphs, if possible, each graph containing only tasks related by constraints. Scheduling a plurality of graphs independently is faster than scheduling a single more complex graph. In the example shown in FIG. 6, the tasks cannot be simultaneous and there is therefore only one succession graph. For each graph the method of the invention consists firstly in grouping the tasks into layers such that: each task belongs to only one layer of the graph; a given task belongs to a layer K>2 if all the predecessor tasks of that task belong to layers below layer K and if at least one of the predecessor tasks belongs to layer K-1. FIG. 6 shows the succession graph for the tasks effected in the system shown in FIGS. 2 and 3. The nodes corresponding to the tasks are grouped into six successive layers L1 through L6. The constraints R26, R12, R11, R10, R9, R1, R33 are timing constraints relative to an absolute reference time DM which is the start of the microcycle. The layer L1 comprises the nodes representing the tasks which transmit the information IDS, ID12, ID11, ID10, ID9, ID1, ID20. The layer L2 comprises the nodes corresponding to the tasks which transmit the information ID8, ID2, ID14, ID13. The layer L3 comprises the nodes corresponding to the tasks which transmit the information ID6 and ID16. The layer L4 comprises the nodes corresponding to the tasks which transmit the information ID15 and ID3. The layer L5 comprises the nodes corresponding to the tasks which transmit the information ID7, ID17, ID18, ID19. The layer L6 contains only the node corresponding to the task which transmits the information ID4. The method of the invention determines a schedule layer by layer, successively in the order of increasing position L1, L2, . . . , L6 corresponding to the sequence imposed by the constraints. FIG. 7 shows the flowchart of one embodiment of the method of the invention. A preliminary step E0 determines the succession graph arising from the constraints that apply to the tasks to be scheduled, i.e. groups the tasks into a number of subsets constituting the layers of the graph in accordance with the sequences imposed by the constraints. The specific case in which there are repetitive tasks is described below. The list of constraints is scanned a first time. Each task is assigned to a first layer if it is subject only to timing constraints relative to an initialization time. Each task is assigned to a second layer if it is subject to at least one sequence constraint such that it must execute after a task assigned to layer 1 and if it is not subject to any sequence constraint such that it must execute after a task that has not yet been assigned to any layer and which therefore belongs to a layer above layer 1, for example layer 2. The layers are constructed in increasing order, repeating the scanning of the list of constraints and eliminating from this list the constraints applying to the tasks that have been assigned to a layer. Any task is assigned to the layer i>1 if it is subject to at least one sequence constraint such that it must execute after a task that has been assigned to the layer i-1 and if it is not subject to any sequence constraint such that it must execute after a task that has not yet been assigned. When all of the list of constraints has been scanned and there remain tasks not yet assigned, then i is incremented and the list of constraints is scanned again until all of the tasks have been assigned. A first step E1 determines the time intervals in which execution of the tasks constituting the first layer of the graph must start. The limits of each of these time intervals are given directly by the values of the parameters of a timing constraint. It is therefore not necessary to calculate the absolute value of the times which delimit the time intervals for the first layer. Step E2 schedules all the tasks belong to a layer called the current layer, verifying that the schedule is compatible with any scheduling done previously for other layers. Step E2 is repeated for layers other than the first layer, as will become clear below. Step E2 is described in detail below, with reference to FIG. 13. If step E2 succeeds (S) step E3 determines if there is a layer after the current layer. If there is no next layer, step E4 concludes that scheduling of all the tasks of the graph in question has succeeded. If there is a next layer, it becomes the current layer and step E5 groups the data constituting the constraints applying to the tasks constituting this next layer. Step E6 then calculates the limits of the time intervals ›t.sub.min, t.sub.max ! in which execution of the tasks constituting the current layer must start. This calculation is described below with reference to FIG. 8. If the calculation of a time interval for each task succeeds (S) step E2 is repeated to schedule the tasks belonging to the current layer. If the calculation of at least the time interval for at least one task yields an empty interval, step E6 fails (F). This situation is described below with reference to FIG. 4. A test E7 then determines if the current layer is the first layer. If it is the first layer, step E8 concludes that the scheduling has failed, so that it is not possible to modify anything upstream of the first layer. If the current layer is not the first layer, step E9 determines a layer below the current layer in which the scheduling will be modified to remedy the failure of scheduling in the current layer. The layer determined by step E9 becomes the current layer. The test E7 is also carried out if the scheduling of the current layer by step E2 fails (F). In this case there is an incompatibility between the intervals ›t.sub.min, t.sub.max ! of at least two tasks of the current layer. This is not the same type of conflict as in the case of failure in step E6, but it also requires rescheduling of at least one layer below the current layer. Step E9 determines that layer by considering which constraints are not satisfied. For each of these constraints there is a predecessor task which belongs to a layer that has been scheduled previously. If there is more than one constraint that is not satisfied, step E9 determines for each of them the layer containing the predecessor task and then determines which of these layers is the highest layer, in order to minimize the number of layers to be rescheduled. For the unsatisfied constraint corresponding to the layer determined in this way step E9 determines the direction and amount of a shift in the execution start time of that predecessor task such that the unsatisfied constraint could be satisfied during subsequent rescheduling of the current layer. Step E10 then verifies if it is possible to achieve the time shift determined by step E9 by modifying the permutation determined previously by step E2 in respect of the layer determined by step E9. If step E10 determines that it is possible to apply this time shift by modifying the permutation determined for the layer determined by step E9, step E11 determines a new initial permutation by making this modification. After step E11, step E2 is repeated to reschedule the current layer from the new initial permutation. If step E10 determines that it is not possible to obtain this time shift by modifying the initial permutation, the layer determined by step E9 fails. Test E7 then determines if the layer determined by step E9 was the first layer or not. If it was the first layer, step E8 decides that scheduling of the graph as a whole fails. If it was not the first layer, step E9 is repeated to determine another layer in which scheduling will be repeated on the basis of a modified initial permutation. Step E9 looks for a layer to modify, considering the layers corresponding to unsatisfied constraints in decreasing order from the current layer. Step E9 determines the layer at which the scheduling procedure E2 must be restarted from a new initial permutation, allowing for the nature of the conflict which prevented success of scheduling in the layer in question. If this is a conflict between a task of the current layer and another task of the same layer, step E9 proposes modification of the permutation for the scheduling procedure of the current layer. If it is a conflict between a task of the current layer and a task of one of the layers scheduled previously, it determines which layer that was, from the identity of the task in conflict with the task of the current layer: in this case a new permutation constitutes the initial permutation. FIG. 8 shows steps E1 and E6 of the scheduling method. It shows the start DM of the macrocycle of a graph such as that shown in FIG. 6 comprising layers 1, . . . m, . . . n, p. g. Each of the task of layer 1 is subject to a single timing type constraint referenced to the macrocycle start DM. For example, task G must satisfy a constraint R.sup.G whereby the time t.sup.G.sub.st at which execution of task G starts must be in an interval ›t.sup.G.sub.min, t.sup.G.sub.max !. The time t.sup.G.sub.st can be coincident with the upper limit t.sup.G.sub.max. In FIG. 8 a small black rectangle shows the time interval occupied by execution of the task. For each task other than those of the first layer, one or more after constraints can require that the execution start time of that task is in a given time interval relative to a predecessor task. Consider a task K in layer p, for example. Layers 1, . . . , m, . . . , n are assumed to have been scheduled previously. Layer p is currently being scheduled and layer g has not yet been scheduled. Task K must satisfy three after constraints R.sup.K1, R.sup.K2, R.sup.K3. The constraint R.sup.K1 requires that execution of task K start in a time interval defined by two time values referenced to the time t.sub.1 at which execution of a given task in layer a starts. The constraint R.sup.K2 requires that execution of task K start in an interval defined by two time values referenced to the time t.sub.2 at which execution of a given task in layer m starts. The constraint R.sup.K3 requires that execution of task K start at a time in an interval defined by two time values referenced to the time t.sub.3 at which execution of a given task in layer n starts. The after constraints have values such that there cannot be any overlap between the execution interval of the predecessor task and the execution interval of the task subject to the constraint in question. Given these conditions, if the scheduling of a layer satisfies all the constraints applying to the tasks of that layer, it is not necessary to verify that the scheduling also satisfies other constraints applying to lower layers. Step E6 determines the absolute limits referenced to the macrocycle start time DM of each of these three intervals. It accordingly determines three intervals ›t.sup.K1.sub.min, t.sup.K1.sub.max ! ›t.sup.K2.sub.min, t.sup.K2.sub.max ! and ›t.sup.K3.sub.min, t.sup.K3.sub.max !. The task K must satisfy the three constraints R.sup.K1, R.sup.K2, R.sup.K3 simultaneously and so execution of task K must start in an interval ›k.sup.K.sub.min, t.sup.K.sub.max ! which is obtained by applying the AND operator to these three intervals. If this is not possible, it is necessary to call into question again the scheduling of at least one of the layers m and n linked to task K by the constraints R.sup.K1, R.sup.K2 and R.sup.K3. By modifying the scheduling of layer n it is possible to modify the relative positions of the times t.sub.1, t.sub.3 of starting execution of tasks linked to task K by the constraints R.sup.K1 and R.sup.K3. It is also possible to modify the position of t.sub.2 relative to t.sub.1 and t.sub.3 by rescheduling layer m, but it is preferable to give priority to rescheduling higher layers, i.e. layer n in this example. If a layer is rescheduled it is necessary to reschedule all higher layers that may have been scheduled previously. In the example shown in FIG. 8, if rescheduling starts in layer m it is necessary to reschedule layers m+1, . . . , n. It is therefore preferable to start rescheduling in the highest possible layer. In this example it is preferable to start rescheduling in layer n rather than in layer m. If the rescheduling of layer n makes the constraints R.sup.K1, R.sup.K2, R.sup.K3 mutually compatible, i.e. if it determines a non-empty interval ›k.sup.K.sub.min, t.sup.K.sub.max !, then the number of layers in which rescheduling is needed is restricted to 1. When step E6 has succeeded in determining an interval ›t.sup.K.sub.min, t.sup.K.sub.max ! for each task of the layer p in question, then step E2 schedules those tasks. FIGS. 9 through 12 show the basic principles of the method applied in step E2. This procedure schedules all the tasks in the same layer, minimizing the number of permutations to be verified. This procedure succeeds if it determines a permutation constituting a schedule satisfying all the constraints applying to the tasks in this layer. FIG. 9 shows a timing diagram illustrating a first basic principle of the method of the invention for scheduling tasks in the same layer. This first basic principle imposes priority execution of tasks for which the time interval starts the soonest, i.e. with the smallest value t.sub.min. In practise the initial permutation of the tasks, i.e. the first permutation to be verified, is constituted by a series MIN-SERIES, in which the tasks are arranged in increasing order of their t.sub.min values. The rectangles IDA and IDB in FIG. 9 show time intervals respectively assigned to the execution of a task A and to the execution of a task B. Constraints require that execution of task A start within an interval ›t.sup.A.sub.min, t.sup.A.sub.max ! or, at worst, at time t.sup.A.sub.max. They require that execution of task B start within an interval ›t.sup.B.sub.min, t.sup.B.sub.max ! or, at worst, at time t.sup.B.sub.max, In this example t.sup.A.sub.min is before t.sup.B.sub.min. The first basic principle is to execute task A first, shifting the interval in which this execution occurs as close as possible to the lower limit t.sup.A.sub.min ; then executing task B during an interval IDB starting as close as possible to the lower limit t.sup.B.sub.min without overlapping the interval IDA. In this example the interval IDA has a duration .delta..sub.A which overlaps the interval ›t.sup.B.sub.min, t.sup.B.sub.max ! and consequently the intervals IDA and IDB will be as close together as possible by choosing: t.sup.B.sub.st =t.sup.A.sub.min +.delta..sup.A FIG. 10 shows, for the same example, the consequences of failure to apply this basic principle, i.e. of having task B executed before task A. The execution interval IDB then starts as soon as possible, i.e. at the lower limit of the interval ›t.sup.B.sub.min, t.sup.B.sub.max !, The execution interval IDA should start after the end of the execution interval IDB in order not to overlap the interval IDB, but in the example the execution interval IDB has a length such that it goes beyond the upper limit t.sup.A.sub.max of the interval in which starting execution of task A is permitted. At best, task A could start at time t.sup.A.sub.st =t.sup.A.sub.max, but then the two execution intervals IDB and IDA overlap. The overlap area is cross-hatched in FIG. 10. The example thus shows that failing to respect the first basic principle increases the probability that some constraints will not be satisfied. FIG. 11 shows a timing diagram illustrating a second basic principle of the method of the invention for scheduling tasks in the same layer. This basic principle chooses the task to be given execution priority from a plurality of tasks for which the lower limit t.sub.min has the same value. In this case, this second basic principle imposes priority execution of the task for which the upper limit t.sub.max has the smallest value. In example shown in FIG. 11, two tasks A and B have the same lower limit t.sup.A.sub.min =t.sup.B.sub.min for the time interval in which execution must start. Constraints imposed by the existence of other execution intervals that are not shown prohibit execution of tasks A and B before a time t.sub.0 after t.sup.A.sub.min =t.sup.B.sub.min, in a time interval shown cross-hatched. Thus the execution intervals IDA and IDB can only start from this time t.sub.0. The upper limit t.sup.B.sub.max for task B is greater than the upper limit t.sup.A.sub.max for task A. In accordance with the second basic principle, task A takes priority for execution. Task B is then executed from a time: t.sup.B.sub.st =t.sup.A.sub.min +.delta..sup.A Thus the two execution intervals IDA and IDB occur one after the other with no particular problem due to the upper limit t.sup.B.sub.max. FIG. 12 shows, for the same example, a conflict that is more likely to occur if the second basic principle is not respected. Task B is executed first, from time t.sup.B.sub.st which coincides with the end to of the prohibited interval shown by the cross-hatching. Task A must then be executed from a time t.sup.A.sub.st =t.sup.B.sub.min +.delta..sup.A to prevent the intervals IDA and IDB overlapping, but this time t.sup.A.sub.st would then be in a prohibited area, shown cross-hatched in the figure, after the upper limit t.sup.A.sub.max of the interval in which execution should start. There is therefore a constraint that is not satisfied. This example shows that failing to respect the second basic principle increases the probability that some constraints will not be satisfied. Step E2 which schedules the tasks of a layer can be implemented using a known method such as the simplex algorithm. Any other method of scheduling a set of tasks subject to constraints defined for each task by a time interval in which execution of the task must start can be used provided that, in the event of failure, it supplies: the identity of the task which causes scheduling of the current task to fail; the direction and amount of the modification of its execution start time needed to remedy the failure, this direction and amount being used thereafter to modify the scheduling in a lower layer in order to modify the interval ›t.sub.min, t.sub.max ! for that task. FIG. 13 shows a flowchart of a preferred embodiment of step E2 of the FIG. 7 flowchart. It starts with a step E21 to determine the series MIN-SERIES comprising all the tasks scheduled in increasing order of their lower limit t.sub.min. This series will be used to apply the first basic principle stated above. To maximize the probability of finding quickly a permutation that satisfies all the constraints applying to all the tasks of the layer in question, the initial permutation is constituted by MIN-SERIES and the permutations verified thereafter, in the event of failure, are deduced from MIN-SERIES by successive modifications. Step E21 also determines the series MAX-SERIES comprising all the tasks in the current layer in increasing order of their upper limit t.sub.max. This series will be used to apply the second basic principle stated above if the initial permutation has to be modified. The next step E22 verifies the current permutation, i.e. verifies if it satisfies all the constraints applying to the tasks in the current layer. At the beginning of this step the current permutation is the initial permutation determined by step E21. This verification consists in taking each successive task in the order of the current permutation and verifying that the execution interval ›t.sub.st, t.sub.end ! imposed by the position occupied by that task in the current permutation is compatible with the time interval ›t.sub.min, t.sub.max ! imposed by the constraints that apply to that task. The task for which this verification is in progress is called the current task. If the result of the verification is positive for each of the tasks of the current permutation, this indicates that the current permutation succeeds (S), and scheduling can continue with step E3 of the FIG. 7 flowchart. If the verification finds at least one task whose position in the permutation imposes starting execution at a time t.sub.st that is not in the time interval ›t.sub.min, t.sub.max ! imposed by the constraints, that task is regarded as ill-placed since there is a conflict between two constraints. When step E22 finds a task (X) that is the first ill-placed task in the current permutation, it draws the conclusion (R) that it is necessary to look for a task that is a candidate for shifting to constitute a new permutation. The method then executes a step E23 which looks for the task immediately following the current task X in the series MAX-SERIES. If there is no such task, step E23 fails (F), and scheduling continues with step E3 of the FIG. 7 flowchart. If step E23 finds a candidate task Q immediately following the current task X in the series MAX-SERIES, the next step E24 of the method verifies that the task Q has already been considered to be well-placed during an earlier step E21. All the tasks considered to be well-placed are those which have a position below that of the current task X, since the verification of step E22 is carried out according to increasing positions in the current permutation. Consequently, step E24 simply verifies that the candidate task Q precedes the current task X in the current permutation. If step E24 determines that the task Q was not considered to be well-placed, then step E23 is repeated to find another candidate task immediately following the task Q in MAX-SERIES. On the other hand, if the candidate task Q was considered to be well-placed, the next step E25 of the method compares the execution start time t.sup.Q.sub.st of the task Q to the upper limit t.sup.x.sub.max of the time interval corresponding to the current task X. If t.sup.Q.sub.st .gtoreq.t.sup.X.sub.max, the outcome is that denoted .alpha.. The next step is then a step E29 which shifts the task Q in the current permutation to insert it between the current task X and the task after the task X in the current permutation. The tasks that were between Q and X, and the task X itself, are shifted one position downwards to fill in the space left free by Q. Consequently, the task Q subsequently occupies the position that was previously that of X. The method then repeats step E22 to verify if the new current permutation obtained in this way satisfies all the constraints. Note that the task Q and all the other tasks that followed it have been shifted. They can no longer be considered to have been well-placed as they do not necessarily satisfy all the constraints in their respective new positions. The tasks below Q retain the same position, and it is therefore not necessary to verify that they satisfy all the constraints applying to them, and therefore the work of verifying those constraints is not done again. If t.sup.Q.sub.st <t.sup.X.sub.max, the outcome is that denoted .alpha. (see below) and the next step of the method is step E26. FIG. 14 shows the outcome .alpha., for example. The execution intervals are shown in dashed outline if a conflict prevents execution and in full outline otherwise. Consider a task X in position PSi of the current permutation and a task Q considered to be well-placed and in position PSj of the current permutation. The position PSi imposes the start of execution of task X at a time t.sub.st (PSi) that is beyond the limit t.sup.X.sub.max. The position PSj imposes the start of execution of task Q at a time t.sub.st (PSj) which in this example is beyond the time t.sup.X.sub.max. Since the time t.sup.Q.sub.st (PSj) is beyond the time t.sup.X.sub.max, the limit t.sup.Q.sub.max is therefore a fortiori greater than or equal to t.sup.X.sub.max, and therefore has a chance of being near t.sub.st (PSi), the ideal being that t.sub.st (PSi) falls short of t.sup.Q.sub.max. FIG. 15 shows that by shifting the tasks Q and X respectively into the positions PSi-1 and PSj, the probability that the time t.sub.st (PSi-1) falls in the interval ›t.sup.X.sub.min, t.sup.X.sub.max ! is greater than the probability that the time t.sub.st (PSi) had of falling in this same interval, because t.sub.st increases systematically with the position PS. The figure shows that the end t.sup.X.sub.max, of the segment corresponding to task X has moved closer to an execution interval, namely that which starts at t.sub.st (PSi-1), and therefore has a greater chance of intersecting with that interval. The end t.sup.Q.sub.max of the segment corresponding to the task Q has a non-null chance of intercepting the rectangle representing the execution interval starting at time t.sub.st (PSi). Consequently, the new permutation has a greater chance than the old one of satisfying all the constraints and it is therefore beneficial to try out this new permutation. In the example shown, t.sub.st (PSi-1) is beyond t.sub.max and there is therefore still a conflict in respect of the task X. It is therefore necessary to make one or more further modifications to the current permutation. In this example, t.sub.st (PSi) is beyond t.sup.Q.sub.max and there is therefore also a conflict in respect of the task Q after the shift. However, in other examples corresponding to the outcome .alpha. it may be that the constraints applying to X and those applying to Q are satisfied simultaneously. Consequently, it is beneficial to verify any new permutation corresponding to the outcome .alpha.. In the case of the outcome .alpha., on the other hand, further verifications are needed before it is possible to conclude that the task Q is a worthwhile candidate task. The next step of the method is then step E26 that compares the time t.sup.Q.sub.end of end of execution of the task Q to the upper limit t.sup.X.sub.max, of the interval in which execution of the task X must start. If t.sup.Q.sub.end .gtoreq.t.sup.X.sub.max, the outcome is that denoted .beta. and the next step of the method is the step E29 which shifts the task Q to insert it after the task X. The contrary outcome is that denoted .beta.. Other verifications are needed before it is possible to conclude that the task Q is a worthwhile candidate task. FIGS. 16 and 17 show the outcome .beta.. FIG. 16 shows a task X in the position PSi and a task Q in the position PSj such that the outcome .alpha. and the outcome .beta. apply: the time t.sup.Q.sub.end of end of execution of the task Q, i.e. the time t.sub.end (PSj) imposed by the position PSj of Q in the current permutation, is beyond the time t.sup.X.sub.max. FIG. 17 shows that by displacing the tasks Q and X to the positions PSi-1 and PSj, respectively, the probability that the time t.sub.st (PSi-1) falls in the interval ›t.sup.X.sub.min, t.sup.X.sub.max ! is greater than the probability that the time t.sub.st (PSi) had of falling in that same interval, because t.sub.st increases systematically with the position PS. What is more, the time t.sup.Q.sub.end =t.sub.end (PSj) is beyond the limit t.sup.X.sub.max, and there is no conflict. This means that t.sup.Q.sub.max is either greater than t.sup.X.sub.max or slightly less than t.sup.X.sub.max, being at most at a distance equal to the interval ›t.sub.st (PSj), t.sub.end (PSj)!. There is therefore little chance that t.sup.Q.sub.max is greater than t.sup.X.sub.max, and therefore in this case there is little chance that t.sup.Q.sub.max will be beyond t.sub.st (PSi) after the shift. It is therefore worthwhile to try out a permutation corresponding to the outcome .beta., which will not necessarily be a waste of time. In the example shown in FIG. 17, the shifting of Q and X is not sufficient for all the constraints on Q and X to be satisfied. The current permutation needs to be modified a little more. In the case of the outcome .beta., step E27 compares the upper limit t.sup.Q.sub.max of the time interval in which execution of task Q must start to the upper limit t.sup.X.sub.max of the time interval in which execution of task X must start. If t.sup.Q.sub.max >t.sup.X.sub.max, the outcome is denoted .eta. and the next step of the method is then a step E28. The contrary outcome is that denoted .eta. and step E23 is then repeated since there is no chance that the candidate task Q is worthwhile. FIGS. 18 and 19 show the outcome .eta. by means of an example in which the limit t.sup.Q.sub.max is before the time t.sup.X.sub.max. FIG. 18 shows the tasks X and Q shifted into the positions PSi-1 and PSi, respectively. This figure shows that the time t.sup.Q.sub.max is closer to the time t.sub.st (PSi) than it was to the time t.sub.st (PSj) but there is no chance of the task Q being executed since t.sup.Q.sub.max is still farther from t.sub.st (PSi) than t.sup.Q.sub.max was. Since there is a 100% chance of the task Q being ill-placed, it is not worthwhile to attempt any modification of the current permutation and for this reason the next step of the method is a step E23 that looks for another candidate task for shifting. In the case of outcome .eta., step E28 compares the lower limit t.sup.Q.sub.min of the interval in which execution of task Q must start with the lower limit t.sup.X.sub.min of the time interval in which the execution of task X must start. The objective of this step E28 is to verify that the task Q is before the current task X in the series MIN-SERIES so that the task Q can be moved after the task X. Otherwise (outcome .alpha.) the next step of the method is a step E23 that looks for another task that is a candidate for shifting. In the case of the outcome .chi., the next step of the method is a step E29 that shifts the task Q after the task X; step E22 is then repeated to verify if all the constraints applying to the tasks of the current layer are satisfied. FIG. 20 shows an example in which the outcomes .alpha., .beta., .chi., .eta. apply simultaneously. FIG. 21 shows the tasks X and Q shifted into the positions PSi-1 and PSi, respectively, in an example in which the constraints are such that they are satisfied after this shifting: t.sub.st (PSi) is in the interval ›t.sup.Q.sub.min, t.sup.Q.sub.max ! and t.sub.st (PSi-1) is in the interval ›t.sup.X.sub.min, t.sup.X.sub.max !. FIGS. 22 through 31 show the implementation of step E2 for scheduling a layer comprising thirteen tasks: A, B, C, D, E, G, J, K, L, N, P, S, T. FIG. 22 shows on a time scale from 0 to 14 ms the position of the execution intervals respectively corresponding to thirteen positions PS1 through PS13. The tasks are executed in the order of the positions PS1 through PS13 and each execution interval has a duration equal to 1 ms. Each task must satisfy one or more constraints that result in a single constraint. The start of the execution interval (cross-hatched rectangle in FIG. 22) must be in a given time interval (bold segments in FIG. 23). In the worst case it can begin at the upper limit. Step E21 determines the series MIN-SERIES comprising all the tasks of the current layer scheduled in increasing order of their lower limit t.sub.min. MIN-SERIES=N, J, S, D, E, B, T, A, K, P, L, C, G. In FIG. 23 the thirteen tasks are shown in the same order as MIN-SERIES, along the ordinate axis. To maximize the probability of quickly finding a permutation that satisfies all the constraints applying to the tasks of the layer in question, the so-called initial permutation verified first is that consisting of MIN-SERIES, and those verified thereafter, in the event of failure, are deduced from MIN-SERIES by successive modifications. Step E21 further determines the series MAX-SERIES comprising all the paths of the current layer scheduled in order of increasing t.sub.max values. This series will be used to apply the second basic principle stated above if the initial permutation has to be modified. In this example: MAX-SERIES=E, D, A, K, P, B, L, C, G, T, J, S, N. A step E22 then verifies the current permutation, i.e. verifies if it satisfies all the constraints applying to the tasks of the layer in question. At the start of step E2 the current permutation is the initial permutation determined by step E21. The verification is performed successively for each task, in the order of the current permutation: N, J, S, D, E, . . . , G. If the result of the verification is positive for a task, that task is considered to be well-placed in the permutation, but its position can be called into question again subsequently if this is needed to satisfy other constraints. Comparing FIGS. 22 and 23 shows that there is no problem in executing the tasks N, J, S and D, respectively, during the execution intervals shown in FIG. 22. They are therefore all considered to be well-placed, the current permutation is: N, J, S, D, E, B, T, A, K, P, L, C, G. The tasks underlined are those considered to be well-placed. FIG. 24 shows the first conflict encountered in verifying the initial permutation. Cross-hatched rectangles in FIG. 24 represent execution intervals for which there is no conflict between the constraint and a dashed outline black rectangle shows the execution interval that is causing a conflict. It corresponds to the position PS5 currently occupied by the task E. This execution interval does not intersect the interval in which the execution of the task E must start. Step E23 therefore looks in the series MAX-SERIES for a task following the task E, i.e. such that the limit t.sub.max has a higher value. MAX-SERIES=E, D, A, K, P, B, L, C, G, T, J, S, N. Step E23 finds the task D. Step E24 verifies that it is considered to be well-placed, by verifying that its position is below the position of the current task E in the current permutation. Step E25 then arrives at a conclusion .alpha.. Step E26 then arrives at a conclusion .beta.. Step E29 then shifts D into the position POS5 and E moves back into the position POS4. Step E22 verifies that the constraints applying to E and the subsequent tasks are satisfied but finds that the constraint applying to D are no longer satisfied. The permutation tried out is not suitable. It is not retained at the new current permutation. FIG. 24 shows that this modification cannot succeed because the interval corresponding to D has an upper limit which is not higher than that of the interval corresponding to E. They are in fact exactly the same. To prevent unnecessary verification of new permutations it is possible to take precautions when constructing MAX-SERIES during step E21: If two tasks of the same layer have a common time interval constraint ›t.sub.min, t.sub.max !, it is possible to put them in two different positions in the series MIN-SERIES that constitutes the initial permutation and in the series MAX-SERIES. In the example shown in FIGS. 22 through 31 there are at least two possibilities for constructing the series MAX-SERIES since it is possible to permutate D and E: D, E, A, K, P, B, L, C, G, T, J, S, N or E, D, A, K, P, B, L, C, G, T, J, S, N. It would have been preferable to choose the order D, E that is the opposite of the order E, D in which they are taken to constitute the initial permutation. MIN-SERIES=N, J, Si D, E, B, T, A, K, P, L, C, G. Step E23 then finds as successive candidate tasks the tasks A, K, P, B, L, C, G, T, J and step E24 retains task J. It can be shown that, as a general rule, if the tasks of the layer to be scheduled have to satisfy only timing constraints, it is preferable to place in a reverse order all the tasks having the same interval ›t.sub.min, t.sub.max ! regardless of their number. On the other hand, if both timing constraints and sequence constraints apply, it is preferable to place them in the same order. Consider the remainder of this example, retaining the initial choice of MAX-SERIES: E, D, A, K, P, B, L, C, G, T, J, S, N. The current permutation is: N, J, S, E, D, B. T, A, K, P, L, C, G. After this unfortunate attempt to modify the permutation, step E23 finds as successive candidate tasks the tasks A, K, P, B, L, C, G, T and these are rejected by step E24. Step E23 then finds task J. FIG. 25 shows this new attempt at modification. Step E24 verifies that task J is considered to be well-placed. Step E25 reaches the conclusion .alpha.. Step E26 reaches the conclusion .beta.. Step E27 and E28 arrive at the conclusions .eta. and .chi.. Consequently step E29 places task J in position PS5 in place of E. Task E, D and S move back one place: S to position PS2, D to position PS3 and E to position PS4. The other tasks do not change place. Step E22 then verifies that the tasks that have been shifted satisfy all the constraints applying to them, starting with the shifted task in the lowest position: S, then E, then D, then J. It then verifies that there is no conflict between the successive constraints for tasks B, T, A, K. FIG. 26 shows the new current permutation. Note that the execution interval for task K starts at the exact time which is the end of the interval in which execution of task K should start. There is no conflict, but the constraints are satisfied. The current permutation is: N, S, E, D, J, B, T, A, K, P, L, C, G. FIG. 27 shows that a conflict occurs for task P. Step E23 is then repeated to determine in the series MAX-SERIES the task immediately following the task P. It finds task B. Step E24 verifies that task B is considered to be well-placed. Steps E25 and E26 reach conclusions .alpha. and then .beta.. Step E27 is then executed. This finds that t.sup.B.sub.max =t.sup.P.sub.max and consequently arrives at the conclusion .eta.. Step E23 is then repeated to find another candidate task in the series MAX-SERIES. The segment representing the time interval corresponding to B would not intersect with the execution interval ›9 ms, 10 ms! corresponding to the position POS10 if task B were shifted to that position. Consequently, the constraints that apply to B would not be satisfied. Step E23 then finds the successive tasks L, C, G but step E24 rejects them as they are not considered to be well-placed in the permutation. Finally, steps E23 and E24 find task T. Steps E25 through E28 successively arrive at the conclusions .alpha., .beta., .eta., .chi.. Step E29 shifts T to position POS10. Tasks P, K, A move back into positions POS9, POS8, POS7, respectively. Step E22 then verifies that the constraints applying to the shifted tasks A, K, P, T and the subsequent tasks are satisfied. The new current permutation is: N, S, E, D, J, B, A, K, P, T, L, C, G. As shown in FIG. 28, step E22 then finds that the constraints applying to task L are not satisfied. Step E23 then finds task T and step E24 verifies that it is considered to be well-placed. Step E25 and the subsequent steps can then be executed. They arrive at conclusions .alpha., .beta. then .eta. and .chi.. Step E29 can then be executed. It places task T in the position POS11 that was occupied by task L, which moves back one place. Step E22 verifies that the constraints applying to the shifted tasks L and T are satisfied. Consequently, the current permutation becomes: N, S, E, D, J, V, A, K, P, L, T, C, G As shown in FIG. 29, there is a conflict between the constraints applying to task C. Step E23 determines the task following task C in the series MAX-SERIES. It finds task G but step E24 finds that task G is not considered to be well-placed in the permutation. Step E23 is repeated and determines another task T preceding task C in the series MAX-SERIES. Step E24 verifies that task T is considered to be well placed in the permutation. Step E25 arrives that the conclusion .alpha. since t.sup.T.sub.st =t.sup.C.sub.max. Step 29 is therefore executed immediately and places task T after task C in the permutation, which is the same thing as permutating the positions of C and T. Step E22 then verifies that all the constraints applying to the shifted tasks C and T are satisfied. The new current permutation is: N, S, E, D, J, L, A, K, P, L, C, T, G. As shown in FIG. 30, step E22 finds that there is a conflict between the constraints applying to task G. Step E23 determines a task T immediately following task G in the series MAX-SERIES. Step E24 verifies that task T is considered to be well-placed in the permutation. Step E25 arrives at the conclusion .alpha. since t.sup.T.sub.st =t.sup.G.sub.max. Step E29 places T after G in the permutation, which is the same thing as permutating T and G. Step E22 then verifies that all the constraints applying to the shifted tasks G and T are satisfied. The new current permutation is: N, S, E, D, J, B, A, K, P, L, C, G, T. All the tasks are considered to be well-placed because all the constraints are satisfied, as shown in FIG. 31, and consequently step E22 succeeds (S). If there are other, higher layers, they are scheduled by step E3 of the FIG. 7 flowchart. Although the invention has been illustrated and described with respect to an exemplary embodiment thereof, it should be understood by those skilled in the art that the foregoing and various other changes, omissions, and additions may be made therein and therefor, without departing from the spirit and scope of the present invention. Therefore, the present invention should not be understood as limited to the specific embodiment set out above but to include all possible embodiments which can be embodied within a scope encompassed and equivalents thereof with respect to the features set out in the appended claims.
|
Same subclass Same class Consider this |
||||||||||