Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
2005-10-31
2008-08-05
Donaghue, Larry D (Department: 2154)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C718S103000, C718S104000, C709S226000
Reexamination Certificate
active
07409689
ABSTRACT:
The present invention provides providing predictable scheduling of programs using repeating precomputed schedules on discretely scheduled and/or multiprocessor operating systems. In one embodiment, a scheduler accesses an activity scheduling graph. The activity scheduling graph is comprised of nodes each representing a recurring execution interval, and has one root, one or more leaves, and at least one path from the root to each leaf. Each node is on at least one path from the root to a leaf, and the number of times the execution interval represented by each node occurs during the traversal of the graph is equal to the number of paths from the root to a leaf that the node is on. Each node has associated with it an execution interval length, and is adapted to being dedicated to executing the threads of a single activity. There may be one scheduling graph for each processor, or a scheduling graph may traverse multiple processors. Start and end times for reservations and constraints are adjusted to compensate for the granularity of the clock of the system. Furthermore, the scheduler may use an existing priority-based scheduler in order to cause scheduling decisions it has made to be acted upon.
REFERENCES:
patent: 5109512 (1992-04-01), Bahr et al.
patent: 5202975 (1993-04-01), Rasbold et al.
patent: 5210872 (1993-05-01), Ferguson et al.
patent: 5247675 (1993-09-01), Farrell et al.
patent: 5301333 (1994-04-01), Lee
patent: 5317734 (1994-05-01), Gupta
patent: 5392430 (1995-02-01), Chen et al.
patent: 5467268 (1995-11-01), Sisley et al.
patent: 5528513 (1996-06-01), Vaitzblit et al.
patent: 5606695 (1997-02-01), Dworzecki
patent: 5634113 (1997-05-01), Rusterholz
patent: 5640563 (1997-06-01), Carmon
patent: 5742821 (1998-04-01), Prasanna
patent: 5768592 (1998-06-01), Chang
patent: 5768594 (1998-06-01), Blelloch et al.
patent: 5781531 (1998-07-01), Charny
patent: 5812844 (1998-09-01), Jones et al.
patent: 5828886 (1998-10-01), Hayashi
patent: 5872972 (1999-02-01), Boland et al.
patent: 5978363 (1999-11-01), Dimitrijevic et al.
patent: 6003061 (1999-12-01), Jones et al.
patent: 6041354 (2000-03-01), Biliris et al.
patent: 6049332 (2000-04-01), Boetje et al.
patent: 6085218 (2000-07-01), Carmon
patent: 6269390 (2001-07-01), Boland
patent: 6633897 (2003-10-01), Browning et al.
patent: 7000232 (2006-02-01), Jones et al.
Jones, “Adaptive Real-Time Management Supporting Composition of Independently Authored Time-Critical Services”, 1993, IEEE, pp. 135-139.
Keckler, “The Importance of Locality in Scheduling and Load Balancing for Multiprocessors”, pp. 1-18, MIT Feb. 1994.
Salehi et al., “The Effectiveness of Affinity-Based Scheduling in Multiprocessor Networking”, 1996 IEEE, pp. 215-223.
Subramaniam et al., “Affinity Scheduling of Unbalanced Workloads”, 1994 IEEE, pp. 214-226.
Anderson et al., “Support for Continuous Media in the Dash System,” Proceedings of the 10th International Conference on Distributed Computing Systems, Paris, France, pp. 54-61, May 1990.
Bollella et al., “Support of Real-Time Computing Within General Purpose Operating Systems: Supporting Co-Resident Operating Systems,” in Proceedings of the IEEE Real-Time Technology and Applications Symposium, Chicago, IL, pp. 4-14, May 1995.
Bolosky et al., “Distributed Schedule Management in the Tiger Video Flleserver,” In Proceedings of the 16th ACM Symposium on Operating Systems Principles, Saint Malo, France, Oct. 1997.
Bolosky et al., “The Tiger Video Fileserver,” in Proceedings of the 6th International Workshop on Network and Operating System Support for Digital Audio and Video, IEEE Computer Society, Zushi, Japan, Apr. 1996.
Clark et al., “Supporting Real-Time Applications in an Integrated Services Packet Network: Architecture and Mechanism,” ACM SIGCOMM, pp. 14-26, 1992.
Deng et al., “Dynamic Scheduling of Hard Real-Time Applications Environment,” in Proceedings of the Real-Time Systems Symposium, Washington, D.C., Dec. 1996.
Dertouzos et al., “Multiprocessor On-Line Scheduling of Hard-Real-Time Tasks,” IEEE Transactions on Software Engineering, 15 (12): 1497-1506, 1989.
Ford et al., “Evolving Mach 3.0 to a Migratibg Thread Model,” in Proceedings of the Winter 1994 USENIX Conference, USENIX Association, San Francisco, CA, pp. 97-114, Jan. 1994.
Golub, David B., “Operating System Support for Coexistence of Real-Time and Conventional Scheduling,” Technical Report CMU-CS-94-212, Carnegie Mellon University, Pittsburgh, PA, 1994.
Jones et al., “Modular Real-Time Resource Management in the Rialto Operating System,” in Proceedings of the 5th Workshop on Hot Topics in Operating Systems, IEEE Computer Society, Orcas Island, WA, pp. 12-17, May 1995.
Jones et al., “An Overview of the Rialto Real-Time Architecture,” in Proceedings of the 7th ACM SIGOPS European Workshop, Connemara, Ireland, pp. 249-256, Sep. 1996.
Khanna et al., “Realtime Scheduling In SunOS 5.0,” in Proceedings of the Winter 1992 USENIX Conference, USENIX Association, San Francisco, CA, Jan. 1992.
Leslie et al., “The Design and Implementation of an Operating System to Supporting Distributed Multimedia Applications,” Journal on Selected Areas in Communications, 13(4), May 1995.
Mercer et al., “Processor Capacity Reserves: Operating System Support for Multimedia Applications,” in Proceedings of the IEEE International Conference on Multimedia Computing and Systems, May 1994.
Nieh et al., “The Design, Implementation and Evaluation of Smart: A Scheduler for Multimedia Applications,” in Proceedings of the 16th ACM Symposium on Operating Systems Principles, Saint-Malo, France, Oct. 1997.
Stoica et al., “A Proportional Share Resource Allocation Algorithm for Real-Time, Time-Shared Systems,” in Proceedings of the Real-Time Systems Symposium, Washington, D.C., Dec. 1996.
Waldspurger, Carl A., “Lottery and Stride Scheduling: Flexible Proportional-Share Resource Management,” dissertation, Massachusetts Institute of Technology, pp. 4-5, 8-151, Sep. 1995.
Compton et al., “Collaborative Load Shedding,” in Proceedings of the Workshop on the Role of Real-Time in Multimedia/Interactive Computing Systems, IEEE Computer Society, Raleigh-Durham, NC, pp. 1-7, Nov. 1993.
Liu et al., “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment,” Journal of the ACM 20(1): 46-61, 1973.
Northcutt, J. Duane, “The Alpha Operating System: Requirements and Rationale,” Archons Project Technical Report #88011, Department of Computer Science, Carnegie-Mellon, pp. 1-70, Jan. 1988.
Schwan et al., “Dynamic Scheduling of Hard-Real-Time Tasks and Real-Time Threads,” IEEE Transactions on Software Engineering 18(8): 736-748, 1992.
Sha et al., “Priority Inheritance Protocols: An Approach to Real-Time Synchronization,” IEEE Transactions on Computers 39(9): 1175-1185, 1990.
Sommer et al., “Operating System Extensions for Dynamic Real-Time Applications,” in Proceedings of the Real-Time Systems Symposium, Washington, D.C., pp. 45-50, Dec. 1996.
Stankovic et al., “The Spring Kernel: A New Paradigm for Real-Time Systems,” IEEE Software 8(3): 62-72, 1991.
Wall et al., “Bus Bandwidth Management in a High Resolution Video Workstation,” in Proceedings of the Third International Workshop on Network and Operating System Support for Digital Audio and Video, IEEE Computer Society, San Diego, CA, pp. 236-250, Nov. 1992.
Jones et al., “CPU Reservations and Time Constraints: Predictable Scheduling of Independent Activities” Proceedings of the 16.sup.th ACM Symposium on Operating Systems Principles., Saint-Malo, France, pp. 198-211, Oct. 1997.
Goyal et al., “A Hierachical CPU Scheduler for Multimedia Operating Systems”, Proceedings of the Second Symposium on Operating Systems Design and I
Jones Michael B.
Regehr John
Donaghue Larry D
Lee & Hayes PLLC
Microsoft Corporation
LandOfFree
Providing predictable scheduling of programs using repeating... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Providing predictable scheduling of programs using repeating..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Providing predictable scheduling of programs using repeating... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3998102