Computer system for detecting object updates Number:7,386,854 from the United States Patent and Trademark Office (PTO) owispatent A computer system is used to run one or more programs. It includes a memory having at least a first heap and a second heap in which objects are stored, with a first object being stored on the first heap. A write barrier is provided for detecting that said the first object has been updated by a program to include a first reference to a memory location in the second heap.<H detecting, Computer, Computer, system, 7386854.html, Patent, pto, 7386854

Title: Computer system for detecting object updates

Abstract: A computer system is used to run one or more programs. It includes a memory having at least a first heap and a second heap in which objects are stored, with a first object being stored on the first heap. A write barrier is provided for detecting that said the first object has been updated by a program to include a first reference to a memory location in the second heap.

Patent Number: 7,386,854 Issued on 06/10/2008 to Borman, et al.

Inventors: Borman; Samuel David (Southsea, GB), Slattery; Edward John (Winchester, GB)
Assignee: International Business Machines, Incorporation (Armonk, NY)

Appl. No.: 10/176,794

Filed: June 21, 2002

Foreign Application Priority Data


Jun 29, 2001 [GB]			0115965.6

Current U.S. Class: 719/310 ; 707/206

Field of Search: 719/316,310 707/206

References Cited [Referenced By]

U.S. Patent Documents


5900001	May 1999	Wolczko et al.
6049810	April 2000	Schwartz et al.
6249793	June 2001	Printezis et al.
6694346	February 2004	Aman et al.
6760815	July 2004	Traversat et al.
6763440	July 2004	Traversat et al.
6820101	November 2004	Wallman

Primary Examiner: Thomson; William
Assistant Examiner: Truong; LeChi
Attorney, Agent or Firm: McKinley; Martin J. Hoffman, Warnick & D'Alessandro, LLC

Claims

The invention claimed is:

1. A method of running one or more programs on a computer system including a memory in which objects are stored, said method comprising the steps of: providing a card table containing multiple cards, each card corresponding to a portion of said memory; and detecting with a write barrier that a first object has been updated by a program to include a reference to a second object, and marking the card that corresponds to the memory location of said second object, wherein the card table is adapted to enable a Java Virtual Machine to begin a second application after a first application has run to completion by resetting the Java Virtual Machine without restarting the Java Virtual Machine and without performing garbage collection; wherein said memory is divided into at least first and second heaps; wherein each card comprises first and second components, the first component being marked if an object in a corresponding memory location is updated to include a reference to another object, and the second component being marked if and object in a corresponding memory location is referenced from another object; wherein the method further includes performing a reset including: marking the second component of each card corresponding to a memory location referenced by the system stack or registers; detecting if the first component of any card corresponding to objects in the first heap is marked; responsive to so detecting, for determining if the second component of any such card is marked; and responsive to determining that no cards have both the first and second components marked, proceeding with the reset.

2. The method of claim 1, wherein the card is only marked if the first object is located in the first heap.

3. The method of claim 1, wherein the first component is only marked if the object being updated is in the first heap, and the object being referenced is in the second heap.

4. The method of claim 1, wherein the second component is only marked if the object being updated is in the first heap, and the object being referenced is also in the first heap.

5. The method of claim 4, wherein the second component is not marked if the object being updated and the object being referenced are in memory locations corresponding to a single card.

6. The method of claim 1, wherein if an object is moved from the second heap to the first heap, then any object references within the moved object are regarded as having been updated and the card table is marked accordingly.

7. The method of claim 1, wherein the card table is reset if a garbage collection is performed on the system.

8. The method of claim 1, wherein a reset can be performed on the system, involving the deletion of all objects in the second heap, and the first component of each card is restored to an unmarked value as part of such reset.

9. The method of claim 8, wherein the second component of each card is maintained through said reset, and only restored to an unmarked value if a garbage collection is performed on the system.

10. A computer program product comprising instructions on a medium in machine readable form which when loaded into a computer system for running one or more programs and including a memory in which objects are stored, will cause said system to perform the steps of: providing a card table containing multiple cards, each card corresponding to a portion of said memory; and detecting with a write barrier that a first object has been updated by a program to include a reference to a second object, and marking the card that corresponds to the memory location of said second object, wherein the card table is adapted to enable a Java Virtual Machine to begin a second application after a first application has run to completion by resetting the Java Virtual Machine without restating the Java Virtual Machine and without performing garbage collection; said memory is divided into at least first and second heaps; wherein each card comprises first and second components, the first component being marked if an object in a corresponding memory location is updated to include a reference to another object, and the second component being marked if an object in a corresponding memory location is referenced from another object; wherein a reset can be performed on the system, involving the deletion of all objects in the second heap, and the first component of each card is restored to an unmarked value as part of such reset; wherein the second component of each card is maintained through said resent, and only restored to an unmarked value if a garbage collection is performed on the system; wherein the instructions further cause the system to perform a reset by the step of: marking the second component of each card corresponding to a memory location referenced by the system stack or registers; detecting if the first component of any card corresponding to objects in the first heap is marked; responsive to so detecting, determining if the second component of any such card is marked; and responsive to determining that no cards have both the first and second components marked, processing with the reset.

11. The computer program product of claim 10, wherein the card is only marked if the first object is located in the first heap.

12. The computer program product of claim 10, wherein the first component is only marked if the object being updated is in the first heap, and the object being referenced is in the second heap.

13. The computer program product of claim 10, wherein the second component is only marked if the object being updated is in the first heap, and the object being referenced is also in the first heap.

14. The computer program product of claim 13, wherein the second component is not marked if the object being updated and the object being referenced are in memory locations corresponding to a single card.

15. The computer program product of claim 10, wherein if an object is moved from the second heap to the first heap, then any object references within the moved object are regarded as having been updated and the card table is marked accordingly.

16. The computer program product of claim 10, wherein the card table is reset if a garbage collection is performed on the system.

Description

FIELD OF THE INVENTION

The present invention relates to a computer system for running one or more programs and including a memory for storing objects, and in particular to the processing when one object updates a reference to another.

BACKGROUND OF THE INVENTION

Programs written in the Java programming language (Java is a trademark of Sun Microsystems Inc) are generally run in a virtual machine environment, rather than directly on hardware. Thus a Java program is typically compiled into byte-code form, and then interpreted by a Java virtual machine (VM) into hardware commands for the platform on which the Java VM is executing. The Java VM itself is an application running on the underlying operating system. An important advantage of this approach is that Java applications can then run on a very wide range of platforms.

Java is an object-oriented language. Thus a Java program is formed from a set of class files having methods that represent sequences of instructions. A hierarchy of classes can be defined, with each class inheriting properties (including methods) from those classes which are above it in the hierarchy. For any given class in the hierarchy, its descendants (i.e. below it) are called subclasses, whilst its ancestors (i.e. above it) are called superclasses. At run-time objects are created as instantiations of these class files, and indeed the class files themselves are effectively loaded as objects One Java object can call a method in another Java object. In recent years the Java environment has become very popular, and is described in many books, for example "Exploring Java" by Niemeyer and Peck, O'Reilly & Associates, 1996, USA, and "The Java Virtual Machine Specification" by Lindholm and Yellin, Addison-Wedley, 1997, USA.

The standard Java VM architecture is generally designed to run only a single application, although this can be multi-threaded. In a server environment used for database transactions and such-like, each transaction is typically performed as a separate application, rather than as different threads within an application. This is to ensure that every transaction starts with the Java VM in a clean state. In other words, a new Java VM is started for each transaction (i.e. for each new Java application). Unfortunately however this results in an initial delay in running the application (the reasons for this will be described in more detail later). The overhead due to this frequent starting and then stopping a Java VM as successive transactions are processed is significant, and seriously degrades the scalability of Java server solutions.

Various attempts have been made to mitigate this problem. EP-962860-A describes a process whereby one Java VM can fork into a parent and a child process, this being quicker than setting up a fresh Java VM. The ability to run multiple processes in a Java-like system, thereby reducing overhead per application, is described in "Processes in KaffeOS: Isolation, Resource Management, and Sharing in Java" by G back, W Hsieh, and J

Another approach is described in "Oracle JServer Scalability and Performance" by Jeremy Litzt, July 1999. The JServer product available from Oracle Corporation, USA, supports the concept of multiple sessions (a session effectively representing a transaction or application), each session appears to its JServer session. Each individual session appears to its JServer client to be a dedicated conventional Java VM.

U.S. patent application Ser. No. 09/304160, filed Apr. 30, 1999 ("A long Running Reusable Extendible Virtual Machine"), assigned to IBM Corporation (IBM docket YOR9-1999-0170), discloses a virtual machine having two types of heap, a private heap and a shared heap. The former is intended primarily for storing application classes, whilst the latter is intended primarily for storing system classes and, as its name implies, is accessible to multiple VMs. A related idea is described in "Building a Java virtual machine for server applications: the JVM on OS/390" by Dillenberger et al, IBM Systems Journal, Vol 39/1, January 2000.

The above documents are focused primarily on the ability to easily run multiple Java VMs in parallel. A different (and potentially complementary) approach is based on a serial rather than parallel configuration. Thus it is desirable to run repeated transactions (i.e. applications) on the same Java VM, since this could avoid having to reload all the system classes at the start of each application. However, one difficulty with this is that each application expects to run on a fresh, clean, Java VM. There is a danger with serial re-use of a Java VM that the state left from a previous transaction somehow influences the outcome of a new transaction. This unpredictability is unacceptable in most circumstances.

U.S. provisional application No. 60/208268 filed May 31, 2000 in the name of IBM Corporation (IBM docket number YOR9-2000-0359) discloses the idea of having two heaps in a JVM. One of these is a transient heap, which is used to store transaction objects that will not persist into the next transaction, whilst a second, persistent, heap is used for storing objects, such as system objects, that will persist. This approach provides the basis for an efficient reset mechanism by deleting the transient heap.

This concept is developed in GB application 0027045.4, filed 6 Nov. 2000 in the name of IBM Corporation (IBM docket number GB9-2000-0101), which focuses particularly on the deletion of the transient heap. One difficulty that arises at reset is how to handle pointers from objects in the persistent heap to objects in the transient heap, since following reset and deletion of the transient heap, these pointers will no longer be valid. The general policy in the above application is that if such cross-heap pointers exist, the Java VM is no longer resettable, and so will normally have to be terminated.

However, it is possible that the objects in the persistent heap from which the cross-heap pointers originate are no longer live, but rather are waiting to be garbage collected (the process of garbage collection in Java is described in more detail below). It is clearly undesirable to terminate the Java VM as unresettable simply on the basis of a cross-heap pointer that could possibly be deleted. Therefore, as described in the above application, if any cross-heap pointers are found at reset, a garbage collection operation is performed, which will remove any objects that are no longer live. In many cases this will eliminate all the objects that have the cross-heap pointers, thereby allowing reset to proceed.

Although the approach in the GB 0027045.4 application is effective, it suffers from the problem that garbage collection is a relatively time-consuming operation. Thus if any cross-heap pointers are found, there is a significant wait while the garbage collection is performed in order to determine whether or not the Java VM is safe to reset. This wait is unfortunate, given that one of the main motivations for being able to reset the Java VM in the first place was to overcome the start-up delay when having to launching a new Java VM for each transaction.

SUMMARY OF THE INVENTION

Accordingly, the invention provides a computer system for running one or more programs and including a memory in which objects are stored, said system further including:

a card table containing multiple cards, each card corresponding to a portion of said memory; and

a write barrier for detecting that a first object has been updated by a program to include a reference to a second object, and for marking the card that corresponds to the memory location of said second object.

In broad terms each card is simply a small region of memory, which corresponds to a much larger region of memory. The card is then marked if an object in its corresponding larger region of memory is referenced. This provides an effective record of memory usage, a form of memory map, to track objects which may potentially be live, because they are referenced by other objects. Scanning the card table can therefore provide a short cut to identifying live objects, compared to a full garbage collection.

It will be appreciated that there are many possibilities as regards the detailed structure of the card table, and this will typically depend on performance aspects. For example, if cards in the card table are contiguous with an order that matches the corresponding memory locations, access speed to the card table will be much greater since a card can be located in the card table directly from a given memory location. However, other configurations of the card table may also be adopted.

In the preferred embodiment, the computer memory is divided into at least first and second heaps, and a reset can be performed on the system, involving the deletion of all objects in the second heap. At such reset, any pointers from the first heap into the second heap (cross-heap pointers) become invalid, or put another way, the presence of any such cross-heap pointer prevents a valid reset operation.

Note that the first and second heaps do not need to be physically separate, but may for example be one heap logically partitioned into two or more heaps. In addition, there may be large number of logically separate heaps, and also a variety of different heap models, such as providing local heaps for threads. In this context a cross-heap pointer should simply be interpreted as a pointer from a first region of memory that is not being reset into a second region of memory that is being reset.

The main objective of the present invention is to allow a quick determination at reset of whether a cross-heap pointer is still live, without having to perform a full garbage collection. To this end, each card in the card table comprises first and second components. The first component is marked if an object in a corresponding memory location is updated to include a reference to another object. In the preferred embodiment, this first component is only marked if the object being updated is in the first heap, and the object being referenced is in the second heap. This approach therefore flags all cross-heap pointers. An alternative approach is simply to mark the cards for all updated objects (or optionally just those in the middleware heap) irrespective of the location of the objects they reference. This effectively defers checking whether the reference is a cross-heap pointer until the reset itself, which may be desirable for performance reasons.

Further in the preferred embodiment, the second component of the card table is marked if an object in a corresponding memory location is referenced from another object, providing the object being updated (i.e. the referencing object) is in the first heap (this is because references from the second heap should be deletable at reset, and so cannot make an object live). Preferably the second component of the card is only marked if the object being referenced is in the first heap. Alternatively it may be simpler to drop this requirement (so no testing of which heap contains the referenced object); in this case the marked cards corresponding to the second heap would simply be ignored at reset.

Note that in the preferred embodiment, the second component of a card is not marked if the object being updated and the object being referenced are in memory locations corresponding to a single card. This is because there must be some other reference to the card from outside for any object within it to be potentially live.

At reset itself, the second component of each card corresponding to a memory location referenced by the system stack or registers is marked. These locations are termed the roots, and represent live objects. Any other objects which are live must be referenced directly or directly from one of the roots. Thus by marking the roots, and also by using the write barrier to mark referenced objects, the second component of cards corresponding to all potentially live objects should have been marked.

This means that at reset the first component of each card corresponding to objects in the first heap is checked to see if it is marked, in other words, to see if an object in the corresponding portion of memory contains a cross-heap pointer. If so, it is determined if the second component of any such card is marked. If not, it is known that any objects in the portion of memory corresponding to the card cannot be live, and therefore any cross-heap pointer therein can be ignored. On the other hand, if the second component is marked, then the object containing the cross-heap pointer may still potentially be live, and so reset cannot proceed. In the preferred embodiment at this stage, a full garbage collection is performed, to allow a more accurate determination of which objects are live (the use of the card table conservatively indicates cards as live, in that any live object will imply its corresponding card is live, but the converse is not necessarily true, i.e. a live card does not mean that all, or indeed any, of its corresponding objects are actually live). If the garbage collection shows that the objects containing the cross-heap pointers are in fact not live, then the reset can proceed after all.

At reset, the first component of each card is restored to its initial (zero) value as part of such reset, in other words to its unmarked state. On the other hand, the second component of each card persists through reset, to mirror the fact that object references within the first heap can likewise persist through reset. The second component is only reset itself if a garbage collection is performed on the system, whereupon it is known exactly which objects are live, and the second component in the corresponding cards can therefore be marked accordingly. (Note that in this context reset of the second component is not back to its initial, completely unmarked state, but rather back to a state in which it is known to be fully current).

The invention further provides a method for running one or more programs on a computer system including a memory in which objects are stored, said method including the steps of:

providing a card table containing multiple cards, each card corresponding to a portion of said memory; and

detecting with a write barrier that a first object has been updated by a program to include a reference to a second object, and marking the card that corresponds to the memory location of said second object.

The invention further provides a computer program product comprising instructions encoded on a computer readable medium for causing a computer to perform this method. A suitable computer readable medium may be a DVD or computer disk, or the instructions may be encoded in a signal transmitted over a network from a server. It will be appreciated that the method and computer program product of the invention will benefit from the same preferred features as the system of the invention.

BRIEF DESCRIPTION OF THE DRAWINGS

A preferred embodiment of the invention will now be described in detail by way of example only with reference to the following drawings:

FIG. 1 shows a schematic diagram of a computer system supporting a Java Virtual Machine (VM);

FIG. 2 is a schematic diagram of the internal structure of the Java VM;

FIG. 3 is a flowchart depicting the steps required to load a class and prepare it for use;

FIG. 4 is a flowchart depicting at a high level the serial reuse of a Java VM;

FIG. 5 is a schematic diagram showing the heap and its associated components in more detail;

FIGS. 6A and 6B form a flowchart illustrating garbage collection;

FIG. 7 is a diagram of a lookup table used to determine if a reference is in a heap;

FIG. 8 is a diagram of a modified lookup structure for the same purpose as FIG. 7, but for use in a system with much larger memory;

FIGS. 9A and 9B form a flowchart illustrating the operations taken to delete the transient heap during Java VM reset;

FIG. 10 is a diagram illustrating some objects in memory and the corresponding portion of a card table;

FIG. 11 is a flow chart depicting a write barrier for writing to the card table; and

FIG. 12 is a diagram illustrating the structure of the card table.

DETAILED DESCRIPTION

FIG. 1 illustrates a computer system 10 including a (micro)processor 20 which is used to run software loaded into memory 60. The software can be loaded into the memory by various means (not shown), for example from a removable storage device such as a floppy disk, CD ROM, or DVD, or over a network such as a local area network (LAN), telephone/modem connection, or wireless link, typically via a hard disk drive (also not shown). Computer system runs an operating system (OS) 30, on top of which is provided a Java virtual machine (VM) 40. The Java VM looks like an application to the (native) OS 30, but in fact functions itself as a virtual operating system, supporting Java application 50. A Java application may include multiple threads, illustrated by threads T1 and T2 71, 72.

System 10 also supports middleware subsystem 45, for example a transaction processing environment such as CICS, available from IBM Corporation (CICS is a trademark of IBM Corporation). The middleware subsystem runs as an application or environment on operating system 30, and initiates the Java VM 40. The middleware also includes Java programming which acts to cause transactions as Java applications 50 to run on top of the Java VM 40. In accordance with the present invention, and as will be described in more detail below, the middleware can cause successive transactions to run on the same Java VM. In a typical server environment, multiple Java VMs may be running on computer system 10, in one or more middleware environments.

It will be appreciated that computer system 10 can be a standard personal computer or workstation, network computer, minicomputer, mainframe, or any other suitable computing device, and will typically include many other components (not shown) such as display screen, keyboard, sound card, network adapter card, etc which are not directly relevant to an understanding of the present invention. Note that computer system 10 may also be an embedded system, such as a set top box, handheld device, or any other hardware device including a processor 20 and control software 30, 40.

FIG. 2 shows the structure of Java VM 40 in more detail (omitting some components which are not directly pertinent to an understanding of the present invention). The fundamental unit of a Java program is the class, and thus in order to run any application the Java VM must first load the classes forming and required by that application. For this purpose the Java VM includes a hierarchy of class loaders 110, which conventionally includes three particular class loaders, named Application 120, Extension 125, and Primordial 130. An application can add additional class loaders to the Java VM (a class loader is itself effectively a Java program). In the preferred embodiment of the present invention, a fourth class loader is also supported, Middleware 124.

For each class included within or referenced by a program, the Java VM effectively walks up the class loader hierarchy, going first to the Application class loader, then the Middleware loader, then the Extension class loader, and finally to the Primordial class loader, to see if any class loader has previously loaded the class. If the response from all of the class loaders is negative, then the JVM walks back down the hierarchy, with the Primordial class loader first attempting to locate the class, by searching in the locations specified in its class path definition. If this is unsuccessful, the Extension class loader then makes a similar attempt, if this fails the Middleware class loader tries. Finally, if this fails the Application class loader tries to load the class from one of the locations specified in its class path (if this fails, or if there is some other problem such as a security violation, the system returns an error). It will be appreciated that a different class path can be defined for each class loader.

The Java VM further includes a component CL 204, which also represents a class loader unit, but at a lower level. In other words, this is the component that actually interacts with the operating system to perform the class loading on behalf of the different (Java) class loaders 110.

Also present in the Java VM is a heap 140, which is used for storage of objects 145 (FIG. 2 shows the heap 140 only at a high level; see FIG. 5 below for more details). Each loaded class represents an object, and therefore can be found on the heap. In Java a class effectively defines a type of object, and this is then instantiated one or more times in order to utilise the object. Each such instance is itself an object which can be found in heap 140. Thus the objects 145 shown in the heap in FIG. 2 may represent class objects or other object instances. (Note that strictly the class loaders as objects are also stored on heap 140, although for the sake of clarity they are shown separately in FIG. 2). Although heap 140 is shared between all threads, typically for reasons of operational efficiency, certain portions of heap 140 can be assigned to individual threads, effectively as a small region of local storage, which can be used in a similar fashion to a cache for that thread.

The Java VM also includes a class storage area 160, which is used for storing information relating to the class files stored as objects in the heap 140. This area includes the method code region 164 for storing byte code for implementing application logic such as class method calls, and a constant pool 162 for storing strings and other constants associated with a class. The class storage area also includes a field data region 170 for sharing static variables (static in this case implies belonging to the class rather than individual instances of the class, or, to put this another way, shared between all instances of a class), and an area 168 for storing static initialisation methods and other specialised methods (separate from the main method code 164). The class storage area further includes a method block area 172, which is used to store information relating to the code, such as invokers, and a pointer to the code, which may for example be in method code area 164, in JIT code area 185 (as described in more detail below), or loaded as native code such as C, for example as a dynamic link library (DLL).

Classes stored as objects 145 in the heap 140 contain a reference to their associated data such as method byte code etc in class storage area 160. They also contain a reference to the class loader which loaded them into the heap, plus other fields such as a flag (not shown) to indicate whether or not they have been initialised.

FIG. 2 further shows a monitor pool 142. This contains a set of locks (monitors) that are used to control access to an object by different threads. Thus when a thread requires exclusive access to an object, it first obtains ownership of its corresponding monitor. Each monitor can maintain a queue of threads waiting for access to any particular object. Hash table 141 is used to map from an object in the heap to its associated monitor.

Another component of the Java VM is the interpreter 156, which is responsible for reading in Java byte code from loaded classes, and converting this into machine instructions for the relevant platform. From the perspective of a Java application, the interpreter effectively simulates the operation of a processor for the virtual machine.

Also included within the Java VM are class loader cache 180 and garbage collection (GC) unit 175. The former is effectively a table used to allow a class loader to trace those classes which it initially loaded into the Java VM. The class loader cache therefore allows each class loader to check whether it has loaded a particular class--part of the operation of walking the class loader hierarchy described above. Note also that it is part of the overall security policy of the Java VM that classes will typically have different levels of permission within the system based on the identity of the class loader by which they were originally loaded.

Garbage collection (GC) facility 175 is used to delete objects from heap 140 when those objects are no longer required. Thus in the Java programming language, applications do not need to specifically request or release memory, rather this is controlled by the Java VM. Therefore, when Java application 50 creates an object 145, the Java VM secures the requisite memory resource. Then, when Java application 50 finishes using object 145, the Java VM can delete the object to free up this memory resource. This latter process is known as garbage collection, and is generally performed by briefly interrupting all threads 71, 72, and scanning the heap 140 for objects which are no longer referenced, and hence can be deleted. The garbage collection of the preferred embodiment is described in more detail below.

The Java VM further includes a just-in-time (JIT) compiler 190. This forms machine code to run directly on the native platform by a compilation process from the class files. The machine code is created typically when the application program is started up or when some other usage criterion is met, and is then stored for future use. This improves run-time performance by avoiding the need for this code to be interpreted later by the interpreter 156.

Another component of the Java VM is the stack area 195, which is used for storing the stacks 196, 198 associated with the execution of different threads on the Java VM. Note that because the system libraries and indeed parts of the Java VM itself are written in Java, and these frequently use multi-threading, the Java VM may be supporting multiple threads even if the user application 50 running on top of the Java VM contains only a single thread itself.

It will be appreciated of course that FIG. 2 is simplified, and essentially shows only those components pertinent to an understanding of the present invention. Thus for example the heap may contain thousands of Java objects in order to run Java application 50, and the Java VM contains many other components (not shown) such as diagnostic facilities, etc.

FIG. 3 is a flowchart illustrating the operations conventionally performed to load a class in order to run a Java application. The first operation is loading (step 310) in which the various class loaders try to retrieve and load a particular class. The next operation is linking, which comprises three separate steps. The first of these is verification (step 320), which essentially checks that the code represents valid Java programming, for example that each instruction has a valid operational code, and that each branch instruction goes to the beginning of another instruction (rather than the middle of an instruction). This is followed by preparation (step 330) which amongst other things creates the static fields for a class. The linking process is completed by the step of resolution, in which a symbolic reference to another class is typically replaced by a direct reference (step 340).

At resolution the Java VM may also try to load additional classes associated with the current class. For example, if the current class calls a method in a second class then the second class may be loaded now. Likewise, if the current class inherits from a superclass, then the superclass may also be loaded now. This can then be pursued recursively; in other words, if the second class calls methods in further classes, or has one or more superclasses, these too may now be loaded. Note that it is up to the Java VM implementation how many classes are loaded at this stage, as opposed to waiting until such classes are actually needed before loading them.

The final step in FIG. 3 is the initialisation of a loaded class (step 350), which represents calling the static initialisation method (or methods) of the class. According to the formal Java VM specification, this initialisation must be performed once and only once before the first active use of a class, and includes things such as setting static (class) variables to their initial values (see the above-mentioned book by Lindholm and Yellin for a definition of "first active use"). Note that initialisation of an object also requires initialisation of its superclasses, and so this may involve recursion up a superclass tree in a similar manner to that described for resolution. The initialisation flag in a class object 145 is set as part of the initialisation process, thereby ensuring that the class initialisation is not subsequently re-run.

The end result of the processing of FIG. 3 is that a class has been loaded into a consistent and predictable state, and is now available to interact with other classes. In fact, typically at start up of a Java program and its concomitant Java VM, some 1000 objects are loaded prior to actual running of the Java program itself, these being created from many different classes. This gives some idea of the initial delay and overhead involved in beginning a Java application.

As mentioned above, the problems caused by this initial delay can be greatly reduced by serial reuse of a Java VM, thereby avoiding the need to reload system classes and so on. FIG. 4 provides a high-level flowchart of a preferred method for achieving such serial reuse. The method commences with the start of the middleware subsystem 45, which in turn uses the Java Native Interface (JNI) to perform a Create JVM operation (step 410). Next an application or transaction to run on the Java VM is loaded by the Application class loader 120. The middleware includes Java routines to provide various services to the application, and these are also loaded at this point, by the Middleware class loader 124.

The application can now be run (step 420), and in due course will finally terminate. At this point, instead of terminating the Java VM as well as the application, the middleware subsystem makes a Reset JVM call to the Java VM (step 430). The middleware classes may optionally include a tidy-up method and/or a reinitialize method. Both of these are static methods. The Java VM responds to the Reset JVM by calling the tidy-up method of the middleware classes (step 440). The purpose of this is to allow the middleware to leave the Java VM in a tidy state, for example removing resources and closing files that are no longer required, and deleting references to the application objects. In particular, all those middleware classes which have been used since the previous Java VM reset (or since the Java VM was created if no resets have occurred) have their tidy-up method called, assuming of course that they have a tidy-up method (there is no requirement for them to have such a tidy-up method).

The tidy-up method may be similar to the finalise method of a class, which is a standard Java facility to allow an object to perform some close-down operation. However, there is an important difference in that tidy-up is a static method. This means that contrary to the finalise method it applies to the class rather than any particular object instance, and so will be called even if there are no current object instances for that class. In addition the timing of the tidy-up method is different from finalise, in that the former is called in response to a predetermined command to reset the Java VM. In contrast, in accordance with the Java VM specification, the finalise method is only triggered by a garbage collection. More particularly, if an object with a finalizer method is found to be unreachable during a garbage collection (i.e. it is no longer effectively active) then it is queued to the finalizer thread, which then runs the finalizer method after the garbage collection is completed. Note that the finalizer method of an object may never be called, if an application finishes and the Java VM shuts down without the system needing to perform a garbage collection.

Once the tidy-up has been completed, a refresh heap operation is performed (step 445). As will be described in more detail below, this deletes those portions of the heap that relate to the application or transaction that has just been completed, generally analogous to a garbage collection cycle. Note that many of the objects deleted here might not have been removable prior to the tidy-up method, since they could still have been referenced by the middleware classes.

At this point, the middleware subsystem makes a determination of whether or not there is another application to run on the Java VM (step 450). If not, the middleware subsystem uses the JNI to make a Destroy JVM call (step 460) which terminates the Java VM, thereby ending the method of FIG. 4. If on the other hand there is another application to run, then this new application is started by the middleware. The system responds to this new application by calling in due course the reinitialisation method in each of the middleware classes to be reused (step 455). The purpose of this is to allow the middleware classes to perform certain operations which they might do at initialisation, thereby sidestepping the restriction that the Java VM specification prevents the initialisation method itself being called more than once. As a simple example, the reinitialisation may be used to reset a clock or a counter. As shown in FIG. 4, the system is now in a position to loop round and run another application (step 420).

It is generally expected that the reinitialisation method will be similar in function to the initialisation method, but there may well be some differences. For example, it may be desired to reset static variables which were initialised implicitly. Another possibility is to allow some state or resources to persist between applications; for example, if a class always outputs to one particular log file which is set up by the initialisation method, it may be more efficient to keep this open in between successive Java VMs, transparent to the application.

It should be noted that whilst FIG. 4 indicates the distinct logical steps performed by the method of the invention, in practice these steps are not all independent. For example, calling the tidy-up methods (step 440) is part of the overall Reset JVM operation (step 430). Likewise, calling the reinitialisation methods (step 455) is effectively part of the start-up processing of running the new application (step 420). Thus reinitialisation is performed prior to first active use of a class, and this may occur at any stage of a program. Therefore class reinitialisation (like conventional initialisation) is not necessarily completed at start-up of the program, but rather can be regarded as potentially an ongoing process throughout the running of a program.

It will also be appreciated that there is some flexibility with regard to the ordering of the steps shown in FIG. 4. In particular, the decision of whether or not there is to be another application (step 450) could be performed earlier, such as prior to the refresh heap step, the tidyup step, and/or the Reset JVM step. In the latter case, which corresponds to immediately after the first application has concluded (i.e. straight after step 420), the alternative outcomes would be to destroy the Java VM (step 460) if there were no further applications, or else to reset the JVM, tidy up, refresh the heap, and reinitialise (steps 430, 440, 445, and 455) if there were further applications. If instead the decision step 450 is intermediate these above two extreme positions, the logic flow can be determined accordingly.

It should be noted that in the preferred embodiment, the ability to reset the Java VM, and to have tidyup and reinitialise methods, is only available for middleware classes (i.e. those loaded by the middleware class loader). This is to allow the middleware classes to be re-used by successive applications or transactions, for which they can perform various services. The basis for this approach is that typically the middleware is a relatively sophisticated and trusted application, and so can be allowed to take responsibility for proper implementation of the tidy-up and reinitialise methods. On the other hand, individual transactions are not treated as reliable.

Note also that the system classes themselves do not have tidyup or reinitialisation methods, despite persisting across a Java VM reset. Rather, if the middleware makes any change to a system class, then the middleware itself is expected to take the necessary action (if any) for a reset with respect to the system class as part of the middleware's own tidyup operation.

An important part of the Reset JVM/tidyup operation (steps 430 and 440) in the preferred embodiment is to make sure that the Java VM is in a state which is amenable to being tidied up. If this is the case, the Java VM is regarded as being clean, if not, it is regarded as being dirty or unresettable.

Considering this in more detail, if the application has performed certain operations, then it will not be possible for the middleware classes to be certain that their tidy-up and reinitialise methods will fully reset the system to a fresh state. With such a contaminated Java VM, the system still calls the tidy-up methods of the class objects as per normal (step 440), but the return code back to the middleware associated with the reset JVM operation (step 430) effectively indicates failure. The expectation here is that the Java VM would actually be terminated by the middleware subsystem at this point, as it is no longer in a predictable condition.

One important situation which would prevent the Java VM from being able to properly reset is where the application has performed certain operations directly such as making security or environment changes, loading native code, or performing Abstract Windowing Toolkit (AWT) operations. These affect the state of the Java VM or the underlying computer system and cannot be reliably tidied up by the middleware, for the simple reason that the middleware does not necessarily know about them. Such changes could then persist through a Reset JVM call, and contaminate the Java VM for any future applications. In contrast, if an application performs such operations through a middleware call, then this does not cause any problems, because the middleware now does know about the situation and so can perform whatever tidyup measures are required.

The Java VM thus monitors for operations that may prevent proper reset, including whether they have been performed by an application or middleware. This is determined by the Java VM keeping track of its context, which is set to application context for an application class, and to middleware context for a middleware class, whilst a primordial or extension class has no impact on the existing context of application or middleware. In particular, context can be determined based on the type of class which contains the method that is currently being performed, whilst the type of class is determined from its original class loader.

As previously mentioned, the list of problematic operations given above only causes difficulty when performed in an application context, since in a middleware context it is possible for them to be reset by the appropriate tidy-up routines of the relevant middleware classes.

Referring now to FIG. 5, in the preferred embodiment the heap 140 is split into three components. Objects in one component can reference objects in another component. At the bottom (logically) of heap 140 is middleware section 510, and at the top of the heap is transient section 520. The data in these two heaps grows towards each other, thus transient heap grows in the direction of arrow 521, and middleware heap in the direction of arrow 511. The middleware heap is defined by boundary 512, and the transient heap by boundary 522, with unassigned space 515 between them. It should be appreciated that boundaries 512 and 522 represent the maximum size currently assigned to the two heaps, rather than their current fill levels--these are instead shown by dashed lines 513 and 523. In other words, as the middleware heap fills up, the fill level 513 will approach towards middleware heap boundary 512; likewise as the transient heap fills up, the fill level 523 will approach towards transient heap boundary 522.

Finally, and separate from the transient heap and middleware heap, is system heap 550. Note that the combined transient and middleware heaps, together with intervening unassigned space, are allocated from a single physically contiguous block of memory 560. In contrast, the system heap 550 may be formed from multiple non-contiguous regions of memory.

In one preferred embodiment, memory 560 comprises 64 MBytes, and the initial size of the middleware and transient heaps is 0.5 Mbyte each. Thus it can be seen that initially the unassigned region 515 dominates, although the transient and middleware heaps are allowed to expand into this space (details of the expansion policy are provided in the above mentioned GB 0027045.4 application, although these have no direct relevance to the present invention). However, the values quoted are exemplary only, and suitable values will vary widely according to machine architecture and size, and also the type of application.

Heap control block 530 is used for storing various information about the heap, such as the location of the heap within memory, and the limits of the transient and middleware sections as defined by limits 512 and 522. Free chain block 532 is used for listing available storage locations within the middleware and transient sections (there is actually one free chain block for each section). Thus although the middleware and transient heaps start to fill sequentially, the likely result of a garbage collection cycle is that space may become available within a previously occupied region. Typically therefore there is no single fill line such as 513, 523 between vacant and occupied space, rather a fragmented pattern. The free chain block is a linked list which specifies the location and size of empty regions within that section of the heap. It is quick to determine whether and where a requested amount of storage is available in the heap by simply scanning through the linked list. Note that in the preferred embodiment, empty regions in the heap which are below a predetermined size (typically a few hundred bytes) are excluded from the free chain list. This prevents the list from becoming too long through containing a large number of very small vacant regions, although it does mean that these regions effectively become inaccessible for storage (although they can be retrieved later, as described in more detail below).

The transient heap 520 is used for storing objects having no expected currency beyond the end of the application or transaction, including application object instances, and primordial object instances and arrays created by application methods (arrays can be regarded as a specialised form of object). Since the lifetime of such objects is commensurate with the application itself, it should be possible to delete all the objects in the transient heap at the end of the application. The application class objects are also on the transient heap. In contrast, the middleware heap 510 is used for storing objects which have a life expectancy longer than a single transaction, including middleware object instances, and primordial object instances and arrays created by middleware methods. In addition, string objects and arrays for strings interned in the Interned String Table are also stored in the middleware heap (the Interned String Table is a tool whereby if multiple identical strings are to be stored on the heap, it is possible to store only one copy of the string itself, which can then be referenced elsewhere). Lastly, the system heap 550 is used for storing primordial class objects and reusable class objects, where the term reusable class object is used to denote a class which can be used again after JVM reset.

The type of class is dependent on the class loader which originally loaded it, in other words a middleware class and an application class are loaded by the middleware class loader 124 and the application class loader 120 respectively. For the purposes of the present discussion, primordial classes can be considered as classes loaded by the Primordial or Extensions class loader (130 and 125 respectively in FIG. 2). In the preferred embodiment, classes loaded by the middleware class loader are automatically regarded as reusable.

Instances of primordial classes, such as the basic string class java/lang/String, can be located either in the middleware heap or the transient heap, depending on the method which created them. In a preferred embodiment of the present invention, the determination of where to place such primordial class instances is based on the current context described above (also referred to as method-type). Thus if a method belonging to an application class is invoked, the context or method-type becomes Application, whilst if a method belonging to a middleware class is invoked, the method-type becomes Middleware. Finally, if a method belonging to a primordial class is invoked, the method-type is unchanged from its previous value. The context or method-type is stored in the Java frame for the method (which is stored on stack 195--see FIG. 2); at the completion of the method, the method-type reverts to its value at the time the method was invoked, which was stored in the previous frame.

It should be noted that for the above purpose a method belongs to the class that actually defines it. For example, if class A subclasses class B, but does not override method C, then method C belongs to class B. Therefore the method-type is that of class B, even if method C is being run for an instance of class A. In addition, the reason for tracking method-type on a per-thread basis is that it is possible for various threads within an application to be executing different methods having different context.

The transient region of the heap, containing objects created by the application or transaction, is subject to normal garbage collection. However, the intention is that it will be sufficiently large that this is unlikely to occur within the lifetime of a typical application, since as previously mentioned garbage collection is a relatively slow operation. At the end of each application, the transient region of the heap is reset. (The repetition of this pattern will thereby avoid having to perform garbage collection during most applications). In contrast the middleware region generally contains objects created by the trusted middleware. It is again subject to conventional garbage collection, although in a transaction environment it is expected that the majority of objects will be created in the transient heap, so that garbage collection is not expected to occur frequently. The middleware heap is not cleared between applications, but rather remains to give the middleware access to its persistent state (it is assumed that the middleware can take responsibility for resetting itself to the correct state to run the next application).

The preferred embodiment is actually somewhat more complicated than described above, in that it supports two types of application class loader, one of which is for standard application classes, the other for reusable application classes. The motivation here is that when the next transaction is to run, it will in fact require many of the same application classes as the previous transaction. Therefore it is desirable to retain some application classes rather than having to reload them, although certain additional processing is required to make them look newly loaded to the next transaction. Conversely it would be possible to have a second middleware class loader which is for non-reusable middleware classes. In the former situation the reusable application classes are treated essentially in the same manner as the reusable middleware classes, (eg loaded into the system heap); in the latter situation the non-reusable middleware classes would be treated similarly to the non-reusable application classes, but loaded into the middleware heap (since they may exist after the conclusion of a transaction, even if they do not endure for the next transaction). However, for present purposes in order to explain the invention more clearly, it will be assumed that all the middleware classes are reusable, and that none of the application classes are reusable.

Referring now to FIGS. 6A and 6B, these illustrate the garbage collection strategy of the preferred embodiment. In particular, the method involves firstly a mark phase, which marks all objects in the heap that are currently in use (known as live or active objects), and secondly a sweep phase, which represents the actual deletion of objects from the heap. Note that general background on garbage collection algorithms can be found in "Garbage Collection: Algorithms for Automatic Dynamic Memory Management" by R Jones and R Lins, Wiley, 1996 (ISBN 0 471 94148 4), whilst one implementation for garbage collection in a system having multiple heaps is described in: "A customisable memory management framework for C++" by G Attardi, T Flagella, and P Iglio, in Software Practice and Experience, vol 28/11, 1998.

As shown in FIG. 6A, the method starts with a review of the registers and stack, both the Java stack, as shown in FIG. 2, and also the C stack, (assuming that the Java VM 40 is running as a C application on OS 30, see FIG. 1) (step 610). Each thirty-two bit data word (for a 32-bit system) contained therein could represent anything, for example a real number, or part of a string, but it is assumed at least initially that it may denote a 32 bit reference to an object location in the heap. To firm up on this assumption, three tests are made. Firstly, it is tested whether or not the number references a location within the heap (step 612); if not then the number cannot represent an object reference. Secondly, in the preferred embodiment, all objects commence on an 8-byte boundary. Thus if the location corresponding to the data word from the stack/register does not fall on an object boundary (tested at step 615), then the original assumption that the data/number represents a reference to the heap must again be rejected. Thirdly, in the preferred embodiment, a table 538 is maintained (see FIG. 5) which has a bit for each object location in the heap; this bit is set to unity if there is an object stored at that location, and zero if no object is stored at that location (the relevant bit is updated appropriately whenever an object is created, deleted, or moved). If the data word from the stack/register corresponds to an object location for which the bit is zero, in other words, no object at that location, then once more the original assumption that the data/number represents a reference to the heap must be rejected (step 620). If the data word passes all three of the tests of steps 612, 615 and 620, then there are three remaining possibilities: (a) the word references an object on the heap; (b) the word is an integer that happens to have the same value as the object reference; or (c) the word is a previous value from uninitialized storage. As a conservative measure, it is assumed that option (a) is correct, and so the object is marked as live (step 625). A special array of bits is provided (block 534, see FIG. 5), one bit per object, in order to store these mark bits. If there remain other values on the stacks/registers to test (step 630), the method then loops back to examine these in the same manner as just described; if not the first stage of the mark process is complete. The objects so far identified are known as "roots", in the sense that any other objects which are still live must be referenced directly or indirectly from one of these objects.

In the second stage of the mark process, shown in FIG. 6B, the objects marked as live (i.e. the roots) are copied onto a list of active objects (step 635) (in the preferred embodiment objects are actually copied to the active list when originally marked, i.e. at the same time as step 625 in FIG. 6A). An object from this list is then selected (step 640), and examined to see if it contains any references (step 645). Note that this is a reasonably straightforward procedure, because the structure of the object is known from its corresponding class file,