Concurrent Execution of Critical Sections by Eliding Ownership of Locks

Abstract

One embodiment of the present invention provides a system that facilitates avoiding locks by speculatively executing critical sections of code. During operation, the system allows a process to speculatively execute a critical section of code within a program without first acquiring a lock associated with the critical section. If the process subsequently completes the critical section without encountering an interfering data access from another process, the system commits changes made during the speculative execution, and resumes normal non-speculative execution of the program past the critical section. Otherwise, if an interfering data access from another process is encountered during execution of the critical section, the system discards changes made during the speculative execution, and attempts to re-execute the critical section.

1 . A method for avoiding locks by speculatively executing critical sections of code, comprising:
 allowing a process to speculatively execute a critical section of code within a program without first acquiring a lock associated with the critical section;   wherein if the process completes the critical section without encountering an interfering data access from another process, the method further comprises:   committing changes made during the speculative execution, and resuming normal non-speculative execution of the program past the critical section;   and wherein if an interfering data access from another process is encountered during execution of the critical section, the method further comprises:   discarding changes made during the speculative execution, and attempting to re-execute the critical section zero or more times;   wherein attempting to re-execute the critical section involves speculatively re-executing the critical section, wherein if the critical section is not successfully completed after a number of attempts at speculative execution, the method further comprises:   acquiring a lock associated with the critical section, non-speculatively executing the critical section, and releasing the lock associated with the critical section.   
     
     
         2 . The method of  claim 1 , wherein data accesses from other processes are allowed to proceed during the speculative execution of the critical section. 
     
     
         3 . 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 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.   
     
     
         4 . The apparatus of  claim 3 , wherein the speculative execution mechanism is configured to allow data accesses from other processes to proceed during the speculative execution of the critical section. 
     
     
         5 . An electronic computer executing a stored program to coordinate access by multiple program threads to common memory accessible to the multiple program threads, the program threads having instructions in a critical section enforcing acquisition of a lock before access to the common memory, the electronic computer operating to:
 for at least one program thread:   (a) speculatively execute the critical section without acquisition of the lock; and   (b) committing the speculative execution of the critical section when there has been no interruption to access of the common memory by another program thread during that execution and squashing the speculative execution of the critical section when there has been an interruption to axis of the common memory by another program thread.