Method for efficient soft real-time execution of portable byte code computer programs

• US 6,081,665 A
• Filed: 12/19/1997
• Issued: 06/27/2000
• Est. Priority Date: 12/19/1997
• Status: Expired due to Fees

• Current Assignee: Aonix
• Original Assignee: NewMonics, Inc. (Société Aonix SA)
• Inventors: Lee, Steven J., Mitra, Simanta, Nilsen, Kelvin D.
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): Khatri, Anil
• Application Number:
  US08/994,393
• Time in Patent Office: 921 Days
• Field of Search: 395/701, 395/703, 395/705, 395/706, 395/702, 395/704, 395/707, 707/103, 707/206, 364/134, 709/201
• US Class Current: 717/116
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence
• CPC Class Codes: G06F 2212/702 Conservative garbage collection
• CPC Class Codes: G06F 9/4488 Object-oriented
• CPC Class Codes: G06F 9/45504 Abstract machines for programme code execution, e.g. Java virtual machine [JVM], interpreters, emulators

Abstract

The invention is a method for use in executing portable virtual machine computer programs under real-time constraints. The invention includes a method for implementing a single abstract virtual machine execution stack with multiple independent stacks in order to improve the efficiency of distinguishing memory pointers from non-pointers. Further, the invention includes a method for rewriting certain of the virtual machine instructions into a new instruction set that more efficiently manipulates the multiple stacks. Additionally, using the multiple-stack technique to identify pointers on the run-time stack, the invention includes a method for performing efficient defragmenting real-time garbage collection using a mostly stationary technique. The invention also includes a method for efficiently mixing a combination of byte-code, native, and JIT-translated methods in the implementation of a particular task, where byte-code methods are represented in the instruction set of the virtual machine, native methods are written in a language like C and represented by native machine code, and JIT-translated methods result from automatic translation of byte-code methods into the native machine code of the host machine. Also included in the invention is a method to implement a real-time task dispatcher that supports arbitrary numbers of real-time task priorities given an underlying real-time operating system that supports at least three task priority levels. Finally, the invention includes a method to analyze and preconfigure virtual memory programs so that they can be stored in ROM memory prior to program.

Claims

1. A real-time virtual machine method (RTVMM) for implementing real-time systems and activities, the RTVMM comprising the steps:

implementing an O-OPL program that can run on computer systems of different designs, an O-OPL program being based on an object-oriented programming language (O-OPL) comprising object type declarations called classes, each class definition describing the variables that are associated with each object of the corresponding class and all of the operations called methods that can be applied to instantiated objects of the specified type, a "method" being a term of art describing the unit of procedural abstraction in an object-oriented programming system, an O-OPL program comprising one or more threads wherein the run-time stack for each thread is organized so as to allow accurate identification of type-tagged pointers contained on the stack without requiring type tag information to be updated each time the stack'"'"'s content changes, the O-OPL being an extension of a high-level language (HLL) exemplified by Java, HLL being an extension of a low-level language (LLL) exemplified by C and C++, a thread being a term of art for an independently-executing task, an O-OPL program being represented at run time by either O-OPL byte codes or by native machine codes.

2. The RTVMM of claim 1 wherein an O-OPL program utilizes a pointer stack and a non-pointer stack.

3. The RTVMM of claim 1 wherein an O-OPL program comprises one or more classes represented in read-only memory, the methods thereof h aving been converted into O-OPL byte codes prior to run time.

4. The RTVMM of claim 1 wherein an O-OPL program comprises one or more classes represented in read-only memory, the methods thereof having been converted into native machine language prior to run time.

5. The RTVMM of claim 1 wherein a byte-code O-OPL method is an O-OPL method represented at run time by O-OPL byte codes, a byte-code O-OPL method being written in O-OPL, an O-OPL, method represented at run time by native machine codes being either a native O-OPL method or a native-translated O-OPL method, a native O-OPL method being written in LLL, a native-translated O-OPL method being written in HLL, the implementing step comprising the steps:

compiling the byte-code O-OPL methods into HLL byte codes and transforming the HLL byte codes into O-OPL byte codes;

compiling the native O-OPI, methods into native machine codes;

compiling the native-translated O-OPL methods into HLL byte codes and compiling HLL byte codes into native machine codes.

6. The RTVMM of claim 1 wherein a calling function is a native-translated O-O-OPL method and the called function is a byte-code method, a native-translated O-OPL method being an O-OPL method written using byte codes which are translated into native machine language at the time of execution, a byte-code method being a method written using O-OPL or HLL and translated into O-OPL, byte codes prior to execution, the implementing step comprising the steps:

providing each byte-code method with a stub procedure which honors the native-translated method execution protocol, the stub procedure switching from native-translated method to O-OPL byte code interpretation protocols and then invoking an O-OPL, interpreter.

7. The RTVMM of claim 6 wherein the stub procedure switches back to the native-translated O-OPL mode when the O-OPL, interpreter returns.

8. The RTVMM of claim 1 wherein a calling function is a native-translated O-OPL method and the called function is a native method, a native-translated O-OPL method being a method written using byte codes which are translated into native machine language at the time of execution, a native method being a method written in LLL, the implementing step comprising the steps:

providing each native method with a stub procedure which honors the native-translated method execution protocol, the stub procedure switching from native-translated method to LLL-code protocols and then invoking the native method.

9. The RTVMM of claim 8 wherein the stub procedure switches back to the native-translated O-OPL mode when the O-OPL interpreter returns.

10. The RTVMM of claim 1 wherein the implementing step comprises the step:

causing an application thread to periodically check whether the system desires to preempt the thread.

11. The RTVMM of claim 1 wherein the implementing step comprises the step:

causing an application thread that is to be preempted to provide notification as to when the thread is at a point where safe garbage collection can take place.

12. The RTVMM of claim 1 wherein one of the implemented threads is a garbage collection thread that operates asynchronously thereby resulting in the garbage collection thread being interleaved with other threads in arbitrary order, objects subject to garbage collection being either finalizable or non-finalizable, a finalizable object being subject to an action that is performed when the memory space allocated to the finalizable object is reclaimed by the garbage collection thread, the finalizing action being specified by including a non-empty finalizer method in the class definition, the garbage collection thread being able to distinguish a thread'"'"'s pointer variables from the thread'"'"'s non-pointer variables, preemption of a thread being allowed only if the thread is in a state identified as a preemption point, a thread being allowed to hold pointers in variables between preemption points that may not be visible to the garbage collection thread, pointer variables that may not be visible to the garbage collection thread being called fast pointers, pointer variables that are visible to the garbage collection thread being called slow pointers, each LLL, function being identified as either preemptible or non-preemptible.

13. The RTVMM of claim 12 wherein the implementing step comprises the steps:

causing the values of essential fast pointers to be copied into slow pointers immediately prior to a preemption point of a preemptible thread. (5.0/4)

causing the values of essential fast pointers to be restored after preemption by causing the values of the slow pointers to be copied to the locations where the values of the fast pointers were previously stored.

14. The RTVMM of claim 12 wherein the implementing step comprises the steps:

causing the values of all of the essential fast pointers of a preemptible LLL function to be copied into slow pointers prior to calling the prcemptible LLL function;

causing the values of the essential fast pointers to be restored when the called preemptible LLL function returns by causing the values of the slow pointers to be copied to the locations where the values of the fast pointers were previously stored.

15. The RTVMM of claim 12 wherein the implementing step comprises the steps:

providing a plurality of macros representing (1) an interface that permits the use of different garbage-collection techniques and (2) an implementation of a mostly-stationary garbage-collection technique.

16. The RTVMM of claim 12 wherein the implementing step comprises the step:

providing parameterized access to heap memory in order to facilitate the implementation of read and write barriers, heap memory being a region of memory wherein objects of arbitrary size can be allocated space to satisfy the dynamic memory needs of application programs, heap memory being subject to garbage collection.

17. The RTVMM of claim 16 wherein the implementing step comprises the step:

providing a macro that returns the value of a fast pointer in the heap given the identity of the pointer and its type.

18. The RTVMM of claim 16 wherein the implementing step comprises the step:

providing a macro that assigns a value from a fast pointer in heap memory given the identity of the pointer, its type, and the value.

19. The RTVMM of claim 16 wherein the implementing step comprises the step:

providing a macro that returns the value of a nonpointer in heap memory given the identity of the nonpointer and its type.

20. The RTVMM of claim 16 wherein the implementing step comprises the step:

providing a macro that assigns a value to a nonpointer in heap memory given the identity of the nonpointer, its type, and the value.

21. The RTVMM of claim 16 wherein the implementing step comprises the step:

providing direct access to stack data using LLL pointer indirection.

22. The RTVMM of claim 21 wherein the implementing step comprises the step:

representing stack pointers by LLL global variables declared as pointers.

23. The RTVMM of claim 12 wherein the implementing step comprises the step:

maintaining a finalizable list of finalizable objects that have not been finalized, a finalizable object being removed from the finalizable list after it has been finalized, the finalizable list of objects being linked through a "finalize link" field.

24. The RTVMM of claim 12 wherein the implementing step comprises the steps:

partitioning memory into at least three demi-spaces, at least one of the demi-spaces being a static space excluded from the garbage collection process;

designating two of the demi-spaces as to-space and from-space at the beginning of a garbage collection cycle, live objects residing in from-space subsequently being copied into to-space;

designating the remaining demi-spaces as mark-and-sweep spaces at the beginning of a garbage collection cycle, the mark-and-sweep spaces being garbage collected using a mark-and-sweep technique.

25. The RTVMM of claim 24 wherein the implementing step comprises the step:

including an "activity pointer" field for each object in memory, the "activity pointer" identifying the activity that was responsible for allocating the object, the "activity pointer" field containing a "null" value if the object was not allocated by a real-time activity.

26. The RTVMM of claim 25 wherein the implementing step comprises the step:

maintaining a free pool of space segments for to-space and for each mark-and-sweep sweep space, a free pool being organized as a plurality of doubly-linked lists, each linked list being a list of free space segments ranging in size from a lower value to an upper value, the size ranges for the plurality of linked lists being non-overlapping;

causing the "activity pointer" field to specify the size of a free space segment.

27. The RTVMM of claim 24 wherein the implementing step comprises the step:

including a "signature pointer" field for each object in memory, the "signature pointer" field containing a pointer to a structure that represents the internal organization of the O-OPL data within the object.

28. The RTVMM of claim 27 wherein the implementing step comprises the steps:

maintaining a free pool of space segments for to-space and for each mark-and-sweep space, a free pool being organized as a plurality of doubly-linked lists, each linked list being a list of free space segments ranging in size from a lower value to an upper value, the size ranges for the plurality of linked lists being non-overlapping;

causing the "signature pointer" field to be used as a backward link to the preceding segment.

29. The RTVMM of claim 24 wherein a garbage-collection cycle begins, the implementing step comprising the steps:

causing the non-empty mark-and-sweep space having the most available free space to be designated as the new from-space;

causing the old to-space to be designated as the new to-space if the allocated space within the new from-space is less than the free space available as a single contiguous region in the old to-space;

otherwise,

causing the old from-space to be designated as the new to-space.

30. The RTVMM of claim 24 wherein the implementing step comprises the step:

including a "scan list" field for each object in memory, the "scan list" field distinguishing marked and unmarked objects residing in a mark-and-sweep space but not on a free list, the "scan list" field for each object in a mark-and-sweep space having a "scan clear" value at the beginning of a garbage collection cycle, an object recognized as being a live object being placed on a list of recognized live objects, the "scan list" field for an object on the list of recognized live objects having either a "scan end" value denoting the last object on the list of recognized live objects or a value identifying the next object on the list of recognized live objects, the "scan list" field for an object residing on a free list within a mark-and-sweep space or to- space having the "scan free" value, the "scan list" field for an object residing in from-space which has been scheduled for copying into to-space being a pointer to the to-space copy, the "scan list" field otherwise being assigned the "scan clear" value, the "scan list" field for an object residing in to-space having the "scan clear" value at the beginning of a garbage collection cycle, a to-space object recognized as live during garbage collection being placed on a list of recognized live objects, the "scan list" field for a to-space object on the list of recognized live objects having a value identifying the next object on the list of recognized live objects, the "scan list" field for each object queued for copying into to-space having the "scan end" value denoting that the object is live.

31. The RTVMM of claim 24 wherein the implementing step comprises the steps:

providing a memory allocation budget for each real-time activity;

allocating memory from the memory allocation budget to an object associated with the real-time activity;

causing the garbage collection thread to credit the memory allocation budget of the real-time activity when the memory allocated to the object is reclaimed.

32. The RTVMM of claim 24 wherein a real-time activity has allocated memory to an object which is subject to finalization and the garbage collection thread endeavors to reclaim the allocated memory, the implementing step comprising the step:

causing the garbage collection thread to place the object on a list of the real-time activity'"'"'s objects that are awaiting finalization.

33. The RTVMM of claim 24 wherein the implementing step comprises the step:

causing memory space to be allocated, memory space being preferably allocated in the mark-and-sweep space having the requisite space available and that is most full, memory space being allocated in to-space only if the allocation cannot be made in any of the mark-and-sweep sweep spaces.

34. The RTVMM of claim 24 wherein the implementing step comprises the steps:

causing a "finalize link" bit and a "finalize object" bit in an "activity pointer" field of a finalizable object to be set when space is allocated to the finalizable object, the "finalize link" bit being set indicating that the object has a "finalize link" field appended to the object, the "finalize object" bit being set indicating that the object needs to be finalized;

causing the "finalize object" bit to be cleared when a finalizable object has been finalized.

35. The RTVMM of claim 24 wherein a pointer is to be written into memory, the implementing step comprising the steps:

causing the pointer to an object in from-space to be replaced by a pointer to the object'"'"'s new address in to-space;

causing an object in mark-and-sweep space to which the pointer points to be marked if the object has not yet been marked.

36. The RTVMM of claim 24 wherein the implementing step comprises the steps:

causing the available memory in a newly-selected to-space to be divided into a new-object segment for allocation of memory to new objects and an old-object segment for receiving copies of live from-space objects, the old-object segment being equal to or larger than the allocated space in from-space, new objects being allocated space in sequence from the end of the new-object segment away from the old-object segment, old objects being copied in sequence from the end of the old-object segment away from the new-object segment;

causing the unallocated portions of the old-object segment and the new-object segment to be coalesced into a single contiguous segment of free memory at the end of a garbage collection cycle.

37. The RTVMM of claim 24 wherein, after to-space and from-space have been selected at the beginning of a garbage collection cycle, the implementing step comprises the steps:

causing the free pools of memory in the mark-and-sweep spaces and to-space to be linked together into a global free pool, the free pools of the mark-and-sweep spaces being linked in increasing order of amount of free memory, the free pool of to-space being linked to the mark-and-sweep space having the greatest amount of free memory, a request for a new memory allocation being satisfied by the first memory segment of sufficient size found by searching the global free pool according to the linking order.

38. The RTVMM of claim 24 wherein the implementing step comprises the steps:

maintaining a list of root pointers to live objects;

causing space for a copy of an object in to-space to be allocated if a root pointer to the object refers to from-space;

causing the from-space address of the object to be written in an "indirect pointer" field of the object'"'"'s allocated space in to-space;

causing the root pointer to be replaced with the address of the object in to-space;

causing the to-space address of the object to be written into a "scan list" field of the object in from-space.

39. The RTVMM of claim 24 wherein the implementing step comprises the steps:

maintaining a list of root pointers to live objects;

causing an object to be marked if the root pointer to the object refers to a mark-and-sweep space or to-space and the object has not yet been marked, marking consisting of placing the object on a scan list.

40. The RTVMM of claim 24 wherein the marking and copying processes for a particular garbage collection cycle have been completed, the implementing step comprising the steps:

causing all objects needing finalization to be transferred from a list of finalizable objects to a finalizee list;

causing the transferred objects residing in mark-and-sweep space to be placed on a scan list;

causing the transferred objects residing in from-space to be placed on a copy list.

41. The RTVMM of claim 40 wherein the marking and copying processes for a particular garbage collection cycle have been completed, the implementing step comprising the steps:

causing an object from a list of finalizable objects to be transferred to a finalizee list if the object has not been marked or if the object is a from-space object that has not been copied into to-space, the object being placed on the copy list and space being allocated in to-space if the object resides in from-space, the object being marked by being placed on the scan list if the object resides in mark-and-sweep space.

42. The RTVMM of claim 41 wherein the implementing step comprises the step:

implementing the finalizee list by causing the address of the next finalizee on the activity'"'"'s finalizee list to be placed in a "finalize link" field of a finalizee.

43. The RTVMM of claim 40 wherein the transfer of objects needing finalization on the list of finalizable objects to the finalizee list has been completed, the implementing step comprising the steps:

causing the objects on the copy list to be copied to to-space;

causing the objects on the scan list to be scanned, scanning consisting of tending each pointer contained within an object, tending being a term of art describing the garbage collection process of (1) examining a pointer and, if the object has not already been recognized as live, arranging for the referenced object to be subsequently scanned by placing the object on a scan list if it resides in a mark-and-sweep space or in to-space or by arranging for the object to be copied into to-space if it resides in from-space and (2) updating the pointer to refer to the object'"'"'s new location if it has been queued for copying into to-space.

44. The RTVMM of claim 24 wherein the transfer of objects needing finalization from a list of finalizable objects to a finalizee list has been accomplished, the implementing step comprising the step:

causing each finalizee on the finalizee list to be transferred to the appropriate activity'"'"'s finalizee list or onto an orphaned finalizee list.

45. The RTVMM of claim 44 wherein an activity'"'"'s finalizee list is implemented by placing in an "activity pointer" field of a finalizee the address of the next finalizes on the activity'"'"'s finalizee list.

46. The RTVMM of claim 44 wherein after transferring a finalizee on the finalizee list to the appropriate activity'"'"'s finalizee list or onto an orphaned finalizee list, the implementing step comprises the step:

causing a "finalize link" bit in an "activity pointer" field of the object corresponding to the finalizee to be cleared, a cleared "finalize link" bit indicating that the object is no longer on the list of finalizable objects.

47. The RTVMM of claim 24 wherein the transfer of objects needing finalization from a list of finalizable objects to an activity'"'"'s finalizee list or an orphaned finalizee list has been accomplished, the implementing step comprising the steps:

causing the mark-and-sweep spaces and to-space to be swept and identifying each object that is not marked, that is not on a free list, and that is a "hashlock object";

causing the garbage collection thread to copy the value of a "hash value" field of the "hashlock object" onto a list of recycled hash values if the list is not full;

otherwise;

causing the garbage collection thread to (1) make the "hashlock object" live, (2) change a "signature" field in the "hashlock object" to represent a "hashcache object", (3) add the "hashcache object" to the list of recycled hash values, and (4) copy the value of the "hash value" field of the original "hashlock object" onto a list of recycled hash values.

48. The RTVMM of claim 24 wherein the transfer of objects needing finalization from a list of finalizable objects to an activity'"'"'s finalizee list or an orphaned finalizee list has been accomplished, the implementing step comprising the steps:

causing from-space to be examined and each object to be identified that was not copied into to-space and that is a "hashlock object" with a hash value that needs to be reclaimed;

causing the garbage collection thread to copy the value of a "hash value" field of the "hashlock object" into a list of recycled hash values if the list is not full;

otherwise;

causing the garbage collection thread to (1) make the "hashlock object" live, (2) change a "signature" field in the "hashlock object" to represent a "hashcache object", (3) add the "hashcache object" to the list of recycled hash values, and (4) copy the value of the "hash value" field of the original "hashlock object" onto a list of recycled hash values;

causing zeros to be written into all of from-space.

49. The RTVMM of claim 12 wherein the implementing step comprises the step:

designating portions of memory as a to-space and zero or more mark-and-sweep spaces;

maintaining a free pool of space segments for to-space and for each mark-and-sweep space, a free pool being organized as a plurality of linked lists, each linked list being a list of free space segments ranging in size from a lower value to an upper value, the size ranges for the plurality of linked lists being non-overlapping.

50. The RTVMM of claim 49 wherein an object of specified size is to be allocated space in a demi-space by an allocation routine, the allocation routine comprising the steps:

causing the linked list with the smallest size range having space segments equal to or greater than the specified size of the object to be selected from the free pool of the demi-space;

causing a portion of the space segment equal in size to the object to be allocated to the object;

causing the unallocated portion of the space segment to be returned to the appropriate linked list.

51. The RTVMM of claim 12 wherein the implementing step comprises the step:

designating portions of memory as a to-space, from-space, and zero or more mark-and-sweep spaces;

including an "indirect pointer" field for each object in memory, the "indirect pointer" field containing a pointer to the location of the currently valid copy of the data that corresponds to the object, the pointer pointing to the object itself for objects in a mark-and-sweep space, the pointer pointing to the location of the object that currently represents the object'"'"'s contents for objects in to-space and from-space.

52. The RTVMM of claim 51 wherein the implementing step comprises the steps:

maintaining a free pool of space segments for to-space and for each mark-and-sweep space, a free pool being organized as a plurality of doubly-linked lists, each linked list being a list of free space segments ranging in size from a lower value to an upper value, the size ranges for the plurality of linked lists being non-overlapping;

causing the "indirect pointer" field to be used as a forward link to the succeeding segment.

53. The RTVMM of claim 12 wherein the implementing step comprises the step:

including an "activity pointer" field for each object in memory, the "activity pointer" identifying the real-time activity object that was responsible for allocation of the object, the "activity pointer" field containing a "null" value if the object was not allocated by a real-time activity;

maintaining a finalizees list of objects waiting to be finalized for each real-time activity, the objects on the finalizees list being linked through the "activity pointer" field;

maintaining a list of the headers of the finalizees lists, the pointer "finalizees" being a root pointer to the headers list.

54. The RTVMM of claim 53 wherein the implementing step comprises the step:

implementing a finalizer thread that operates in the background and is responsible for incrementally executing the finalizer methods associated with finalizee objects reachable from the "finalizees" pointer.

55. The RTVMM of claim 54 wherein the finalizer thread comprises the steps:

causing a finalizer method associated with a finalizee object to be executed;

causing the finalizee object to be removed from the associated finalizee list;

causing the "activity pointer" field of the finalizee object to be overwritten with a reference to the allocating object;

causing a "finalize object" bit in the "activity pointer" field of the finalizee object to be cleared indicating that the object has been finalized.

56. The RTVMM of claim 53 wherein the implementing step comprises the step:

implementing a finalizer thread that is part of a real-time activity and is responsible for incrementally executing the finalizer methods associated with finalizee objects associated with the real-time activity and reachable from the "finalizees" pointer.

57. The RTVMM of claim 56 wherein the finalizer thread comprises the steps:

causing a finalizer method associated with a finalizee object to be executed;

causing the finalizee object to be removed from the associated finalizee list;

causing the "activity pointer" field of the finalizee object to be overwritten with a reference to the allocating object;

causing a "finalize object" bit in the "activity pointer" field of the finalizee object to be cleared indicating that the object has been finalized.

58. The RTVMM of claim 53 wherein the implementing step of claim 1 comprises the steps:

causing memory space to be allocated to a finalizee list head object when an object associated with a particular activity and requiring finalization is encountered;

causing a finalizee list head pointer associated with the activity to be overwritten with a pointer to the finalizee list head object;

causing the finalizee list head object to be destroyed when the finalizee list becomes empty and overwriting the finalizee list head pointer with the "null" value.

59. The RTVMM of claim 1 wherein each object has a "lock" field initialized to a "null" value, the implementing step comprising the steps:

causing a "hashlock object" to be allocated memory space if the "lock" field of the object contains a "null" value;

causing the next available hash value to be identified;

causing the "hash value" field of the "hashlock object" to be initialized to the next available hash value;

causing the "lock" field of the object to be initialized to refer to the newly-allocated "hashlock object".

60. The RTVMM of claim 59 wherein the implementing step comprises the step:

causing the "hash value" field of the "hashlock object" to be overwritten to the next available hash value if the "lock" field of the object does not have a "null" value and if the "hash value" field has the value zero.

61. The RTVMM of claim 59 wherein one of the implemented threads is a garbage collection thread the implementing step comprising the steps:

maintaining a list of available hash values consisting of previously assigned hash values for which the corresponding objects have been reclaimed by the garbage collection thread;

causing one of the hash values on the list of available hash values to be designated as the next available hash value to be assigned to a "hash object" if the list of available hash values is non-empty;

causing a static counter to be incremented if the list of available hash values is empty and causing the new counter value to be designated as the next available hash value to be assigned to a "hash object".

62. The RTVMM of claim 1 wherein each object has a "lock" field initialized to a "null" value, the implementing step comprising the steps:

causing a "hashlock object" for each object needing either a lock or a hash value to be allocated memory space and initialized, the "hashlock object" having a "hash value" field;

causing the address of the "hashlock object" to be written into the "lock" field of the object;

causing the hash value of an object to be retrieved by reading the "hash value" field of the associated "hashlock object".

63. The RTVMM of claim 62 wherein a monitor object is to be accessed and a "lock" field of the monitor object has a "null" value, the implementing step comprising the steps:

causing memory space to be allocated for a "hashlock object";

causing a "count" field of the "hashlock object" to be initialized to 1;

causing a "u-owner" field of the "hashlock object" to be set to represent the current thread;

causing access to be granted to the monitor object.

64. The RTVMM of claim 62 wherein a monitor object is to be accessed and a "lock" field of the monitor does not have a "null" value thereby indicating the existence of a "hashlock object", the implementing step comprising the steps:

causing a "count" field of the "hashlock object" to be incremented;

causing a "u-owner" field of the "hashlock object" to be set to represent the current thread;

causing access to be granted to the monitor object;

provided the "count" field is 0 or the "u-owner" field refers to the currently-executing thread;

otherwise;

causing the currently-executing thread to be placed on a waiting list queue;

causing the execution of the currently-executing thread to be blocked until access can be granted to the monitor object.

65. The RTVMM of claim 62 wherein threads are assigned priorities and a higher-priority thread'"'"'s access to an object is being blocked by a lower-priority thread, the implementing step comprising the step:

causing the priority of the higher-priority thread to be assigned to the lower-priority thread until the lower-priority thread releases its lock on the object.

66. The RTVMM of claim 62 wherein a thread requests access to a monitor object be terminated, the implementing step comprising the steps:

causing verification that a "u-owner" field of the "hashlock" object associated with the monitor object represents the thread;

causing a "count" field in the "hashlock" object to be decremented;

if the new value in the "count" field is zero, then;

causing the "u-owner" field of the "hashlock" object to be set to represent the highest-priority member of a waiting list for the monitor object;

causing the "count" field of the "hashlock" object to be set to 1;

causing the removal of the highest-priority member of the waiting list for the monitor object;

provided the waiting list is not empty;

otherwise;

causing the "u-owner" field of the "hashlock" object to be set to a "null" value.

67. The RTVMM of claim 62 wherein a thread'"'"'s access to a monitor object has been terminated and a "hash value" field of a "hashlock object" associated with the monitor object is 0, the implementing step comprising the steps:

causing a "lock" field in the monitor object to be set to a "null" value;

causing the placement of the "hashlock object" on a list of available "hashlock objects" to be used in satisfying new requests for "hashlock objects".

68. The RTVMM of claim 67 wherein the placing step is accomplished by the step:

causing a "u-next" field in the "hashlock object" to be set to point to the next "hashlock object" on the list of "hashlock objects".

69. The RTVMM of claim 1 wherein the implementing step comprises the steps:

creating a normally-sleeping thread called a thread dispatcher;

causing the thread dispatcher to be awakened if an interrupt arrives from an alarm timer that has determined that a specified time period has expired, the thread dispatcher then suspending execution of the currently-executing thread;

causing the thread dispatcher to be awakened if an interrupt arrives indicating the necessity of preempting the currently-executing thread so that a sporadic task can be executed;

causing the thread dispatcher to be awakened if the currently-executing thread blocks on an I/O request, the thread dispatcher then suspending execution of the currently-executing thread.

70. The RTVMM of claim 69 wherein the implementing step comprises the step:

creating a watchdog thread that sends an interrupt to the thread dispatcher when a thread that is scheduled for execution blocks.

71. The RTVMM of claim 1 wherein the implementing step comprises the step:

creating a thread called a thread dispatcher which makes only one application task ready to run at a time in accordance with the priorities of the application tasks waiting to run.

72. The RTVMM of claim 1 wherein the implementing step comprises the step:

causing symbolic references to be replaced with integer indices and direct pointer references when a program is loaded into a computer system.

73. The RTVMM of claim 1 wherein the implementing step comprises the step:

causing all operands supplied to each byte-code instruction to be of the appropriate type prior to execution of a program.

74. The RTVMM of claim 1 wherein an O-OPL byte-code loader is used to load a program into a computer system, the implementing step comprises the step:

causing each byte code of an HLL program to be translated into an O-OPL byte code.

75. The RTVMM of claim 1 wherein the implementing step comprises the step:

causing symbolic values for constants to be replaced with the actual values when a class is loaded into a computer.

76. The RTVMM of claim 1 wherein there is a slow variant and a fast variant of every byte code instruction, a program to be loaded into a computer consisting of one or more slow variants, the implementing step comprising the step:

causing all byte codes corresponding to each method to be examined;

causing the slow variants to be replaced by the quick variants when a class is loaded into a computer.

77. The RTVMM of claim 1 wherein an O-OPL byte-code loader is used to load an HLL byte-code program into a computer system, the implementing step comprises the step:

causing each byte code to be examined when a class is loaded to determine whether it operates on pointer or non-pointer data;

causing pointers to be pushed onto and popped from a pointer stack;

causing non-pointers to bc pushed onto and popped from a non-pointer stack.

78. The RTVMM of claim 77 wherein the implementing step comprises the step:

causing the O-OPL byte-code loader to remap the offsets for all local-variable operations.

79. The RTVMM of claim 1 wherein the implementing step comprises the step:

utilizing only O-OPL pointer and non-pointer stacks in executing methods compiled by a JIT compiler, JIT standing for "just in time" and denoting a process for translating HLL, byte codes to native machine language codes on the fly, just in time for its execution, the translation of byte codes to native codes being a form of JIT compiling.

80. The RTVMM of claim 79 wherein a method compiled by a JIT compiler invokes a byte-code or nativc-code method, the implementing step comprises the step:

causing the frame and stack pointers necessary for the execution of the corresponding LLL routines to be set up;

causing the return address to be removed from the non-pointer stack and stored temporarily in an LLL local variable.

81. The RTVMM of claim 79 wherein a method of a thread is being executed, the method having been compiled by a JIT compiler, the implementing step comprising the step:

causing the status of the thread to be set to a value indicating that the thread can be preempted at any time.

82. The RTVMM of claim 79 wherein the implementing step comprises the step:

causing the JIT compiler to provide special translations of exception handling contexts so that only the contents of those registers are saved and restored that are actually live on entry into the exception handling context.

83. The RTVMM of claim 1 wherein the implementing step comprises the steps:

creating a thread called a thread dispatcher;

creating a watchdog thread that sends an interrupt to the thread dispatcher when a thread that is scheduled for execution blocks, the thread dispatcher then scheduling another thread for execution.

84. The RTVMM of claim 1 wherein each thread maintains its own versions of global variables "pointer stack pointer" (psp), "pointer stack frame pointer" (pfp), "non-pointer stack pointer" (npsp) and "non-pointer stack frame pointer" (npfp), the implementing step comprising the steps:

creating a thread called a thread dispatcher, the thread dispatcher saving psp, pfp, npsp, and npfp into the state variables of an executing thread when the executing thread is preempted, the preempted thread restoring these state variables when the preempted thread resumes execution.

85. The RTVMM of claim 1 wherein the implementing step includes providing a ROMizer tool which produces a load file appropriate for ROM storage, the ROMizer tool comprising the steps:

analyzing and verifying byte code;

performing byte code and constant-pool transformations;

supporting standard compiler transformations designed to optimize the performance of executed code.

86. The RTVMM of claim 85 wherein the implementing step relating to the load file includes the step:

causing an object placed into the object region to be marked by setting a "scan list" field of the object to SCAN-END.

87. The RTVMM of claim 85 wherein the implementing step relating to the load file includes the step:

causing the "indirect pointer" field of each object to refer to itself.

88. The RTVMM of claim 85 wherein the implementing step relating to the load file includes the steps:

causing all byte codes to be pre-transformed into an O-OPL instruction set;

causing all references to the constant pool to have been resolved.

89. The RTVMM of claim 85 wherein the implementing step relating to the load file includes the steps:

causing a search to be made for common strings;

causing multiple--string objects to refer to the same substring data.