Method of scheduling successive tasks subject only to timing con

Details Method of scheduling successive tasks subject only to timing con Method of scheduling successive tasks subject only to timing con

1995-08-02

1997-02-25

Kriess, Kevin A.

Boots, shoes, and leggings

364DIG1, 3642818, 3642816, 3642817, 3642813, G06F 946

Patent

active

056066953

ABSTRACT:
A method of scheduling successive tasks subject only to timing constraints calculates for each task upper and lower limits of the interval in which execution of that task must start. It then constructs a first series in which all the tasks are scheduled in increasing order of their lower limit and a second series in which all the asks are scheduled in increasing order of their upper limit, before constructing an initial permutation by scheduling all the tasks in the order of the first series and verifying if the initial permutation satisfies all the constraints. If not all the constraints are satisfied, the method determines in the initial permutation the first ill-placed task for which a constraint is not satisfied and a candidate task in the second series immediately preceding the ill-placed task in the second series in the current permutation. It then verifies that if the candidate task is shifted in the current permutation to a position immediately after the ill-placed task all the constraints applying to all the tasks shifted in this way are then satisfied.

REFERENCES:
Zhao et al, Simple and Integrated Hevristics, 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, 1989, pp. 240-248.
Schwan et al, Dynamic Scheduling of Hard Real-Time Tasks and Real-Time Thread S, IEEE Trans. on Software Engr., vol. 18, No. 8 Aug. 1992.
Al-Mouhamed, Lower Bound on the Number of Processors and Time for Scheduling Precedence Graphs with Communications Costs, IEEE Transactions on Software Engnr. v816 No. 12 Dec. 1990.
Stankovic et al, The Spring Kernel: A New Paradigm for Real-Time Systems, IEEE Software, v;8, issue 3 May 1991, pp. 62-72.
Lorts et al, Empirical Evalvation of Weighted and Prioritzed Static Scheduling Hevristics for Real-Time Multiprocessing Parallel and Distributed Real-Time Systems, Conf Date: 28-29 Apr. 1994, pp. 58-63.
Saksena et al, Temporal Analysis for Hard Real-Time Scheduling, Computers & Communications, 1993 Int'l Phoenix Conference, pp. 538-544.
IEEE Transaction on Software Engineering, vol. SE-13, No. 5, May 1987, New York, US pp. 564-576, Wei 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".

Affiliated with

Also associated with

Rating

Method of scheduling successive tasks subject only to timing con 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 subject only to timing con, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of scheduling successive tasks subject only to timing con will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1980801