Scalable Reader-Writer Locks for Parallel Systems

摘要

Current algorithms for reader writer synchronization exhibit poor scalabilitybecause 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.