Information Technology Reference
In-Depth Information
6.1
Multi-object synchronization
Having multiple shared objects in a program raises challenges to reasoning about
interactions across objects. For example, consider a system storing a bank's
accounts. A reasonable design choice might be for each customer's account to be
a shared object with a lock (either a mutual exclusion lock or a readers/writers
lock as described in the previous chapter.) Consider, however, transferring $100
from account A to account B as follows:
A->subtract(100);
B->add(100);
Although each individual action is atomic, the sequence of actions is not.
As a result, there may be a time where, say, A tells B that the money has been
sent and B gets mad because the money does not appear in B's account.
Similarly, consider a bank manager running a program to answer a question:
\How much money does the bank have?" If the program simply reads from
each account, the calculation may exclude or double-count money \in ight"
between accounts such as in the transfer from A to B.
These examples illustrate a general problem that arises whenever a program
contains multiple shared objects accessed by threads. Even if each object has a
lock and guarantees that its methods operate atomically, sequences of operations
by different threads across different objects can be interleaved. For example,
you would face the same issues if you tried to solve Too Much Milk with a
Note
object that has 2 methods,
readNote
and
writeNote
, and a
Fridge
object that
has 2 methods,
checkForMilk
and
addMilk
.
One big lock v. fine-grained locking. The simplest solution is to include
all of a program's data structures in a single shared object with a single lock.
Then, all threads operate by calling that object's methods, each of which can
operate while holding the object's lock. This approach can yield acceptable
performance for some applications, especially if the code is structured so that
threads do not hold the lock when they perform high-latency I/O operations.
However, for other applications, a single global lock may restrict parallelism
too much.
In these cases, different data structures may each have their own
lock.
By the same token, although the previous chapter focused on the simple case
of a shared object with a single lock protecting all of the object's state, ne-
grained locking |partitioning an object's state into dierent subsets protected
Definition: fine-grained
locking
by dierent locks|is sometimes warranted.
Example: Hash table with fine grained locking.
A hash table provides
put(key,value)
,
value=get(key)
, and
value=remove(key)
methods.
A simple coarse-grained locking implementation would use a single lock that
is acquired and released at the start and end of each of these methods.
If
