METHOD AND APPARATUS FOR FINE GRAIN PERFORMANCE MANAGEMENT OF COMPUTER SYSTEMS

• US 20090055829A1
• Filed: 08/22/2008
• Published: 02/26/2009
• Est. Priority Date: 08/24/2007
• Status: Active Grant

• Current Assignee: Virtualmetrix, Inc.
• Original Assignee: Virtualmetrix, Inc.
• Inventors: Gibson, Gary A.
• Granted Patent: US 8,397,236 B2
• Time in Patent Office: Days
• US Class Current: 718/103
• 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 tasks to be executed by the processor system with each task having an associated task profile that specifies task parameters including a computed start time;

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

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

delaying the scheduling of the execution of the task when the value of the difference between the current real time and the calculated start time fails to meet a threshold criteria;

prioritizing the execution schedule of the task based on the task parameters including a configured priority;

monitoring the execution of the task to determine a monitored value related to the amount of work completed for the task; and

comparing the monitored value related to the amount of work completed to a parameter value related to the amount of work to be completed of the task and taking a responsive action when the difference between the monitored value related to the amount of work completed and the parameter value related to the amount of work to be completed meets a first threshold criteria, the amount of work to be completed is a task parameter that determines the expected work to be performed by the task when it is scheduled for execution.

2. The method of claim 1 further comprising tracking the credit associated with a task, wherein the credit for a task is accumulated at a rate equal to the product of work rate and elapsed time.

3. The method of claim 2, wherein the responsive action further comprises throttling the task from completing additional work until sufficient credit for performing work is accumulated.

4. The method of claim 1, wherein the responsive action comprises signaling the processor system that the current task has completed its scheduled work and the next selected task should replace the current task.

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

6. The method of claim 1, further comprising determining start time including a time between scheduled execution runs of the task.

7. The method of claim 2, further comprising controlling the allocation of execution resources to the one or more tasks by delaying the execution of the one or more tasks that have used their workload allocation until sufficient time has passed to accumulate credit for execution.

8. The method of claim 1, further comprising blocking the scheduling of the execution of the task when the task is waiting on the occurrence of an event.

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

10. The method of claim 1, wherein the task profile is selected from one of task priority, scheduling interval, work to be completed and maximum work to be completed.

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

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

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

14. The method of claim 1, wherein the one or more tasks are selected from the group of tasks 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 state machines.

15. The method of claim 6, further comprising selecting a task of the one or more tasks belonging to the same task priority class based on the smallest calculated start time.

16. The method of claim 1, further comprising allocating a 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.

17. The method of claim 1, further comprising monitoring the allocation of buffers to a task to determine a monitored buffer value related to one of a buffer size value and number of buffers.

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

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

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

21. The method of claim 1, wherein the processor system is a state machine.

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

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

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

a shaper module configured to compare a current real time and a computed start time associated with a task of a plurality of tasks to determine whether to select a task to be scheduled for execution, to select the task to be scheduled for execution when the value of the difference between the current real time and the calculated start time meets a threshold criteria and in accordance with the task parameters including a parameter indicating the task is not waiting on one of the occurrence and non-occurrence of an event, to delay the scheduling of the execution of the task when the value of the difference between the current real time and the calculated start time fails to meet a threshold criteria;

a scheduler module configured to prioritize the 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 the amount of work completed for the task and to compare the monitored value related to the amount of work completed to a parameter value related to the amount of work to be completed of the task so that a responsive action can be taken when the difference between the monitored value related to the amount of work completed and the parameter value related to the amount of work to be completed meets a first threshold criteria, the amount of work to be completed is a task parameter that determines the expected work to be performed by the task when it is scheduled for execution.

25. The system of claim 24, wherein the responsive action further comprises throttling the task from completing additional work until sufficient credit for performing work is accumulated.

26. The system of claim 25, wherein the credit is accumulated at a rate equal to the product of expected work rate and elapsed time.

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

28. The system of claim 27, 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.

29. The system of claim 28, 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.

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

31. The system of claim 30, 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.

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

33. A means for managing the performance of a processor system comprising:

a means for creating a list of task to be executed by the processor system with each task having an associated task profile that specifies task parameters including a computed start time;

a means for comparing a current real time with the computed start times associated with each of the tasks in the list of task;

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

a means for delaying the scheduling of the execution of the task when the value of the difference between the current real time and the calculated start time fails to meet a threshold criteria;

a means for prioritizing the execution schedule of the task based on the task parameters including a configured priority;

a means for monitoring the execution of the task to determine a monitored value related to the amount of work completed for the task; and

a means for comparing the monitored value related to the amount of work completed to a parameter value related to the amount of work to be completed of the task and taking a responsive action when the difference between the monitored value related to the amount of work completed and the parameter value related to the amount of work to be completed meets a first threshold criteria, the amount of work to be completed is a task parameter that determines the expected work to be performed by the task when it is scheduled for execution.

34. The means for managing the performance of a processor system claim of 33, further comprising a means for tracking the credit associated with a task, wherein the credit for a task is accumulated at a rate equal to the product of expected work rate and elapsed time.

35. The means for managing the performance of a processor system of claim 33, further comprising a means for determining scheduling interval including a time between scheduled execution run of the task.

36. The means for managing the performance of a processor system of claim 33, further comprising a means for controlling the allocation of execution resources to the one or more tasks by delaying the execution of the one or more tasks that have used their workload allocation until sufficient time has passed to accumulate credit for execution.

37. The means for managing the performance of a processor system of claim 33, further comprising a means for blocking the scheduling of the execution of the task when the task is waiting on the occurrence of an event.