Banker's Safety Algorithm - Python Implementation
Tags: tutorial, programming, bankersalgorithm, python
Published: 2021-05-31 00:35:58

#Implementation of Banker's Safety algorithm using Python

The banker’s algorithm is a resource allocation and deadlock avoidance algorithm that tests for safety by simulating the allocation for predetermined maximum possible amounts of all resources, then makes an “s-state” check to test for possible activities, before deciding whether allocation should be allowed to continue.

Following Data structures are used to implement the Banker’s Algorithm:

Let ‘n’ be the number of processes in the system and ‘m’ be the number of resources types.

Available :

It is a 1-d array of size ‘m’ indicating the number of available resources of each type. Available[ j ] = k means there are ‘k’ instances of resource type Rj Max :

It is a 2-d array of size ‘n*m’ that defines the maximum demand of each process in a system. Max[ i, j ] = k means process Pi may request at most ‘k’ instances of resource type Rj.

Allocation :

It is a 2-d array of size ‘n*m’ that defines the number of resources of each type currently allocated to each process. Allocation[ i, j ] = k means process Pi is currently allocated ‘k’ instances of resource type Rj Need :

It is a 2-d array of size ‘n*m’ that indicates the remaining resource need of each process. Need [ i, j ] = k means process Pi currently allocated ‘k’ instances of resource type Rj Need [ i, j ] = Max [ i, j ] – Allocation [ i, j ] Allocationi specifies the resources currently allocated to process Pi and Needi specifies the additional resources that process Pi may still request to complete its task.

Banker’s algorithm consist of Safety algorithm and Resource request algorithm

Safety Algorithm

The algorithm for finding out whether or not a system is in a safe state can be described as follows:

Let Work and Finish be vectors of length ‘m’ and ‘n’ respectively.

Initialize: Work= Available Finish [i]=false; for i=1,2,……,n

Find an i such that both a) Finish [i]=false b) Need_i<=work

if no such i exists goto step (4) Work=Work + Allocation_i Finish[i]= true goto step(2) If Finish[i]=true for all i, then the system is in safe state. Safe sequence is the sequence in which the processes can be safely executed.

In this post, implementation of Safety algorithm of Banker’s Algorithm is done.

![image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zloqtfx55zl87a9j74c4.png)
 

We must determine whether the new system state is safe. To do so, we need to execute Safety algorithm on the above given allocation chart.

Following is the resource allocation graph:

![image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/l2mdlp359vfx5vlhts51.png)
 
Executing safety algorithm shows that sequence < P1, P3, P4, P0, P2 > satisfies safety requirement.

Code:
# Python code to illustrate Banker's Algorithm

P = 5 (Processes)
R = 3 (Resources)


# Function to find the need of each process
def calculateNeed(need, maxm, allot):

	# Calculating Need of each P
	for i in range(P):
		for j in range(R):
			
			# Need of instance = maxm instance -
			# allocated instance
			need[i][j] = maxm[i][j] - allot[i][j]

# Function to find the system is in
# safe state or not
def isSafe(processes, avail, maxm, allot):
	need = []
	for i in range(P):
		l = []
		for j in range(R):
			l.append(0)
		need.append(l)
		
	Function to calculate need matrix
	calculateNeed(need, maxm, allot)

	Mark all processes as infinish
	finish = [0] * P
	
	To store safe sequence
	safeSeq = [0] * P

	Make a copy of available resources
	work = [0] * R
	for i in range(R):
		work[i] = avail[i]

	While all processes are not finished or system is not in safe state.
	count = 0
	while (count < P):
		
		# Find a process which is not finish
		# and whose needs can be satisfied
		# with current work[] resources.
		found = False
		for p in range(P):
		
			# First check if a process is finished,
			# if no, go for next condition
			if (finish[p] == 0):
			
				# Check if for all resources
				# of current P need is less
				# than work
				for j in range(R):
					if (need[p][j] > work[j]):
						break
					
				# If all needs of p were satisfied.
				if (j == R - 1):
				
					# Add the allocated resources of
					# current P to the available/work
					# resources i.e.free the resources
					for k in range(R):
						work[k] += allot[p][k]

					# Add this process to safe sequence.
					safeSeq[count] = p
					count += 1

					# Mark this p as finished
					finish[p] = 1

					found = True
				
		# If we could not find a next process
		# in safe sequence.
		if (found == False):
			print("System is not in Safe state")
			return False
		
	# If system is in safe state then
	# safe sequence will be as below
	print("System is in Safe state.",
			"\n Safe sequence is: ", end = " ")
	print(*safeSeq)

	return True

# Driver code
if __name__ =="__main__":
	
	processes = [0, 1, 2, 3, 4]

	# Available instances of resources
	avail = [3, 3, 2]

	# Maximum R that can be allocated
	# to processes
	maxm = [[7, 5, 3], [3, 2, 2],
			[9, 0, 2], [2, 2, 2],
			[4, 3, 3]]

	# Resources allocated to processes
	allot = [[0, 1, 0], [2, 0, 0],
			[3, 0, 2], [2, 1, 1],
			[0, 0, 2]]

	# Check system is in safe state or not
	isSafe(processes, avail, maxm, allot)

Time complexity = O(nnm) where n = number of processes and m = number of resources.