Wisconsin Alumni Research Foundation

Information Technology
Information Technology
Concurrent Execution of Critical Sections by Omitting Lock Acquisition
WARF: P02070US

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.
Multi-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 Invention
UW-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.
  • 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
Additional Information
For current licensing status, please contact Emily Bauer at [javascript protected email address] or 608-960-9842