Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1997-08-20
2001-02-13
Banankhah, Majid (Department: 2755)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
Reexamination Certificate
active
06189022
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention is directed generally to criticality support for aperiodics when using slack scheduling. This invention is also directed towards slack scheduling for improved response times of period transformed processes. Further, this invention is directed towards slack scheduling applied to incremental periodic processes.
Existing methods for scheduling critical real-time periodic processes treat the execution time as a fixed, worst-case and known quantity that cannot change at run-time. In many optimizing control applications, processes can be written so they consume a fixed minimum execution time, followed by one or more optional execution increments of some size. The minimum execution time produces an acceptable but suboptimal solution that can be incrementally improved if additional execution time can be made available at run-time. Functions with this property are called incrementally precise functions or incremental processes. Aerospace applications that may be candidate algorithms are “optimal problems”, such as optimal control, optimal guidance, or optimal orbit transfer, which have solution techniques that are iterative. Other candidates might be fault detection, weapon deployment algorithms and diagnostic session interactions.
Alternatively, a process may be such that its execution time is parameterizable in the sense that a “bigger” problem can be solved when more time is available, and the problem “size” actually solved is determined by the amount of time available at run-time. This type of scheduling is known as design-to-time. As an example, the precision of a guidance calculation might be determined by the “size” of the grid/array modeling the terrain used to compute the trajectory. If a guidance algorithm with this property were modeled as a design-to-time application, the largest size array that would fit the available compute time would be selected.
SUMMARY OF THE INVENTION
A method for increasing the potential use of processor time and increasing response time. The process comprises the steps of defining process criticalities. Then transforming a periodic task set, and finally allocating available slack to transformed period processes.
REFERENCES:
patent: 3648253 (1972-03-01), Mullery et al.
patent: 5408663 (1995-04-01), Miller
patent: 5560032 (1996-09-01), Nguyen et al.
patent: 5566177 (1996-10-01), Bhandari et al.
patent: 5630096 (1997-05-01), Zuravleff et al.
Audsley, N.C., et al., “Fixed Priority Pre-emptive Scheduling: An Historical Perspective”,Real-Time Systems, 8, 1995 Kluwer Academic Publishers, Boston, 173-198, (1995).
Bettati, R. et al., “End-to-End Scheduling to Meet Deadlines in Distributed Systems”,Proceedings of the 12th International Conference on Distributed Computing Systems, 452-459, (Jun. 1992).
Binns, P., “Incremental Rate Monotonic Scheduling for Improved Control System Performance”,Real-Time Applications Symposium, Honeywell Technology Center, 11 pgs., (Jun. 1997).
Binns, P., “Scheduling Slack in MetaH”,Real-Time Systems Symposium, Work in Progress Session, Honeywell Technology Center, 4 pgs., (Dec. 1996).
Binns, P., et al., “Precedence Constrained Fixed Priority Scheduling with Solutions to Some Practical Problems”, Honeywell Technology Center; Submitted to RTSS '99, (1999).
Garcia, J.J., et al., “Optimized Priority Assignment for Tasks and Messages in Distributed Hard Real-Time Systems”,IEEE, 124-132, (1995).
Gerber, R., et al., “Semantics-Based Compiler Transformations for Enhanced Schedulability”,IEEE, 232-242, (1993).
Gertz, M.W., et al., “A Human-Machine Interface to Support Reconfigurable Software Assembly for Virtual Laboratories”,IEEE Robotics and Automation Magazine, 1-8, (Dec. 1994).
Gillies, D.W., et al., “Scheduling Tasks with and/or Precedence Constraints”,Siam J. Comput., 24, 1995 Society for Industrial and Applied Mathematics 797-810, (Aug. 1995).
Harbour, M.G., et al., “Fixed Priority Scheduling of Periodic Tasks with Varying Execution Priority”,IEEE, 116-128, (1991).
Johnson, M., “Boeing 777 Airplane Information Management System—Philosophy and Displays”, Honeywell, Inc. Air Transpost Systems, Phoenix, Arizona, USA, 8 pgs.
Lehoczky, J., et al., “The Rate Monotonic Scheduling Algorithm: Exact Characterization And Average Case Behavior”,IEEE, 166-171, (1989).
Lehoczky, J.P., “Fixed Priority Scheduling of Periodic Task Sets with Arbitrary Deadlines”,IEEE, 201-209, (1990).
Lehoczky, J.P., et al., “An Optimal Algorithm for Scheduling Soft-Aperiodic Tasks in Fixed-Priority Preemptive Systems”,IEEE, 110-123, (1992).
Lehoczky, J.P., et al., “Enhanced Aperiodic Responsiveness in Hard Real-Time Environments”,IEEE, 261-270, (1987).
Leung, J.Y., et al., “On the Complexity of Fixed-Priority Scheduling of Periodic, Real-Time Tasks”,Performance Evaluation 2, North-Holland Publishing Company, 237-250, (1982).
Liu, C.L., et al., “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment”, 46-61, (Jan. 1973).
Luqi, “Real-Time Constraints In a Rapid Prototyping Language”,Computer Lang., vol. 18, No. 2, Computer Science Department. Naval Postgraduate School. Monterey. CA. 93943. USA, 77-103, (1993).
McConnell, D.J., et al., “Reengineering a Single Threaded Embedded Missile Application Onto a Parallel Processing Platform Using MetaH”,IEEE, Proceedings of the 4th WPDRTS, 57-64, (1996).
Mok, A.K., et al., “Synthesis of a Real-Time Message Processing System with Data-driven Timing Constraints”,IEEE, 133-143, (1987).
Saksena, M., et al., “Design and Implementation of Maruti-II”,in Principles of Real-Time Systems, Sang Son Ed., Chapter 4, (1994).
Saksena, M., et al., “Guidelines for Automated Implementation of Executable Object Oriented Models for Real-Time Embedded Control Systems”,IEEE, 240-251, (1997).
Sha, L., et al., “Priority Inheritance Protocols: An Approach to Real-Time Synchronization”,IEEE Transactions On Computers, 39, 1175-1185, (Sep. 1990).
Sha, L., et al., “Solutions For Some Practical Problems In Prioritized Preemptive Scheduling”,IEEE, 181-191, (1986).
Sprunt, B., et al., “Exploiting Unused Periodic Time For Aperiodic Service Using The Extended Priority Exchange Algorithm”,IEEE, 251-258, (1988).
Spuri, M., et al., “How to Integrate Precedence Constraints and Shared Resources in Real-Time Scheduling”,IEEE Transactions on Computers, 43, 1407-1412, (Dec. 1994).
Stoyenko, A.D., “A Schedulability Analyzer for Real-Time Euclid”,IEEE, 218-227, (1987).
Sun, J., et al., “Synchronization Protocols in Distributed Real-Time Systems”,IEEE, 38-45, (1996).
Vestal, S., “Fixed-Priority Sensitivity Analysis for Linear Compute Time Models”,IEEE Transactions on Software Engineering, 20, 308-317, (Apr., 1994).
Vestal, S., “MetaH Support for Real-Time Multi-Processor Avionics”, Joint Workshop on Parallel and Distributed Real-Time Systems, Geneva, Switzerland, 10 pgs., (Apr. 1997).
Vestal, S., “Mode Changes in a Real-Time Architecture Description Language”,Second International Workshop on Configurable Distributed Systems, 11 pgs., (Mar. 1994).
Vestal, S., et al., “Scheduling and Communication in MetaH”,Proceedings of the Real-Time Systems Symposium, Raleigh-Durham, NC, 7 pgs., (Dec. 1993).
Xu, J., et al., “Scheduling Processes with Release Times, Deadlines, Precedence, and Exculsion Relations”,IEEE Transactions on Software Engineering, 16, 360-369, (Apr., 1994).
“A feasibility test for scheduling tasks in a distributed hard real-time systems”, M Chetto, H. Chetto, APII vol. 24, 1990, pp. 239-252, Copyright AFCET 1990.
Banankhah Majid
Honeywell International , Inc.
Shudy, Jr. John G.
LandOfFree
Slack scheduling for improved response times of period... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Slack scheduling for improved response times of period..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Slack scheduling for improved response times of period... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2591281