Schedulability determination method and real-time system

• US 20060218558A1
• Filed: 09/23/2005
• Published: 09/28/2006
• Est. Priority Date: 03/25/2005
• Status: Active Grant

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Torii, Osamu, Maeda, Seiji
• Granted Patent: US 7,913,256 B2
• Time in Patent Office: Days
• US Class Current: 718/107
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic

Abstract

A real-time system includes a plurality of processors for executing jobs of a plurality of periodic tasks each having predetermined period, assigns each job in a period of each of the tasks to the processors, calculates distribution of execution times during which jobs assigned are executed on the processors, determines, based on the distribution, whether each of the jobs finishes by a deadline within the period, determines that scheduling is impossible, when one of the jobs is determined not to finish by the deadline, determines whether the distribution of the execution times of the jobs each determined to finish by the deadline converge, and determines that scheduling is possible, when the distribution converge.

Claims

1. A schedulability determination method in a real-time system including a plurality of processors for executing jobs of a plurality of periodic tasks each having predetermined period, comprising;

preparing scheduling means for assigning the processors each job in a period of each of the tasks;

calculating distribution of execution times during which jobs assigned by the scheduling means are executed on the processors;

determining, based on the distribution, whether each of the jobs finishes by a deadline;

determining that scheduling is impossible, when one of the jobs is determined not to finish by the deadline;

determining whether the distribution of the execution times of the jobs each determined to finish by the deadline converges; and

determining that scheduling is possible, when the distribution converges.

2. A method according to claim 1,

wherein determining whether the distribution converges determines whether the distribution converges, based on unexecuted jobs of the tasks whose periods have started at a first time point and a second time point that have a time difference corresponding to a least common multiple of the periods of the tasks, and

wherein determining that scheduling is possible determines that scheduling is possible, when the unexecuted jobs at the first time point and those at the second time point are identical to each other.

3. A method according to claim 1, wherein determining whether the distribution converges determines whether the distribution converges, when the distribution during one of two successive time intervals and the distribution during another of the two successive time intervals are identical to each other, each of the two successive time intervals corresponding to a least common multiple of the periods of the tasks after the latest release time among release times of the tasks.

4. A method according to claim 1, wherein the scheduling means assigns the each job to the processors in accordance with priority of the each job.

5. A method according to claim 1, wherein the scheduling means assigns the each job to the processors based on the deadline of the each job.

6. A method according to claim 4,.wherein the scheduling means assigns the each job to the processors by using a scheduling algorithm of, when, a time difference in execution start time between two jobs of first task which is one of the tasks and a time difference in execution start time between two jobs of second task which is another of the tasks are integer multiples of a least common multiple of the periods of the tasks, and a job to be executed first among the two jobs of the first task is executed preferentially to a job to be executed first among the two jobs of the second task, executing a job to be executed later among the two jobs of the first task preferentially to a job to be executed later among the two jobs of the second task.

17. A method according to claim 1, wherein the scheduling means assigns the each job to the processors by using an EDF (Earliest Deadline First) algorithm.

7. A schedulability determination method in a real-time system including a plurality of processors for executing jobs of a plurality of periodic tasks each having predetermined period, comprising;

preparing scheduling means for assigning the processors each job in a period of each of the tasks;

calculating grid times after the latest release time among release times of the tasks, each of the grid times being a time point at which start times of periods of the tasks coincide with each other;

calculating distribution of execution times during which jobs assigned by the scheduling means are executed in the processors;

determining, based on the distribution, whether each of the jobs finishes by a deadline within the period;

determining that scheduling is possible, when jobs assigned by the scheduling means by a second grid time are determined to finish by their deadline;

determining that scheduling is impossible, when one of jobs assigned by the scheduling means by the second grid time is determined not to finish by its deadline.

8. A real-time system including a plurality of processors for executing jobs of a plurality of periodic tasks each having predetermined period, comprising;

scheduling means for assigning each job in a period of each of the tasks to the processors;

calculating means for calculating distribution of execution times during which jobs assigned by the scheduling means are executed in the processors;

first determination means for determining, based on the distribution, whether each of the jobs finishes by a deadline;

second determination means for determining that scheduling is impossible, when one of the jobs is determined not to finish by the deadline;

third determination means for determining whether the distribution of the execution times of the jobs each determined to finish by the deadline converges; and

fourth determination means for determining that scheduling is possible, when the distribution converges.

9. A system according to claim 8,

wherein the third determination means determines whether the distribution converges, based on unexecuted jobs of the tasks whose periods have started at a first time point and a second time point that have a time difference corresponding to a least common multiple of the periods of the tasks, and

the fourth determination means determines that scheduling is possible, when the unexecuted jobs at the first time point and those at the second time point are identical to each other.

10. A system according to claim 8, further comprises:

fifth determination means for determining whether grid times exist after the latest release time among release times of the tasks, each of the grid times being a time point at which start times of periods of the tasks coincide with each other;

sixth determination means for determining that scheduling is possible, when the grid times exist and jobs assigned by the scheduling means by a second grid time are determined to finish by their deadline; and

seventh determination means for determining that scheduling is impossible, when the grid times exist and one of jobs assigned by the scheduling means by the second grid time is determined not to finish by its deadline.

11. A system according to claim 8, wherein the scheduling means assigns the each job to the processors based on the deadline of the each job.

12. A system according to claim 8, wherein the fourth determination means determines that the distribution converges, when the distribution during one of two successive time intervals and the distribution during another of the two successive time intervals are identical to each other, each of the two successive time intervals corresponding to a least common multiple of the periods of the tasks after the latest release time among release times of the tasks.

13. A system according to claim 8, wherein the scheduling means assigns the each job to the processors in accordance with priority of the each job.

14. A system according to claim 8, wherein the scheduling means assigns the each job to the processors based on the deadline of the each job.

15. A system according to claim 13, wherein the scheduling means assigns the each job to the processors by using a scheduling algorithm of, when, a time difference in execution start time between two jobs of first task which is one of the tasks and a time difference in execution start time between two jobs of second task which is another of the tasks are integer multiples of a least common multiple of the periods of the tasks, and a job to be executed first among the two jobs of the first task is executed preferentially to a job to be executed first among the two jobs of the second task, executing a job to be executed later among the two jobs of the first task preferentially to a job to be executed later among the two jobs of the second task.

16. A system according to claim 8, wherein the scheduling means assigns the each job to the processors by using an EDF (Earliest Deadline First) algorithm.

18. A computer program stored on a computer readable medium, the computer including a plurality of processors for executing jobs of a plurality of periodic tasks each having predetermined period, the computer program comprising:

first program instruction means for instructing a computer processor to assign each job in a period of each of the tasks to the processors;

second program instruction means for instructing a computer processor to calculate distribution of execution times during which jobs assigned are executed on the processors;

third program instruction means for instructing a computer processor to determine, based on the distribution, whether each of the jobs finishes by a deadline within the period;

fourth program instruction means for instructing a computer processor to determine that scheduling is impossible, when one of the jobs is determined not to finish by the deadline;

fifth program instruction means for instructing a computer processor to determine whether the distribution of the execution times of the jobs each determined to finish by the deadline converge; and

sixth program instruction means for instructing a computer processor to determine that scheduling is possible, when the distribution converge.