Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-11-05
2002-12-31
Breene, John (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C711S133000, C709S241000, C709S241000, C709S241000
Reexamination Certificate
active
06502109
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to memory management in distributed systems, and more particularly, to garbage collection in such systems.
BACKGROUND OF THE INVENTION
Within conventional computer systems, applications are executed by microprocessors which necessarily use memory locations for storing data and instructions. The contents of memory are changing over time such that, at different times, a memory location is said to be allocated, i.e., used, or unallocated, i.e., unused. More particularly, allocated memory locations are those locations that contain data or instructions that are referenced by other allocated memory locations during normal program execution.
For example, in modern object oriented computing, an “object” is data that share a particular attribute and occupy a contiguous region of memory. If all objects in a given computer system are permanent, there is no real concern with regard to memory management. That is, the memory space assigned to each object at the start of program execution never changes. However, in most conventional object oriented systems, objects have varying lifetimes that cannot be predicted in advance such that memory locations will transition between allocated and unallocated states. In order to promote the efficient use of memory, unallocated memory locations must be “reclaimed” so that they may be later allocated as required.
“Garbage” is a well-known term in the computer science arts which refers to memory storage locations which contain data that is no longer being used, e.g., in the execution of an application program. “Garbage collection” is another well-known term of art used in describing automatic techniques for identifying garbage and reclaiming those memory locations for future allocation. By automatically identifying accessible, and therefore potentially in-use data, e.g., objects, garbage collection routines shoulder the error-prone task of memory allocation and deallocation for the computer programmer. In freeing computer programmers from such low-level detail, garbage collection at a minimum can improve the quality of program code, increase programmer productivity, and reduce program development costs.
Of course, the many advantages associated with garbage collection are not “free” in terms of computing resources. Traditional garbage collection techniques such as “stop & copy”, “mark & sweep” and “reference counting” are described by, for example, Paul R. Wilson, “Uniprocessor Garbage Collection Techniques”, In
International Workshop on Memory Management
, Springer-Verlag, 1992, and Richard Jones et al.,
Garbage Collection Algorithms for Automatic Dynamic Memory Management
, John Wiley & Sons, 1996. The costs associated with such traditional garbage collection techniques manifest themselves, for example, as combinations of increased memory usage, run-time overheads on data accesses, and disruptive latencies in a program's execution. For example, stop & copy garbage collectors require a substantial amount of additional storage for making copies of live, i.e., allocated, data. This is due to the fact that such collectors periodically copy all reachable objects into a second memory space so the first memory space can be reclaimed in its entirety.
In order to address the inherent costs of garbage collection techniques as described above, the developers of garbage collection routines have incorporated concurrency in their designs whereby garbage collection occurs contemporaneously with application execution. More particularly, concurrent garbage collection techniques fall generally into one of two classes: (1) variations on mark & sweep collectors, see, for example, E. W. Dijkstra et al., “On-the-fly garbage collection: An exercise in cooperation”,
Communications of the ACM
, 21(11):966-975, November 1978, and G. L. Steele, Jr., “Multiprocessing compactifying garbage collection”,
Communications of the ACM
, 18(9):495-508, September 1975; and (2) incremental generational collectors, see, for example, H. G. Baker, “List processing in real time on a serial computer”,
Communications of the ACM
, 21(4):280-294, April 1978, A. W. Appel et al., “Real-time concurrent collection on stock multiprocessors”, In
Conference on Programming Language Design and Implementation
, pp. 11-20, June 1988, and S. Nettles et al., “Replication-based real-time garbage collection”, In
Conference on Programming Language Design and Implementation
, Association for Computing Machinery, June 1993.
As will be appreciated, the task of defining and implementing garbage collection routines as detailed above using traditional functional programming languages, e.g., C or C++, is ultimately left to the program developer. For example, the emerging use of so-called Java™ bytecodes, particularly in the form of applets, for executing programs via the well-known World Wide Web (“WWW”) is one area of tremendous programming growth and technical focus. As is well-known, Java is a popular programming language which enables users to create applications that can be used and executed across the well-known Internet without concerns about platform compatibility or network security. That is, Java is a platform-neutral language which means that programs developed using Java can execute on any computer system without the need for any modifications. Such platform independence stems from the use of a special format for compiled Java programs called “bytecodes” which are a set of instructions which look similar to conventional machine code, but are not specific to any one processor. Thus, a Java bytecode can be read and executed by any computer system that has a Java interpreter.
This is in contrast to compilers for non-Java programming languages, e.g., the well-known C programming language, which translate source programs into machine code or processor instructions which are specific to the processor or computer system. In such non-Java systems, if one wants to use the same program on another computer system, the source program must be found and provided as input to the compiler for the different system for recompilation. Thereafter, the recompiled program can be executed on the different computer system. In contrast, to execute a Java program, Java bytecodes are generated by a Java compiler which are executed by a Java interpreter, i.e., a bytecode interpreter, which in turn executes the Java program. Thus, placing the Java program in bytecode form enables the execution of such programs across any platform, operating system, or windowing system so long as the Java interpreter is available. As such, the capability of having a single binary file, i.e., Java bytecode file, executable across multiple platforms is a key attribute which is making Java bytecode, particularly in the form of applets, a common way of executing programs across the World Wide Web.
As will be appreciated, a class file (it will be noted that the terms “class file(s)” and “bytecode file(s)” are used interchangeably herein) is typically obtained by compiling a Java file and is a stream of bytes representing a single class in a form suitable for the well-known Java Virtual Machine (“JVM”). The Java Virtual Machine executes bytecodes and provides Java with certain fundamental capabilities such as object creation and garbage collection. In particular, Java, as a virtual machine based language, automatically handles all aspects of memory management thereby alleviating the necessity of the programmer having to write specific code modules to perform such tasks, e.g., garbage collection. With regard to garbage collection, because objects are automatically garbage-collected in Java, programmers do not have to (and are barred from) manually freeing memory allocated to an object when use of that object is no longer required by a process. More specifically, the JVM implements parallel garbage collection by executing a separate thread, silently and in the background, dedicated to cleaning up the Java environment of garbage. Essentially, the JVM implements this parallel garbage collect
Aravamudan Murali
Iyer Prakash
Breene John
Dinella Donald P.
Pham Khanh
LandOfFree
Distributed communications system having garbage collecting... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distributed communications system having garbage collecting..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed communications system having garbage collecting... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2982721