Thread synchronization in a garbage-collected system using execution barriers
First Claim
1. A method in a computer system for synchronizing the execution of each of a plurality of threads with a garbage collection process, the method comprising the steps of:
- for each thread,before the thread enters a series of instructions that interacts with references to garbage-collected objects, under the control of the thread, calling a first application programming interface (API) for disabling garbage collection if garbage collection is not already in progress, the first API returning immediately if called before garbage collection is initiated and returning only after garbage collection has completed if called after garbage collection is initiated;
before the thread enters a series of instructions that does not interact with references to garbage-collected objects, under the control of the thread, calling a second application programming interface (API) for enabling garbage collection, the second API returning immediately;
in a garbage collection thread, receiving a request to initiate garbage collection;
in response to the request, identifying threads that have enabled garbage collection more recently than they have disabled garbage collection;
after the identifying step, until all threads are identified or suspended,identifying threads that enable garbage collection, andsuspending threads that disable garbage collection; and
when all threads are identified or suspended,performing garbage collection, andsuspending identified threads that disable garbage collection during the performance of garbage collection.
2 Assignments
0 Petitions
Accused Products
Abstract
The present invention synchronizes threads in a garbage-collected system. In accordance with the invention, each thread may enable or disable garbage collection. A synchronization facility receives a request to initiate garbage collection. In response to the request, the facility identifies threads that have enabled garbage collection more recently than they have disabled garbage collection. Then, until all of the threads are identified or suspended, the facility identifies threads that enable garbage collection and suspends threads that disable garbage collection. When all threads are identified or suspended, the facility performs garbage collection. The facility also suspends any identified threads that attempt to disable garbage collection during the performance of garbage collection.
-
Citations
36 Claims
-
1. A method in a computer system for synchronizing the execution of each of a plurality of threads with a garbage collection process, the method comprising the steps of:
-
for each thread, before the thread enters a series of instructions that interacts with references to garbage-collected objects, under the control of the thread, calling a first application programming interface (API) for disabling garbage collection if garbage collection is not already in progress, the first API returning immediately if called before garbage collection is initiated and returning only after garbage collection has completed if called after garbage collection is initiated; before the thread enters a series of instructions that does not interact with references to garbage-collected objects, under the control of the thread, calling a second application programming interface (API) for enabling garbage collection, the second API returning immediately; in a garbage collection thread, receiving a request to initiate garbage collection; in response to the request, identifying threads that have enabled garbage collection more recently than they have disabled garbage collection; after the identifying step, until all threads are identified or suspended, identifying threads that enable garbage collection, and suspending threads that disable garbage collection; and when all threads are identified or suspended, performing garbage collection, and suspending identified threads that disable garbage collection during the performance of garbage collection.
-
-
2. A method in a computer system for synchronizing the execution of each of a plurality of threads with a garbage collection process, the method comprising the steps of:
-
for each thread, before the thread enters a series of instructions that interacts with references to garbage-collected objects, under the control of the thread, calling a first application programming interface (API) for disabling garbage collection if garbage collection is not already in progress, the first API returning immediately if called before garbage collection is initiated and returning only after garbage collection has completed if called after garbage collection is initiated; before the thread enters a series of instructions that does not interact with references to garbage-collected objects, under the control of the thread, calling a second application programming interface (API) for enabling garbage collection, the second API returning immediately, such that garbage collection may commence at a time after garbage collection initiation when each thread has either (1) called the second API more recently than it has called the first API or (2) called the first API after garbage collection was initiated, and such that instructions that interact with references to garbage-collected objects are not executed while garbage collection is being performed, while instructions that do not interact with references to garbage-collected objects may be executed while garbage collection is being performed.
-
-
3. A computer-readable medium whose contents cause a computer system to synchronize the execution of a thread with a garbage collection process by performing the steps of:
-
before the thread enters a series of instructions that interacts with references to garbage-collected objects, disabling garbage collection for the thread; when garbage collection is disabled for the thread, proceeding to execute the series of instructions that interacts with references to garbage-collected objects if garbage collection has not yet been initiated, and deferring execution of the series of instructions that interacts with references to garbage-collected objects if garbage collection has been initiated; before the thread enters a series of instructions that does not interact with references to garbage-collected objects, enabling garbage collection for the thread; and when garbage collection is enabled for the thread, proceeding to execute the series of instructions that does not interact with references to garbage-collected objects irrespective of whether garbage collection has been initiated, such that garbage collection may commence at a time after garbage collection initiation when either (1) garbage collection has been enabled for the thread more recently than it has been disabled for the thread or (2) garbage collection is disabled for the thread after garbage collection is initiated, and such that instructions that interact with references to garbage-collected objects are not executed while garbage collection is being performed, while instructions that do not interact with references to garbage-collected objects may be executed while garbage collection is being performed.
-
-
4. A method in a computer system for synchronizing a garbage collection process with the execution of each of a plurality of threads which may each enable and disable garbage collection, the method comprising the steps of:
-
receiving a request to initiate garbage collection; identifying threads that currently have garbage collection enabled; until all threads are identified or suspended, identifying threads that enable garbage collection, and suspending threads that disable garbage collection; when all threads are identified or suspended, performing garbage collection, and suspending identified threads that disable garbage collection during the performance of garbage collection; and when garbage collection is completed, unsuspending threads that a resuspended. - View Dependent Claims (5, 6, 7, 8, 9, 10)
-
-
11. A computer-readable medium whose contents synchronize a garbage collection process with the execution of a thread by performing the steps of:
-
receiving a request to initiate garbage collection; in response to the request, identifying threads that have enabled garbage collection more recently than they have disabled garbage collection; after the identifying step, until all threads are identified or suspended, identifying threads that enable garbage collection, and suspending threads that disable garbage collection; and when all threads are identified or suspended, performing garbage collection, and suspending identified threads that disable garbage collection during the performance of garbage collection. - View Dependent Claims (12, 13, 14, 15, 16, 17)
-
-
18. A method in a computer system for synchronizing an operation with the execution of each of a plurality of threads which may each enable and disable the operation, the method comprising the steps of:
-
receiving a request to initiate the operation; in response to the request, identifying threads that have enabled the operation more recently than they have disabled the operation; after the identifying step, until all threads are identified or suspended, identifying threads that enable the operation, and suspending threads that disable the operation; when all threads are identified or suspended, performing the operation, and suspending identified threads that disable the operation; and when the operation is completed, unsuspending threads that are suspended.
-
-
19. A computer-readable medium whose contents cause a computer system to synchronize an operation with the execution of each of a plurality of threads which may each enable and disable the operation by performing the steps of:
-
receiving a request to initiate the operation; in response to the request, identifying threads that have enabled the operation more recently than they have disabled the operation; after the identifying step, until all threads are identified or suspended, identifying threads that enable the operation, and suspending threads that disable the operation; and when all threads are identified or suspended, performing the operation, and suspending identified threads that disable the operation.
-
-
20. A method in a computer-based garbage collection system for determining when to initiate garbage collection in a computer program, the computer program having a plurality of thread, the method comprising:
-
receiving from each thread indications before it is about to execute GC-safe code and before it is about to execute non-GC-safe code; when receiving an indication that a thread is about to execute non-GC-safe code, suspending execution of the thread; and when each thread either has most-recently indicated that it is about to execute GC-safe code or is currently suspended, indicating that garbage collection can be initiated, so that threads that are executing GC-safe code are not suspended during garbage collection. - View Dependent Claims (21)
-
-
22. A method in a computer system for suspending the execution of a thread when the execution of the thread is in a stable state, the first thread having a stack containing one or more return addresses for pending calls that have been made but that have not returned, the method comprising the steps of:
in a second thread, selecting a return address from among the return addresses contained by the stack for pending calls; generating a copy of the selected return address; and in the stack, replacing the selected return address with a suspending program address, a suspending program being stored at the suspending program address, the suspending program containing steps for suspending the execution of the first thread and for jumping to the selected return address when the first thread is unsuspended. - View Dependent Claims (23, 24, 25, 26, 27)
-
28. A computer-readable medium whose contents cause a computer system to suspend the execution of a thread when the execution of the thread is in a stable state, the first thread having a stack containing one or more return addresses for pending calls that have been made by that have not returned, by performing the steps of:
in a second thread, selecting a return address from among the return addresses contained by the stack for pending calls; generating a copy of the selected return address; and in the stack, replacing the selected return address with a suspending program address, a suspending program being stored at the suspending program address, the suspending program containing steps for suspending the execution of the first thread and for jumping to the selected return address when the first thread is unsuspended. - View Dependent Claims (29, 30, 31, 32, 33)
-
34. An apparatus for synchronizing execution of a garbage collection program with the execution of threads in other programs, comprising:
-
one or more processors that use threads to execute programs including the garbage collection program, some of the programs other than the garbage collection program including code blocks that access object references; a synchronization agent for the thread executing the garbage collection program that permits the thread executing the garbage collection program to proceed to execute the garbage collection program when no other thread is executing in a code block that accesses object references; and a synchronization agent for the threads executing other programs that permits the threads executing other programs to proceed to execute code blocks that access object references only when the garbage collection program is not being executed.
-
-
35. A computer memory containing a garbage collection synchronization data structure for synchronizing a garbage collection process with the execution of each of a plurality of threads, the data structure comprising:
-
a condition of a first type that is set to a first state when garbage collection is initiated and that is set to a second state when the garbage collection completes; and for each of the plurality of threads, a condition of a second type that is set to a first state when the thread enters code accessing references to garbage-collected objects and that is set to a second state when the thread exits code accessing references to garbage-collected objects, such that each of the plurality of threads may wait for the condition of the first type to be set to the second state before entering code accessing references to garbage-collected objects, and such that the garbage collection process may wait for each of the plurality of conditions of the second type to be set to the second state after garbage collection is initiated and before garbage collection is performed, in order to synchronize the garbage collection process with the execution of the plurality of threads. - View Dependent Claims (36)
-
Specification