Method for automatic memory reclamation for object-oriented systems with real-time constraints

Claim 1

A method for effecting recovery of memory resources for use by a digital data processing system, said digital data processing system comprising a computer, said digital data processing system performing real-time operations, said digital data processing system including a limited amount of memory, wherein said digital data processing system performs said real-time operations by sending ones of a plurality of messages to selected ones of a plurality of objects, said plurality of objects being allocated when needed for a specific functionality of said real-time operations and wherein a portion of said limited amount of memory is assigned to each object as said object is allocated, each of said plurality of objects being referenced when at least one other object may send a message to the object, ones of said plurality of objects becoming unreferenced when that object's functionality is no longer needed by the referencing object, said plurality of objects being stored in memory in a time-ordered sequence according to when they were allocated, and each of said plurality of objects being either marked or unmarked, wherein each of said plurality of objects is initially unmarked, said method executing in said computer as a program comprising the steps of: a. determining a dynamically growing condemned region of said memory by selecting a first object from said time-ordered plurality of objects as a beginning of said condemned region of said memory, said condemned region of said memory including all objects allocated after said first object; b. marking all objects within said condemned region of said memory that are referenced from any of said time-ordered plurality of objects that were allocated prior to said first object; c. marking objects within said condemned region of memory that are referenced from all objects within said condemned region of memory that are marked in accordance with step b; d. determining as a last object of said condemned region of memory a most recently allocated object, so that said condemned region includes all objects allocated between said first object and said last object, and so that no object allocated later in time than said last object is included in said condemned region; and e. deallocating memory resources, for use in allocating new objects in said limited amount of memory, associated with unmarked objects within said condemned region of memory; wherein each of said steps a through e comprises one or more cycles of operation, each of said cycles comprises one or more tasks, each task comprises a short, uninterruptible operation of said recovery process, wherein the latency of each task is deterministic, each pair of adjacent cycles is separated by performance of said real-time operations, and execution of each cycle is limited to a predefined fine-grained time period without replicating objects.

Claim 2

A method for effecting recovery of memory resources for use by a digital data processing system, said digital data processing system comprising a computer, said digital data processing system performing real-time operations, said digital data processing system including a limited amount of memory, wherein said digital data processing system performs said real-time operations by sending ones of a plurality of messages to selected ones of a plurality of objects, said plurality of objects being allocated when needed for a specific functionality of said real-time operations and wherein a portion of said limited amount of memory is assigned to each object as said object is allocated, each of said plurality of objects being referenced when at least one other object may send a message to the object, ones of said plurality of objects becoming unreferenced when that object's functionality is no longer needed by the referencing object, said plurality of objects being stored in memory in a time-ordered sequence according to when they were allocated, and each of said plurality of objects being either marked or unmarked, wherein each of said plurality of objects is initially unmarked, said method executing in said computer as a program comprising the steps of: a. determining a dynamically growing condemned region of said memory by selecting a first object from said time-ordered plurality of objects as a beginning of said condemned region of said memory, said condemned region of said memory including all objects allocated after said first object; b. marking all objects within said condemned region of said memory that are referenced from any of said time-ordered plurality of objects that were allocated prior to said first object; c. marking objects within said condemned region of memory that are referenced from all objects within said condemned region of memory that are marked in accordance with step b; d. determining as a last object of said condemned region of memory a most recently allocated object, so that said condemned region includes all objects allocated between said first object and said last object, and so that no object allocated later in time than said last object is included in said condemned region; and e. deallocating memory resources, for use in allocating new objects in said limited amount of memory, associated with unmarked objects within said condemned region of memory; wherein each of said steps a through e comprises one or more cycles of operation, each of said cycles comprises one or more tasks, each task comprises a short, uninterruptible operation of said recovery process, wherein the latency of each task is deterministic, each pair of adjacent cycles is separated by performance of said real-time operations, and execution of each cycle is limited to a predefined fine-grained time period without replicating objects.

Claim 17

A method for effecting recovery of memory resources for use by a digital data processing system performing real-time operations, said digital data processing system comprising a computer, said digital data processing system including a limited amount of memory, wherein said digital data processing system performs said real-time operations by sending ones of a predefined plurality of messages to selected ones of a plurality of objects, said plurality of objects being allocated when needed for a specific functionality of said real-time operations and wherein a portion of said limited amount of memory is assigned to each object as said object is allocated, each of said plurality of objects being referenced when at least one other object may send a message to the object, ones of said plurality of objects becoming unreferenced when that object's functionality is no longer needed by the referencing object, said plurality of objects being stored in memory in a time-ordered sequence according to when they were allocated, said plurality of objects being grouped into a plurality of generations each containing approximately the same number of objects, and said plurality of objects being either marked or unmarked, each of said plurality of objects being initially unmarked, said method executing in said computer as a program comprising the steps of: a. selecting a contiguous one or more of said plurality of generations as a dynamically growing condemned region of said memory by selecting a first generation from said plurality of generations as a beginning of said condemned region of said memory, said condemned region of said memory including all generations created after said first generation, b. marking all objects within said condemned region of said memory that are referenced from any of said time-ordered plurality of objects that were allocated prior to said first generation; c. marking objects within said condemned region of memory that are referenced from all objects within said condemned region of memory that are marked in accordance with step b; d. determining a last generation of said plurality of generations as an end of said condemned region of memory; and e. deallocating memory resources, for use in defining new objects in said limited amount of memory, associated with unmarked objects within said condemned region of memory; wherein each of said steps a through e comprises one or more cycles of operation, and each of said cycles comprises one or more tasks, each task comprising a short, uninterruptible operation of said recovery process, wherein the latency of each task is deterministic, said method further comprising the step of performing real-time operations between said cycles and between steps a-e as required by said computer without replicating objects.

Claim 18

A method for effecting recovery of memory resources for use by a digital data processing system performing real-time operations, said digital data processing system comprising a computer, said digital data processing system including a limited amount of memory, wherein said digital data processing system performs said real-time operations by sending ones of a predefined plurality of messages to selected ones of a plurality of objects, said plurality of objects being allocated when needed for a specific functionality of said real-time operations and wherein a portion of said limited amount of memory is assigned to each object as said object is allocated, each of said plurality of objects being referenced when at least one other object may send a message to the object, ones of said plurality of objects becoming unreferenced when that object's functionality is no longer needed by the referencing object, said plurality of objects being stored in memory in a time-ordered sequence according to when they were allocated, said plurality of objects being grouped into a plurality of generations each containing approximately the same number of objects, and said plurality of objects being either marked or unmarked, each of said plurality of objects being initially unmarked, said method executing in said computer as a program comprising the steps of: a. selecting a contiguous one or more of said plurality of generations as a dynamically growing condemned region of said memory by selecting a first generation from said plurality of generations as a beginning of said condemned region of said memory, said condemned region of said memory including all generations created after said first generation, b. marking all objects within said condemned region of said memory that are referenced from any of said time-ordered plurality of objects that were allocated prior to said first generation; c. marking objects within said condemned region of memory that are referenced from all objects within said condemned region of memory that are marked in accordance with step b; d. determining a last generation of said plurality of generations as an end of said condemned region of memory; and e. deallocating memory resources, for use in defining new objects in said limited amount of memory, associated with unmarked objects within said condemned region of memory; wherein each of said steps a through e comprises one or more cycles of operation, and each of said cycles comprises one or more tasks, each task comprising a short, uninterruptible operation of said recovery process, wherein the latency of each task is deterministic, said method further comprising the step of performing real-time operations between said cycles and between steps a-e as required by said computer without replicating objects.

Claim 33

A method for effecting recovery of memory resources for use by a digital data processing system performing real-time operations, said digital data processing system comprising a computer, said digital data processing system including a limited amount of memory, wherein said digital data processing system performs said real-time operations by sending one of a predefined plurality of messages to selected ones of a plurality of objects, said digital data processing system using stacks for a portion of its processing, each of said plurality of objects being either stack objects or non-stack objects, said plurality of objects being allocated when needed for a specific functionality of said real-time operations and wherein a portion of said limited amount of memory is assigned to each object as said object is allocated, each of said plurality of objects being referenced when at least one other object may send a message to the object, ones of said plurality of objects becoming unreferenced when that object's functionality is no longer needed by a referencing object when said referencing object deletes its reference to the object, said plurality of objects being stored in memory in a time-ordered sequence according to when they were allocated, said plurality of objects being grouped into a plurality of generations containing approximately the same number of objects, each of said generations having a remembered set containing references to ones of said plurality of objects allocated prior in time to said each of said generations that reference objects within said each of said generations, and said plurality of objects being either marked or unmarked, each of said plurality of objects being initially unmarked, said method executing in said computer as a program comprising the steps of: a. selecting a contiguous one or more of said plurality of generations as a dynamically growing condemned region of said memory by selecting a first generation from said plurality of generations as a beginning of said condemned region of said memory, said condemned region of said memory including all generations created after said first generation; b. comparing a number of objects in each generation in said condemned region to a predefined number, and if said number of objects is less than said predefined number, combining said generation with an adjacent generation; c. marking all objects within said condemned region of memory that are referenced from objects in generations allocated prior to said first generation by traversing said remembered sets for each generation in said condemned region of memory and marking objects in said condemned region of memory that are referenced from objects in generations allocated prior to said first generation; d. marking objects referenced from said marked objects within said condemned region of memory by sequentially traversing said condemned region of memory from a first object in said first generation to any most recently defined object and determining whether each object is marked, and if one of said plurality of objects is marked, determining whether said one of said plurality of objects references another object within said condemned region of memory, and if said one of said plurality of objects references another object within said condemned region of memory, marking said referenced object and placing said referenced object on a SAVELIST for determining whether said marked object references another object within said condemned region of memory at a subsequent time; e. determining a last generation of said plurality of generations as an end of said condemned region of memory; f. marking objects in said condemned region that are referenced from stack objects allocated prior in time to said condemned region and from marked stack objects within said condemned region; and g. recovering memory resources, for use in allocating new objects in said limited amount of memory, associated with unmarked objects within said condemned region of memory by sequentially examining each object within said condemned region, removing all unmarked objects and then unmarking all marked objects; wherein each of said steps a through g comprises one or more cycles of operation, each of said cycles comprises one or more tasks comprising a short, uninterruptible operation of said recovery process; wherein the latency of each task is deterministic, each pair of adjacent cycles is separated by performance of said real-time operations, and each cycle is limited to a predefined fine-grained time period without replicating objects.

Claim 34

A method for effecting recovery of memory resources for use by a digital data processing system performing real-time operations, said digital data processing system comprising a computer, said digital data processing system including a limited amount of memory, wherein said digital data processing system performs said real-time operations by sending one of a predefined plurality of messages to selected ones of a plurality of objects, said digital data processing system using stacks for a portion of its processing, each of said plurality of objects being either stack objects or non-stack objects, said plurality of objects being allocated when needed for a specific functionality of said real-time operations and wherein a portion of said limited amount of memory is assigned to each object as said object is allocated, each of said plurality of objects being referenced when at least one other object may send a message to the object, ones of said plurality of objects becoming unreferenced when that object's functionality is no longer needed by a referencing object when said referencing object deletes its reference to the object, said plurality of objects being stored in memory in a time-ordered sequence according to when they were allocated, said plurality of objects being grouped into a plurality of generations containing approximately the same number of objects, each of said generations having a remembered set containing references to ones of said plurality of objects allocated prior in time to said each of said generations that reference objects within said each of said generations, and said plurality of objects being either marked or unmarked, each of said plurality of objects being initially unmarked, said method executing in said computer as a program comprising the steps of: a. selecting a contiguous one or more of said plurality of generations as a dynamically growing condemned region of said memory by selecting a first generation from said plurality of generations as a beginning of said condemned region of said memory, said condemned region of said memory including all generations created after said first generation; b. comparing a number of objects in each generation in said condemned region to a predefined number, and if said number of objects is less than said predefined number, combining said generation with an adjacent generation; c. marking all objects within said condemned region of memory that are referenced from objects in generations allocated prior to said first generation by traversing said remembered sets for each generation in said condemned region of memory and marking objects in said condemned region of memory that are referenced from objects in generations allocated prior to said first generation; d. marking objects referenced from said marked objects within said condemned region of memory by sequentially traversing said condemned region of memory from a first object in said first generation to any most recently defined object and determining whether each object is marked, and if one of said plurality of objects is marked, determining whether said one of said plurality of objects references another object within said condemned region of memory, and if said one of said plurality of objects references another object within said condemned region of memory, marking said referenced object and placing said referenced object on a SAVELIST for determining whether said marked object references another object within said condemned region of memory at a subsequent time; e. determining a last generation of said plurality of generations as an end of said condemned region of memory; f. marking objects in said condemned region that are referenced from stack objects allocated prior in time to said condemned region and from marked stack objects within said condemned region; and g. recovering memory resources, for use in allocating new objects in said limited amount of memory, associated with unmarked objects within said condemned region of memory by sequentially examining each object within said condemned region, removing all unmarked objects and then unmarking all marked objects; wherein each of said steps a through g comprises one or more cycles of operation, each of said cycles comprises one or more tasks comprising a short, uninterruptible operation of said recovery process; wherein the latency of each task is deterministic, each pair of adjacent cycles is separated by performance of said real-time operations, and each cycle is limited to a predefined fine-grained time period without replicating objects.