Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-12-07
2003-02-18
Oberley, Alvin (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C707S793000
Reexamination Certificate
active
06523059
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to the facilitation of a global safepoint operation in a multithreaded computer system environment. More particularly, the present invention relates to facilitating a global safepoint operation while avoiding suspending all threads during safepoint synchronization.
In computer science, the term “multitasking” is often used to refer to an operating system's ability to support multiple processes simultaneously. A process, as will be appreciated by those skilled in the art, is often a program that is being executed. Support for multiple processes is necessary in applications where several computations proceed in parallel, i.e., substantially simultaneously. In time-sharing systems, multiple users share a single computer system and all processes created by the users should, at least in principle, potentially execute simultaneously. Real time systems that control multiple devices also need to support multiple processes. For instance, an avionics computer on board an airplane runs processes for monitoring the engines, updating the flight instruments, processing radar signals, and keeping the airplane on course. Batch operating systems depend on multitasking for overlapping computation with input/output (I/O) operations. For instance, when a process performs I/O, the operating system may run another process to avoid idling the central processor for long periods of time.
One type of process is known as a primitive process, or a thread. A single process may also include multiple threads. Typically, the simplest way to execute multiple threads simultaneously is to assign each thread to its own processor in a multiprocessor system. If the number of threads exceeds the number of processors, then processors must typically be multiplexed among the threads. By switching a processor rapidly from one thread to the next, it appears to the observer as if all threads are making progress, even if the processor can execute only one instruction at a time. While processor multiplexing typically implements only quasi-parallelism, peripheral devices may provide true parallelism even if the computer system contains only a single, central processor. Many peripheral devices may be regarded as specialized processors that operate concurrently with the central processor. A device runs a single process specialized, for example, for printing a line or writing a disk block. The device generally receives commands from a device driver process that itself runs on the central processor. After a device driver has issued a command to a device, the device driver waits for a completion signal. During this wait, the main processor typically switches its attention from the device driver to other threads.
While maintaining multiple threads, the computer system may need to perform global operations which require synchronization, or control of all or a group of threads at a given time. An example of such a global operation is garbage collection. As will be appreciated by those skilled in the art, garbage collection is a method which allows memory storage associated with objects which are no longer alive to be automatically reclaimed.
Many programming languages and systems provide for dynamic as well as static allocation of memory storage to abstract data objects. The performance of these systems relies on their ability to reclaim and reuse storage for dynamically allocated objects after the dynamically allocated objects are no longer needed by the executed program. Some language systems require programmers to return unneeded objects to the memory system explicitly. Although this explicit return of memory permits precise and efficient recycling of storage when performed carefully, it often results in objects being recycled prematurely or being forgotten and thus lost to the system. Other systems reclaim abandoned objects automatically through a process such as “garbage collection.” Reclaiming storage automatically in this way is both a convenience to the programmer and a means for insuring that every object's storage is recycled correctly.
Garbage collection typically occurs in two phases. A first phase typically involves identifying unneeded objects, while a second phase renders the storage associated with the unneeded objects available for reallocation. An object in a program is needed, or live, at a given time if the program might access the object in the future. When an object is such that no program will access it in the future, the object is considered to be dead. In practice, garbage collection algorithms, or “garbage collectors,” typically consider an object to be dead only if the program has abandoned all pointers to it, making future access impossible.
For a global operation, such as garbage collection, all the locations of objects and all locations of reference pointers typically need to be known to perform such a global operation. In a multithreaded environment, a “stop” instruction is typically sent to all threads prior to performing a global operation. Once a stop instruction is sent to all threads, it needs to be determined whether each thread is in a “safe” region or an “unsafe” region. A safe region is typically a region of code through which a thread is processing, and in which pointers are not being manipulated. An unsafe region is a region of the code through which a thread is processing, and in which pointers may be manipulated. Conventionally, all threads are typically suspended (“thread suspends”) in order to evaluate each thread and determine if each thread is in a safe or unsafe region. If a thread is in an unsafe region, then the thread operation is resumed and is stopped later to attempt to suspend it at a safe region.
Although thread suspends can be effective in some systems, typically, the more concurrent threads that are in use at any given time, the slower the thread suspend progresses. Accordingly, suspend processes may be very expensive to perform on many of today's advanced processors which support many concurrent threads, due to the fact that the speed associated with a system may be significantly compromised. Additionally, many threads are in a situation such that they may not need to be suspended. For example, when a thread is in a safe region, then that particular thread causes no problems for the performance of a global safepoint operation. However, conventionally, all the threads are suspended in order to evaluate and determine whether each thread is in a safe or unsafe region.
Therefore, what is desired is a relatively inexpensive method and apparatus for performing a global safepoint operation. Specifically, what is needed is a method and an apparatus for facilitating a global safepoint operation, without the need to suspend all threads, e.g., without the need to suspend threads which are in a safe region.
SUMMARY OF THE INVENTION
The present invention relates to a system and a method for facilitating a global safepoint operation in a multithreaded computer system. According to one aspect of the present invention, each thread keeps track of its safepoint regions by maintaining a variable which indicates a state, such as whether the current region of the thread is safe, unsafe, or transitional. In this manner, it can be determined whether a thread is currently in a safepoint region without suspending the thread. When a thread is currently in a safepoint region, the thread can continue to operate while a global safepoint operation, such as garbage-collection, is being performed. When the thread begins to transition out of the safe region, it moves into a transitional region. The transitional region automatically blocks the transition into the non-safe region to assure that the safepoint operation occurs in a safe region.
In one embodiment, one thread may begin a safepoint procedure after it acquires a safepoint lock. The safepoint lock blocks other threads from attempting to perform the safepoint procedure at the same time. Prior to initiating a safepoint operation, the thread attempting to initiate the
Beyer Weaver & Thomas LLP
Oberley Alvin
Sun Microsystems Inc.
Zhen Li
LandOfFree
System and method for facilitating safepoint synchronization... 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 facilitating safepoint synchronization..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for facilitating safepoint synchronization... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3163801