Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
2007-11-27
2007-11-27
Lee, Thomas (Department: 2115)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C718S104000, C370S415000
Reexamination Certificate
active
09751834
ABSTRACT:
In a multitasking system executing real-time harmonic and dynamic tasks having various priority levels, slack is stolen from timeline and reclaimed slack to enable execution of high priority non-essential tasks on a best efforts basis. Counts of the amount of slack consumed, slack reclaimed, and periodic compute time consumed are maintained by individual priority level and dynamically updated at certain times. Idle time is calculated by priority level. Available slack is calculated, allocated and consumed by rate, with the highest rate first and the lowest last. Slack is made available to tasks in more than one time partition. All slack belongs to a common system-wide pool of slack obtained from any one or more time partitions. Common slack can also be time-shared by static, non-harmonic tasks residing in different time partitions. Also described are a computer system and methods that perform slack scheduling in a time-partitioned system.
REFERENCES:
patent: 5408663 (1995-04-01), Miller
patent: 5521837 (1996-05-01), Frankle et al.
patent: 6233724 (2001-05-01), LaBerge
patent: 6275239 (2001-08-01), Ezer et al.
patent: 6452933 (2002-09-01), Duffield et al.
Alia K. Atlas and Azer Bestavros, “Slack Stealing Job Admission Control Scheduling”, Boston University Technical Report 98-009, May 1998.
Audsley, N.C., et al., “Fixed Priority Pre-emptive Scheduling: An Historical Perspective”,Real-Time Systems, 8, Kluwer Academic Publishers, Boston, pp. 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, Yokohama, Japan, 8 p., (Jun. 1992).
Binns, P., “Incremental Rate Monotonic Scheduling for Improved Control System Performance”,Real-Time Applications Symposium, Honeywell Technology Center, 11 p., (Jun. 1997).
Binns, P., “Scheduling Slack in MetaH”,Real-Time Systems Symposium, Work in Progress Session, Honeywell Technology Center, 4 p., (Dec. 1996).
Garcia, J.J.G., et al., “Optimized Priority Assignment for Tasks and Messages in Distributed Hard Real-Time Systems”,IEEE, pp. 124-132, (1995).
Gerber, R., et al., “Semantics-Based Compiler Transformations for Enhanced Schedulability”,IEEE, pp. 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 (4), pp. 1-8, (Dec. 1994).
Gillies, D.W., et al., “Scheduling Tasks with and/or Precedence Constraints”,SIAM J. Comput., 24 (4), Society for Industrial and Applied Mathematics, pp. 797-810, (Aug. 1995).
Harbour, M.G., et al., “Fixed Priority Scheduling of Periodic Tasks with Varying Execution Priority”,IEEE, pp. 116-128, (1991).
Lehoczky, J., et al., “The Rate Monotonic Scheduling Algorithm: Exact Characterization And Average Case Behavior”,IEEE, pp. 166-171, (1989).
Lehoczky, J.P., et al., “An Optimal Algorithm for Scheduling Soft-Aperiodic Tasks in Fixed-Priority Preemptive Systems”,IEEE, pp. 110-123, (1992).
Lehoczky, J.P., et al., “Enhanced Aperiodic Responsiveness in Hard Real-Time Environments”,IEEE, pp. 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, pp. 237-250, (1982).
Liu, C.L., et al., “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment”,Journal of the Association for Computing Machinery, 20, (1), pp. 46-61, (Jan. 1973).
Luqi, “Real-Time Constraints In a Rapid Protyping Language”,Computer Lang., 18 (2), Computer Science Department, Naval Postgraduate School, Monterey, CA, pp. 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, pp. 57-64, (1996).
Mok, A.K., et al., “Synthesis of a Real-Time Message Processing System with Data-driven Timing Constraints”,IEEE, pp. 133-143, (1987).
Penix, J., et al., “Verification of Time Partitioning in the DEOS Scheduler Kernel”,The 22nd International Conference on Software Engineering, Limeric, Ireland, ACM Press, pp. 1-10, (Jun. 4, 2000).
Saksena, M., et al., “Design and Implementation of Maruti-II”,In: Principles of Real-Time Systems, Chapter 4, Sang Son, Ed., pp. 72-102, (1994).
Saksena, M., et al., “Guidelines for Automated Implementation of Exceutable Object Oriented Models for Real-Time Embedded Control Systems”,IEEE, pp. 240-251, (1997).
Sha, L., et al., “Priority Inheritance Protocols: An Approach to Real-Time Synchronization”,IEEE Transactions on Computers, 39 (9), pp. 1175-1185, (Sep. 1990).
Sha, L., et al., “Solutions For Some Practical Problems In Prioritized Preemptive Scheduling”,IEEE, pp. 181-191, (1986).
Spuri, M., et al., “How to Integrate Precedence Constraints and Shared Resources in Real-Time Scheduling”,IEEE Transactions on Computers, 43 (12), pp. 1407-1412, (Dec. 1994).
Stoyenko, A.D., “A Schedulability Analyzer for Real-Time Euclid”,IEEE, pp. 218-227, (1987).
Sun, J., et al., “Synchronization Protocols in Distributed Real-Time Systems”,IEEE, pp. 38-45, (1996).
Vestal, S., “Fixed-Priority Sensitivity Analysis for Linear Compute Time Models”,IEEE Transactions on Software Engineering, 20 (4), pp. 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 p., (Apr. 1997).
Vestal, S., “Mode Changes in a Real-Time Architecture Description Language”,Second International Workshop on Configurable Distributed Systems, 11 p., (Mar. 1994).
Vestal, S., et al.., “Scheduling and Communication in MetaH”,Proceedings of the Real-Time Systems Symposium, Raleigh-Durham, NC, 7 p., (Dec. 1993).
Xu, J., et al., “Scheduling Processes with Release Times, Deadlines, Precedence, and Exclusion Relations”,IEEE Transactions on Software Engineering, 16 (3), pp. 360-369, (Apr. 1994).
Cofer, D., et al., “Using Model Checking for Verification of Partitioning Properties in Integrated Modular Avionics”,IEEE, Digital Avionics System Conference(DASC), pp. 1.D2-1-1.D.2-1, (Oct. 2000).
Ripoll, Ismael et al., “An Optimal Algorithm for Scheduling Soft Aperiodic Tasks in Dynamic-Priority Preemptive Systems,” IEEE Transactions on Software Engineering: vol. 23, No. 6, Jun. 1997, pp. 388-399, the whole document.
Binns, Pam, “Incremental Rate Monotonic Scheduling for Improved Control System Performance,” Third IEEE Montreal Quebec Canada, Jun. 9-11, 1997, pp. 80-90, p. 80-p. 85.
Atlas, Alia K. et al., “Slack Stealing job Admission Control*,” Technical Report—Boston University, May 2, 1998, pp. 1-14, p. 1-p. 6.
Davis, R.I., “Approximate Slack Stealing Algorithms for Fixed Priority Pre-emptive Systems,” Real-time Systems Research Group, Dept. of Computer Science, University of York, England, Nov. 1993, p. 1.
Tia, Too-Seng et al., “Aperiodic Request Scheduling in Fixed-Priority Preemptive Systems,” University of Illinois at Urbana-Champaign, Jul. 1994, p. 9-p. 14.
Lehoczky, J.P. et al., “Chapter 8: Scheduling Periodic and Aperiodic Tasks using the Slack Stealing Algorithm,” Advances in Real Time Systems, 1995, pp. 172-195, paragraph ′08/3!.
Binns Pamela A.
Larson Aaron R.
Honeywell International , Inc.
Lee Thomas
McDonnell Boehnen & Hulbert & Berghoff LLP
Suryawanshi Suresh K
LandOfFree
Methods and apparatus for sharing slack in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for sharing slack in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for sharing slack in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3808266