Technologies
PDF


WARF: P02070US

Concurrent Execution of Critical Sections by Omitting Lock Acquisition


INVENTORS -

James Goodman, Ravi Rajwar

The Wisconsin Alumni Research Foundation (WARF) is seeking commercial partners interested in developing a novel method for coordinating access to data shared by multiple program threads.
OVERVIEWMulti-threaded software provides many execution “threads” that act like independent programs and can be assigned to separate computer processors for parallel, and thus faster, execution. When different threads modify a common data source, however, lack of coordination can lead to errors. In airline reservations systems, for example, threads handling reservations for different customers may read and write data to a common database of available seats. If separate threads modify data for the same seat simultaneously, double booking may occur.

To avoid this, such “critical sections” of data are often protected by a lock that the thread must acquire before executing a section. But while locking a critical section for use by a single thread prevents conflict, it also reduces the benefits provided by parallel execution in the first place.
THE INVENTIONUW-Madison researchers have developed a novel method for coordinating access to data shared by multiple program threads. Based on the insight that critical sections can often be executed simultaneously without conflict, each program thread of this invention first detects the beginning of a critical section, and then tentatively executes it without first acquiring the lock. The provisional execution is finalized only if no conflict is detected; otherwise execution is quashed. In other words, when a critical section can be executed concurrently by more than one thread without conflict, the step of acquiring the lock becomes unnecessary and is omitted.
APPLICATIONS
  • Coordinating access to data shared by multiple program threads, such as data in airline reservation systems
KEY BENEFITS
  • Ensures that locks implemented to prevent conflict carry little or no performance penalty (except when they are truly needed)
  • 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
  • By avoiding the slowdowns imposed by unnecessary lock acquisitions, should speed execution times by multi-threaded software programs accessing common data
  • Uses existing cache protocols to indicate whether conflict has occurred during the provisional execution of a critical section
  • By including a step of reading a lock and performing the provisional execution only if the lock is available, avoids the potential for reduced performance when the number of actual conflicts is high
  • Identifies critical sections without modifying existing software or compilers
Contact Information
For current licensing status, please contact Emily Bauer at emily@warf.org 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.