1995-08-02
1998-10-20
Kriess, Kevin A.
G06F 1300, G06F 1500
Patent
active
058260803
ABSTRACT:
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.
REFERENCES:
"Fixed Priority Scheduling Periodic Tasks with Varying execution Priority" Harbor, et al, IEEE Comput. Soc. Press. Los Alamitos, CA. U.S.A. 1991, Dec. 4-6.
"An Optimal Algorithm for Guaranteeing Sporadic Tasks in Hard Real-Time Systems". IEEE Comput. Soc. Press, Los Alamitos, CA, USA 9-13 Dec. 1990.
Zhao et al, "Simple and Integrated Heuristic Algorithms for Scheduling Tasks with Time and Resource Constraints," Journal of Systems and Software, vol. 7, pp. 195-205, 1987.
Yuan et al, "A Decomposition Approach to Non-Preemptive Scheduling in Hard Real-Time Systems," Real-Time Systems Symposium, 1989, pp. 240-248.
Schwan et al, "Dynamic Scheduling of Hard Real-Time Tasks and Real-Time Threads," IEEE Trans. on Software Engineering, vol. 18, No. 8, Aug. 1992.
Al-Mouhamed, "Lower Bound on the Number of Processors and Time for Scheduling Precedence Graphs with Communication Costs," IEEE Trans. on Software Engineering, vol. 16, No. 12, Dec. 1990.
Stankovic et al, "The Spring Kernel: A New Paradigm for Real-Time Systems," IEEE Software, vol. 8, Issue 3, May 1991 pp. 62-72.
Lorts et al, "Empirical Evaluation of Weighted and Prioritized Static Scheduling Heuristic for Real-Time Multiprocessing Parallel and Distributed Real-Time Systems," Parallel and Distributed Real Time Systems Workshop; Apr. 28-29, 1994, pp. 58-63.
Saksena et al, "Temporal Analysis for Hard Real-Time Scheduling," Computers and Communications, 1993, International Phoenix Conference, pp. 538-544.
IEEE Transactions on Software Engineering, vol. SE-13, No. 5, May 1987, New York, US, pp. 564-576, Weis Zhao et al, "Scheduling Tasks with Resource Requirements in Hard Real-Time Systems".
Real Time Systems, vol. 1, No. 1, Jun. 1989, Dordrecht, NL pp. 27-60, Brinkley Sprunt et al, "A Periodic Task Scheduling for Hard-Real-Time Systems".
Proceedings of the IEEE, vol. 82, No. 1, Jan. 1994, New York, US, pp. 55-67, Krithi Ramamritham et al, "Scheduling Algorithms and Operating Systems Support for Real-Time Systems".
Proceedings of the Real-Time Systems Symposium, 2 Dec. 1986, New Orleans, USA, pp. 166-174; S. Cheng et al, "Dynamic Scheduling of Groups of Tasks with Precedence Constraints in Distributed Hard Real-Time Systems".
Cegelec
Kriess Kevin A.
Park Alice Y.
LandOfFree
Method of scheduling successive tasks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of scheduling successive tasks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of scheduling successive tasks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-257855