METHOD OF COMPUTING LATEST START TIMES TO ALLOW REAL-TIME PROCESS OVERRUNS

摘要

A method is provided for allowing process overruns while guaranteeing satisfaction of various timing constraints. At least one latest start time for an uncompleted process is computed. If an uncompleted process does not start at its latest start time, then at least one of the predetermined constraints may not be satisfied. A timer is programmed to interrupt a currently executing process at a latest start time. In another embodiment, information about ordering of the end times of the process time slots in a pre-run-time schedule is used by a run-time scheduler to schedule process executions. Exclusion relations can be used to prevent simultaneous access to shared resources. Any process that does not exclude a particular process is able to preempt that particular process at any appropriate time at run-time, which increases the chances that a process will be able to overrun while guaranteeing satisfaction of various timing constraints.

主权项

1. A method of scheduling executions of a plurality of real-time processes, comprising:
(A) during run-time scheduling the process executions, such that predetermined constraints comprising
(1) deadline,(2) exclusion relations wherein each exclusion relation being defined between a selected pair of processes comprising a first process and a second process, not allowing preemption of an execution of said first process by an execution of said first process if said first process excludes said second process. will be satisfied, (B) allowing preemption of an execution of a particular first process at any point in time by an execution of a particular second process if said particular first process does not exclude said particular second process and if said preemption allows said predetermined constraints to be satisfied at run-time, (C) , computing latest start times for the uncompleted processes, such that if any one of the uncompleted processes does not start at its latest start time, then said any one of the uncompleted processes may not be able to satisfy at least one of the predetermined constraints, (D) during run-time allowing each process to overrun until the latest start time of another uncompleted process or the deadline of said each process is reached, programming the timer to interrupt a currently executing process at times which include at least one of the latest start times, (E) during run-time recomputing at least one of the latest start times, wherein the latest start time of a first process A may be increased, if the remaining computation time of a second process B has decreased due to a partial or complete execution of said second process B.