19
Banker's Algorithm
The resource allocation graph algorithm is not
applicable to a resource - allocation system with
multiple instances of each resource type. so
we hove
avoidance
banker's algorithm for deadlock
and resovrce allocation. It is
less efficient than ther the resource allocation
graph scheme.
-
The Banker's algorithm is run by the operating
system whenever a process requests resources.
The algorithm prevents deadlock by denying or
postponing the request if it determines that
accepting the request could put the system
in an unsafe state.
When a new process enters the system, it
must declare the maximum number of yam
instances of each resource type that it m
AA need. when the user requests a set of
resources, the system must determine whether
all allocation of these resources will leave
the syste m
tem in a safe state. If it will,
the resources are allocated, otherwise, the
process must wait until some other process
releases enough resources.
20
Data structiure.
Several data structiure must be maintained to
implement the banker's algorithm. These data struc-
-tures encode the state of resource allocation
-
system. det n be no. of processes and m be
the number o
of resources types
• Available : A vector of length m indicates the no
of available resources of each type. If available [j
avail
= k, there are k instances of resource type Rj
available.
Max: An n xm matrux defines the maximum
demand of each process. If max [ijj] = k, then
process Pi may request at most k instances of
resource type Rj.
Allocation: n nxm defines
matruix the mumber
of of each
resources type currently allocated to
lach process. If Allocation [is kj] = k, then Peroress
Pi is cworently allocated k instances of
resource typе Рj.
Need : An nxm matrix indicates the remaining
resources need of each process. If need lij=k
intances of reoorce tiype Rj, then Pi may need k
more instances of resource type Rj to complete
its task.
Need Lisj]= Max [i,j]- Allocation [i,j.
21
Safety algorithm.
The algorithm for finding out whether or not a
system is in a safe state can be described as
follows:-
1) Let work and Finish be vectors of length m andn,
respectively. Inittalize Work = available and Finish ti]-
false fou i = 12, 3 ---n.
2) Find an i such that both
a) Finish Ci = false
b) Needi = work
If no such i exists, go to step 4.
3) Work = work + allocation i
Jinish [i] = true
go to tep 2.
4) If Finish Li] = ture for all is then the
system is in a safe state.
Resource - Request Algorithm
Let Request i be the request vector for process
Pi. If requestilj] = k, then process Pi wants
* instances of resowrice type Rj. When a request
for ressurces is made by process Pi, the
following actions are taken -
22
1) of Requesti & Needi, go to stepz, otherwise, raise
an erior condition, since the process has
exceeded its maximum claim.
2) ff Requesti & Available, go to step 3. Otherwise,
raist Pi must wait, since the resoures are
not available.
3) Pretend to allocate requested resources to Pi by
modifying the state as follows?-
Available = Available - Request:
Allocation = Allocation i + Request i
Need i = Needi - Requesti
If the resulting resource allocatton state is sxfe,
the transaction is completed aund Process PE
is allocated its resources. However, if the new
state is unsafe, then Pi must wait for
Requesti, and old resource allocation state
is t restored.
