Thread suspension system and method using trapping...

Details Thread suspension system and method using trapping... Thread suspension system and method using trapping...

1999-02-22

2001-10-23

Dam, Tuan Q. (Department: 2122)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S152000, C707S793000, C709S241000, C710S260000, C711S132000

Reexamination Certificate

active

06308319

ABSTRACT:

BACKGROUND
1. Field of the Invention
The present invention relates to synchronization amongst execution sequences in computer programs and, in some applications thereof, to techniques for facilitating garbage collection in multi-threaded software environments.
2. Description of the Related Art
Traditionally, most programming languages have placed responsibility for dynamic allocation and deallocation of memory on the programmer. For example, in the C programming language, memory is allocated from the heap by the malloc procedure (or its variants). Given a pointer variable, p, execution of machine instructions corresponding to the statement p=malloc (size of (SomeStruct) ) causes pointer variable p to point to newly allocated storage for a memory object of size necessary for representing a SomeStruct data structure. After use, the memory object identified by pointer variable p can be deallocated, or freed, by calling free (p). Pascal and C++ languages provide analogous facilities for explicit allocation and deallocation of memory.
Unfortunately, dynamically allocated storage becomes unreachable when no chain of references (or pointers) can be traced from a “root set” of references (or pointers) to the storage. Memory objects that are no longer reachable, but have not been freed, are called garbage. Similarly, storage associated with a memory object can be deallocated while still referenced. In this case, a dangling reference has been created. In general, dynamic memory can be hard to manage correctly. In most programming languages, heap allocation is required for data structures that survive the procedure that created them. If these data structures are passed to further procedures or functions, it may be difficult or impossible for the programmer or compiler to determine the point at which it is safe to deallocate them.
Because of this difficulty, garbage collection, i.e., automatic reclamation of heap-allocated storage after its last use by a program, can be an attractive alternative model of dynamic memory management. Garbage collection is particularly attractive for languages such as the Java™ language (Java and all Java-based marks and logos are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries), Prolog, Lisp, Smalltalk, Scheme, Eiffel, Dylan, M L, Haskell, Miranda, etc. See generally, Jones & Lins,
Garbage Collection: Algorithms for Automatic Dynamic Memory Management
, pp. 1-41, Wiley (1996) for a discussion of garbage collection and of various classical algorithms for performing garbage collection.
In general, garbage collection methods can be described with reference to a garbage collection strategy implemented by a “collector” and its interaction or coordination with a useful computation—a “mutator”—that changes the state of heap-allocated storage. Many collector implementations, including some mark-sweep and copying collector implementations, are based on a stop-start approach, i.e., they involve suspending the mutator, collecting garbage, and resuming execution of the mutator after garbage collection. In such implementations, garbage collection is performed when the “root set” of pointers to dynamically allocated memory locations referenceable by the mutator is available to the garbage collector. A mutator in this state is called “consistent”, and one that is not is “inconsistent.”
Typically, a compiler for a garbage-collected language supports the collector by generating code that allocates objects, by describing storage locations that make up the root set, and by describing the layout of objects allocated from the heap. For efficiency, compilers typically generate code that uses registers and/or stack locations provided by a target processor architecture. As a result, execution of compiled code puts pointers in such registers or stack locations. Unfortunately, a mutator running such code is generally inconsistent, because the exact set of registers and/or stack locations containing pointers can change with every instruction. The overhead of exactly maintaining a root set description at each instruction tends to defeat the purpose of using registers and stack locations in the first place. Compilers therefore identify safe points in the code, places in the code where the compiler emits information describing which registers and stack locations contain pointers. When a mutator is suspended at a safe point it is consistent and hence garbage collection can proceed. See generally, Appel,
Modern Compiler Implementation in C: Basic Techniques
, pp. 291-297, Cambridge University Press (1998) for a description of compiler support for garbage collection.
Accordingly, a mechanism is desired by which a processor executing mutator code may suspend execution at a safe point defined therein to facilitate garbage collection. A desirable mechanism is computationally efficient and imposes minimal overhead on the mutator computation. Furthermore, it is desirable for the mechanism to operate in the context of multi-threaded mutator computation and to limit the delay between a request to start garbage collection and suspension of all threads of the mutator computation.
SUMMARY
Encoding an exception triggering value in storage referenced by an instruction in the delay slot of a delayed control transfer instruction coinciding with a safe point provides an efficient coordination mechanism for multi-threaded code. Because the mechanism(s) impose negligible overhead when not employed and can be engaged in response to an event (e.g., a start garbage collection event), safe points can be defined at call, return and/or backward branch points throughout mutator code to reduce the latency between the event and suspension of all threads. In contrast, mechanisms based on conditional execution of suspension code can impose substantial overhead. Furthermore, unlike mechanisms based on self-modifying code, complexities associated with maintaining memory model consistency are avoided. Though particularly advantageous for thread suspension to perform garbage collection at safe points, the techniques described herein are more generally applicable to program suspension at coordination points coinciding with calls, returns, branches or combinations thereof.
Illustrative embodiments in accordance with the present invention exploit a variety of exception triggering instructions and configurations of storage referenced thereby to suspend threads at safe points coinciding with call, return and/or backward branch sites. Some embodiments in accordance with the present invention include support for garbage collection. Some embodiments in accordance with the present invention include compiler techniques and implementations to generate suitable execution sequences of instructions.


REFERENCES:
patent: 5088036 (1992-02-01), Ellis et al.
patent: 5321834 (1994-06-01), Weiser et al.
patent: 5560003 (1996-09-01), Nilsen et al.
patent: 5920876 (1999-07-01), Ungar et al.
patent: 5953736 (1999-09-01), O'Connor et al.
patent: 6098089 (2000-08-01), O'Connor et al.
patent: 6101580 (2000-08-01), Agesen et al.
Cramer et al., “Compiling Java Just In Time,” IEEE Micro, vol. 17, Issue 3, pp. 36-43, May-Jun. 1997.*
Sansom et al., “Generation garbage collection for Haskell,” Proceedings of the conference on Functional programming languages and computer architecture, ACM-FPCA'93, Copenhagen Denmark, pp. 106-116, Jun. 9-11, 1993.*
Kuechlin et al., “On Multi-Threaded List-Processing and Garbage Collection,” Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing, Dec. 2-5, 1991, pp. 894-897.*
Jones & Lins, “Garbage Collection: Algorithms for Automatic Dynamic Memory Management”, Wiley (1996), pp. 1-41.
Appel, “Modern Compiler Implementation in C: Basic Techniques”, Cambridge University Press (1998), pp. 125-149 and pp. 291-297.
Weaver and Germond, The SPARC Architecture Manual Version 9, Prentice-Hall, Inc. (1994), pp. 237-238.

Affiliated with

Also associated with

Rating

Thread suspension system and method using trapping... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Thread suspension system and method using trapping..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Thread suspension system and method using trapping... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2608418