Memory management and method for allocation using free-list
View Patent ↗A method of managing a memory of an apparatus, the apparatus executing one or more processes using the memory. The method comprises maintaining a plurality of lists of identifiers, wherein each list has an associated size value and an associated threshold corresponding to a maximum number of identifiers in that list, wherein each identifier identifies a corresponding region of the memory that had been allocated for a process but that is currently not required by any of the one or more processes, and wherein the size of a region of the memory identified by an identifier of a list equals the size value associated with that list. When a process requests allocation of a region of the memory: one of the lists are identified that has an associated size value suitable for the allocation request; and if that list is not empty, to that process a region is identified of the memory identified by one of the identifiers stored in that list and that identifier is removed from that list, and, otherwise, a region of the memory is allocated with a size of the identified associated size value and the allocated region is identified of the memory to that process. The method comprises adjusting one or more of the thresholds in dependence upon the current usage of the memory by the one or more processes.
1. A method of managing a memory of an apparatus, the apparatus executing one or more processes using the memory, the method comprising:
(a) maintaining a plurality of lists of identifiers, wherein each list has an associated size value and an associated threshold corresponding to a maximum number of identifiers in that list, wherein each identifier identifies a corresponding region of the memory that had been allocated for a process but that is currently not required by any of the one or more processes, and wherein a size of a region of the memory identified by an identifier in a list equals the size value associated with that list;
(b) when a process requests allocation of a region of the memory:
selecting one of the lists that has an associated size value suitable for the allocation request; and
if the selected list is not empty, indicating to that process a region of the memory identified by one of the identifiers in the selected list and removing that identifier from the selected list, and, otherwise, allocating a region of the memory with a size of the size value associated with the selected list and indicating the allocated region of the memory to that process; and
(c) adjusting one or more of the thresholds in dependence upon the current usage of the memory by the one or more processes.
2. A method according to claim 1 , comprising:
(d) when a process indicates that a region of the memory that has been allocated for that process is no longer required by that process:
identifying one of the lists that has an associated size value equal to the size of that region of the memory; and
if the number of identifiers in that list is less than the threshold associated with that list, adding an identifier to that list to identify that region of the memory, and, otherwise, deallocating that region of the memory.
3. A method according to claim 2 , in which step (c) comprises:
if the step of allocating in step (b) is successful, then incrementing the threshold associated with the selected list.
4. A method according to claim 2 , in which step (c) comprises:
if the step of allocating in step (b) is unsuccessful, then:
(e) deallocating a region of the memory identified by one of the identifiers in one of the lists;
(f) removing that identifier from that list; and
(g) decrementing the threshold associated with that list.
5. A method according to claim 2 , in which step (c) comprises:
periodically determining whether the amount of the memory being used by the one or more processes exceeds a predetermined threshold; and
if it is determined that the amount of the memory being used by the one or more processes exceeds the predetermined threshold, then:
(h) deallocating a region of the memory identified by one of the identifiers in one of the lists;
(i) removing that identifier from that list; and
(j) decrementing the threshold associated with that list.
6. A method according to claim 1 , in which step (c) comprises:
if the step of allocating in step (b) is successful, then incrementing the threshold associated with the selected list.
7. A method according to claim 6 , in which the step of allocating in step (b) is unsuccessful if the time to allocate the region of the memory exceeds a threshold time.
8. A method according to claim 6 , in which the step of allocating in step (b) is unsuccessful if an unallocated region of the memory with a size of the size value associated with the selected list cannot be found.
9. A method according to claim 6 , in which step (c) comprises:
if the step of allocating in step (b) is unsuccessful, then:
(e) deallocating a region of the memory identified by one of the identifiers in one of the lists;
(f) removing that identifier from that list; and
(g) decrementing the threshold associated with that list.
10. A method according to claim 1 , in which step (c) comprises:
if the step of allocating in step (b) is unsuccessful, then:
(e) deallocating a region of the memory identified by one of the identifiers in one of the lists;
(f) removing that identifier from that list; and
(g) decrementing the threshold associated with that list.
11. A method according to claim 10 , comprising:
determining an amount of the memory to deallocate; and
repeating steps (e), (f) and (g) until the amount of the memory that is deallocated at step (e) is at least the determined amount of the memory.
12. A method according to claim 10 , in which the step of allocating in step (b) is unsuccessful if the time to allocate the region of the memory exceeds a threshold time.
13. A method according to claim 1 , in which step (c) comprises:
periodically determining whether the amount of the memory being used by the one or more processes exceeds a predetermined threshold; and
if it is determined that the amount of the memory being used by the one or more processes exceeds the predetermined threshold, then:
(h) deallocating a region of the memory identified by one of the identifiers in one of the lists;
(i) removing that identifier from that list; and
(j) decrementing the threshold associated with that list.
14. A method according to claim 13 , comprising:
determining an amount of the memory to deallocate; and
repeating steps (h), (i) and (j) until the amount of the memory that is deallocated at step (h) is at least the determined amount of the memory.
15. A method of managing a memory of an apparatus, the apparatus executing one or more processes using the memory, the method comprising:
(a) maintaining a plurality of lists of identifiers, wherein each list has an associated size value and an associated threshold corresponding to a maximum number of identifiers in that list, wherein each identifier identifies a corresponding region of the memory that had been allocated for a process but that is currently not required by any of the one or more processes, and wherein a size of a region of the memory identified by an identifier in a list equals the size value associated with that list;
(b) when a process requests allocation of a region of the memory:
selecting one of the lists that has an associated size value suitable for the allocation request; and
if the selected list is not empty, indicating to that process a region of the memory identified by one of the identifiers in the selected list and removing that identifier from the selected list, and, otherwise, allocating a region of the memory with a size of the size value associated with the selected list and indicating the allocated region of the memory to that process;
(c) adjusting one or more of the thresholds in dependence upon the current usage of memory by the one or more processes; and
(d) maintaining an order indication that indicates the relative order with which the identifiers in the lists were added to the lists.
16. A method according to claim 15 , comprising:
maintaining a counter; and
when, during step (d), an identifier is added to a list:
setting an indicator corresponding to that identifier to the value of the counter; and
incrementing or decrementing the counter.
17. A method according to claim 16 , wherein counter is incremented or decremented each time a predetermined number of identifiers have been added to the lists.
18. A method according to claim 15 , wherein step (e) comprises selecting an identifier which the order indication indicates as having been added to the corresponding list before the other identifiers were added to the lists, wherein the region of the memory deallocated at step (e) is the region of the memory identified by the selected identifier.
19. A method according to claim 15 , when wherein step (h) comprises selecting an identifier which the order indication indicates as having been added to the corresponding list before the other identifiers were added to the lists, wherein the region of the memory deallocated at step (h) is the region of the memory identified by the selected identifier.
20. A method of managing a memory of an apparatus, the apparatus executing one or more processes using the memory, the method comprising:
maintaining a plurality of free-lists, each free-list having an associated threshold corresponding to a maximum number of regions of the memory identified by that free-list;
when a process requests allocation of a region of the memory:
selecting one of the lists that has an associated size value suitable for the allocation request; and
if the selected list is not empty, indicating to the process a region of the memory identified in the selected list and removing that an identifier for that region of the memory from the selected list; and
adjusting one or more of the thresholds in dependence upon the current usage of the memory by the one or more processes.