Information Technology Reference
In-Depth Information
In a deadlocked state, the system has at least one deadlock.
Definition: deadlocked
state
So, as long as the system is in a safe state, it has control of its own destiny: for
any workload, it can avoid deadlock by delaying the processing of some requests.
In particular, the Banker's Algorithm will delay any request that would take it
from a safe to an unsafe state because once the system enters an unsafe state,
it may not be able to avoid deadlock.
Notice that an unsafe state does not always lead to deadlock. A system in an
unsafe state may remain in an unsafe state or return to a safe state, depending
on the specific interleaving of resource requests and completions. However, as
long as the system is in an unsafe state, a bad workload or unlucky scheduling
of requests can force it to deadlock.
The Banker's Algorithm is an approach to keeping a system in a safe state.
The algorithm is based on a loose analogy with a small town banker who has
a maximum total amount that can be loaned at one time total and a set
of businesses that each have a credit line max[i] for business i . A business
will borrow and pay back amounts of money as various projects are started
and finished, so that the business i will always have an oustanding loan amount
between 0 and max[i] . For each business with a credit line, if all of the business's
requests are granted, the business will eventually reach a state where all current
projects are finished and the loan balance returns to 0 .
A conservative banker might only issue credit lines so that the sum of the
credit lines is at most total ; this approach is analogous to the atomically ac-
quire all resources approach or the provide sucient resources approach, and it
trivially guarantees that the system remains in a safe state and that eventually
all businesses with credit lines will complete their projects.
However, a more aggressive banker can issue more credit as long as the bank
can live up to its commitment to each business|to provide a loan of max[i] if
business i requests it. The key observation is that the bank can delay requests
to increase a loan amount within a businesses existing credit line. For example,
the bank might lose the paperwork for a few hours, days, or weeks.
By delaying loan requests, the bank can remain in a safe state|a state for
which there exists at least one series of loan fulfillments by which every business
i can eventually receive its maximal loan max[i] , complete its projects, and
pay back all of its loan. The bank can then use that repaid money to grant
pending loans to other businesses.
Figure 6.10 shows pseudo-code for a version of the banker's algorithm that
manages a set of r resources for a set of t threads. For simplicity of discus-
sion, threads request each unit of resource separately, but the algorithm can be
extended to allow multiple resources to be requested at the same time.
The high-level idea is simple: when a request arrives, wait until it is safe to
grant the request before granting it. As Figure 6.9 shows, we can realize this
 
Search WWH ::




Custom Search