WARF: P03229US

Computer Architecture Providing Transactional, Lock-Free Execution of Lock-Based Programs


Ravi Rajwar, James Goodman

The Wisconsin Alumni Research Foundation (WARF) is seeking commercial partners interested in developing a transactional lock removal (TLR) protocol that provides "lock-free" execution even when data conflicts are present.
OVERVIEWMulti-threaded software provides multiple execution “threads” that act like independent (but cooperating) programs and can be assigned to different computer processors for parallel, and thus faster, execution. However, when different threads modify a common data source, lack of coordination can lead to errors. To avoid this, each “critical section,” consisting of a set of operations performed atomically (all at once), is typically protected by a lock, which a thread must acquire before executing the critical section.

While this technique prevents conflict, it also reduces the benefits of parallel execution. Based on the insight that different threads can often execute critical sections simultaneously without conflict, UW-Madison researchers previously developed a speculative lock elision (SLE) protocol in which each thread detects and then tentatively executes a critical section without first obtaining the lock. Execution is finalized only if no conflict is detected; otherwise execution is rolled back and reverts to acquiring the lock.
THE INVENTIONThe researchers have now extended this work to create a transactional lock removal (TLR) protocol that provides "lock-free" execution even when data conflicts are present. When data conflict is detected, TLR employs a conflict resolution scheme that determines which thread can retain ownership of the necessary data and execute the critical section first without causing errors. The scheme executes critical sections concurrently, but fairly, whenever possible, and efficiently when not.
  • Multi-threaded computer software
  • By using the critical shared data itself to order any conflicting accesses to the data, TLR provides successful lock-free execution even in the presence of data conflicts.
  • Provides a much more feasible and efficient programming environment for multi-threaded software because programmers can use locks freely to prevent conflict without fear of compromising software performance
  • Provides hardware support for "lock-freedom" -- the guarantee that a critical section will either be executed to completion or not at all, thus protecting against hardware (and some software) failures that might leave the database in an inconsistent state
  • By eliminating software wait on locks, TLR improves system-wide interactions and increases application stability.
  • Designers can implement the conflict resolution scheme in hardware by building on existing cache coherence protocols.
Contact Information
For current licensing status, please contact Emily Bauer at or 608-960-9842.
The WARF Advantage

Since its founding in 1925 as the patenting and licensing organization for the University of Wisconsin-Madison, WARF has been working with business and industry to transform university research into products that benefit society. WARF intellectual property managers and licensing staff members are leaders in the field of university-based technology transfer. They are familiar with the intricacies of patenting, have worked with researchers in relevant disciplines, understand industries and markets, and have negotiated innovative licensing strategies to meet the individual needs of business clients.