Method for scheduling executions of real-time processes to guarantee satisfaction of various timing constraints

• US 7,444,638 B1
• Filed: 01/30/2006
• Issued: 10/28/2008
• Est. Priority Date: 06/21/1999
• Status: Expired due to Fees

• Current Assignee: Jia Xu
• Original Assignee: Jia Xu
• Inventors: Xu, Jia
• Primary Examiner(s): An; Meng-Ai
• Assistant Examiner(s): Tang; Kenneth
• Application Number:
  US11/341,713
• Time in Patent Office: 1,002 Days
• Field of Search: 718100-108
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/483 Multiproc
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic

Abstract

A system and methods for scheduling executions of real-time processes, including periodic processes and asynchronous processes to guarantee satisfaction of various timing constraints. The system schedules their executions in two phases: a pre-run-time (off-line) phase performed by a pre-run-time scheduler, and a run-time (on-line) phase performed by a run-time scheduler.

Claims

1. A method of converting one or more asynchronous processes into corresponding new periodic processes,

each asynchronous process having predetermined constraints including

(a) worst-case computation time,

(b) deadline,

(c) minimum time between two consecutive requests,

(d) earliest time at which a request for execution can be made,

each asynchronous process being converted to one corresponding new periodic process,

comprising:

(1) determining a deadline constraint and a period constraint for each corresponding new periodic process, wherein the period of each corresponding new periodic process must be less than or equal to the minimum time between two requests of the corresponding being converted asynchronous process, and less than or equal to the deadline of the corresponding being converted asynchronous process minus the deadline of said corresponding new periodic process plus one,

(2) determining a permitted range of offset constraint for each corresponding new periodic process, wherein

said permitted range of offset comprising an interval that begins at a lower bound value and ends at an upper bound value which may be equal to the lower bound value, the duration of the time interval between the beginning of the first period of said corresponding new periodic process and time zero must be greater than or equal to said lower bound value and less than or equal to said upper bound value,

said permitted range of offset being a subinterval of an interval or a full interval that begins at the earliest time at which a request for execution can be made by the corresponding being converted asynchronous process, and ends at a time equal to the sum of the earliest time at which a request for execution can be made by the corresponding being converted asynchronous process plus the period length of the new periodic process minus one time unit,

such that satisfaction of said constraints of each corresponding new periodic process guarantees satisfaction of the predetermined constraints of the corresponding being converted asynchronous process.

2. The method as defined in claim 1, including reducing possible timing conflicts with other periodic or asynchronous processes with less latitude in meeting their deadlines, by taking into consideration the computation time requirements of the latter processes when determining the deadline of each of the new periodic processes.

3. The method as defined in claim 1, including reducing possible timing conflicts with other periodic or asynchronous processes with less latitude in meeting their deadlines, by including conversion room comprising the sum of the computation times of all possible occurrences of the latter processes within a time interval that is of length equal to the deadline of the corresponding new periodic process, when determining the deadline of each of the corresponding new periodic processes.

4. The method as defined in claim 1, wherein it is also determined whether the corresponding being converted asynchronous process should or should not be converted into a corresponding new periodic process.

5. The method as defined in claim 1, including automatically adjusting lengths of periods of one or more periodic processes, including new periodic processes converted from asynchronous processes, and setting the deadline for any new periodic processes to be equal to the deadline of the corresponding being converted asynchronous process minus the length of the period of said any new periodic process plus one in the event that the length of the period of said any new periodic processes has been changed.

6. The method as defined in claim 1, including mapping the corresponding new periodic processes into time slots in a pre-run-time schedule.

7. The method as defined in claim 6, including further scheduling executions of the corresponding new periodic processes such that the deadline, period, and permitted range of offset constraints of the corresponding new periodic processes are satisfied.

8. The method as defined in claim 6, including further executing a set of asynchronous processes that are not mapped to time slots during run-time of the processor at times which do not interfere with execution of processes mapped to time slots in the pre-run-time schedule.

9. The method as defined in claim 6, including scheduling, between the beginning time and end time of each of the time slots in the pre-run-time schedule reserved for execution of a corresponding periodic process, time capacity sufficient to complete execution of said corresponding periodic process and additional time capacity sufficient to complete execution of asynchronous processes that are not converted to new periodic processes and hence not mapped to time slots in the pre-run-time schedule and have less latitude than said corresponding periodic process in meeting their respective deadlines.

10. A method as defined in claim 6, including generating the pre-run-time schedule as a feasible two-part pre-run-time-schedule for execution of periodic processes that may have non-zero offsets (a) an initial part which may be of zero length, and (b) a repeating part having length which is equal to a least common multiple of lengths of the periods of the periodic processes,

all executions of all periodic processes within a time interval of length equal to the length of the least common multiple of the periodic process periods being included in the repeating part of the pre-run-time schedule, wherein all said predetermined constraints being satisfied for all executions of all periodic processes within said initial part and said repeating part.

11. A method as defined in claim 10, including using any offset value in a permitted range of offsets of each periodic process, including any offset value in the permitted range of offsets of any new periodic process that may have been converted from an asynchronous process, to generate said feasible pre-run-time schedule.

12. A method as defined in claim 10, further comprising:

(A) constructing a first schedule for executions of the periodic processes within an interval starting from zero and having length equal to maximum offset value plus a bounded number of times of the length of a least common multiple of the periodic process periods, conditions for determining feasibility requiring the existence of a point in said first schedule wherein starting from the latter point the schedule repeats in subschedule interval lengths equal to a least common multiple of lengths of the periodic process periods, timing of all executions of all periodic processes within a time interval having length equal to the length of the least common multiple of the periodic process periods being included in each said repeating subschedule interval, and including satisfaction of all predetermined constraints for all executions of all periodic processes within the subschedule interval starting from time zero and ending at said point plus the length of the least common multiple of the periodic process periods in said first schedule, and checking for the first occurrence of said point in said first schedule,

(B) generating said feasible two-part pre-run-time-schedule by

(1) using a subschedule interval starting from time zero and ending at said point in said first schedule as said initial part of said feasible two-part pre-run-time schedule, and

(2) using a subschedule interval starting from said point and ending at said point plus the length of the least common multiple of the periodic process periods in said first schedule as said repeating part of said feasible two-part pre-run-time schedule.

13. A method as defined in claim 12, including using any offset value in a permitted range of offsets of each periodic process, including any offset value in the permitted range of offsets of any new periodic process that may have been converted from an asynchronous process, to generate said feasible pre-run-time schedule.

14. The method as defined in claim 1, including mapping the corresponding new periodic processes into time slots in a pre-run-time schedule in a manner similar to mapping of other periodic processes.

15. The method as defined in claim 14, including further scheduling executions of the corresponding new periodic processes such that the deadline, period, and permitted range of offset constraints of the corresponding new periodic processes are satisfied.

16. The method as defined in claim 1, including further scheduling executions of the corresponding new periodic processes such that the deadline, period, and permitted range of offset constraints of the corresponding new periodic processes are satisfied.