Prerrequisito: Algoritmo del banquero
El algoritmo del banquero es un algoritmo de asignación de recursos y evitación de puntos muertos que prueba la seguridad simulando la asignación de cantidades máximas posibles predeterminadas de todos los recursos, luego realiza una verificación de «estado s» para probar posibles actividades, antes de decidir si se debe permitir la asignación. continuar.
Las siguientes estructuras de datos se utilizan para implementar el algoritmo del banquero:
Sea ‘n’ el número de procesos en el sistema y ‘m’ el número de tipos de recursos.
Disponible :
- Es una array unidimensional de tamaño ‘m’ que indica el número de recursos disponibles de cada tipo.
- Disponible[ j ] = k significa que hay ‘k’ instancias del tipo de recurso R j
máx.:
- Es una array bidimensional de tamaño ‘ n*m’ que define la demanda máxima de cada proceso en un sistema.
- Max[ i, j ] = k significa que el proceso P i puede solicitar como máximo ‘k’ instancias del tipo de recurso R j.
Asignación :
- Es una array bidimensional de tamaño ‘n*m’ que define la cantidad de recursos de cada tipo actualmente asignados a cada proceso.
- Asignación[ i, j ] = k significa que al proceso P i se le asignan actualmente ‘k’ instancias del tipo de recurso R j
Necesitar :
- Es una array bidimensional de tamaño ‘n*m’ que indica la necesidad de recursos restante de cada proceso.
- Necesidad [ i, j ] = k significa proceso P i actualmente asignado ‘k’ instancias del tipo de recurso R j
- Necesidad [ i, j ] = Max [ i, j ] – Asignación [ i, j ]
La asignación i especifica los recursos actualmente asignados al proceso P i y la necesidad i especifica los recursos adicionales que el proceso P i aún puede solicitar para completar su tarea.
El algoritmo del banquero consiste en un algoritmo de seguridad y un algoritmo de solicitud de recursos
El algoritmo para averiguar si un sistema está o no en un estado seguro se puede describir de la siguiente manera:
- Sean Work y Finish vectores de longitud ‘m’ y ‘n’ respectivamente.
Inicializar: Trabajo= Disponible
Terminar [i]=falso; para i=1,2,……,n - Encuentre una i tal que ambas
a) Terminar [i]=false
b) Need_i<=worksi no existe tal i vaya al paso (4)
- Trabajo=Trabajo + Asignación_i
Terminar[i]= verdadero
ir al paso(2) - Si Finish[i]=true para todos los i,
entonces el sistema está en estado seguro.
Secuencia segura es la secuencia en la que los procesos se pueden ejecutar de forma segura.
En esta publicación, se realiza la implementación del algoritmo de seguridad del algoritmo de Banker.
C++
// C++ program to illustrate Banker's Algorithm
#include<iostream>
using namespace std;
// Number of processes
const int P = 5;
// Number of resources
const int R = 3;
// Function to find the need of each process
void calculateNeed(int need[P][R], int maxm[P][R],
int allot[P][R])
{
// Calculating Need of each P
for (int i = 0 ; i < P ; i++)
for (int j = 0 ; j < R ; j++)
// 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
bool isSafe(int processes[], int avail[], int maxm[][R],
int allot[][R])
{
int need[P][R];
// Function to calculate need matrix
calculateNeed(need, maxm, allot);
// Mark all processes as infinish
bool finish[P] = {0};
// To store safe sequence
int safeSeq[P];
// Make a copy of available resources
int work[R];
for (int i = 0; i < R ; i++)
work[i] = avail[i];
// While all processes are not finished
// or system is not in safe state.
int count = 0;
while (count < P)
{
// Find a process which is not finish and
// whose needs can be satisfied with current
// work[] resources.
bool found = false;
for (int p = 0; p < P; 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
int j;
for (j = 0; j < R; j++)
if (need[p][j] > work[j])
break;
// If all needs of p were satisfied.
if (j == R)
{
// Add the allocated resources of
// current P to the available/work
// resources i.e.free the resources
for (int k = 0 ; k < R ; k++)
work[k] += allot[p][k];
// Add this process to safe sequence.
safeSeq[count++] = p;
// Mark this p as finished
finish[p] = 1;
found = true;
}
}
}
// If we could not find a next process in safe
// sequence.
if (found == false)
{
cout << "System is not in safe state";
return false;
}
}
// If system is in safe state then
// safe sequence will be as below
cout << "System is in safe state.\nSafe"
" sequence is: ";
for (int i = 0; i < P ; i++)
cout << safeSeq[i] << " ";
return true;
}
// Driver code
int main()
{
int processes[] = {0, 1, 2, 3, 4};
// Available instances of resources
int avail[] = {3, 3, 2};
// Maximum R that can be allocated
// to processes
int maxm[][R] = {{7, 5, 3},
{3, 2, 2},
{9, 0, 2},
{2, 2, 2},
{4, 3, 3}};
// Resources allocated to processes
int allot[][R] = {{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);
return 0;
}
Java
// Java program to illustrate Banker's Algorithm
import java.util.*;
class GFG
{
// Number of processes
static int P = 5;
// Number of resources
static int R = 3;
// Function to find the need of each process
static void calculateNeed(int need[][], int maxm[][],
int allot[][])
{
// Calculating Need of each P
for (int i = 0 ; i < P ; i++)
for (int j = 0 ; j < R ; j++)
// 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
static boolean isSafe(int processes[], int avail[], int maxm[][],
int allot[][])
{
int [][]need = new int[P][R];
// Function to calculate need matrix
calculateNeed(need, maxm, allot);
// Mark all processes as infinish
boolean []finish = new boolean[P];
// To store safe sequence
int []safeSeq = new int[P];
// Make a copy of available resources
int []work = new int[R];
for (int i = 0; i < R ; i++)
work[i] = avail[i];
// While all processes are not finished
// or system is not in safe state.
int count = 0;
while (count < P)
{
// Find a process which is not finish and
// whose needs can be satisfied with current
// work[] resources.
boolean found = false;
for (int p = 0; p < P; p++)
{
// First check if a process is finished,
// if no, go for next condition
if (finish[p] == false)
{
// Check if for all resources of
// current P need is less
// than work
int j;
for (j = 0; j < R; j++)
if (need[p][j] > work[j])
break;
// If all needs of p were satisfied.
if (j == R)
{
// Add the allocated resources of
// current P to the available/work
// resources i.e.free the resources
for (int k = 0 ; k < R ; k++)
work[k] += allot[p][k];
// Add this process to safe sequence.
safeSeq[count++] = p;
// Mark this p as finished
finish[p] = true;
found = true;
}
}
}
// If we could not find a next process in safe
// sequence.
if (found == false)
{
System.out.print("System is not in safe state");
return false;
}
}
// If system is in safe state then
// safe sequence will be as below
System.out.print("System is in safe state.\nSafe"
+" sequence is: ");
for (int i = 0; i < P ; i++)
System.out.print(safeSeq[i] + " ");
return true;
}
// Driver code
public static void main(String[] args)
{
int processes[] = {0, 1, 2, 3, 4};
// Available instances of resources
int avail[] = {3, 3, 2};
// Maximum R that can be allocated
// to processes
int maxm[][] = {{7, 5, 3},
{3, 2, 2},
{9, 0, 2},
{2, 2, 2},
{4, 3, 3}};
// Resources allocated to processes
int 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);
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python3 program to illustrate
# Banker's Algorithm
# Number of processes
P = 5
# Number of resources
R = 3
# 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.",
"\nSafe 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)
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
C#
// C# program to illustrate Banker's Algorithm
using System;
class GFG
{
// Number of processes
static int P = 5;
// Number of resources
static int R = 3;
// Function to find the need of each process
static void calculateNeed(int [,]need, int [,]maxm,
int [,]allot)
{
// Calculating Need of each P
for (int i = 0 ; i < P ; i++)
for (int j = 0 ; j < R ; j++)
// 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
static bool isSafe(int []processes, int []avail, int [,]maxm,
int [,]allot)
{
int [,]need = new int[P,R];
// Function to calculate need matrix
calculateNeed(need, maxm, allot);
// Mark all processes as infinish
bool []finish = new bool[P];
// To store safe sequence
int []safeSeq = new int[P];
// Make a copy of available resources
int []work = new int[R];
for (int i = 0; i < R ; i++)
work[i] = avail[i];
// While all processes are not finished
// or system is not in safe state.
int count = 0;
while (count < P)
{
// Find a process which is not finish and
// whose needs can be satisfied with current
// work[] resources.
bool found = false;
for (int p = 0; p < P; p++)
{
// First check if a process is finished,
// if no, go for next condition
if (finish[p] == false)
{
// Check if for all resources of
// current P need is less
// than work
int j;
for (j = 0; j < R; j++)
if (need[p,j] > work[j])
break;
// If all needs of p were satisfied.
if (j == R)
{
// Add the allocated resources of
// current P to the available/work
// resources i.e.free the resources
for (int k = 0 ; k < R ; k++)
work[k] += allot[p,k];
// Add this process to safe sequence.
safeSeq[count++] = p;
// Mark this p as finished
finish[p] = true;
found = true;
}
}
}
// If we could not find a next process in safe
// sequence.
if (found == false)
{
Console.Write("System is not in safe state");
return false;
}
}
// If system is in safe state then
// safe sequence will be as below
Console.Write("System is in safe state.\nSafe"
+" sequence is: ");
for (int i = 0; i < P ; i++)
Console.Write(safeSeq[i] + " ");
return true;
}
// Driver code
static public void Main ()
{
int []processes = {0, 1, 2, 3, 4};
// Available instances of resources
int []avail = {3, 3, 2};
// Maximum R that can be allocated
// to processes
int [,]maxm = {{7, 5, 3},
{3, 2, 2},
{9, 0, 2},
{2, 2, 2},
{4, 3, 3}};
// Resources allocated to processes
int [,]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);
}
}
// This code has been contributed by ajit.
Producción:
System is in safe state. Safe sequence is: 1 3 4 0 2
Ilustración :
Considerando un sistema con cinco procesos P0 a P4 y tres tipos de recursos A, B, C. El tipo de recurso A tiene 10 instancias, B tiene 5 instancias y el tipo C tiene 7 instancias. Supongamos que en el momento t0 se ha tomado la siguiente instantánea del sistema:
Debemos determinar si el nuevo estado del sistema es seguro. Para hacerlo, debemos ejecutar el algoritmo de seguridad en el cuadro de asignación anterior.
El siguiente es el gráfico de asignación de recursos: La ejecución del algoritmo de seguridad muestra que la secuencia < P1, P3, P4, P0, P2 > satisface el requisito de seguridad.
Complejidad de tiempo = O(n*n*m) donde n = número de procesos ym = número de recursos.
Este artículo es una contribución de Sahil Chhabra (akku) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA