Credit based performance managment of computer systems

• US 8,397,236 B2
• Filed: 08/22/2008
• Issued: 03/12/2013
• Est. Priority Date: 08/24/2007
• Status: Expired due to Fees

• Current Assignee: Virtualmetrix, Inc.
• Original Assignee: Virtualmetrix, Inc.
• Inventors: Gibson, Gary A.
• Primary Examiner(s): An, Meng
• Assistant Examiner(s): Arcos, Caroline H
• Application Number:
  US12/197,165
• Publication Number:
  US 20090055829A1
• Time in Patent Office: 1,663 Days
• Field of Search: 718/100, 718/102, 718/103, 718/104
• US Class Current: 718/102
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A system and method to control the allocation of processor (or state machine) execution resources to individual tasks executing in computer systems is described. By controlling the allocation of execution resources, to all tasks, each task may be provided with throughput and response time guarantees. This control is accomplished through workload metering shaping which delays the execution of tasks that have used their workload allocation until sufficient time has passed to accumulate credit for execution (accumulate credit over time to perform their allocated work) and workload prioritization which gives preference to tasks based on configured priorities.

Claims

1. A method of managing the performance of a processor system comprising:

creating a list of processor tasks to be executed by one or more processors of the processor system with each task having an associated task profile that specifies task parameters including a calculated start time, wherein each task comprises a set of instructions to be executed by at least one processor of the processor system and wherein the calculated start time characterizes a time at which the corresponding task should be next scheduled to be executed by at least one of the processors;

tracking credit for each of the tasks in the lists of tasks, wherein credit is accumulated at a rate equal to a corresponding product of work rate and elapsed time and credit for the task is reduced when the task is selected for execution by the corresponding work completed;

comparing a current real time with the calculated start times associated with each of the tasks in the list of tasks;

selecting at least one first task to be scheduled for execution from the list of tasks when a value of a difference between the current real time and the calculated start time for the at least one first task meets a first threshold criteria and in accordance with the task parameters including a parameter indicating the at least one first task is not dependent on one of an occurrence and non-occurrence of an event;

monitoring the execution of the at least one first task to determine a monitored value related to an amount of work completed for the at least one first task;

comparing the monitored value related to the amount of work completed to a value based on the tracked credit that is related to an amount of work to be completed by the at least one first task; and

throttling the at least one first task from completing additional work when a difference between the monitored value related to the amount of work completed and the value related to the amount of work to be completed meets a second threshold criteria until a pre-defined amount of credit for performing work is accumulated.

2. The method of claim 1, further comprising:

signaling the processor system that the at least one first task has completed its scheduled work and a next selected task should replace the at least one first task.

3. The method of claim 2, wherein signaling the processor system comprises sending an interrupt to an instruction fetch/branch unit of the processor system.

4. The method of claim 1, further comprising determining start time including a time between scheduled execution runs of the at least one first task.

5. The method of claim 4, wherein the at least one first task has a smallest calculated start time as compared to other tasks having a same task priority class.

6. The method of claim 1, further comprising controlling allocation of processing resources to the at least one first task by delaying the execution of one or more other tasks that have used their respective workload allocation until sufficient time has passed to accumulate credit for execution above a pre-defined threshold.

7. The method of claim 1, further comprising blocking the scheduling of execution of at least one second task when the at least one second task is waiting on the occurrence of an event.

8. The method of claim 1, wherein the event includes waiting for arrival of one of a message from another task and data from an external input-output device.

9. The method of claim 1, wherein the task profile comprises one or more of:

task priority, work rate, scheduling interval, work to be completed and maximum work to be completed.

10. The method of claim 1, further comprising managing execution of resources by scheduling the tasks based on completing a certain amount of work periodically.

11. The method of claim 1, wherein the amount of work completed is a measure of one of data transference and processor instructions completed.

12. The method of claim 1, further comprising setting the task parameters of the one or more tasks by control software, the task parameters being predetermined during the process of mapping the corresponding task to a target computer system.

13. The method of claim 1, wherein the tasks are selected from a group consisting of:

computer processes, instances of computer programs that are being executed, threads of execution including one or more simultaneously, pseudo-simultaneously, executing instances of a computer program closely sharing resources that execute within one or more processors, virtual machines including virtual execution environments on one or more processors, or state machine tasks.

14. The method of claim 1, further comprising allocating at least one buffer occupancy value to each task and storing the buffer occupancy value as a parameter of the associated task profile, the buffer occupancy value related to one of a buffer size value and number of buffers.

15. The method of claim 14, further comprising monitoring allocation of buffers on behalf of a task to determine a monitored buffer value related to one of a buffer size value and number of buffers.

16. The method of claim 15, further comprising comparing the monitored buffer value to a buffer occupancy value associated with a task and taking a responsive action when a difference between the monitored buffer value and the buffer occupancy value meets a second threshold criteria.

17. The method of claim 16, wherein the responsive action includes one of replacing the buffers of the task and preventing the allocation of new buffers.

18. The method of claim 1, wherein the processor system is a state machine, and the tasks are state machine tasks.

19. The method of claim 1, wherein the start time is calculated continuously or when the task is no longer being executed.

20. The method of claim 1, wherein the task list can be created dynamically, with tasks added and subtracted over time.

21. The method of claim 1, further comprising:

prioritizing an execution schedule for at least a portion of the tasks based on task parameters including a configured priority.

22. The method of claim 1, further comprising:

limiting an amount of credit associated with a task by a maximum work to be completed parameter.

23. A processor system of managing the performance of a computer system comprising:

one or more processors

memory storing instructions for execution by the one or more data processors, the instructions implementing;

a shaper module configured to track credit for each tasks of a plurality of tasks, wherein credit is accumulated at a rate equal to a corresponding product of work rate and elapsed time and credit for the task is reduced when the task is selected for execution by the corresponding work completed, wherein the shaper module is further configured to compare a current real time and a computed start time associated with each task to determine whether to select a task to be scheduled for execution, wherein tasks are scheduled for execution when a value of a difference between a current real time and a calculated start time meets a first threshold criteria and in accordance with task parameters including a parameter indicating the corresponding task is not dependent on one of an occurrence and non-occurrence of an event, wherein each task comprises a set of instructions to be executed by at least one of the one or more processors of the processor system and wherein the calculated start time characterizes a time at which the corresponding task should be next scheduled to be executed by at least one of the one or more processors;

a scheduler module configured to prioritize an execution schedule of the plurality of tasks based on the task parameters including a configured priority after the tasks have been selected to be scheduled by the shaper module; and

a metering module configured to monitor the execution of tasks being executed by the computer system to determine a monitored value related to an amount of work completed by the task and to compare the monitored value related to an amount of work completed to a value based on the tracked credit that is related to the amount of work to be completed by the task so that a responsive action can be taken, wherein the responsive action comprises selectively allocating or de-allocating processing resources provided by the one or more processors for the corresponding task, wherein the selectively allocated or de-allocating processing resources comprises;

throttling a task from completing additional work when a difference between the corresponding monitored value related to the amount of work completed and the corresponding value related to the amount of work to be completed meets a second threshold criteria until a pre-defined amount of credit for performing work is accumulated.

24. The system of claim 23, further comprising an instruction cache configured to store instructions received from a system memory.

25. The system of claim 24, further comprising an instruction fetch/branch unit configured to receive instructions from the instruction cache and to receive an interrupt signal to cause the processor system to move to execute a different task selected by the scheduler.

26. The system of claim 25, wherein the metering module is further configured to receive the monitored value from the instruction fetch/branch unit, the monitored value measured in instructions completed by the instruction fetch/branch unit.

27. The system of claim 23 further comprising a data cache configured to store data items that have been recently accessed from a system memory.

28. The system of claim 27, further comprising a load/store unit configured to access the data cache to perform load and store operations and to generate the monitored value to be received by the metering module, the monitored value measured in memory operations.

29. The system of claim 23, wherein the metering module when used to monitor memory operations is configured to account for memory operations to/from certain addresses.

30. An apparatus for managing the performance of a processor system comprising:

one or more processors;

memory storing instructions, which when executed by the one or more processors result in operations comprising;

creating a list of processor tasks to be executed by one of the one or more processors of the processor system with each task having an associated task profile that specifies task parameters including a calculated start time, wherein each task comprises a set of instructions to be executed by at least one of the one or more processors of the processor system and wherein the calculated start time characterizes a time at which the corresponding task should be next scheduled to be executed by at least one of the processors;

tracking credit for each of the tasks in the list of tasks, wherein credit is accumulated at a rate equal to a corresponding product of work rate and elapsed time, and credit for the task is reduced when the task is selected for execution by the corresponding work completed;

comparing a current real time with the calculated start times associated with each of the tasks in the list of tasks;

selecting at least one first task to be scheduled for execution from the list of tasks when a value of a difference between the current real time and the calculated start of a task time for the at least one first task meets a first threshold criteria and in accordance with the task parameters including a parameter indicating the at least one first task is not dependent on one of an occurrence and non-occurrence of an event;

for prioritizing an execution schedule for the tasks based on the task parameters including a configured priority;

monitoring the execution of the at least one first task to determine a monitored value related to an amount of work completed for the at least one first task;

comparing the monitored value related to the amount of work completed to a value based on the tracked credit that is related to an amount of work to be completed by the at least one first task; and

throttling the at least one first task from completing additional work when a difference between the monitored value related to the amount of work completed and the value related to the amount of work to be completed meets a second threshold criteria until a pre-defined amount of credit for performing work is accumulated.

31. The apparatus for managing the performance of a processor system of claim 30, wherein the operations further comprise determining scheduling interval including a time between scheduled execution run of the at least one first task.

32. The apparatus for managing the performance of a processor system of claim 30, wherein the operations further comprise controlling allocation of processing resources to the at least one tasks by delaying the execution of one or more other tasks that have used their workload allocation until sufficient time has passed to accumulate credit for execution.

33. The apparatus for managing the performance of a processor system of claim 30, wherein the operations further comprise blocking the scheduling of execution of at least one second task when the at least one second task is waiting on the occurrence of an event.

34. A method comprising:

scheduling a plurality of processor tasks for execution by one or more processors of a processors system, wherein each task comprises a set of instructions to be executed by at least one processor of the processor system and wherein each task has an associated task profile that specifies task parameters including a calculated start time that characterizes a time at which the corresponding task should be next scheduled to be executed by at least one of the processors, the scheduling;

tracking credit for each of the tasks in the list of tasks, wherein credit is accumulated at a rate equal to a corresponding product of work rate and elapsed time, and credit for the task is reduced when the task is selected for execution by the corresponding work completed;

comparing a current real time with the calculated start times associated with each of the tasks in the list of tasks;

selecting at least one first task to be scheduled for execution from the list of tasks when a value of a difference between the current real time and the calculated start time for the at least one first task meets a first threshold criteria and in accordance with the task parameters including a parameter indicating the at least one first task is not dependent on one of an occurrence and non-occurrence of an event;

monitoring execution of the plurality of tasks to determine, for each executing task, a monitored value related to an amount of work completed for the task, wherein the amount of work to be completed is a task parameter that determines expected work to be performed by the corresponding task when it is scheduled for execution; and

selectively allocating, or de-allocating processing resources provided by the one or more processors for each task based on a comparison of the monitored value related to the amount of work completed to a value based on the tracked credit that is related to an amount of work to be completed by the corresponding task, wherein the selectively allocating, or de-allocation processors resources comprises;

throttling the at least one first task from completing additional work when a difference between the monitored value related to the amount of work completed and the value related to the amount of work to be completed meets a second threshold criteria until a pre-defined amount of credit for performing work is accumulated.

35. A computer program product comprising a non-transitory computer storage medium storing instructions, which when executed by at least one or more processors of a processor system, result in operations comprising:

creating a list of processor tasks to be executed by the one or more processors of the processor system with each task having an associated task profile that specifies task parameters including a calculated start time, wherein each task comprises a set of instructions to be executed by at least one processor of the processor system and wherein the calculated start time characterizes a time at which the corresponding task should be next scheduled to be executed by at least one of the processors;

tracking credit for each of the tasks in the lists of tasks, wherein credit is accumulated at a rate equal to a corresponding product of work rate and elapsed time and credit for the task is reduced when the task is selected for execution by the corresponding work completed;

comparing a current real time with the calculated start times associated with each of the tasks in the list of tasks;

selecting at least one first task to be scheduled for execution from the list of tasks when a value of a difference between the current real time and the calculated start time for the at least one first task meets a first threshold criteria and in accordance with the task parameters including a parameter indicating the at least one first task is not dependent on one of an occurrence and non-occurrence of an event;

monitoring the execution of the at least one first task to determine a monitored value related to an amount of work completed for the at least one first task;

comparing the monitored value related to the amount of work completed to a value based on the tracked credit that is related to an amount of work to be completed by the at least one first task; and

throttling the at least one first task from completing additional work when a difference between the monitored value related to the amount of work completed and the value related to the amount of work to be completed meets a second threshold criteria until a pre-defined amount of credit for performing work is accumulated.

36. The computer program product of claim 35, wherein the operations further comprise:

signaling the processor system that the at least one first task has completed its scheduled work and a next selected task should replace the at least one first task.

37. The computer program product of claim 36, wherein signaling the processor system comprises sending an interrupt to an instruction fetch/branch unit of the processor system.

38. The computer program product of claim 35, wherein the operations further comprise:

determining start time including a time between scheduled execution runs of the at least one first task.

39. The computer program product of claim 38, wherein the at least one first task has a smallest calculated start time as compared to other tasks having a same task priority class.

40. The computer program product of claim 35, wherein the operations further comprise:

controlling allocation of processing resources to the at least one first task by delaying the execution of one or more other tasks that have used their respective workload allocation until sufficient time has passed to accumulate credit for execution above a pre-defined threshold.

41. The computer program product of claim 35, wherein the operations further comprise:

blocking the scheduling of execution of at least one second task when the at least one second task is waiting on the occurrence of an event.

42. The computer program product of claim 35, wherein the event includes waiting for arrival of one of a message from another task and data from an external input-output device.

43. The computer program product of claim 35, wherein the task profile comprises one or more of:

task priority, work rate, scheduling interval, work to be completed and maximum work to be completed.

44. The computer program product of claim 35, wherein the operations further comprise:

managing execution of resources by scheduling the tasks based on completing a certain amount of work periodically.

45. The computer program product of claim 35, wherein the amount of work completed is a measure of one of data transference and processor instructions completed.

46. The computer program product of claim 35, wherein the operations further comprise:

setting the task parameters of the one or more tasks by control software, the task parameters being pre-determined during the process of mapping the corresponding task to a target computer system.

47. The computer program product of claim 35, wherein the tasks are selected from a group consisting of:

computer processes, instances of computer programs that are being executed, threads of execution including one or more simultaneously, pseudo-simultaneously, executing instances of a computer program closely sharing resources that execute within one or more processors, virtual machines including virtual execution environments on one or more processors, or state machine tasks.

48. The computer program product of claim 35, wherein the operations further comprise:

allocating at least one buffer occupancy value to each task and storing the buffer occupancy value as a parameter of the associated task profile, the buffer occupancy value related to one of a buffer size value and number of buffers.

49. The computer program product of claim 48, wherein the operations further comprise:

monitoring allocation of buffers on behalf of a task to determine a monitored buffer value related to one of a buffer size value and number of buffers.

50. The computer program product of claim 49, wherein the operations further comprise:

comparing the monitored buffer value to a buffer occupancy value associated with a task and taking a responsive action when a difference between the monitored buffer value and the buffer occupancy value meets a second threshold criteria.

51. The computer program product of claim 50, wherein the responsive action includes one of replacing the buffers of the task and preventing the allocation of new buffers.

52. The computer program product of claim 35, wherein the processor system is a state machine, and the tasks are state machine tasks.

53. The computer program product of claim 35, wherein the start time is calculated continuously or when the task is no longer being executed.

54. The computer program product of claim 35, wherein the task list can be created dynamically, with tasks added and subtracted over time.

55. The computer program product of claim 35, wherein the operations further comprise:

prioritizing an execution schedule for at least a portion of the tasks based on task parameters including a configured priority.

56. The computer program product of claim 35, wherein the operations further comprise:

limiting an amount of credit associated with a task by a maximum work to be completed parameter.