Information Technology Reference
In-Depth Information
rather than having applications request additional memory as needed, we might
instead have each application state its maximum memory needs and allocate
that much memory when each application starts. Disadvantages of this approach
include the challenge of having applications accurately estimate their worst-
case needs and the cost of allocating significantly more resources than may be
necessary in the common case.
No wait while holding: Release lock when calling out of module. If
we have a series of nested modules, each of which has a lock, then waiting on
a condition variable in an inner module can lead to a nested waiting deadlock.
One solution is to restructure a module's code so that no locks are held when
calling other modules. For example, we can change the code on the left to the
code on the right:
Module::foo(){
lock.acquire();
doSomeStuff();
otherModule->bar();
doOtherStuff();
lock.release();
Module::foo(){
doSomeStuff();
otherModule->bar();
doOtherStuff();
}
Module::doSomeStuff(){
lock.acquire();
x=x+1;
lock.release();
}
Module::doSomeStuff(){
x=x+1;
}
Module::doOtherStuff(){
y=y-2;
}
Module::doOtherStuff(){
lock.acquire();
y=y-2;
lock.release();
}
}
Circular waiting: Lock ordering. An approach used in many systems is
to identify an ordering among locks and to forbid acquiring a lock if any higher-
ordered lock is already held.
For example, we can eliminate deadlock among the dining philosophers if|
instead of always grabbing the chopstick on the left and then the one on the
right, the philosophers number the chopsticks from 1 to n and always grab the
lower-numbered chopstick before the higher-numbered one.
Similarly, for our hash table with per-bucket locks that supports a
changeKeys(k1,
k2)
operation, we can avoid deadlock by always grabbing the lock for the lower-
numbered bucket before the one for the higher-numbered bucket.
6.2.3
The Banker's Algorithm for avoiding deadlock
The Banker's Algorithm is another deadlock prevention approach. It is more
complex to describe than the ones above, and systems seldom use it in its
full generality. Nonetheless, we include this discussion both because simplified
