Electrical computers and digital processing systems: virtual mac – Task management or control
Reexamination Certificate
1999-12-14
2004-11-30
An, Meng-Al T. (Department: 2127)
Electrical computers and digital processing systems: virtual mac
Task management or control
C718S102000, C718S106000, C718S107000, C717S100000, C717S114000
Reexamination Certificate
active
06826752
ABSTRACT:
BACKGROUND
Many computer programs are computationally intensive, meaning that they require large amounts of computing power. As a consequence, these programs may execute more slowly than the computer user desires, even on the fastest computers. One way of increasing the execution speed of a computationally intensive computer program is to divide the program into multiple units, or loci, of concurrent execution. These units of execution are known as “threads”. A program with multiple threads of execution is known as a “multithreaded program”. A program with only a single thread of execution is known as a “sequential program”. The threads that make up a multithreaded program may be executed concurrently on multiple computer processors, allowing many operations in the program to be carried out simultaneously, thereby speeding up program execution.
In a multithreaded program, the program or operating system must control the access of threads to data objects in the program, in order to the prevent the multiple threads from concurrently accessing the same data object in an undesirable manner. If multiple threads modify the same data object concurrently, or read and modify the same data object concurrently, the resulting state of the program is extremely difficult to determine. Developing a multithreaded program is significantly more difficult than developing a sequential program because of the problems of (1) expressing the division of a program into multiple threads and (2) structuring and controlling the access of those threads to data objects.
SUMMARY
The present application teaches a structured thread (“Sthread”) system with thread synchronization and production mechanisms.
Another aspect produces multithreadable code. The multithreadable code can be annotated using information indicative of its multithreadability. The multithreadable code constructs are code constructs that can be executed in a multithreadable manner, or equivalently in a sequential manner. Multithreadable code constructs may be expressed by annotating sequential code constructs to indicate that their multithreaded execution is equivalent to sequential execution. The multithreadable code can be used along with multithreaded code. Specific instances of a multithreadable constructs: a multithreadable block, and a multithreadable for loop, and are disclosed.
The second aspect of the system is the integration of multithreadable code constructs with traditional explicitly multithreaded code constructs. Explicitly multithreaded code constructs must always be executed in a multithreaded manner. Examples of explicitly multithreaded code constructs include multithreaded block constructs, multithreaded for loop constructs, and library-based thread creation functions. Multithreadable code constructs and explicitly multithreaded code constructs may be intermingled within a program as required, with well-defined meaning.
According to a first aspect, a special counter called an “s-counter”, is used as a thread synchronization mechanism.
Special “s-Flags” can also be used for thread synchronization, and flag synchronization is also described herein.
Yet another aspect is the implementation of the programming system within an existing compiler environment using a special pre-processing system.
The embodiments of the invention describe additional details, including the following:
The s-counter synchronizing the access of threads to shared data objects. The mechanisms use “monotonic” synchronization objects, with operations that can be constrained to only move the value of the object in one direction. Monotonic synchronization objects can be used to synchronize the access of threads to shared data objects in multithreadable code constructs in a manner that guarantees the equivalence of sequential and multithreaded execution. Specific instances of monotonic synchronization objects are disclosed, namely a form of counter called an “s-counter” and a form of flag called an “s-flag”. The s-counter is a particularly powerful thread synchronization mechanism in many contexts, with its use in multithreadable code constructs being one example.
The application describes implementation of the multithreaded programming system within an existing program development and compilation environment using a special source-to-source preprocessing system and high-level thread library. This allows the system to be transparently and seamlessly integrated with existing programming systems such as Microsoft Visual Studio for the Microsoft Windows family of operating systems, the GNU program development tools for Linux and other versions of the Unix operating system, or on any version of the Java programming language, for example.
REFERENCES:
patent: 5179702 (1993-01-01), Spix et al.
patent: 5197130 (1993-03-01), Chen et al.
patent: 5551034 (1996-08-01), Herz
patent: 5768594 (1998-06-01), Blelloch et al.
patent: 5822588 (1998-10-01), Sterling et al.
patent: 5862376 (1999-01-01), Steele et al.
patent: 5928334 (1999-07-01), Mandyam et al.
patent: 5951653 (1999-09-01), Hill et al.
patent: 6009269 (1999-12-01), Burrows et al.
patent: 6064818 (2000-05-01), Brown et al.
patent: 6067604 (2000-05-01), Ramachandran et al.
patent: 6158048 (2000-12-01), Lueh et al.
patent: 6237043 (2001-05-01), Brown et al.
patent: 6286130 (2001-09-01), Poulsen et al.
patent: 6430638 (2002-08-01), Kessler et al.
patent: 6453466 (2002-09-01), Eidt
patent: 2002/0059358 (2002-05-01), Kanamori
Chandy K. Mani
Ishii Hiroshi
Thornley John
An Meng-Al T.
California Institute of Technology
Fish & Richardson P.C.
Vo Lilian
LandOfFree
Programming system and thread synchronization mechanisms for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Programming system and thread synchronization mechanisms for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Programming system and thread synchronization mechanisms for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3300961