Advanced Synchronization - Operating Systems: Principles and Practice - page 254

serializing all requests limits performance, a fine-grained alternative is to have
one lock per hash bucket and to acquire the lock for bucket b before accessing
any record that hashes to bucket b.
There is no fundamental difference between a program with multiple shared
objects, each with its own lock, and a shared object that uses fine grained locking
and that has multiple locks covering different subsets of its data structures. All
of our discussions about issues that arise when accessing multiple shared objects
in a program also apply to fine-grained locking within an object.
Complexity v. performance. Beware of premature optimization: di-
viding an object's state into dierent pieces protected by dierent locks can
signicantly increase the object's complexity and does not always signicantly
improve performance.
Example: Resizable hash table. Suppose we want to implement a hash
table whose number of hash buckets grows as the number of objects it stores
increases. If we have a single lock, this is easy to do. But, what if we use
fine-grained locking? Then the design becomes more complex because we
have some operations like put() and get() that operate on one bucket and
other operations like resize() that operates across multiple buckets.
One solution is to have a readers-writers lock on the overall structure of the
table (e.g., the number of buckets and the array of buckets) and a mutual
exclusion locks on each bucket. Then, put() and get() acquire the table's
readers-writers lock in read mode and also acquire the relevant bucket's mu-
tual exclusion lock, and resize() acquires the readers-writers lock in write
mode.
A second solution is to have one mutual exclusion lock for each bucket, for
get() and put() to acquire the relevant bucket's mututal exclusion lock, and
for resize() to iterate through the buckets, acquiring all of the buckets' locks.
A third solution is to divide the hash key space into r regions, to have a mutual
exclusion lock for each region, and to allow each region to be resized inde-
pendently when that region becomes heavily loaded. Then, get() , put() , and
resizeRegion() each acquire the relevant region's mutual exclusion lock.
Which is solution is best? It is not obvious. The first solution is simple and
appears to allow good concurrency, but acquiring the readers-writers lock even
in read mode often involves writing a cache line that will be shared by many
processors, so it may have poor cache performance. The second solution
makes resize() expensive, but if resize() is a rare operation, that may be
OK. The third solution could balance concurrency for get()/put() against the
cost of resize() , but it is more complex and may require tuning the number
of groups to get good performane. And, these trade-offs may change as the
implementation becomes more complex; for example to trigger resize() at
appropriate times, we probably need to maintain an additional nObjects count
of the number of objects currently stored in the hash table, so whatever locking
approach we use would need to be extended to cover this information.