Transaction and task scheduler

• US 20070073693A1
• Filed: 09/16/2005
• Published: 03/29/2007
• Est. Priority Date: 09/16/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Harris, Tim, Peyton-Jones, Simon, Douceur, John, Howell, Jonathan
• Granted Patent: US 7,716,249 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance

Abstract

The described implementations relate to efficient scheduling of transactions and tasks. A memory location, address, or variable previously accessed by a blocked entity is observed periodically to determine an appropriate time to wake and retry the blocked entity. If the previous accessed memory location, address or variable changes state, a scheduler wakes the blocked entity and the blocked entity retries processing. A doubly-indexed data structure of blocked entities and memory locations associated with the blocked entities may be used to efficiently determine when a retrying execution would be profitable.

Claims

1. A method implemented by a computer device, comprising:

determining a transaction of a thread has blocked; and

retrying the blocked transaction based on a state of a memory previously accessed by the blocked entity.

2. The method according to claim 1, wherein retrying the blocked entity occurs if the state of the memory previously accessed by the blocked entity has changed.

3. The method according to claim 1, further comprising waiting for at least one transaction to commit before retrying the blocked entity.

4. The method according to claim 2, further comprising observing that a transaction has committed before retrying the blocked entity, the transaction that committed having changed the state of the memory previously accessed by the blocked entity.

5. An article of manufacture for use in programming a processor, the article of manufacture comprising at least one computer readable storage device including at least one computer program embedded therein that causes the processor to perform the method of claim 1.

6. A method implemented by a computer device, comprising:

accounting for entities that block in a computer device; and

retrying a blocked entity based on a reference to a data structure that is doubly-indexed.

7. The method according to claim 6, wherein retrying includes referencing two separate indexes of the doubly-indexed data structure before retrying the blocked entity.

8. The method according to claim 6, further comprising building the data structure that is doubly-indexed from information associated with entities that are blocked.

9. The method according to claim 6, wherein one index of the doubly-indexed data structure includes references that identify blocked transactions, and another index of the doubly-indexed data structure includes references to memory locations that blocked transactions attempted to access before blocking occurred.

10. The method according to claim 6, further comprising removing information from the data structure before retrying a blocked entity.

11. The method according to claim 10, wherein the removing includes removing information related to a blocked entity, and if the removed information completely eliminates a blocked entity and information associated with the blocked entity, retrying the blocked entity.

12. The method according to claim 6, wherein the blocked entity is one of a thread, a transaction, and a task having associated transactions.

13. An article of manufacture for use in programming a processor, the article of manufacture comprising at least one computer readable storage device including at least one computer program embedded therein that causes the processor to perform the method of claim 6.

14. A method implemented by a computer device, comprising:

maintaining a data structure that includes an index of blocked entities and an index of memory addresses that blocked entities attempted to access before being blocked; and

referencing the data structure after an entity commits to determine if a blocked entity may benefit from a retrying execution.

15. The method according to claim 14, further comprising adding blocked entities to the data structure as entities are blocked, wherein each added blocked entity includes a reference to one or more memory addresses that necessitated blocking the blocked entity.

16. The method according to claim 14, further comprising adding memory addresses to the data structure as entities are blocked, wherein each added memory address includes a reference to one or more blocked entity that attempted to access the added memory address before the blocked entity blocked.

17. An article of manufacture for use in programming a processor, the article of manufacture comprising at least one computer readable storage device including at least one computer program embedded therein that causes the processor to perform the method of claim 14.

18. The method according to claim 14, wherein the blocked entities are thread transactions.

19. The method according to claim 14, further comprising removing a blocked entity and memory addresses referenced by the blocked entity from the index of blocked entities and the index of memory addresses.

20. The method according to claim 19, further comprising retrying the blocked entity after removing the blocked entity and the memory addresses referenced by the blocked entity from the index of blocked entities and the index of memory addresses.