Selection of a resource in a distributed computer system

• US 6,886,164 B2
• Filed: 05/08/2001
• Issued: 04/26/2005
• Est. Priority Date: 05/08/2001
• Status: Expired due to Term

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Meiri, David
• Primary Examiner(s): BANANKHAH, MAJID A
• Application Number:
  US09/851,039
• Publication Number:
  US 20020169816A1
• Time in Patent Office: 1,449 Days
• Field of Search: 718/104, 718/107, 718/100, 718/101, 718/103, 718/105, 709/226, 709/229, 709/200, 702/186, 702/179
• US Class Current: 718/104
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]

Abstract

A method for selecting a resource from a plurality of resources includes determining a score for that resource on the basis of a stochastic property of that resource. An interval corrsesponding to that resource is then defined to have an extent that depends on the score. A particular resource is then selected by generating a random number and selecting that resource when the random number falls within the interval.

Claims

1. A method for selecting a resource from a plurality of resources, said method comprising:

determining a score for said resource on the basis of a stochastic property of said resource;

defining an interval corresponding to said resource, said interval having an extent that depends on said score;

generating a random number; and

selecting said resource if said random number is within said interval.

2. The method of claim 1, wherein defining an interval corresponding to said resource comprises

determining a normalized score for said resource;

and

defining an extent of said interval on the basis of said normalized score.

3. The method of claim 2, wherein determining a normalized score comprises

evaluating a sum of scores assigned to each resource in said plurality of resources;

and

normalizing said score assigned to said resource by said sum of scores.

4. The method of claim 1, wherein generating a random number comprises generating a uniformly distributed random number.

5. The method of claim 1, further comprising polling a selected resource to update a prior measurement of said stochastic property associated with said resource.

6. The method of claim 1, wherein determining said score comprises estimating a present value of said stochastic property on the basis of a prior measurement of said stochastic property.

7. The method of claim 6, further comprising selecting said prior measurement to be a most-recently known value of said stochastic property.

8. The method of claim 1, further comprising selecting said resource to be a processor having a variable workload.

9. The method of claim 8, wherein determining a score for said resource comprises obtaining an estimate of a present workload of said processor.

10. The method of claim 9, wherein determining a score for said resource further comprises evaluating an inverse of said estimate of said present workload of said processor.

11. The method of claim 9, wherein obtaining an estimate of a present workload of said processor comprises retrieving, from memory, a last-known workload of said processor.

12. The method of claim 1, further comprising selecting said resource to be a queue having a variable queue-length.

13. A method for selecting a queue from a plurality of queues, said method comprising:

assigning a score to said queue;

defining an interval corresponding to said queue, said interval having an extent that depends on said score;

generating a random number; and

selecting said queue if said random number is within said interval.

14. The method of claim 13, wherein assigning said score comprises determining an effective queue-length of said queue.

15. The method of claim 14, wherein determining said effective queue-length comprises estimating a queue-length of said queue.

16. The method of claim 15, wherein determining said effective queue-length comprises determining a priority of said queue.

17. The method of claim 16, wherein assigning said score comprises weighting said queue-length with said priority.

18. The method of claim 13, wherein defining an interval comprises selecting said extent on the basis of a normalized score.

19. The method of claim 18, wherein selecting said extent on the basis of a normalized score comprises:

evaluating a sum of scores of all queues in said plurality of queues; and

normalizing said score for said queue by said sum of scores.

20. The method of claim 13, wherein generating a random number comprises generating a uniformly distributed random number.

21. The method of claim 15, wherein estimating the number of waiting elements in said queue comprises determining a last-known queue-length for said queue.

22. The method of claim 21, further comprising:

polling said selected queue to determine a queue-length of said selected queue; and

updating said last-known queue-length for said selected queue.

23. The method of claim 22, wherein updating said last-known queue length comprises polling said selected queue to determining a number of waiting elements in said selected queue.

24. The method of claim 23, further comprising caching said number of waiting elements for use in estimating a length of said queue.

25. A computer-readable medium having encoded thereon software for selecting a resource from a plurality of resources, said software comprising instructions for:

determining a score for said resource on the basis of a stochastic property of said resource;

defining an interval corresponding to said resource, said interval having an extent that depends on said score;

generating a random number; and

selecting said resource if said random number is within said interval.

26. A computer-readable medium having encoded thereon software for selecting a queue from a plurality of queues, said software comprising instructions for:

assigning a score to said queue;

defining an interval corresponding to said queue, said interval having an extent that depends on said score;

generating a random number; and

selecting said queue if said random number is within said interval.