Memory allocator for a multiprocessor computer system

• US 6,785,888 B1
• Filed: 02/24/1998
• Issued: 08/31/2004
• Est. Priority Date: 08/29/1997
• Status: Expired due to Fees

• Current Assignee: Sequent Computer Systems, Inc. (International Business Machines Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Kingsbury, Brent A., Friedberg, Stuart A., Krueger, Phillip E., McKenney, Paul E.
• Primary Examiner(s): BULLOCK JR, LEWIS ALEXANDER
• Application Number:
  US09/028,285
• Time in Patent Office: 2,380 Days
• Field of Search: 709/104, 709/206, 709/229, 709/226, 711/147, 711/150, 710/200, 710/220, 710/240-244, 718/104
• US Class Current: 718/104
• CPC Class Codes: G06F 9/5016 the resource being the memory

Abstract

Methods for dynamically allocating memory in a multiprocessor computer system such as a non-uniform memory access (NUMA) machine having distributed shared memory. The methods include allocating memory by specified node, memory class, or memory pool in response to requests by the system (kernel memory allocation) or a user (application memory allocation). Through these methods memory is allocated more efficiently in a NUMA machine. For example, allocating memory on a specified node in a NUMA machine, such as the same node on which a process requiring the memory is running, reduces memory access time. Allocating memory from a specified memory class allows device drivers with restricted DMA ranges to operate with dynamically allocated memory. Other benefits of these methods include minimizing expensive remote-memory accesses using a distributed reference count mechanism and lock-free cache access.

Claims

1. A computer-implemented method of maintaining a count with multiple second variables and a first variable, the method comprising the following steps:

determining dynamically changeable desired of levels of value of the second variable as based on a distance between a total value of the second variable and a predetermined limit of the second variable;

maintaining a third variable that stores the dynamically changeable desired levels of value of the second variable, a the predetermined limit of the second variable, and a leftover value of the second variable of no less than one;

determining whether an instance of a second variable can be changed by a requested amount and stay within the dynamically changeable desired levels of value of the variable based on a total value of the variable and the predetermined limit of the variable as stored in the third variable;

if so, changing the second variable by the requested amount; and

if not, changing the first variable by the requested amount.

2. The method of claim 1 including further changing the first and second variable by opposite amounts to maintain the second variable within a desired range.

3. The method of claim 1 wherein limits on the second variable decrease as the amount of the first variable nears a given maximum or minimum amount.

4. The method of claim 1 wherein the count maintained is a count of allocated memory blocks.

5. The method of claim 1 including maintaining the count with multiple fourth variables per an associated second variable, the method including the following steps;

determining whether an instance of a fourth variable can be changed by a requested amount without crossing a limit on the variable;

if so, changing the fourth variable by the requested amount; and

if not, changing the associated second variable by the requested amount.

6. The method of claim 5 including further changing the first and second variable by opposite amounts to maintain the second variable within a desired range and further changing the second and fourth variable by opposite amounts to maintain the fourth variable within a desired range.

7. The method of claim 5, wherein the first variable represents a value for a computer system implementing the method, and the second variables represent values for nodes of said system, and the fourth variable represents values for processors of the node of the associated second variable.

8. The method of claim 1, wherein the first variable represents a value for a node of a computer system implementing the method, and the second variables represent values for processors of said node.

9. The method of claim 1, wherein the first variable represents a value for a computer system implementing the method, and the second variables represent values for nodes of said system.

10. The method of claim 1, wherein the first and second variables represent numbers of memory structures allocated in a computer system implementing the method.

11. The method of claim 1, wherein the first and second variables represent numbers of I/Os outstanding on a device of a computer system implementing the method.

12. In a multiprocessor system having an operating system and a shared memory, the method comprising the steps of:

assigning a first variable to represent a count of memory structure'"'"'s in the memory;

assigning multiple second variables, each to represent a count of memory structures in the memory;

determining dynamically changeable desired of levels of value of the second variable as based on a distance between a total value of the second variable and a predetermined limit of the second variable;

maintaining a third variable that stores the dynamically changeable desired levels of value of the second variable, a the predetermined limit of the second variable, and a leftover value of the second variable of no less than one;

determining whether an instance of a second variable can be changed by a requested amount and stay within the dynamically changeable desired levels of value of the variable based on a total value of the variable and the predetermined limit of the variable as stored in the third variable;

if so, changing the second variable by the requested amount; and

if not, changing the first variable by the requested amount.

13. The method of claim 12, wherein the system has a plurality of nodes, and the shared memory is distributed among at least some of the nodes;

and

wherein the first variable represents a count of memory structures allocated in the system, and the second variables represent counts of memory structures allocated in one or more of the nodes of the system.

14. The method of claim 12, wherein the system has a plurality of nodes, and the shared memory is distributed among at least some of the nodes;

and

wherein the first variable represents a count of memory structures allocated in the system, and the second variables represent counts of memory structures allocated in one or more respective nodes of the system.

15. The method of claim 12, wherein the system has a plurality of processors, and the shared memory is allocated between at least some of the processors;

and

wherein the first variable represents a count of memory structures allocated in the system, and the second variables represent counts of memory structures allocated to one or more of the processors of the system.

16. The method of claim 15, wherein the system has a plurality of nodes each having one or more of the processors.

17. The method of claim 12, further including the steps of:

assigning multiple fourth variables per an associated second variable, each to represent a count of memory structures in the memory;

determining whether an instance of a fourth variable can be changed by a requested amount without crossing a limit on the variable;

if so, changing the fourth variable by the requested amount; and

if not, changing the associated second variable by the requested amount.

18. The method of claim 17, wherein the system has a plurality of nodes, at least some of the nodes having a plurality of processors, and the shared memory is distributed among at least some of the nodes;

and

wherein the first variable represents a count of memory structures allocated in the system, and the second variables represent counts of memory structures allocated in one or more respective nodes of the system, and the fourth variables represent counts of memory structures allocated to one or more of the processors of respective associated second variables.

19. A computer system, comprising:

multiple processors;

a shared resource accessible by the processors;

a first variable representing a count of allocations of the resource;

multiple second variables, each variable representing a count of allocations of the resource to one or more of the processors;

a third variable storing dynamically changeable desired levels of value of the second variable, a predetermined limit of the second variable, and a leftover value of the second variable of no less than one, the dynamically changeable desired levels of value of the second variable determined as based on a distance between a total value of the second variable and the predetermined limit of the second variable;

a changer of the first variable when one of the second variables falls out of the dynamically changeable desired levels of value of the variable based on a total value of the variable and the predetermined limit of the variable, as stored in the third variable.

20. The system of claim 19, wherein the resource is memory.

21. The system of claim 19, wherein the resource is an I/O device.

22. An article comprising:

a computer-readable medium having instructions executable by a multiprocessor system having a shared resource;

a first variable recorded on the medium to represent a count of the resource;

multiple second variables recorded on the medium, each to represent a count of the resource;

a third variable storing dynamically changeable desired levels of value of the second variable, a predetermined limit of the second variable, and a leftover value of the second variable of no less than one, the dynamically changeable desired levels of value of the second variable determined as based on a distance between a total value of the second variable and the predetermined limit of the second variable;

a comparison of an instance of a second variable to be changed by a requested amount so that the second variable stays within dynamically changeable desired levels of value of the variable based on a total value of the variable and a predetermined limit of the variable, as stored in the third variable;

a change of the second variable by the request amount if the changed second variable stays within the desired levels; and

a change of the first variable by the requested amount if the changed second variable does not stay within the desired levels.

23. The article of claim 22, wherein the resource is shared memory of the system.

24. The article of claim 22, wherein the resource is a shared I/O device of the system.

25. The article of claim 22, wherein the system is a computer system and the instructions comprise at least in part an operating system of the system.