Method and apparatus for avoiding locks by speculatively executing critical sections

An apparatus that avoids locks by speculatively executing critical sections of code, comprising:

• a speculative execution mechanism configured to allow a process to speculatively execute a critical section of code within a program without first acquiring a lock associated with the critical section;
• a commit mechanism, wherein if the process completes the critical section without encountering an interfering data access from another process, the commit mechanism is configured to:
• commit changes made during the speculative execution, and to
• resume normal non-speculative execution of the program past the critical section;
• and
• a re-execution mechanism, wherein if an interfering data access from another process is encountered during execution of the critical section, the re-execution mechanism is configured to:
• discard changes made during the speculative execution, and to attemp to re-execute the critical section zero or more times;
• wherein the re-execution mechanism is configured to speculatively re-execute the critical section, wherein if the critical section is not successfully completed after a number of attempts at speculative execution, the re-execution mechanism is configured to:
• acquire a lock associated with the critical section,
• non-speculatively execute the critical section, and to
• release the lock associated with the critical section.

A computer system that facilitates avoiding locks by speculatively executing critical sections of code, comprising:

• a processor;
• a speculative execution mechanism within the processor configured to allow a process to speculatively execute a critical section of code within a program without first acquiring a lock associated with the critical section;
• a commit mechanism within the processor, wherein if the process completes the critical section without encountering an interfering data access from another process, the commit mechanism is configured to:
• commit changes made during the speculative execution, and to
• resume normal non-speculative execution of the program past the critical section;
• and
• a re-execution mechanism within the processor, wherein if an interfering data access from another process is encountered during execution of the critical section, the re-execution mechanism is configured to:
• discard changes made during the speculative execution, and to
• attempt to re-execute the critical section zero or more times;
• wherein the re-execution mechanism is configured to speculatively re-execute the critical section, wherein if the critical section is not successfully completed after a number of attempts at speculative execution, the re-execution mechanism is configured to:
• acquire a lock associated with the critical section,
• non-speculatively execute the critical section, and to
• release the lock associated with the critical section.