Transaction and task scheduler

• US 7,716,249 B2
• Filed: 09/16/2005
• Issued: 05/11/2010
• Est. Priority Date: 09/16/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Peyton-Jones, Simon, Harris, Tim L., Douceur, John R., Howell, Jonathan R.
• Primary Examiner(s): Mahmoudi; Tony
• Assistant Examiner(s): Truong; Dennis
• Application Number:
  US11/229,053
• Publication Number:
  US 20070073693A1
• Time in Patent Office: 1,698 Days
• Field of Search: 707/10, 707/3, 707/8, 711/1, 711/145, 718/102
• US Class Current: 707/796
• 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, the method comprising:

determining a transaction of a first thread being executed is blocked from accessing a memory of the computing device by a second thread;

waiting for at least one transaction of the second thread to commit;

detecting that the at least one transaction has committed data to the memory, the at least one transaction having changed the content of the memory that the transaction of the first thread has been blocked from accessing, wherein the detecting includes (1) referring to an accessed address index of a doubly-indexed data structure that lists each memory address that is blocked from being accessed by the transaction of the first thread, and (2) referring to a blocked transaction index of the doubly-indexed data structure that indexes each blocked transaction and corresponding memory addresses of each blocked transaction;

determining the memory is available based on the detecting that the at least one transaction has committed data to the memory;

initiating execution of the blocked transaction of the first thread based on the determining that the memory is available, wherein the initiating includes first referencing the accessed address index to identify each memory location affected by the at least one committed transaction, and then rescheduling each blocked transaction in the blocked transaction index; and

executing the blocked transaction of the first thread.

2. 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.

3. A method implemented by a computer device, the method comprising:

accounting for blocked entities in a computer device, wherein each blocked entity is one of a thread, a thread transaction, or a task having one or more associated transactions; and

retrying an execution of a blocked entity based on a reference to a doubly-indexed data structure, wherein;

one index of the doubly-indexed data structure includes references identifying each of the blocked entities and corresponding memory addresses to be accessed by the respective blocked entity, and another index of the doubly-indexed data structure includes references to each memory location that each blocked entity attempted to access wherein blocking occurred; and

a blocked entity is an entity blocked from accessing a memory address of the computer device due to the memory address being in use by a second entity,

wherein the retrying includes referencing each of the two indexes of the doubly-indexed data structure before retrying the blocked entity;

first referencing the another index to identify each memory location affected by a committed transaction, and then rescheduling each of the blocked entities in the one index of the doubly-indexed data structure that includes references identifying each of the blocked entities and corresponding memory addresses to be accessed by the respective blocked entity.

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

5. The method according to claim 3, further comprising removing information from the doubly-indexed data structure before retrying the execution of the blocked entity.

6. The method according to claim 5, 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 execution of the blocked entity.

7. 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 3.

14. The method according to claim 3, the method further comprising:

adding memory addresses to the another index of the data structure as entities are blocked, wherein each added memory address includes a reference to one or more blocked entities that attempted to access the added memory address before the one or more blocked entities were blocked;

referencing the doubly-indexed data structure after an entity commits to determine a benefit for the blocked entity to retry execution;

removing information related to the blocked entity; and

if the removed information completely eliminates the blocked entity and information associated with the blocked entity from the data structure, retrying the execution of the blocked entity.

15. The method according to claim 14, wherein the removing information related to the blocked entity includes removing, by a thread manager, any read transactions from a read transaction record and removing, by the thread manager, any write transactions from a write transaction record.

8. A method implemented by a computer device, the method comprising:

maintaining a data structure comprising;

an index of entities blocked from accessing memory addresses of the computing device wherein each of the entities comprises a thread, a thread transaction, and a task having associated transactions, and wherein each entry of the index of entities comprises memory addresses corresponding to and affected by each respective blocking transaction; and

an index of memory addresses, and corresponding blocked entities, that blocked entities attempted to access before being blocked;

referencing the index of entities of the data structure to identify each memory location affected by a blocking transaction after the blocking transaction commits;

rescheduling each of the blocked entities in the index of memory addresses of the data structure after the blocking transaction commits; and

retrying an execution of the blocked entity following the referencing of the index of entities and the index of memory addresses.

9. The method according to claim 8, the method further comprising adding blocked entities to the data structure as entities are blocked, wherein each added entry in the index of entities corresponding to a blocked entity includes a reference to one or more memory addresses that necessitated blocking the blocked entity.

10. The method according to claim 8, the method further comprising adding entries corresponding to memory addresses to the index of memory addresses of the data structure as each entity is blocked, wherein each added memory address includes a reference to one or more blocked entities that attempted to access the added memory address before the blocked entity blocked.

11. 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 8.

12. The method according to claim 8, the method further comprising removing a blocked entity and corresponding memory addresses referenced by the blocked entity from the index of blocked entities and the index of memory addresses, respectively, as the blocked entity is identified for the retrying.

13. The method according to claim 12, the method further comprising retrying the execution of the blocked entity after removing the blocked entity and the corresponding memory addresses referenced by the blocked entity from, respectively, the index of blocked entities and the index of memory addresses.