Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-05-06
2002-02-19
Courtenay, III, St. John (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000
Reexamination Certificate
active
06349322
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates, in general, to data processing, and, more particularly, to thread synchronization in JAVA language programs.
2. Relevant Background
The JAVA™ (a trademark of Sun Microsystems, Inc.) programming language, is an object-oriented programming language developed by Sun Microsystems, Inc., the Assignee of the present invention. The JAVA programming language has found success as a language and programming environment for networked applications. The JAVA programming language is attractive due to its many features, including standardized support for concurrent execution of program threads. The JAVA programming language's concurrency features are provided at both a language (syntactic) level and through a “threads” library. At the language level, an object's methods can be declared “synchronized”. Methods within a class that are declared synchronized do not run concurrently and run under control of “monitors” to ensure that variables remain in a consistent state.
Each time a synchronized method is entered or exited, the JAVA language requires calls to the operating system (O/S) kernel to allocate thread synchronization resources. Calls to the kernel may require tens if not hundreds of instructions depending on the O/S in use. In comparison, the synchronized method itself may require only a few lines of code. As an example, a dictionary hash table method can be implemented with fewer than ten instructions, but to implement it as a synchronized method requires more than 100 instruction in a typical operating system. Hence, thread synchronization significantly adds to the execution time of many programs.
This overhead is required in programs that make heavy use of multi-threading and depend on thread synchronization. However, this overhead is undesirable in programs that are single-threaded. Similarly, even in multithreaded programs, a large number of the threads may in fact execute correctly without the synchronization overhead. Hence, a need exists for a thread synchronization mechanism that only incurs the overhead associated with O/S thread management resource allocation only when those resources are needed.
Operating systems conventionally enable multithreading in one of two ways: preemptable and non-preemptable. A preemptable thread operating system (e.g., Solaris and Windows/NT) include O/S techniques and devices that enable one thread to interrupt another concurrently executing thread. Hence, at any given time, an executing thread cannot predict whether it will continue to execute or whether it will be blocked by another thread. Hence, the application cannot manage thread synchronization on its own because it lacks visibility as to when threads will be blocked. Preemptable threads are also valuable in multiprocessing machines to efficiently distribute execution of threads across multiple processors.
Non-preemptable multithreading is an simpler form of multithreading that supports a mode of thread execution, whereby once a thread begins to execute, it cannot be blocked by another thread. A thread may halt or block itself, yield control to other threads, or be blocked by virtue of waiting for input/output (I/O) to complete. There remain a large number of applications that can be implemented as single threads and which do not require the preemptive multithreading features of an operating system. Non-preemptive operating systems will likely exist in information appliances and simpler operating systems for some time. Where the O/S ensures that each thread cannot be preempted, allocation of thread synchronization resources in the O/S increases program execution time with little benefit.
Multithreading takes advantage of parallelism inherent in (or designed into) many programs. However, legacy programs often exhibit little parallelism. Moreover, some programs by the nature of their behavior do not exhibit a high degree of parallelism. These programs are slowed by having to incur the overhead associated with multithreading operating systems without reaping any benefits because of their non-parallel structure. Hence, a need exists for a thread synchronization mechanism that speeds up execution in programs that are essentially un-threaded yet running on a multithreading operating system.
SUMMARY OF THE INVENTION
Briefly stated, the present invention involves a method for synchronized thread execution in a multithreaded processor. Each synchronized thread refers to at least one object identified by an object identification (OID) that is shared among a plurality of synchronized threads. One of the synchronized threads is selected for execution. Upon entering the selected thread, an entry sequence indicates that the shared object should be locked by pushing its OID onto a lock stack. The operations defined by the selected thread are executed and the indication is removed by pushing the OID from the lock stack.
The foregoing and other features, utilities and advantages of the invention will be apparent from the following more particular description of preferred embodiments of the invention as illustrated in the accompany drawings. Still other embodiments of the present invention will become readily apparent to those skilled in the art from the following detailed description, wherein is shown and described only the embodiments of the invention by way of illustration of the best modes contemplated for carrying out the invention. As will be appreciated, the invention is capable of other and different embodiments and several of its details are capable of modification in various obvious respects, all without departing from the spirit and scope of the present invention. Accordingly, the drawings and detailed description are to be regarded as illustrative in nature and not as restrictive.
REFERENCES:
patent: 5706515 (1998-01-01), Connelly et al.
patent: 5835908 (1998-11-01), Bennett et al.
patent: 5862376 (1999-01-01), Steele, Jr. et al.
patent: 5924098 (1999-07-01), Kluge
patent: 5946487 (1999-08-01), Dangelo
patent: 5970242 (1999-10-01), O'Connor et al.
patent: 6108715 (2000-08-01), Leach et al.
Courtenay III St. John
Hogan & Hartson LLP
Opie George L.
Sun Microsystems Inc.
LandOfFree
Fast synchronization for programs written in the JAVA... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast synchronization for programs written in the JAVA..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast synchronization for programs written in the JAVA... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2936900