Scheduling execution contexts with critical regions

• US 9,304,831 B2
• Filed: 09/29/2008
• Issued: 04/05/2016
• Est. Priority Date: 09/29/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Messmer, William R.
• Primary Examiner(s): Faherty, Corey S
• Application Number:
  US12/240,319
• Publication Number:
  US 20100083258A1
• Time in Patent Office: 2,745 Days
• Field of Search: 718/1, 718/102
• US Class Current: 1/1
• CPC Class Codes: G06F 9/5077 Logical partitioning of resources; Management or configuration of virtualized resources specific details on emulation or internal functioning of virtual machines G06F9/455
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A scheduler in a process of a computer system detects an execution context that blocked from outside of the scheduler while in a critical region. The scheduler ensures that the execution context resumes execution on the processing resource of the scheduler on which the execution context blocked when the execution context becomes unblocked. The scheduler also prevents another execution context from entering a critical region on the processing resource prior to the blocked execution context becoming unblocked and exiting the critical region.

Claims

1. A method performed by a scheduler of a process executing on a computer system, the method comprising:

detecting that a first execution context preempted and blocked by an entity other than the scheduler in a first critical region while executing on a processing resource of the scheduler, the first critical region is a set of instructions in the first execution context whose execution becomes contingent on data corresponding to the processing resource; and

ensuring that the first execution context resumes execution on the processing resource in response to an indication to the scheduler from the entity that caused the block indicating the first execution context becoming unblocked and without the scheduler providing any knowledge of the preemption to the first execution context.

2. The method of claim 1 further comprising:

preventing a second execution context from entering a second critical region on the processing resource subsequent to the first execution context blocking and prior to resuming execution of the first execution context, the second critical region is a set of instructions in the second execution context whose execution becomes contingent on data corresponding to the processing resource.

3. The method of claim 1 further comprising:

setting a critical region indicator corresponding to the first execution context in response to the first execution context entering the first critical region.

4. The method of claim 3 wherein the first execution context blocks in response to a block from outside of the scheduler.

5. The method of claim 4 further comprising:

clearing the critical region indicator in response to the first execution context exiting the first critical region subsequent to resuming the first execution context.

6. The method of claim 1 further comprising:

storing an indicator that identifies the processing resource in response to the first execution context blocking in the first critical region.

7. The method of claim 1 further comprising:

providing a signal to the scheduler in response to the first execution context becoming unblocked.

8. The method of claim 1 wherein the first critical region executes to select a second execution context for execution on the processing resource.

9. The method of claim 1 wherein the processing resource includes a virtual processor that maps to a hardware thread.

10. A computer readable storage medium storing computer-executable instructions that, when executed by a computer system, perform a method comprising:

entering a critical region of a first execution context executing on a first processing resource of a scheduler in a process of the computer system, the critical region is a set of instructions in the first execution context whose execution becomes contingent on data corresponding to the first processing resource;

setting a first indicator corresponding to the first execution context in response to entering the critical region;

blocking in response to a preemption and block by an entity other than the scheduler subsequent to setting the first indicator; and

ensuring that the first execution context resumes execution on the first processing resource in response to an indication to the scheduler from the entity that caused the block indicating the first execution context has become unblocked and without the scheduler providing any knowledge of the preemption to the first execution context.

11. The computer readable storage medium of claim 10, the method further comprising:

storing a second indicator that identifies the first processing resource in response to blocking.

12. The computer readable storage medium of claim 11, the method further comprising:

exiting the critical region of the first execution context subsequent to resuming execution of the first execution context on the first processing resource; and

clearing the first indicator in response to exiting the critical region.

13. The computer readable storage medium of claim 12, the method further comprising:

setting the first indicator by incrementing the first indicator; and

clearing the first indicator by decrementing the first indicator.

14. The computer readable storage medium of claim 10, the method further comprising:

blocking in response to the first processing resource not being available to enter the critical region prior to entering the critical region.

15. The computer readable storage medium of claim 10, the method further comprising:

moving to a second processing resource in response to the first processing resource not being available to enter the critical region.

16. A method performed by a scheduler of a process executing on a computer system, the method comprising:

identifying a first execution context that preempted and blocked by an entity other than the scheduler in a first critical region while executing on a processing resource of the scheduler, the first critical region is a set of instructions in the first execution context whose execution becomes contingent on data corresponding to the processing resource; and

resuming execution of the first execution context on the processing resource in response to an indication to the scheduler from the entity that caused the block indicating the first execution context has become unblocked and without the scheduler providing any knowledge of the preemption to the first execution context and prior to allowing a second critical region of a second execution context to execute on the processing resource, the second critical region is a set of instructions in the second execution context whose execution becomes contingent on data corresponding to the processing resource.

17. The method of claim 16 wherein the first critical region holds a lock.

18. The method of claim 16 wherein the first execution context blocks in response to a page fault.

19. The method of claim 16 further comprising:

preventing the execution context from entering the second critical region on the processing resource subsequent to the first execution context blocking and prior to resuming execution of the first execution context.

20. The method of claim 16 wherein the processing resource includes a virtual processor that maps to a hardware thread.