Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
2006-02-14
2006-02-14
An, Meng-Al T. (Department: 2195)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
Reexamination Certificate
active
07000232
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: 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: 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
Anderson, “Metascheduling for Continuous Media,”ACM Transactions on Computer Systems, vol. 11, No. 3, pp. 226-252 (Aug. 1993).
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).
Baccelli et al., “Extremal Scheduling of Parallel Processing with and without Real-Time Constraints,”Journal of the Association for Computing Machinery, vol. 40. No. 5, pp. 1209-1237 (Nov. 1993).
Bollella et al., “Support For Real-Time Computing Within General Purpose Operating Systems: Supporting Co-Resident Operating Systems,”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 Fileserver,”Proceedings of the 16th ACM Symposium on Operating Systems Principles, Saint-Malo, France, 12 pages (Oct. 1997).
Bolosky et al., “The Tiger Video Fileserver,”Proceedings of the 6th International Workshop on Network and Operating System Support for Digital Audio and Video, IEEE Computer Society, Zushi, Japan, 9 pages (Apr. 1996).
Clark et al., “Supporting Real-Time Applications in an Integrated Services Packet Network: Architecture and Mechanism,”ACM SIG COMM, pp. 14-26 (1992).
Compton et al., “Collaborative Load Shedding,”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).
Deng et al., “Dynamic Scheduling of Hard Real-Time Applications in Open System Environment,”Proceedings of the Real-Time Systems Symposium, Washington, D.C., 4 pages (Dec. 1996).
Dertouzos et al., “Multiprocessor On-Line Scheduling of Hard-Real-Time Tasks,”IEEE Transactions on Software Engineering, 15 (12), pp. 1497-1506 (Dec. 1989).
Ford et al., “CPU Inheritance Scheduling”,Proceedings of the Second Symposium on Operating Systems Design and Implementation, Seattle, Washington, pp. 91-105, USENIX Association (Oct. 1996).
Ford et al., “Evolving Mach 3.0 to a Migrating Thread Model,”Proceedings of the Winter 1994 USENIX Conference, USENIX Association, San Francisco, CA, pp. 97-114 (Jan. 1994).
Golub, “Operating System Support for Coexistence of Real-Time and Conventional Scheduling,”Technical Report CMU-CS-94-212, Carnegie Mellon University, Pittsburgh, PA, 13 pages (1994).
Goyal et al., “A Hierachical CPU Scheduler for Multimedia Operating Systems”,Proceedings of the Second Symposium on Operating Systems Design and Implementation, USENIX Association, Seattle, Washington, pp. 107-121 (Oct. 1996).
Hsueh et al., “An Optimal Pinwheel Scheduler Using the Single-Number Reduction Technique”,Proceedings of the Real-Time Systems Symposium, Washington, DC, pp. 196-205 (Dec. 1996).
Jones et al., “CPU Reservations and Time Constraints: Efficient, Predictable Scheduling of Independent Activities”Proceedings of the 16thACM Symposium on Operating Systems Principles, Saint-Malo, France, pp. 198-211 (Oct. 1997).
Jones et al., “Modular Real-Time Resource Management in the Rialto Operating System,”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,”Proceedings of the 7th ACM SIGOPS European Workshop, Connemara, Ireland, pp. 249-256 (Sep. 1996).
Khanna et al., “Realtime Scheduling in SunOS 5.0,”Proceedings of the Winter 1992 USENIX Conference, USENIX Association, San Francisco, CA, 16 pages (Jan. 1992).
Leslie et al., “The Design and Implementation of an Operating System to Support Distributed Multimedia Applications,”Journal on Selected Areas in Communications, 13(4), 22 pages (May 1995).
Liu et al., “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment,”Journal of the Association for Computing Machinery20(1), pp. 46-61 (1973).
Mercer et al., “Processor Capacity Reserves: Operating System Support for Multimedia Applications,”Proceedings of the IEEE International Conference on Multimedia Computing and Systems, 10 pages (May 1994).
Nieh et al., “The Design, Implementation and Evaluation of SMART: A Scheduler for Multimedia Applications,”Proceedings of the 16th ACM Symposium on Operating Systems Principles, Saint-Malo, France, 14 pages (Oct. 1997).
Northcutt, “The Alpha Operating System: Requirements and Rationale,”Archons Project Technical Report #88011, Department of Computer Science, Carnegie-Mellon, pp. 1-70 (Jan. 1988).
Ramamritham et al., “Efficient Scheduling Algorithms for Real-Time Multiprocessor Systems”,IEEE Transactions on Parallel and Distributed Systems, 1(2), pp. 184-194 (Apr. 1990).
Schwan et al., “Dynamic Scheduling of Hard-Real-Time Tasks and Real-Time Threads,”IEEE Transactions on Software Engineering18(7),pp. 736-748 (Jul. 1992).
Sha et al., “Priority Inheritance Protocols: An Approach to Real-Time Synchronization,”IEEE Transactions on Computers39(9), pp. 1175-1185 (Sep. 1990).
Sommer et al., “Operating System Extensions for Dynamic Real-Time Applications,”17thIEEE 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 Software8(3), pp. 62-72 (May 1991).
Stoica et al., “A Proportional Share Resouce Allocation Algorithm for Real-Time, Time Shared Systems,”Proceedings of the Real-Time Systems Symposium, Washington, D.C., 26 pages (Dec. 1996).
Waldspurger, “Lottery and Stride Scheduling: Flexible Proportional-Share Resource Managemen
Jones Michael B.
Regehr John
An Meng-Al T.
Lee & Hayes PLLC
Microsoft Corporation
Vo Lilian
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-3692973