Scalable resource allocation

• US 8,127,295 B1
• Filed: 08/03/2007
• Issued: 02/28/2012
• Est. Priority Date: 08/03/2007
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Jones, Blake A., Cameron, George R., Lowe, Eric E.
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): PATEL, HIREN P
• Application Number:
  US11/833,907
• Time in Patent Office: 1,670 Days
• Field of Search: None
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/5011 Pool
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals

Abstract

A device, system, and method are directed towards managing limited resources in a computer system with multiple processing units. Each processing unit has a corresponding bucket. Each thread executing on a processing unit has a corresponding wallet. Buckets and wallets contain credits corresponding to units of the limited resource. When a request for the resource is made, mechanisms of the invention attempt to fulfill the request by looking in a local wallet, a local bucket, or non-local buckets. In a resource shortage situation, credits may be moved to a primary bucket. A load balancing mechanism may distribute credits among buckets, or move credits from wallets to buckets.

Claims

1. A system for managing a limited resource, comprising:

a plurality of hardware processing units;

a plurality of buckets, each of the plurality of buckets corresponding to a single respective hardware processing unit of the plurality of hardware processing units;

program instructions operative to cause the plurality of hardware processing units to perform actions, the actions including;

receiving, in a thread executing at a first hardware processing unit of the plurality of hardware processing units, a first request for resource units;

identifying a wallet allocated to the thread, wherein the wallet is allocated only to the thread, wherein the wallet comprises credits, allocated to the thread, for resource units;

determining that the wallet allocated to the thread does not comprise enough credits to fulfill the first request, wherein each credit is representative of a number of resource units;

selecting, in response to determining that the wallet does not comprise enough credits, a first bucket of the plurality of buckets based on the first bucket corresponding to the first hardware processing unit and based on the first hardware processing unit executing the thread, wherein the first bucket comprises credits, allocated to the first hardware processing unit, for resource units;

selectively determining that the first bucket corresponding to the first hardware processing unit comprises enough credits to fulfill the first request;

selectively retrieving at least one credit from the first bucket and adding the retrieved at least one credit to the wallet;

deducting at least one credit from the wallet to fulfill the first request;

receiving, in the thread, a second request for resource units;

determining that the wallet allocated to the thread does not comprise enough credits to fulfill the second request;

selectively determining that the first bucket does not comprise enough credits to fulfill the second request; and

selectively retrieving at least one credit from a second bucket corresponding to a second hardware processing unit, based on determining that the wallet allocated to the thread and the first bucket do not comprise enough credits to fulfill the second request.

2. The system of claim 1, wherein the actions further include load balancing the first bucket and a second bucket of the plurality of buckets by moving credits between the first bucket and the second bucket.

3. The system of claim 1, wherein selectively retrieving at least one credit from the first bucket is based on an aggregate of credits in the wallet and the first bucket.

4. The system of claim 1, further comprising a plurality of wallets, each wallet corresponding to a respective thread executing on a respective one of the hardware processing units, wherein the wallet is one of the plurality of wallets, and wherein the actions further include:

selectively moving credits from each of the wallets to a corresponding local bucket.

5. The system of claim 4, wherein the action of moving credits from each of the wallets is selectively performed based on at least one selected from a group consisting of whether a resource shortage condition exists or whether a number of credits contained in each wallet exceeds a predetermined number of credits.

6. The system of claim 1, wherein the actions further include:

selectively blocking the thread based on whether enough credits to fulfill the request are found; and

if the thread is blocked, selectively unblocking the thread based on whether credits have been moved between the first bucket and the second bucket.

7. The system of claim 1, wherein the actions further include:

determining whether an aggregate of credits distributed among the second bucket and at least one other bucket is sufficient to fulfill the request; and

selectively moving credits from the second bucket and the at least one other bucket to the first bucket, based on whether the aggregate of credits is sufficient to fulfill the request.

8. The system of claim 1, wherein the actions further include:

determining whether an aggregate of credits distributed among the second bucket and at least one other bucket is sufficient to fulfill the request; and

selectively moving credits from the second bucket and the at least one other bucket to a primary bucket other than the first bucket, based on whether the aggregate of credits is sufficient to fulfill the request.

9. The system of claim 1, wherein each resource unit corresponds to one of a physical page of memory, a unit of I/O bandwidth, or a system data structure.

10. A computer based method of providing resource units in a computer system having a plurality of hardware processing units, comprising:

providing a set of buckets, each bucket corresponding to a single respective hardware processing unit of the plurality of hardware processing units;

providing a set of wallets, each wallet allocated to a single thread executing on one of the plurality of hardware processing units;

distributing a plurality of credits among the buckets, each credit corresponding to a resource unit;

in response to receiving a first request for resource units from a requesting thread;

identifying a wallet of the set of wallets allocated to the requesting thread, wherein the wallet comprises credits, allocated to the thread, for resource units;

determining that the wallet does not comprise enough credits to successfully respond to the first request;

selecting, in response to determining that the wallet does not comprise enough credits, a first bucket of the set of buckets based on the first bucket corresponding to a first hardware processing unit executing the requesting thread, wherein the first bucket comprises credits, allocated to the first hardware processing unit, for resource units;

determining that the first bucket comprises enough credits to successfully respond to the first request; and

selectively retrieving at least one credit from the first bucket and adding the retrieved at least one credit to the wallet;

deducting at least one credit from the wallet to fulfill the first request;

in response to receiving a second request for resource units from the requesting thread;

determining that the wallet allocated to the thread does not comprise enough credits to fulfill the second request;

selectively determining that the first bucket does not comprise enough credits to fulfill the second request; and

selectively retrieving at least one credit from a second bucket corresponding to a second hardware processing unit, based on determining that the wallet allocated to the thread and the first bucket do not comprise enough credits to fulfill the second request; and

periodically moving credits from at least some of the wallets to at least some of the buckets.

11. The computer based method of claim 10, further comprising:

in response to receiving the second request, selectively moving credits from a plurality of the buckets to a primary bucket at least partly based on a number of credits in the plurality of the buckets.

12. The computer based method of claim 10, further comprising:

in response to receiving the request, selectively moving credits from a plurality of the bucket to a primary bucket at least partly based on a number of credits in each of the plurality of the buckets; and

periodically performing a load balancing process that redistributes credits among the buckets.

13. The computer based method of claim 10, wherein the credits represent at least one selected from a group consisting of units of physical memory or units of I/O bandwidth.

14. The computer based method of claim 10, wherein each of the buckets is sized to fit within a respective CPU cache line.