Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-10-19
2003-12-30
Maung, Zarni (Department: 2126)
Data processing: database and file management or data structures
Database design
Data structure types
C709S241000
Reexamination Certificate
active
06671707
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of computer software optimization. More particularly, the present invention relates to a method for practical concurrent copying garbage collection offering minimal thread blocking times.
BACKGROUND OF THE INVENTION
The popularization of the World Wide Web has exacerbated a problem for software developers trying to create software for networked consumer devices. While millions of people around the globe are surfing the Internet and browsing web pages with their computers, not all of those computers are the same. One person may be using a Macintosh, another a PC, and yet another user a UNIX machine. Hence software developers may find it desirable to design computer programs that could support multiple host architectures and could allow secure delivery of its software components.
The Java programming language and environment is designed to meet the challenges of application development in the context of heterogeneous, network-wide distributed environments. A program written in the Java Language compiles to a bytecode file that can run wherever a Java Platform is present. This portability is possible because at the core of a Java Platform is a Java Virtual Machine. Java bytecodes are designed to operate on a Java Virtual Machine (VM). The Java Virtual Machine is an abstract computing machine that has its own instruction set and uses various memory areas.
FIG. 1
is a block diagram of the elements in a client computer system
100
equipped to interpret and compile Java class files. The client computer system
100
includes computer hardware
110
controlled by an operating system
120
. The computer hardware further comprises of computer memory
112
and machine registers
114
. The system
100
also includes a Java VM implementation
130
for executing code contained in Java class files
160
.
In a networked environment, a user would first access a computer server through the network and download the desired Java class file(s)
160
into a client computer system
100
. After each Java class file has been verified, the interpreter
132
begins interpreting the Java bytecodes of the class file
160
and thus the code is executed.
Alternatively, a Java “Just-In-Time” (JIT) compiler
134
compiles the Java class file and generates compiled Java code
140
in the form of native processor code. The compiled Java code
140
is directly executed on the computer hardware
110
. In order to maintain the state of the Java VM
130
and make system calls, the compiled Java code
140
may make calls
150
into the Java VM
130
. Likewise, the Java VM
130
calls
150
compiled Java code
140
to cause it to execute on the computer hardware
110
.
Java was derived from the C++ programming language. Java includes some other important features from garbage collected languages (e.g., Smalltalk and LISP)—including automatic memory storage management. Garbage collected languages, such as Java, allow the system (garbage collector) to take over the burden of memory management from the programmer. When a program runs low on heap space, the garbage collector (GC) determines the set of objects that that program may still access. Objects in this set are known as live objects. The space used by objects that will no longer be accessed (“dead objects”) is freed by the garbage collector for future use. An object is defined as a collection of contiguous memory locations, lying in a single region that can be addressed and accessed via references.
A reference, also called a pointer, is the address of an object. Objects do not overlap and may be relocated independently of one another by the collector. In some cases, an object corresponds to a Java object. Multiple low-level objects may also be used to represent a single Java object. One example of this is a Java object with complex monitor locking happening. An object may contain slots, non-slot data, or both. A slot is a memory location that may contain a reference (pointer) to an object. A slot may also refer to no object, i.e., contain the null pointer. Memory locations can be categorized into slots and non-slot data correctly and unambiguously.
FIG. 2A
is a diagram of CPU activity in a multiprocessor system using a traditional garbage collection algorithm. The horizontal axis represents time while the vertical axis represents the useful application work. In traditional garbage collection algorithms, all of the threads have to stop. The garbage collector runs, performing garbage collection, and then the threads start up again. Hence there are large blocks of time when none of the CPUs is performing useful work and only one of the CPUs is doing the garbage collection work. The actual useful or mutator work is suspended. In
FIG. 2A
, the threads on CPU
0
through CPU
3
are suspended for time “Z” while the garbage collector is running on CPU
0
. The threads are blocked during garbage collection. Furthermore, threads can not be resumed until the garbage collection completes. The application threads resume execution when garbage collection stops. The thread stoppage may not appear dramatic in a system with a small number of processors. But in a multiprocessor computing system with eight or sixteen processors, the performance loss becomes an issue.
There are many algorithms for performing garbage collection. All the algorithms start with a set of roots that enumerate all objects in the heap that are directly reachable. A root is a slot whose referent object (if any), is considered reachable, along with all objects transitively reachable from the referent. The remaining objects in the heap are unreachable and can be reclaimed. One type of garbage collection is called conservative, or ambiguous roots, garbage collection. In conservative garbage collection, the garbage collector assumes all global variables, in registers or on the stack, are root slots even though some might hold integers, or floating point or string data. Another type of garbage collection is precise garbage collection. In precise garbage collection, the root set must unambiguously contain all reference values, or else memory errors will result. This is because precise garbage collection compacts the memory space by moving all the objects it finds to another memory region. The values in the root set must contain reference values since the garbage collector copies and moves the objects pointed to by references, and then updates the references correspondingly. If a value is mistakenly considered a reference value when it is not, a wrong piece of data will be moved, and/or a non-reference mistakenly modified, and program errors may occur.
Previous concurrent collection algorithms overlap some parts of collection with mutation, but still stop the world to “flip” (adjust, correct) all the mutator stacks and roots. A mutator thread performs application work. In a large server application, where there are perhaps hundreds of threads, thread stack flipping time can introduce unacceptable pauses.
SUMMARY OF THE INVENTION
A method for practical concurrent copying garbage collection offering minimal thread blocking times is described. The method comprises achieving dynamic consistency between objects in an old memory space and objects in a new memory space. Threads are allowed to progress during garbage collection and threads are flipped one at a time. No read barrier is required.
Other features and advantages of the present invention will be apparent from the accompanying drawings and from the detailed description that follows below.
REFERENCES:
patent: 4979810 (1990-12-01), Ogasawara
patent: 5088036 (1992-02-01), Ellis et al.
patent: 5367685 (1994-11-01), Gosling
patent: 5668999 (1997-09-01), Gosling
patent: 5687368 (1997-11-01), Nilsen
patent: 5857210 (1999-01-01), Tremblay et al.
patent: 5909579 (1999-06-01), Agesen et al.
patent: 5930807 (1999-07-01), Ebrahim et al.
patent: 6341293 (2002-01-01), Hennessey
Bacon, D.F.; Graham, S.L.; Sharp, O.J.; “Compiler Transformations for High-Performance Computing”, ACM Digital Li
Hudson Richard L.
Moss J. Eliot B.
Lam Peter
Maung Zarni
Opie George L.
LandOfFree
Method for practical concurrent copying garbage collection... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for practical concurrent copying garbage collection..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for practical concurrent copying garbage collection... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3173321