Thread synchronization in a garbage-collected system using execution barriers

• US 5,842,016 A
• Filed: 05/29/1997
• Issued: 11/24/1998
• Est. Priority Date: 05/29/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Peschel-Gallee, Frank, Dussud, Patrick, Toutonghi, Michael, Kukol, Peter
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US08/864,759
• Time in Patent Office: 544 Days
• Field of Search: 707/206, 395/676, 395/670, 711/165
• US Class Current: 718/106
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

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.

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.

5. The method of claim 4, further comprising the steps of:

when a thread enters a code segment that accesses pointers to garbage-collected objects, disabling garbage collection; and

when a thread enters a code segment that does not access pointers to garbage-collected objects, enabling garbage collection.

6. The method of claim 5 wherein selected threads are suspendable while they are executing code segments that access pointers to garbage-collected objects, the method further including the step of:

after the identifying step, until all threads are identified or suspended,

suspending any selected threads that last disabled garbage collection before the request was received and have not enabled garbage collection more recently.

7. The method of claim 6 wherein the suspending step suspends one selected thread when this thread executes an instruction occurring in the code being executed by the thread for permitting suspension.

8. The method of claim 6 wherein the suspending step suspends one selected thread when this thread returns from a called routine to a calling routine.

9. The method of claim 4, further comprising the steps of

detecting a shortage of memory;

and

generating the request to initiate garbage collection in response to the detecting step.

10. The method of claim 4, further comprising the step of generating the request to initiate garbage collection at a predetermined time.

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.

12. The computer-readable medium of claim 11 wherein the contents of the computer-readable medium further cause the computer system to perform the steps of:

when a thread enters a code segment that accesses pointers to garbage-collected objects, disabling garbage collection; and

when a thread enters a code segment that does not access pointers to garbage-collected objects, enabling garbage collection.

13. The computer-readable medium of claim 11 wherein selected threads are suspendable while they are executing code segments that access pointers to garbage-collected objects, and wherein the contents of the computer-readable medium further cause the computer system to perform the step of:

after the identifying step, until all threads are identified or suspended,

suspending any selected threads that last disabled garbage collection before the request was received and have not enabled garbage collection more recently.

14. The computer-readable medium of claim 13 wherein the suspending step suspends one selected thread when this thread executes an instruction occurring in the code being executed by the thread for permitting suspension.

15. The computer-readable medium of claim 13 wherein the suspending step suspends one selected thread when this thread returns from a called routine to a calling routine.

16. The computer-readable medium of claim 11 wherein the contents of the computer-readable medium further cause the computer system to perform the steps of:

detecting a shortage of memory; and

generating the request to initiate garbage collection in response to the detecting step.

17. The computer-readable medium of claim 11 wherein the contents of the computer-readable medium further cause the computer system to perform the step of generating the request to initiate garbage collection at a predetermined time.

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.

21. The method of claim 20 including the step of, when an indication that a thread is about to execute non-GC-safe code, suspending execution of the thread.

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.

23. The method of claim 22 wherein the selecting step selects as the selected return address the return address of the pending call most recently made.

24. The method of claim 22, further comprising the step of performing garbage collection in response to the suspending step.

25. The method of claim 22, further comprising the steps of:

unsuspending the first thread; and

in response to the unsuspending step, jumping to the selected return address under the control of the suspending program using the copy of the selected return address.

26. The method of claim 22, further comprising the steps of:

in the first thread,

after the step of replacing the selected return address, making an additional call; and

in the second thread,

while the additional call is pending, replacing in the stack the return address for the additional call with the suspending program address.

27. The method of claim 26, further comprising the step of:

in the second thread,

in conjunction with the step of replacing the return address of the additional call, restoring the selected return address to the stack in its original position.

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.

29. The computer-readable medium of claim 28 wherein the selecting step selects as the selected return address the return address of the pending call most recently made.

30. The computer-readable medium of claim 28 wherein the contents of the computer-readable medium further cause the computer system to perform the step of performing garbage collection in response to the suspending step.

31. The computer-readable medium of claim 28 wherein the contents of the computer-readable medium further cause the computer system to perform the steps of:

unsuspending the first thread; and

in response to the unsuspending step, jumping to the selected return address under the control of the suspending program using the copy of the selected return address.

32. The computer-readable medium of claim 28 wherein the contents of the computer-readable medium further cause the computer system to perform the steps of:

in the first thread,

after the step of replacing the selected return address, making an additional call; and

in the second thread,

while the additional call is pending, in the stack, replacing the return address for the additional call with the suspending program address.

33. The computer-readable medium of claim 32 wherein the contents of the computer-readable medium further cause the computer system to perform the step of:

in the second thread,

in conjunction with the step of replacing the return address of the additional call, restoring the selected return address to the stack in its original position.

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.

36. The computer memory of claim 35 wherein the conditions of the data structure are each events.