Scheduling threads based on priority utilizing entitlement vectors, weight and usage level

• US 8,813,085 B2
• Filed: 10/28/2011
• Issued: 08/19/2014
• Est. Priority Date: 07/19/2011
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Elwha LLC (Intellectual Ventures LLC)
• Inventors: Glew, Andrew F., Tegreene, Clarence T., Gerrity, Daniel A.
• Primary Examiner(s): An, Meng
• Assistant Examiner(s): TEETS, BRADLEY A
• Application Number:
  US13/317,826
• Publication Number:
  US 20130111489A1
• Time in Patent Office: 1,026 Days
• US Class Current: 718/103
• CPC Class Codes: G06F 2209/485 Resource constraint
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

An embodiment or embodiments of an information handling apparatus can use an entitlement vector to simultaneously manage and activate entitlement of objects and processes to various resources independently from one another. An information handling apparatus can comprise an entitlement vector operable to specify resources used by at least one object of a plurality of object. The information handling apparatus can further comprise a scheduler operable to schedule a plurality of threads based at least partly on entitlement as specified by the entitlement vector.

Claims

1. An information handling apparatus comprising:

at least one processor including at least;

one or more entitlement vectors configured to allocate one or more user-specified rights to one or more resources used by one or more threads, wherein the one or more entitlement vectors are respectively associated with the one or more threads;

one or more instruction pointers configured to indicate a respective one or more threads of the one or more threads for execution;

a scheduler configured to schedule the respective one or more threads for execution based at least partly on comparison of a resource entitlement as allocated by the one or more entitlement vectors, and configured to assign priority among the respective one or more threads; and

logic used by the scheduler to schedule one of the one or more threads, wherein the one or more of the entitlement vectors respectively associated with the respective one or more of the threads, one or more weights, and one or more resource usage levels are arguments used by the logic, and for a selected thread priority_i is determined at least partly by a comparison of weight_i×

entitlement vector_i entitlement to resource usage level_i over a plurality of cycles i.

2. The information handling apparatus according to claim 1 further comprising:

randomization logic configured to insert random fluctuation into the priority among the one or more threads.

3. The information handling apparatus according to claim 2 wherein:

the randomization logic is configured to insert random fluctuation into the priority using randomization selected from a group including a Boltzmann search, simulated annealing, hop-around, oscillation for detecting a local maximum, comparing new to previous optimum, and a lateral computing technique.

4. The information handling apparatus according to claim 1 further comprising:

supervisory logic configured to modify the one or more of the entitlement vectors and ensure correct context of the one or more of the entitlement vectors during context switching.

5. The information handling apparatus according to claim 1 further comprising:

supervisory logic configured to modify the one or more of the entitlement vectors comprising a library call configured to ensure correct context of the one or more of the entitlement vectors during context switching.

6. The information handling apparatus according to claim 1 further comprising:

the logic is used by the scheduler to schedule ones of the plurality of threads wherein for a thread, priority is determined at least partly by a comparison of a sum of weight_i×

entitlement vector_i entitlement over a plurality of cycles i to resource usage level.

7. The information handling apparatus according to claim 1 further comprising:

monitoring logic configured to monitor the resource usage of the one or more threads during execution and indicate the resource usage in a respective usage vector of the one or more threads.

8. The information handling apparatus according to claim 1 further comprising:

monitoring logic configured to monitor the resource usage and modify the respective one or more of the entitlement vectors of the respective one or more threads based on the respective resource usage.

9. The information handling apparatus according to claim 1 further comprising:

monitoring logic configured to monitor resource usage, modify at least one of the one or more entitlement vectors based on the resource usage, and compare the modified at least one of the one or more entitlement vectors to a user-set or default initial entitlement vector.

10. The information handling apparatus according to claim 1 further comprising:

monitoring logic configured to monitor resource usage, modify the entitlement vector based on the resource usage; and

an entitlement vector memory configured to store a history of entitlement vectors.

11. The information handling apparatus according to claim 1 further comprising:

monitoring logic configured to monitor resource usage, modify at least one of the one or more entitlement vectors based on the resource usage, and merge the modified at least one of the one or more entitlement vectors into an evolving entitlement vector.

12. The information handling apparatus according to claim 1 further comprising:

a priority vector configured to indicate priority for scheduling the respective one or more threads as a function of a combination of entitlement as specified by at least one of the one or more entitlement vectors and a resource usage as specified by a usage vector.

13. The information handling apparatus according to claim 1 wherein:

the resources comprise a plurality of resources comprising physical/logical resources and operational resources.

14. The information handling apparatus according to claim 13 wherein the physical/logical resources are at least one of a group including physical and/or logical instances of:

processors, central processing units (CPUs), graphics hardware, network controllers, memory, memory management, hardware, microarchitecture, sound cards, video cards, network interfaces, instruction set architecture (ISA), library calls, library functions, software objects, compilers, and operating systems.

15. The information handling apparatus according to claim 13 wherein the operational resources are at least one of a group including:

power, voltage, current, electrons, frequency, execution cycles, battery consumption, battery life, constraints, temperature, and measurable phenomena.

16. An information handling apparatus comprising:

at least one processor including at least;

one or more entitlement vectors configured to allocate one or more user-specified rights to one or more resources used by one or more processes, wherein the one or more entitlement vectors are respectively associated with the one or more processes;

one or more instruction pointers configured to indicate the one or more processes for execution; and

logic configured to schedule the one or more processes for execution based at least partly on comparison of a resource entitlement as allocated by the one or more entitlement vectors, and configured to assign priority among the respective one or more processes, wherein the one or more entitlement vectors respectively associated with the one or more processes, one or more weights, and one or more resource usage levels are arguments used by the logic, and for a selected process priority_i is determined by a comparison of weight_i×

entitlement vector_i entitlement to resource usage level_i over a plurality of cycles i.

17. The information handling apparatus according to claim 16 wherein:

the logic is configured to schedule the one or more processes wherein priority_i is determined by a comparison of a sum of a product of weight_i×

entitlement vector_i entitlement to resource usage level_i over a plurality of cycles i.

18. The information handling apparatus according to claim 16 wherein:

the logic is configured to schedule the one or more processes wherein priority is determined at least partly by a comparison of a sum of weight_i×

entitlement vector, entitlement over a plurality of cycles i to resource usage level.

19. An information handling apparatus comprising:

at least one processor including at least;

one or more entitlement vectors configured to allocate one or more user-specified rights to one or more resources used by one or more processes, wherein the one or more entitlement vectors are respectively associated with the one or more processes;

one or more instruction pointers configured to indicate the one or more processes for execution; and

monitoring logic configured to monitor resource usage during execution of the one or more processes and indicate the resource usage in one or more usage vectors, the one or more usage vectors used in combination with the one or more entitlement vectors for scheduling the one or more processes for execution in the at least one processor based at least partly on comparison of a resource entitlement as allocated by the one or more entitlement vectors, and configured to assign priority among the respective one or more processes, wherein the respective one or more entitlement vectors respectively associated with the respective one or more processes, the one or more usage vectors, and one or more weights are arguments used for scheduling the one or more processes, and for a selected process priority_i is determined by a comparison of weight_i×

entitlement vector_i entitlement to resource usage level_i over a plurality of cycles i.

20. The information handling apparatus according to claim 19 wherein:

the monitoring logic is configured to monitor resource usage and modify the one or more entitlement vectors based on the resource usage.

21. The information handling apparatus according to claim 19 wherein:

the monitoring logic is configured to monitor resource usage, modify the one or more entitlement vectors based on the resource usage, and compare the modified one or more entitlement vectors to a user-set or default initial entitlement vector.

22. The information handling apparatus according to claim 19 further comprising:

an entitlement vector memory;

wherein;

the monitoring logic is configured to monitor resource usage, modify the one or more entitlement vectors based on the resource usage; and

the entitlement vector memory is operable to store a history of entitlement vectors.

23. The information handling apparatus according to claim 19 wherein:

the monitoring logic is configured to monitor resource usage, modify the one or more entitlement vectors based on the resource usage, and merge the modified one or more entitlement vectors into an evolving entitlement vector.

24. The information handling apparatus according to claim 19 further comprising:

one or more priority vectors configured to indicate priority for scheduling the one or more processes as a function of a combination of entitlement as specified by the one or more entitlement vectors and resource usage as specified by the one or more usage vectors.