System and method for heuristically allocating memory

• US 6,430,665 B1
• Filed: 06/25/1999
• Issued: 08/06/2002
• Est. Priority Date: 06/25/1999
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Jacoby, Raphael, Allison, David, Poger, Elliot
• Primary Examiner(s): Hudspeth, David
• Assistant Examiner(s): Tzeng, Fred F.
• Application Number:
  US09/339,808
• Time in Patent Office: 1,138 Days
• Field of Search: 711/152, 711/170, 711/172, 711/158, 707/7, 707/205
• US Class Current: 711/172
• CPC Class Codes: G06F 12/023 Free address space management

Abstract

Methods and systems consistent with the invention allocate memory of a memory array using a free list. The free list is a list of pointers to blocks of free memory located within the memory array. First, the system determines whether to sort the free list based on deallocation activity of the memory array. If so, the system sorts the free list according to the memory size of the blocks of free memory pointed to by the free list. The system then allocates memory of the memory array for the storage of data using the sorted free list.

Claims

1. A method for managing a memory array, comprising the steps, performed by a processor, of:

providing a list of pointers to blocks of free memory of the memory array, each block having a memory size;

determining whether to sort the list based on deallocation activity of the memory array, including determining whether to sort the list based on an accumulated number of instructions requesting deallocation of a block of memory; and

sorting the list, based on the sort determination, according to the memory size of the blocks of free memory indicated by the list.

2. The method of claim 1, wherein the accumulated number of instructions constitute instructions received since the list was last sorted.

3. The method of claim 1, wherein the determining step further includes the substeps of:

comparing the accumulated number of deallocation instructions to a threshold value; and

outputting a sort signal when the accumulated number of deallocation instructions is greater than the threshold value; and

wherein the sorting step further includes the substep of initiating the sorting of the list in response to the sort signal.

4. The method of claim 3, wherein the threshold value is set to 100.

5. The method of claim 1, wherein the determining step further includes the substep of:

determining whether to sort the list based on the elapsed time since the list was last sorted.

6. The method of claim 5, wherein the determining step further includes the substeps of:

comparing the elapsed time to a first threshold value; and

comparing to a second threshold value an accumulated number of instructions, received over a particular time, requesting deallocation of a block of memory, wherein the accumulated number of deallocation instructions is compared to the second threshold value when the elapsed time is greater than the first threshold value.

7. The method of claim 6, wherein the determining step further includes the substep of:

outputting a sort signal when the accumulated number of deallocation instructions is greater than the second threshold value; and

wherein the sorting step further includes the substep of initiating the sorting of the list in response to the sort signal.

8. The method of claim 6, wherein the first threshold value is 0.5 seconds.

9. The method of claim 6, wherein the second threshold value is 50.

10. The method of claim 1, wherein the sorting step further includes the substep of:

preventing access of the memory array while sorting the list.

11. The method of claim 1, wherein the allocating step further includes the substep of:

traversing the sorted list to determine the block of free memory in the memory array to store the data.

12. The method of claim 11, wherein the traversing step further includes the substep of:

traversing the list to locate the block of free memory having a memory size that most closely matches the size of the data.

13. The method of claim 1, further including the step of:

allocating blocks of the memory array for the storage of data using the sorted list.

14. A computer for managing a memory array, the computer comprising:

a memory having program instructions; and

a processor, responsive to the programming instructions, configured to;

provide a list of pointers to blocks of free memory of the memory array, each block having a memory size;

determine whether to sort the list based on deallocation activity of the memory array, including determining whether to sort the list based on an accumulated number of instructions requesting deallocation of a block of memory; and

sort the list according to the memory size of the blocks of free memory indicated by the list.

15. The computer of claim 14, wherein the accumulated number of instructions constitute instructions received since the list was last sorted.

16. The computer of claim 14, wherein the processor is further configured to:

compare the accumulated number of deallocation instructions to a threshold

output a sort signal when the accumulated number of deallocation instructions is greater than the threshold value; and

initiate the sorting of the list in response to the sort signal.

17. The computer of claim 14, wherein the threshold value is set to 100.

18. The computer of claim 14, wherein the processor is further configured to determine whether to sort the list based on the elapsed time since the list was last sorted.

19. The computer of claim 18, wherein the processor is further configured to:

compare the elapsed time to a first threshold value; and

compare to a second threshold value an accumulated number of instructions, received over a particular time, requesting deallocation of a block of memory, wherein the accumulated number of deallocation instructions is compared to the second threshold value when the elapsed time is greater than the first threshold value.

20. The computer of claim 19, wherein the processor is further configured to:

output a sort signal when the accumulated number of deallocation instructions is greater than the second threshold value; and

initiate the sorting of the list in response to the sort signal.

21. The computer of claim 19, wherein the first threshold value is 0.5 seconds.

22. The computer of claim 19, wherein the second threshold value is 50.

23. The computer of claim 14, wherein the processor is further configured to prevent access to the memory array while sorting the list.

24. The computer of claim 14, wherein the processor is further configured to traverse the sorted list to determine the block of free memory in the memory array to store the data.

25. The computer of claim 24, wherein the processor is further configured to traverse the list to locate the block of free memory having a memory size that most closely matches the size of the data.

26. The computer of claim 14, wherein the processor is configured to allocate blocks of the memory array for the storage of data using the sorted list.

27. A computer-readable medium containing instructions for controlling a data processing system to perform a method for managing memory, the method comprising the steps of:

providing a list of pointers to blocks of free memory of the memory array, each block having a memory size;

determining whether to sort the list based on deallocation activity of the memory array, including determining whether to sort the list based on an accumulated number of instructions requesting deallocation of a block of memory; and

sorting the list, based on the sort determination, according to the memory size of the blocks of free memory indicated by the list.

28. The method of claim 27, wherein the accumulated number of instructions constitute instructions received since the list was last sorted.

29. The method of claim 27, wherein the determining step further includes the substeps of:

comparing the accumulated number of deallocation instructions to a threshold

outputting a sort signal when the accumulated number of deallocation instructions is greater than the threshold value; and

wherein the sorting step further includes the substep of initiating the sorting of the list in response to the sort signal.

30. The method of claim 27, wherein the threshold value is set to 100.

31. The method of claim 27, wherein the determining step further includes the substep of:

determining whether to sort the list based on the elapsed time since the list was last sorted.

32. The method of claim 31, wherein the determining step further includes the substeps of:

comparing the elapsed time to a first threshold value; and

comparing to a second threshold value an accumulated number of instructions, received over a particular time, requesting deallocation of a block of memory, wherein the accumulated number of deallocation instructions is compared to the second threshold value when the elapsed time is greater than the first threshold value.

33. The method of claim 32, wherein the determining step further includes the substep of:

outputting a sort signal when the accumulated number of deallocation instructions is greater than the second threshold value; and

wherein the sorting step further includes the substep of initiating the sorting of the list in response to the sort signal.

34. The method of claim 32, wherein the first threshold value is 0.5 seconds.

35. The method of claim 32, wherein the second threshold value is 50.

36. The method of claim 27, wherein the sorting step further includes the substep of:

preventing access of the memory array while sorting the list.

37. The method of claim 27, wherein the allocating step further includes the substep of:

traversing the sorted list to determine the block of free memory in the memory array to store the data.

38. The method of claim 37, wherein the traversing step further includes the substep of:

traversing the list to locate the block of free memory having a memory size that most closely matches the size of the data.

39. The method of claim 27, further including the step of:

allocating blocks of the memory array for the storage of data using the sorted list.

40. An apparatus for managing a memory array, the apparatus comprising:

means for providing a list of pointers to blocks of free memory of the memory array, each block having a memory size;

means for determining whether to sort the list based on deallocation activity of the memory array, including means for determining whether to sort the list based on an accumulated number of instructions requesting deallocation of a block of memory; and

means for sorting the list according to the memory size of the blocks of free memory indicated by the list.

41. A computer data signal embodied in a carrier wave and representing sequences of instructions which, when executed by a processor, cause the processor to securely address a peripheral device at an absolute address by performing the steps of:

providing a list of pointers to blocks of free memory of the memory array, each block having a memory size;

determining whether to sort the list based on deallocation activity of the memory array, including determining whether to sort the list based on an accumulated number of instructions requesting deallocation of a block of memory; and

sorting the list, based on the sort determination, according to the memory size of the blocks of free memory indicated by the list.

42. A computer-implemented method for managing a memory array, comprising:

providing a list of pointers to blocks of free memory of the memory array, each block having a memory size;

determining whether to sort the list based on an accumulated number of instructions requesting deallocation of a block of memory, wherein determining whether to sort the list further includes;

comparing the accumulated number of deallocation instructions to a threshold value, and

outputting a sort signal when the accumulated number of deallocation instructions is greater than the threshold value; and

sorting the list, based on the sort signal, according to the memory size of the blocks of free memory indicated by the list, and wherein the accumulated number of instructions is determined from instructions received since the list was last sorted.

43. A computer for managing a memory array, the computer comprising:

a memory having program instructions; and

a processor, responsive to the programming instructions, configured to;

provide a list of pointers to blocks of free memory of the memory array, each block having a memory size;

determine whether to sort the list based on an accumulated number of instructions requesting deallocation of a block of memory, wherein the processor is further configured to;

compare the accumulated number of deallocation instructions to a threshold value, and

output a sort signal when the accumulated number of deallocation instructions is greater than the threshold value; and

sort the list, based on the sort signal, according to the memory size of the blocks of free memory indicated by the list, and wherein the accumulated number of instructions is determined from instructions received since the list was last sorted.

44. A computer-readable medium containing instructions for controlling a data processing system to perform a method for managing memory, the method comprising:

providing a list of pointers to blocks of free memory of the memory array, each block having a memory size;

determining whether to sort the list based on an accumulated number of instructions requesting deallocation of a block of memory, wherein determining whether to sort the list further includes;

comparing the accumulated number of deallocation instructions to a threshold value, and

outputting a sort signal when the accumulated number of deallocation instructions is greater than the threshold value; and

sorting the list, based on the sort signal, according to the memory size of the blocks of free memory indicated by the list, and wherein the accumulated number of instructions is determined from instructions received since the list was last sorted.

45. An apparatus for managing a memory array, the apparatus comprising:

means for providing a list of pointers to blocks of free memory of the memory array, each block having a memory size;

means for determining whether to sort the list based on an accumulated number of instructions requesting deallocation of a block of memory wherein the determining means further includes;

means for comparing the accumulated number of deallocation instructions to a threshold value, and

means for outputting a sort signal when the accumulated number of deallocation instructions is greater than the threshold value; and

means for sorting the list, based on the sort signal, according to the memory size of the blocks of free memory indicated by the list, and wherein the accumulated number of instructions is determined from instructions received since the list was last sorted.