Information Technology Reference
In-Depth Information
Another challenge is that locks may be held for longer than needed. This
aspect of the approach can also reduce concurrency.
Two-phase locking refines the acquire-all/release-all pattern to address these
two challenges.
Two-phase locking
In two phase locking a multi-step task is divided into two phases. During the ex-
Denition: two phase
locking
panding phase, locks may be acquired but not released. Then, in the contracting
phase, locks may be released but not acquired.
For some programs, this approach can support more concurrency than the
acquire-all/release-all pattern. Because locks can be acquired during the ex-
panding phase, two-phase locking does not require deciding what locks to grab
a priori, so programs may be able to avoid acquiring locks they do not end up
needing, and they may not need to hold some locks for as long.
Two phase locking pattern facilitates reasoning about programs because it
also ensures that all executions are serializable. To see this, notice that if two
requests acccess overlapping data, then one of them will lock all of the overlap-
ping data before the other one begins its access to that data; then, once the
thread processing the first request begins releasing locks and the thread process-
ing the second request begins acquiring locks, the second request only modifies
data that the first request will not access again. The execution thus appears as
it would have if the first request finished accessing all of the overlapping data
before the second request accesses any of the overlapping data, which, in turn,
appears as it would have if the first request finished executing before the second
request began executing.
Example: Hash table.
A
changeKey(k1,k2)
function for a hash table with
per-bucket locks could be implemented to acquire
k1
's lock, remove the object
using key
k1
, update the object's key, acquire
k2
's lock, release
k1
's lock, insert
the object using key
k2
, and release
k2
's lock.
Staged architectures
One common pattern is the staged architecture pattern, illustrated in Figure 6.3.
6.3.Definition: staged
architecture
A staged architecture divides a system into multiple subsystems called stages,
where each stage includes some state private to the stage and a set of one or
more worker threads that operate on that state. Different stages communicate
by sending messages to each other via shared producer-consumer queues, and
each worker thread repeatedly pulls the next message from a stage's incoming
queue and then processes it, possibly producing one or more messages for other
stages' queues.
