Compiling join patterns using software transactional memories

• US 7,630,991 B2
• Filed: 10/27/2005
• Issued: 12/08/2009
• Est. Priority Date: 10/27/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Singh, Satnam
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Ruiz; Angelica
• Application Number:
  US11/260,789
• Publication Number:
  US 20070101314A1
• Time in Patent Office: 1,503 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 9/467 Transactional memory G06F9/528 takes precedence

Abstract

Join patterns may be compiled using software transactional memories (STM'"'"'s) without the use of locks or other low level constructs. In particular, any number of STM threads may each perform a corresponding change set on a corresponding channel set. Each such STM thread may perform its corresponding change set by acquiring non-exclusive access to its corresponding channel set. Once each of the STM threads has performed its corresponding change set, a comparison is made to determine whether any two or more of the change sets are inconsistent with one another. The consistent change sets may be committed to memory. The inconsistent change sets may be either committed or rolled back.

Claims

1. A method for executing a choice join pattern that is a choice between a first join pattern branch and a second join pattern branch, the first join pattern branch performing a first set of changes on a first set of channels stored in a memory, the second join pattern branch performing a second set of changes on a second set of channels stored in the memory, the method comprising:

(a) using a processor to designate a randomly selected one of the first join pattern branch and the second join pattern branch as a selected join pattern branch and the other of the first join pattern branch and the second join pattern branch as an unselected join pattern branch;

(b) determining whether each channel in the set of channels operated upon by the selected join pattern branch is accessible to the selected join pattern branch;

(c) if so, then attempting to execute a first software transactional memory code associated with the selected join pattern branch;

(d) if not, then determining whether each channel in the set of channels operated upon by the unselected join pattern branch is accessible to the unselected join pattern branch;

(e) if so, then attempting to execute a second software transactional memory code associated with the unselected join pattern branch; and

(f) if not, then returning to step (b),

wherein attempting to execute the first software transactional memory code associated with the selected join pattern branch comprises;

if the first software transactional memory code is successfully executed, then committing the set of changes performed by the selected join pattern branch; and

if the first software transactional memory code is not successfully executed, then rolling back the set of changes performed by the selected join pattern branch and returning to the step of determining whether each channel in the set of channels operated upon by the selected join pattern branch is accessible to the selected join pattern branch.

2. The method of claim 1, comprising attempting to execute the second software transactional memory code while simultaneously attempting to execute the first software transactional memory code.

3. A computer-readable storage medium for executing a choice join pattern that is a choice between a first join pattern branch and a second join pattern branch, the first join pattern branch performing a first set of changes on a first set of channels stored in a memory, the second join pattern branch performing a second set of changes on a second set of channels stored in the memory, the computer-readable storage medium having stored thereon instructions comprising:

(a) using a processor to designate a randomly selected one of the first join pattern branch and the second join pattern branch as a selected join pattern branch and the other of the first join pattern branch and the second join pattern branch as an unselected join pattern branch;

(b) determining whether each channel in the set of channels operated upon by the selected join pattern branch is accessible to the selected join pattern branch;

(c) if so, the attempting to execute a first software transactional memory code associated with the selected join pattern branch;

(d) if not, then determining whether each channel in the set of channels operate upon by the unselected join pattern branch is accessible to the unselected join pattern branch;

(e) if so, then attempting to execute a second software transactional memory code associated with the unselected join pattern branch; and

(f) if not, then returning to step (b),

wherein attempting to execute the first software transactional memory code associated with the selected join pattern branch comprises;

if the first software transactional memory code is successfully executed, then committing the set of changes performed by the selected join pattern branch; and

if the first software transactional memory code is not successfully executed, then rolling back the set of changes performed by the selected join pattern branch and returning to the step of determining whether each channel in the set of channels operated upon by the selected join pattern branch is accessible to the selected join pattern branch.

4. The computer-readable storage medium of claim 3, wherein the instructions comprises attempting to execute the second software transactional memory code while simultaneously attempting to execute the first software transactional memory code.