Information Technology Reference
In-Depth Information
Acquire−All/Release All Execution (Serializable)
Request 1
Lock(A,B) A=A+1 B=B+2 Unlock(A,B)
Lock(C,D) C=C+3 D=D+4 Unlock(C,D)
Request 2
Lock(A,B) A = A+5 B=B+6 Unlock(A,B)
Request 3
Equivalent Sequential Execution
Lock(A,B) A=A+1 B=B+2 Unlock(A,B)
Request 1
Lock(C,D) C=C+3 D=D+4 Unlock(C,D)
Request 2
Lock(A,B) A = A+5 B=B+6 Unlock(A,B)
Request 3
Figure6.2: Locking multiple objects using an acquire-all/release-all pattern
results in a serializable execution that is equivalent to an execution where
requests are executed sequentially in some order.
Acquire-all/release-all
If a system that processes requests has multiple locks, one way to manage these
locks is the acquire-all/release-all pattern. To process a request in this pattern,
Definition:
acquire-all/release-all
pattern
a thread first acquires all of the locks that will be needed at any point during
request processing, then the thread processes the request, finally the thread
releases all of the locks.
This approach can allow significant concurrency. If requests touch nonover-
lapping subsets of state protected by different locks, then they can proceed in
parallel.
This approach can be easy to reason about because it enforces serializability
Definition: serializability
across requests|the result of any execution of the program is equivalent to an
execution in which requests are processed one at a time in some sequential order.
As Figure 6.2 illustrates, requests that access nonoverlapping data can proceed
in parallel. The result is the same as it woud have been if, instead, the system
first executed one of the requests and then the other. On the other hand, if two
requests touch any of the same data, then one will be processed entirely before
the other's processing begins. Ensuring serializability thus allows one to reason
about multi-step tasks as if each task executed alone.
Example: Hash table.
Consider a hash table with one lock per hash
bucket and that supports a
changeKey(k1,k2)
operation that changes the
object that initially has key
k1
to have key
k2
instead. This function could be
implemented to acquire
k1
and
k2
's locks, remove the object using key
k1
,
update the object's key, insert the object using key
k2
, and then release
k1
and
k2
's locks.
One challenge to using this approach is knowing exactly what locks will be
needed by a request before beginning to process it. One solution is to conser-
vatively acquire more locks than needed (e.g., acquire any locks that may be
needed by a particular request), but this approach can reduce concurrency.
