Tracking operating system process and thread execution and virtual machine execution in hardware or in a virtual machine monitor

• US 20030037089A1
• Filed: 08/15/2001
• Published: 02/20/2003
• Est. Priority Date: 08/15/2001
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Schoenberg, Sebastian, Neiger, Gilbert, Uhlig, Richard, Jeyasingh, Stalinselvaraj, Kagi, Alain, Cota-Robles, Erik, Kozuch, Michael
• Granted Patent: US 7,191,440 B2
• Time in Patent Office: Days
• US Class Current: 718/1
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 2009/45566 Nested virtual machines
• CPC Class Codes: G06F 2009/45591 Monitoring or debugging support
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 2201/86 Event-based monitoring
• CPC Class Codes: G06F 2201/88 Monitoring involving counting
• CPC Class Codes: G06F 9/45541 Bare-metal, i.e. hypervisor runs directly on hardware
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

Transitions among schedulable entities executing in a computer system are tracked in computer hardware or in a virtual machine monitor. In one aspect, the schedulable entities are operating system processes and threads, virtual machines, and instruction streams executing on the hardware. In another aspect, the schedulable entities are processes or threads executing within the virtual machines under the control of the virtual machine monitor. The virtual machine monitor derives scheduling information from the transitions to enable a virtual machine system to guarantee adequate scheduling quality of service to real-time applications executing in virtual machines that contain both real-time and non-real-time applications. In still another aspect, a parent virtual machine monitor in a recursive virtualization system can use the scheduling information to schedule a child virtual machine monitor that controls multiple virtual machines.

Claims

1. A method comprising:

trapping, by a processor, a change in execution among schedulable entities; and

tracking an execution of a schedulable entity that is being switched in for execution as a result of the change in execution.

2. The method of claim 1, wherein the tracking is performed by a privileged entity and further comprising:

calculating, by the privileged entity, an estimated resource requirement for the schedulable entity that is being switched in for execution from the tracking of a previous execution of the schedulable entity; and

scheduling, by the privileged entity, the schedulable entity that is being switched in for execution according to its estimated resource requirement.

3. The method of claim 2, wherein the privileged entity is a virtual machine monitor and the schedulable entities are selected from the group consisting of processes, threads, operating systems, virtual machines, and child virtual machine monitors.

4. The method of claim 2, wherein the virtual machine monitor comprises:

an idle detector to receive notice from the processor of the change in execution and to derive a measured value for a schedulable entity that is being switched out of execution;

a proportional integral derivative (PID) controller logically coupled to the idle detector to receive the measured value and to calculate the estimated resource requirement required by the schedulable entity that is being switched out of execution; and

a scheduler logically coupled to the PID controller to receive the estimated resource requirement and to determine a schedule of execution for the schedulable entity that is being switched out of execution.

5. The method of claim 2, wherein calculating an estimated resource requirement comprises:

assigning an initial value as the estimated resource requirement for the schedulable entity that is being switched in for execution;

reducing the estimated resource requirement for the schedulable entity if the schedulable entity completes execution before the estimated resource requirement is exhausted; and

increasing the estimated resource requirement for the schedulable entity if the schedulable entity does not complete execution before the estimated resource requirement is exhausted.

6. The method of claim 2 further comprising:

initiating, by the privileged entity, the change in execution.

7. The method of claim 6, wherein the tracking of the execution is performed as part of the change in execution initiated by the privileged entity.

8. The method of claim 2 further comprising:

initiating, by the processor, the change in execution if the change in execution is being requested by the privileged entity.

9. The method of claim 1, wherein trapping a change in execution comprises:

detecting an instruction to change a state register that identifies a schedulable entity.

10. The method of claim 9 further comprising:

comparing, by the processor, the state register that identifies the schedulable entity being switched in for execution with a state match register that identifies a schedulable entity that is to be tracked, wherein the schedulable entity being switched into execution is tracked by the processor if the state register and the state match register match.

11. The method of claim 1, wherein trapping a change in execution comprises:

detecting an instruction to change between privileged and non-privileged modes.

12. The method of claim 1, wherein the schedulable entities are selected from the group consisting of operating system processes, operating system threads, virtual machines, and instruction streams to be executed by the processor.

13. A machine-readable medium providing instructions, which when executed by a machine, causes the machine to perform operations comprising:

trapping, by a processor, a change in execution among schedulable entities; and

tracking an execution of a schedulable entity that is being switched in for execution as a result of the change in execution.

14. The machine-readable medium of claim 13, wherein the tracking is performed by a privileged entity and further comprising:

calculating, by the privileged entity, an estimated resource requirement for the schedulable entity that is being switched in for execution based on the tracking of a previous execution of the schedulable entity; and

scheduling, by the privileged entity, the schedulable entity that is being switched in for execution according to the estimated resource requirement.

15. The machine-readable medium of claim 14, wherein the privileged entity is a virtual machine monitor and the schedulable entities are selected from the group consisting of processes, threads, operating systems, virtual machines, and child virtual machine monitors.

16. The machine-readable medium of claim 14, wherein the virtual machine monitor comprises:

an idle detector to receive notice from the processor of the change in execution and to derive a measured value for a schedulable entity that is being switched out of execution;

a proportional integral derivative (PID) controller logically coupled to the idle detector to receive the measured value and to calculate the estimated resource requirement required by the schedulable entity that is being switched out of execution; and

a scheduler logically coupled to the PID controller to receive the estimated resource requirement and to determine a schedule of execution for the schedulable entity that is being switched out of execution.

17. The machine-readable medium of claim 14, wherein calculating an estimated resource requirement comprises:

assigning an initial value as the estimated resource requirement for the schedulable entity that is being switched in for execution;

reducing the estimated resource requirement for the schedulable entity if the schedulable entity completes execution before the estimated resource requirement is exhausted; and

increasing the estimated resource requirement for the schedulable entity if the schedulable entity does not complete execution before the estimated resource requirement is exhausted.

18. The machine-readable medium of claim 14 further comprising:

initiating, by the privileged entity, the change in execution.

19. The machine-readable medium of claim 18, wherein the tracking of the execution is performed as part of the change in execution initiated by the privileged entity.

20. The machine-readable medium of claim 14 further comprising:

initiating, by the processor, the change in execution if the change in execution is being requested by the privileged entity.

21. The machine-readable medium of claim 13, wherein trapping a change in execution comprises:

detecting an instruction to change a state register that identifies a schedulable entity.

22. The machine-readable medium of claim 13 further comprising:

comparing, by the processor, the state register that identifies the schedulable entity being switched in for execution with a state match register that identifies a schedulable entity that is to be tracked, wherein the schedulable entity being switched into execution is tracked by the processor if the state register and the state match register match.

23. The machine-readable medium of claim 13, wherein trapping a change in execution comprises:

detecting an instruction to change between privileged and non-privileged modes.

24. The machine-readable medium of claim 13, wherein the schedulable entities are selected from the group consisting of operating system processes, operating system threads, virtual machines, and instruction streams to be executed by the processor.

25. An apparatus comprising:

a memory;

a processing unit coupled to the memory and configured to trap to a privileged entity, a change in execution among schedulable entities; and

the privileged entity executed from the memory to cause the processing unit to track an execution of a schedulable entity that is being switched in for execution as a result of the change in execution.

26. The apparatus of claim 25, wherein the privileged entity further causes the processing unit to calculate an estimated resource requirement for the schedulable entity that is being switched in for execution based on the tracking of a previous execution of the schedulable entity and to schedule the schedulable entity that is being switched in for execution according to the estimated resource requirement.

27. The apparatus of claim 26, wherein the privileged entity is a virtual machine monitor and the schedulable entities are selected from the group consisting of processes, threads, operating systems, virtual machines, and child virtual machine monitors.

28. The apparatus of claim 27, wherein the virtual machine monitor comprises:

an idle detector to receive notice from the processing unit of the change in execution and to derive a measured value for a schedulable entity that is being switched out of execution;

a proportional integral derivative (PID) controller logically coupled to the idle detector to receive the measured value and to calculate the estimated resource requirement for the schedulable entity that is being switched out of execution; and

a scheduler logically coupled to the PID controller to receive the estimated resource requirement and to determine a schedule of execution for the schedulable entity that is being switched out of execution.

29. The apparatus of claim 26, wherein the privileged entity further causes the processing unit to calculate an estimated machine resource requirement by:

assigning an initial value as the estimated resource requirement for the schedulable entity;

reducing the estimated resource requirement for the schedulable entity if the schedulable entity completes execution before the estimated resource requirement is exhausted; and

increasing the estimated resource requirement for the schedulable entity if the schedulable entity does not complete execution before the estimated resource requirement is exhausted.

30. The apparatus of claim 25, wherein the processing unit is further configured to trap a change in execution by detecting an instruction to change a state register that identifies a schedulable entity.

31. The apparatus of claim 25, wherein the processing unit is further configured to trap a change in execution by detecting an instruction to change between privilege and non-privilege modes.

32. The apparatus of claim 25, wherein the privileged entity further causes the processing unit to initiate the change in execution.

33. The apparatus of claim 32, wherein the privileged entity further causes the processor to track the execution as part of the change in execution initiated by the privileged entity.

34. The apparatus of claim 25, wherein the processing unit is further configured to initiate the change in execution if the change in execution is being requested by the privileged entity.

35. An apparatus comprising:

a processing unit configured to trap a change in execution among schedulable entities, to compare a state register that identifies the schedulable entity being switched in for execution with a state match register that identifies a schedulable entity that is to be tracked, and to track the schedulable entity being switched into execution if the state register and the state match register match.

36. The apparatus of claim 35, wherein the schedulable entities are selected from the group consisting of operating system processes, operating system threads, virtual machines, and instruction streams to be executed by the processing unit.