Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
2006-11-21
2006-11-21
Lee, Thomas (Department: 2115)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C718S100000, C718S101000, C718S102000, C718S103000
Reexamination Certificate
active
07140022
ABSTRACT:
In a multitasking system executing real-time harmonic and dynamic tasks having various priority levels, slack is stolen from both timeline and reclaimed slack to enable the 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, and slack is allocated and consumed by rate, with the highest rate first and the lowest rate last. Also described are a computer system and various methods that perform slack stealing in a multitasking system in which dynamic tasks can request activation or deactivation at any time.
REFERENCES:
patent: 5448735 (1995-09-01), Anderson et al.
patent: 5455825 (1995-10-01), Lauer et al.
patent: 5796719 (1998-08-01), Peris et al.
patent: 5887143 (1999-03-01), Saito et al.
patent: 6047354 (2000-04-01), Yoshioka et al.
patent: 6189022 (2001-02-01), Binns
patent: 6282561 (2001-08-01), Jones et al.
patent: 6393433 (2002-05-01), Kalavade et al.
patent: 6505229 (2003-01-01), Turner et al.
patent: 6567840 (2003-05-01), Binns et al.
patent: 6964048 (2005-11-01), Isham
patent: 2002/0120661 (2002-08-01), Binns et al.
Alia K. Atlas and Azer Bestavros, “Slack Stealing Job Admission Control Scheduling”, Boston University Technical Report 98-009, May 1998.
Cofer, D., et al., “Using Model Checking for Verification of Partitioning Properties in Integrated Modular Avionics”,IEEE, Digital Avionics System Conference(DASC), pp. 1.D.2-1 through 1.D.2-10, (Oct. 2000).
Ripoll, Ismael et al., “An Optimal Algorithm for Scheduling Soft Aperiodic Tasks in Dynamic-Priority Preemptive System,” 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, paragrah ' 08/3!.
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., 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).
Lugi, “Real-Time Constraints In a Rapid Prototyping 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 from Automated Implementation of Executable 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 Procedence 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).
Honeywell International , Inc.
Lee Thomas
McDonnell Boehnen & Hulbert & Berghoff LLP
Weinman Sean
LandOfFree
Method and apparatus for slack stealing with dynamic threads 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 and apparatus for slack stealing with dynamic threads, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for slack stealing with dynamic threads will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3644290