Method and apparatus for scheduling tasks to control hardware devices

• US 20110113431A1
• Filed: 11/08/2010
• Published: 05/12/2011
• Est. Priority Date: 11/09/2009
• Status: Active Grant

• Current Assignee: DENSO Corporation
• Original Assignee: DENSO Corporation
• Inventors: Shidai, Takahiro, Satoh, Yohsuke, Iwai, Akihito
• Granted Patent: US 8,595,746 B2
• Time in Patent Office: Days
• US Class Current: 718/103
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic

Abstract

In a method of scheduling tasks for controlling hardware devices, a specified task having the execution right in a current time slice is terminated by depriving the execution right therefrom, when a time during which the execution right continues reaches the activation time given to the specified task. An identification process is performed when each reference cycle has been completed or each task has been terminated. In the identification process, i) when there remain, time-guaranteed tasks which have not been terminated in the current time slice, a time-guaranteed task whose priority is maximum among the remaining tasks is identified, and ii) when there remain no un-terminated time-guaranteed tasks in the current slice, of remaining non-time-guaranteed tasks which are not terminated yet in the current time slice, a non-time-guaranteed task whose priority is maximum is identified. The execution right is assigned to the identified task through the identification process.

Claims

1. A method for scheduling a plurality of tasks given in an apparatus that produces periodical reference cycles, each of the reference cycles being given as a time slice, the tasks being given execution rights in sequence, the method including steps of:

first performing the tasks, each of the tasks being given an activation time, the tasks including first type of tasks each of which is necessarily given the execution right during the activation time thereof in each of the time slices and second type of tasks each of which is not necessarily given the execution right during the activation time thereof in each of the time slices, a sum of the activation times given to the first type of tasks in each of the time slices being smaller than a period of each of the time slices, the first type of tasks respectively being given a first priority used to give the execution right and the second type of tasks respectively being given a second priority used to give the execution right;

terminating, among the tasks, a specified task to which the execution right is given in a current time slice of the time slices, by depriving the execution right from the specified task, when a time during which the execution right continues reaches the activation time given to the specified task, the current time slice being a time slice beginning after the latest one reference cycle;

second performing an identification process when each of the reference cycles has been completed or each of the tasks has been finished, wherein in the identification process, i) in cases where there remain, among the first type of tasks, remaining first type of tasks which have not been finished in the current time slice, a first type of task of which first priority is maximum among the remaining first type of tasks is identified, and ii) in cases where there remain no first type of tasks which have not been finished in the current slice, of remaining second type of tasks which are not finished yet in the current time slice, a second type of task of which second priority is maximum is identified; and

assigning the execution right to the identified task through the identification process.

2. The method of claim 1, further comprising steps of:

determining whether or not a predetermined abandonment condition for a task among the tasks is met, wherein the determination that the abandonment condition is met allows the task to voluntarily abandon the execution right given thereto; and

regarding that the task has been finished in the current time slice when the task abandons the execution right.

3. The method of claim 1, further comprising steps of:

determining whether or not a predetermined event-waiting condition for a task among the tasks is met, wherein the determination that the event-waiting condition is met allows the task to voluntarily abandon the execution right given thereto and to wait for an event to be generated for the task;

removing the task, which abandons the execution right and start waiting, from the tasks to be given the execution right so that the removed task is waiting for the event;

returning the waiting task to the tasks to be given the execution right when the event is generated,

wherein the second performing step include a step of applying the identification process to the tasks which are not waiting, and a step of allowing the identification process to be performed when the task is removed from the tasks to be given the execution right in the removing step.

4. The method of claim 3, wherein

the second performing step includes a step of performing the identification process to identify the task returned by the returning step, and

the method comprising a step of depriving the tasks of the execution rights thereof to which the execution rights are given currently, when the performing step identifies the returned task in the returning step.

5. The method of claim 1, further comprising a step of updating the second priority assigned to the second type of tasks depending on whether or not each of the second type of tasks has been finished in the current time slice.

6. The method of claim 5, wherein the second priority is calculated on a fixed priority providing a fixed value of the priority and a suspended degree showing how much of the second type of tasks have not finished in each of the time slices, and

the updating step updates the second type of tasks by updating the suspended degree depending on whether or not each of the second type of tasks has been finished in the current time slice.

7. The method of claim 1, wherein each of the first type of tasks has a maximum activation duration and a required activation time, the maximum activation duration being a maximum activation duration allowed for normally activating functions realized by the first type of tasks, the required activation time being a provided time of the execution right necessary at minimum for activating the functions in the maximum activation duration,

the method including steps of:

setting, as the time slice, the maximum activation duration which is shortest among the maximum activation durations of the first type of tasks to be scheduled; and

calculating a value by dividing the necessary activation time which is set to each of the first type of tasks to be scheduled by the maximum activation duration which is set to each of the first type of tasks to be scheduled;

calculating a minimum activation time of each of the first type of tasks by multiplying the calculated value by the time slice; and

setting, as the activation time, a time which is longer than the minimum activation time of each of the first type of tasks such that a sum of the activation times of all the first type of tasks is limited within the time slice.

8. The method of claim 7, further comprising steps of:

removing the task to be scheduled so that the task is not scheduled; and

adding the task which has not been scheduled so that the task is newly added to be a task to be scheduled,

wherein the time slice setting step, the value calculating step, the minimum activation time calculating step, and the activation time setting step are repeated at intervals.

9. The method of claim 8, further comprising steps of:

determining whether or not, when a new task belonging to the first type of tasks to the tasks to be scheduled, it is possible to add the new task to the tasks to be scheduled, based on the maximum activation duration and the minimum activation time of the new task and the maximum activation durations and the minimum activation times of the first type of tasks to be scheduled,

wherein the adding step adds the new task to the tasks to be scheduled when the determining step determines that it is possible to add the new tasks to the tasks to be scheduled.

10. The method of claim 8, wherein the time slice setting step, the value calculating step, the minimum activation time calculating step, and the activation time setting step are executed every time when timing defined by the reference cycles is reached.

11. The method of claim 1, wherein at least one of the tasks is a virtual machine composed by a program re-create a function realized in an apparatus.

12. The method of claim 1, wherein the plurality of tasks control hardware devices mounted in the apparatus.

13. The method of claim 2, further comprising steps of:

determining whether or not a predetermined event-waiting condition for a task among the tasks is met, wherein the determination that the event-waiting condition is met allows the task to voluntarily abandon the execution right given thereto and to wait for an event to be generated for the task;

removing the task, which abandons the execution right and start waiting, from the tasks to be given the execution right so that the removed task is waiting for the event;

returning the waiting task to the tasks to be given the execution right when the event is generated,

wherein the second performing step include a step of applying the identification process to the tasks which are not waiting, and a step of allowing the identification process to be performed when the task is removed from the tasks to be given the execution right in the removing step.

14. The method of claim 13, wherein

the second performing step includes a step of performing the identification process to identify the task returned by the returning step, and

the method comprising a step of depriving the tasks of the execution rights thereof to which the execution rights are given currently, when the performing step identifies the returned task in the returning step.

15. The method of claim 2, further comprising a step of updating the second priority assigned to the second type of tasks depending on whether or not each of the second type of tasks has been finished in the current time slice.

16. The method of claim 2, wherein each of the first type of tasks has a maximum activation duration and a required activation time, the maximum activation duration being a maximum activation duration allowed for normally activating functions realized by the first type of tasks, the required activation time being a provided time of the execution right necessary at minimum for activating the functions in the maximum activation duration,

the method including steps of:

setting, as the time slice, the maximum activation duration which is shortest among the maximum activation durations of the first type of tasks to be scheduled; and

calculating a value by dividing the necessary activation time which is set to each of the first type of tasks to be scheduled by the maximum activation duration which is set to each of the first type of tasks to be scheduled;

calculating a minimum activation time of each of the first type of tasks by multiplying the calculated value by the time slice; and

setting, as the activation time, a time which is longer than the minimum activation time of each of the first type of tasks such that a sum of the activation times of all the first type of tasks is limited within the time slice.

17. A computer-readable program stored in a medium, the program being for scheduling a plurality of tasks given in an apparatus that produces periodical reference cycles, each of the reference cycles being given as a time slice, the tasks being given execution rights in sequence, each of the tasks being given an activation time, the tasks including first type of tasks each of which is necessarily given the execution right during the activation time thereof in each of the time slices and second type of tasks each of which is not necessarily given the execution right during the activation time thereof in each of the time slices, a sum of the activation times given to the first type of tasks in each of the time slices being smaller than a period of each of the time slices, the first type of tasks respectively being given a first priority used to give the execution right and the second type of tasks respectively being given a second priority used to give the execution right,

the program allowing the computer to realize functions of:

terminating, among the tasks, a specified task to which the execution right is given in a current time slice of the time slices, by depriving the execution right from the specified task, when a time during which the execution right continues reaches the activation time given to the specified task, the current time slice being a time slice beginning after the latest one reference cycle;

performing an identification process when each of the reference cycles has been completed or each of the tasks has been finished, wherein in the identification process, i) in cases where there remain, among the first type of tasks, remaining first type of tasks which have not been finished in the current time slice, a first type of task of which first priority is maximum among the remaining first type of tasks is identified, and ii) in cases where there remain no first type of tasks which have not been finished in the current slice, of remaining second type of tasks which are not finished yet in the current time slice, a second type of task of which second priority is maximum is identified; and

assigning the execution right to the identified task through the identification process.

18. An apparatus for scheduling a plurality of tasks given in an apparatus that produces periodical reference cycles, each of the reference cycles being given as a time slice, the tasks being given execution rights in sequence, the apparatus comprises:

first performing means for performing the tasks, each of the tasks being given an activation time, the tasks including first type of tasks each of which is necessarily given the execution right during the activation time thereof in each of the time slices and second type of tasks each of which is not necessarily given the execution right during the activation time thereof in each of the time slices, a sum of the activation times given to the first type of tasks in each of the time slices being smaller than a period of each of the time slices, the first type of tasks respectively being given a first priority used to give the execution right and the second type of tasks respectively being given a second priority used to give the execution right,

terminating means for finishing, among the tasks, a specified task to which the execution right is given in a current time slice of the time slices, by depriving the execution right from the specified task, when a time during which the execution right continues reaches the activation time given to the specified task, the current time slice being a time slice beginning after the latest one reference cycle;

second performing means for performing an identification process when each of the reference cycles has been completed or each of the tasks has been finished, wherein in the identification process, i) in cases where there remain, among the first type of tasks, remaining first type of tasks which have not been finished in the current time slice, a first type of task of which first priority is maximum among the remaining first type of tasks is identified, and ii) in cases where there remain no first type of tasks which have not been finished in the current slice, of remaining second type of tasks which are not finished yet in the current time slice, a second type of task of which second priority is maximum is identified; and

assigning means for assigning the execution right to the identified task through the identification process.

19. The apparatus of claim 18, wherein the plurality of tasks control hardware devices mounted in the apparatus.