Accession Number:

ADA243147

Title:

Scalable Reader-Writer Locks for Parallel Systems

Descriptive Note:

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

Report Date:

1991-11-01

Pagination or Media Count:

22.0

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.

Subject Categories:

  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE