Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1997-12-09
2001-07-03
Banankhah, Majid (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000
Reexamination Certificate
active
06256659
ABSTRACT:
FIELD OF THE INVENTION
The present invention is directed to multi-tasking in computer systems and, more particularly, to a system, method and computer program product for performing hybrid preemptive and cooperative multi-tasking based on logical units of work.
CROSS-REFERENCE TO OTHER APPLICATIONS
This patent application is related to the following commonly owned United States Patent Applications:
1. U.S. Patent Application titled, “System and Method for Emulating Telecommunication Network Devices,” Serial No. (to be assigned), Attorney Docket No. COS-94-027 (1575.1770000), by John V. McLain, Jr., and Damon Curnell, filed concurrently herewith;
2. U.S. Patent Application titled, “System and Method for Managing Computer System Resources Using Command Control Vectors,” Serial No. (to be assigned), Attorney Docket No. COS-97-033 (1575.2620000), by John V. McLain, Jr., and Damon Cumell, filed concurrently herewith;
3. U.S. Patent Application titled, “System and Method for Generating Responses to Inputs Using a Hybrid State Engine Table,” Serial No. (to be assigned), Attorney Docket No. COS-97-034 (1575.2630000), by John V. McLain, Jr., and Damon Curnell, filed concurrently herewith;
4. U.S. Patent Application titled, “Method and Apparatus for Emulating a Dynamically Configured Digital Cross-Connect Network,” Serial No. (to be assigned), Attorney Docket No. COS-94-029 (1575.0690000), by John V. McLain, Jr., and James Dellinger, filed May 1, 1996;
5. U.S. Patent Application titled, “Method and Apparatus for Emulating a Digital Cross-Connect Network,” Serial No. (to be assigned), Attorney Docket No. COS-94-021 (1575.0700000), by John V. McLain, Jr., filed May 1, 1996;
6. U.S. Patent Application titled, “Method and Apparatus for Emulating Digital Cross-Connect Network using a Flexible Topology to Test MCS Network Management,” Serial No. (to be assigned), Attorney Docket No. COS-95-013 (1575.0880000), by John V. McLain, Jr., filed May 1, 1996;
7. U.S. Patent Application titled, “Method and Apparatus for Emulating a Network of State Monitoring Devices,” Ser. No. (08/672,141), filed Jun. 27, 1996;
8. U.S. Patent Application titled, “Method and Apparatus for Simulating Multi-Tasking,” Serial Number (to be assigned), Attorney Docket No. COS-94-030, by John V. McLain, Jr.;
9. U.S. Patent Application titled, “System, Method and Computer Program product for Digital Cross Connect Testing,” Serial Number (to be assigned), Attorney Docket No. COS-96-006, (1575.1710000), by John V. McLain, Jr. and Dale W. Harris, filed Dec. 30, 1996; and.
10. U.S. Patent Application titled, “Digital Cross Connect Command Script Generator,” Ser. No. 08/774,651, filed Dec. 31, 1996.
The above-listed applications are incorporated herein by reference in their entireties.
RELATED ART
In conventional preemptive multi-tasking systems, threads are processed based on allotted time slices. Essentially, each thread is allotted a certain amount of processing time, known as a time slice. When a time slice expires, processing of one thread is interrupted so that another thread can be processed. Generally, a pointer is provided for indicating where, in a stream of instructions, processing was interrupted. When processing resumes at some later point in time, the pointer indicates the next instruction to be executed.
In time-slice preemptive processing, whenever processing of a thread is interrupted, a variety of temporary values must typically be stored until processing of the thread resumes. For example, suppose that a first thread is currently being processed which involves a number of computer instructions to complete. For example, suppose that the processor had to calculate a value (A+B)(C+D). A first computer instruction might add (A+B). A second computer instruction might place the calculated value of (A+B) into a first register. A third computer instruction might calculate (C+D). A fourth computer instruction might place the value (C+D) in a second register. A fifth computer instruction might retrieve the value (A+B) from the first register and the value (C+D) from the second register for multiplication. Finally, a sixth instruction might output the calculated value, (A+B)(C+D), to memory for use by anther thread or process at a later point in time.
Suppose that the time slice allotted to the first thread expired between the fourth and fifth instructions. The values stored in the first and second registers would then have to be stored in memory so that processing could resume at the fifth instruction at a later point in time. A separate pointer to memory would be required for each value stored to insure that the values could be retrieved when processing of this thread resumes. In addition, an instruction pointer is required to indicate that the fifth instruction is the next instruction to be executed when processing of this thread resumes.
Preferably, the values are stored in local physical memory. However, local physical memory is often required for processing subsequent threads. Thus, values might later be moved to a hard disk or other peripheral storage device. In either event, storage and subsequent retrieval of data takes valuable time which could otherwise be spent processing threads.
Time slice-based preemptive multi-tasking systems are thus time and resource consuming because of so many memory reads and writes. Each additional storage of a temporary variable and its associated pointer consumes valuable memory.
In cooperative multi-tasking systems, application programmers design applications with interruption points. When an interruption point is reached, the operating system is permitted to switch to another task. Designers can set interruption points where relatively few temporary values need to be stored. Cooperative multi-tasking systems tend to require fewer temporary storage location and thus can be faster than preemptive multi-tasking systems.
In cooperative multi-tasking systems, however, each application must be designed as a cooperative application. Otherwise, because the operating system has no way to force, or preempt, operation, once an application begins execution, if it does not freely give up control, it will continue to execute until it terminates. In such a situation there can be no multi-tasking.
What is needed, therefore, is a system, method and computer program product for multi-tasking which combines the desired features of preemptive and cooperative multi-tasking systems. That is, a system, method and computer program product which provides the operating system or a controller application preemptive power to interrupt any application but which interrupts at a point in an instruction stream where there are a minimal number of temporary values which must be stored.
SUMMARY OF THE INVENTION
The present invention is directed to a system, method and computer program product for performing hybrid preemptive and cooperative multi-tasking in a computer system. The present invention is based on a principle of logical units of work, which include a set of one or more computer instructions, the completion of which is a logical stopping point.
A logical unit of work can be, for example, one or more instructions in a stream of instructions, where each instruction requires a number of individual computer code instructions to execute. In the example above, a logical stopping point might be at the end of the sixth instruction where the contents of the first and second registers are no longer required by the thread. A logical unit of work can also be referred to as a smallest logical unit of work.
In a preferred embodiment, the present invention is implemented as a controller application which operates under an existing operating system. In an alternative embodiment, the present invention is implemented as an integral part of an operating system.
In operation, the present invention performs a number n of logical units of work for a first task or process. At the completion of the number n of logical unit of work, few, if any, temporary values need to be store
Curnell Damon
McLain, Jr. John V.
Banankhah Majid
MCI Communications Corporation
LandOfFree
System and method for performing hybrid preemptive and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for performing hybrid preemptive and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for performing hybrid preemptive and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2448402