Scalable Reader-Writer Locks for Parallel Systems
Abstract
Current algorithms for reader writer synchronization exhibit poor scalability because they do not allow readers to acquire locks independently. We describe two new algorithms for reader-writer synchronization that allow parallelism among readers during lock acquisition. We achieve this parallelism by distributing the lock state among different processors, and by trading reader throughput for writer throughput; we expect that in highly concurrent programs, the ratio of writers to readers should be very low, so this tradeoff should lead to better overall performance. We used a multiprocessor simulator, Proteus, to compare these algorithms with existing algorithms. Our experiments show that when reads are a large percentage of lock requests, the throughput of both of our algorithms scales significantly better than current algorithms; even when there is a fair percentage of writes, the throughput of one of our algorithms still scales better than current algorithms.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1991
- Accession Number
- ADA243147
Entities
People
- William E. Weihl
- Wilson C. Hsieh
Organizations
- Massachusetts Institute of Technology