Method and system for reactive scheduling

• US 8,701,121 B2
• Filed: 06/27/2011
• Issued: 04/15/2014
• Est. Priority Date: 06/27/2011
• Status: Active Grant

• Current Assignee: British Telecommunications PLC (BT Group PLC), Emirates Telecommunications Corporation, Khalifa University Of Science, Technology & Research
• Original Assignee: British Telecommunications PLC (BT Group PLC), Emirates Telecommunications Corporation, Khalifa University Of Science, Technology & Research
• Inventors: Saffre, Fabrice
• Primary Examiner(s): KESSLER, GREGORY AARON
• Application Number:
  US13/169,488
• Publication Number:
  US 20120331476A1
• Time in Patent Office: 1,023 Days
• Field of Search: None
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/506 Constraint
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 50/06 Energy or water supply

Abstract

A method and system of scheduling demands on a system having a plurality of resources are provided. The method includes the steps of, on receipt of a new demand for resources: determining the total resources required to complete said demand and a deadline for the completion of that demand; determining a plurality of alternative resource allocations which will allow completion of the demand before the deadline; for each of said alternative resource allocations, determining whether, based on allocations of resources to existing demands, said alternative resource allocation will result in a utilization of resources which is closer to an optimum utilization of said resources; and selecting, based on said determination, one of said alternative resource allocations to complete said demand so as to optimise utilization of resources of the system.

Claims

1. A method of scheduling demands on a system having a plurality of resources which can be allocated to said demands, the method including the steps of, on receipt of a new demand for resources:

a) determining the total resources required to complete said demand and a deadline for the completion of that demand;

b) determining a plurality of alternative resource allocations which will allow completion of the demand before the deadline;

c) for each of said alternative resource allocations, determining whether, based on allocations of resources to existing demands, said alternative resource allocation will result in a utilization of resources which is closer to an optimum utilization of said resources; and

d) selecting, based on said determination in step c), one of said alternative resource allocations to complete said demand so as to optimize utilisation of resources of the system; and

wherein the optimum utilisation of the resources of the system varies with time; and

wherein said alternative resource allocations include starting said demand at a plurality of different start times between the time of receipt of the demand and the deadline,

wherein said step c) of determining includes the sub-steps of;

c1) determining, for each of a plurality of timeslots between the time of receipt of the new demand and the deadline, whether, based on allocations of resources to existing demands, said alternative resource allocation will result in a utilization of resources in said timeslot which is closer to an optimum utilization for said timeslot; and

c2) collating the results of said determination in step c1) to generate a value indicating the desirability of each of said alternative resource allocations; and

wherein said step d) of selecting selects based on said generated values; and

wherein if a plurality of alternative resource allocations result in generation of said values which are equal, the step of selecting selects the alternative resource allocation which starts earliest in time.

2. The method according to claim 1 wherein said alternative resource allocations include the allocation of different amounts of said resources to said demand at a particular point in time.

3. The method according to claim 1 wherein said value is the proportion of said plurality of timeslots in which said alternative resource allocation will result in a utilization of resources which is closer to an optimum utilization for said timeslot.

4. The method according to claim 1 wherein said step d) of selecting selects the alternative resource allocation with the highest value.

5. The method according to claim 1 wherein said system comprises a computer system and said demands are tasks to be performed by said computer system.

6. The method according to claim 1 wherein said system comprises an electrical grid and said demands are loads on said grid.

7. A processor system having a plurality of resources which are allocatable to demands requested by one or more users of the system, the processor system further comprising a resource allocation device which is arranged to determine allocation of said resources to said demands, wherein, on receipt of a new demand for resources, the resource allocation device is arranged to:

a) determine the total resources required to complete said demand and a deadline for the completion of that demand;

b) determine a plurality of alternative resource allocations which will allow completion of the demand before the deadline;

c) for each of said alternative resource allocations, determine whether, based on allocations of resources to existing demands, said alternative resource allocation will result in a utilization of resources which is closer to an optimum utilization of said resources;

d) select, based on said determination in c) above, one of said alternative resource allocations to complete said demand so as to optimize utilisation of resources of the system,

and further wherein said system allocates resources to said demand according to the alternative resource allocation selected; and

wherein the optimum utilisation of the resources of the system varies with time; and

wherein said alternative resource allocations include starting said demand at a plurality of different start times between the time of receipt of the demand and the deadline; and

wherein said resource allocation device is further arranged to;

determine, for each of a plurality of timeslots between the time of receipt of the new demand and the deadline, whether, based on allocations of resources to existing demands, said alternative resource allocation will result in a utilization of resources in said timeslot which is closer to an optimum utilization for said timeslot;

collate the results of said determinations for the plurality of timeslots to generate a value indicating the desirability of each of said alternative resource allocations; and

select one of said alternative resource allocations based on said generated values; and

wherein if a plurality of alternative resource allocations result in generation of said values which are equal, the resource allocation device is arranged to select the alternative resource allocation which starts earliest in time.

8. The processor system according to claim 7 wherein said alternative resource allocations include the allocation of different amounts of said resources to said demand at a particular point in time.

9. The processor system according to claim 7 wherein said value is the proportion of said plurality of timeslots in which said alternative resource allocation will result in a utilization of resources which is closer to an optimum utilization for said timeslot.

10. The processor system according to claim 7 wherein said resource allocation device is arranged to select the alternative resource allocation with the highest value.

11. The processor system according to claim 7 wherein said system comprises a computer system and said demands are tasks to be performed by said computer system.

12. The processor system according to claim 11 wherein said resources are processor time.

13. The processor system according to claim 12 wherein the system comprises a computer system having multiple processor cores and the resources are the provision of one or more of said processor cores for a predetermined time period.

14. A method of scheduling demands on a system having a plurality of resources which can be allocated to said demands, the method including the steps of, on receipt of a new demand for resources:

a) determining the total resources required to complete said demand and a deadline for the completion of that demand;

b) determining a plurality of alternative resource allocations which will allow completion of the demand before the deadline;

c) for each of said alternative resource allocations, determining whether, based on allocations of resources to existing demands, said alternative resource allocation will result in a utilization of resources which is closer to an optimum utilization of said resources; and

d) selecting, based on said determination in step c), one of said alternative resource allocations to complete said demand so as to optimize utilisation of resources of the system;

wherein said alternative resource allocations include starting said demand at a plurality of different start times between the time of receipt of the demand and the deadline; and

wherein said step c) of determining includes the sub-steps of;

c1) determining, for each of a plurality of timeslots between the time of receipt of the new demand and the deadline, whether, based on allocations of resources to existing demands, said alternative resource allocation will result in a utilization of resources in said timeslot which is closer to an optimum utilization for said timeslot; and

c2) collating the results of said determination in step c1) to generate a value indicating the desirability of each of said alternative resource allocations;

wherein said step d) of selecting selects based on said generated values; and

wherein said value is the proportion of said plurality of timeslots in which said alternative resource allocation will result in a utilization of resources which is closer to an optimum utilization for said timeslot.

15. The method according to claim 14 wherein the optimum utilisation of the resources of the system varies with time.

16. The method according to claim 14 wherein said alternative resource allocations include the allocation of different amounts of said resources to said demand at a particular point in time.

17. The method according to claim 14 wherein said step d) of selecting selects the alternative resource allocation with the highest value.

18. The method according to claim 14 wherein if a plurality of alternative resource allocations result in generation of said values which are equal, the step of selecting selects the alternative resource allocation which starts earliest in time.

19. The method according to claim 14 wherein said system comprises a computer system and said demands are tasks to be performed by said computer system.

20. The method according to claim 14 wherein said system comprises an electrical grid and said demands are loads on said grid.

21. A processor system having a plurality of resources which are allocatable to demands requested by one or more users of the system, the processor system further comprising a resource allocation device which is arranged to determine allocation of said resources to said demands, wherein, on receipt of a new demand for resources, the resource allocation device is arranged to:

a) determine the total resources required to complete said demand and a deadline for the completion of that demand;

b) determine a plurality of alternative resource allocations which will allow completion of the demand before the deadline;

c) for each of said alternative resource allocations, determine whether, based on allocations of resources to existing demands, said alternative resource allocation will result in a utilization of resources which is closer to an optimum utilization of said resources;

d) select, based on said determination in c) above, one of said alternative resource allocations to complete said demand so as to optimize utilisation of resources of the system,

and further wherein said system allocates resources to said demand according to the alternative resource allocation selected; and

wherein said alternative resource allocations include starting said demand at a plurality of different start times between the time of receipt of the demand and the deadline;

wherein said resource allocation device is further arranged to;

determine, for each of a plurality of timeslots between the time of receipt of the new demand and the deadline, whether, based on allocations of resources to existing demands, said alternative resource allocation will result in a utilization of resources in said timeslot which is closer to an optimum utilization for said timeslot;

collate the results of said determinations for the plurality of timeslots to generate a value indicating the desirability of each of said alternative resource allocations; and

select one of said alternative resource allocations based on said generated values; and

wherein said value is the proportion of said plurality of timeslots in which said alternative resource allocation will result in a utilization of resources which is closer to an optimum utilization for said timeslot.

22. The processor system according to claim 21 wherein the optimum utilisation of the resources of the system varies with time.

23. The processor system according to claim 21 wherein said alternative resource allocations include the allocation of different amounts of said resources to said demand at a particular point in time.

24. The processor system according to claim 21 wherein said resource allocation device is arranged to select the alternative resource allocation with the highest value.

25. The processor system according to claim 21 wherein if a plurality of alternative resource allocations result in generation of said values which are equal, the resource allocation device is arranged to select the alternative resource allocation which starts earliest in time.

26. The processor system according to claim 21 wherein said system comprises a computer system and said demands are tasks to be performed by said computer system.

27. The processor system according to claim 26 wherein said resources are processor time.

28. The processor system according to claim 27 wherein the system comprises a computer system having multiple processor cores and the resources are the provision of one or more of said processor cores for a predetermined time period.

29. The processor system according to claim 21 wherein said system comprises an electrical grid and said demands are loads on said grid.