Algoritmo para averiguar interbloqueo
Algoritmo del Banquero
Introducción:
Este algoritmo recibe el nombre de banquero porque su funcionamiento es parecido a la gestión que hacen los bancos con las cuentas de crédito. Necesita conocer de antemano las necesidades máximas de recursos por parte de cada proceso, esto es poco realista. Además, supone que cuando un proceso ha conseguido todos los recursos que necesita, los libera.
Para entenderlo un poco mejor hagamos la similitud con un banco: Un banquero (s.o.) dispone de unos fondos (recursos) y tiene unos clientes (procesos). Cada cliente dispone de un crédito que corresponde al máximo que el banquero le prestará. El cliente irá solicitando fondos de ese crédito conforme los necesite. Si el banquero tuviese fondos suficientes para prestar el máximo a cada cliente, no habría inconvenientes. Sin embargo, esto no es así, los recursos del banquero son limitados, por lo que si todos reclaman todo su crédito no podrá satisfacerlos simultáneamente. Por lo tanto, la solución es que el banquero gestione sus fondos de manera que todos los clientes puedan llegar al máximo en algún momento, aunque no lo hagan todos al mismo tiempo.
Estado seguro: El estado del sistema es seguro si existe una secuencia de asignaciones y liberaciones de recursos que permita a todos los procesos alcanzar en algún momento sus necesidades máximas de recursos.
La idea genérica del algoritmo es:
1. Buscar un proceso cuya suma recAsig + recDisp >= recMax
2. Suponemos que se asignan dichos recursos y el proceso termina su ejecución.
Sumamos sus recursos al vector recDisp y añadimos el proceso a la lista de finalizados.
3. Repetir primer paso hasta terminar todos los procesos (siendo un estado estable)
o bien hasta el punto en el que no sea posible ninguna asignación de recursos,
existiendo pues interbloqueo.
Ejemplo:
Proceso | Asignados | Maximos | Disponibles
| A B C D E | A B C D E | A B C D E
__________|_____________|___________|_______________
P0 | 1 0 2 1 1 | 1 2 2 1 2 | 0 0 2 1 1 //Recursos Disponibles Iniciales
P1 | 2 0 1 1 0 | 2 2 2 1 0 | 1 1 3 2 1 //P3 finalizado
P2 | 1 1 0 1 0 | 2 1 3 1 0 | 2 2 3 3 1 //P2 finalizado
P3 | 1 1 1 1 0 | 1 1 2 2 1 | 3 2 5 4 2 //P0 finalizado
//P1 finalizado
Pasos:
1. El primer proceso que cumple el paso 1 del algoritmo en esta tabla es P3:
[1 1 1 1 0]+[0 0 2 1 1] >= [1 1 2 2 1]
Lo consideramos terminado y añadimos sus recursos a los disponibles:
[1 1 1 1 0]+[0 0 2 1 1] = [1 1 3 2 1]
2. Volvemos a iterar desde P0. El siguiente proceso que puede adquirir los recursos necesarios
es P2. Añadimos sus recursos a la lista de disponibles.
3. Ahora nos es posible terminar P0 y por último P1.
4. Hemos logrado terminar todos los procesos sin problemas.
Algoritmo en C#
int nRecursos;
int nProcesos;
List<List<int>> asignados = new List<List<int>>();
List<List<int>> maximos = new List<List<int>>();
List<int> disponibles = new List<int>();
Random r = new Random();
//Generamos las matrices aleatoriamente
for (int j1 = 0; j1 < nRecursos;j1++)
{
disponibles.Add(r.Next(0, nRecursos));
}
for (int i = 0; i < nProcesos; i++)
{
asignados.Add(new List<int>());
maximos.Add(new List<int>());
for (int j = 0; j < nRecursos; j++)
{
asignados[i].Add(r.Next(0, nRecursos));
maximos[i].Add(r.Next(0, nRecursos));
}
}
bool aux = true;
for (int proc = 0; proc < nProcesos; proc++)
{
aux = true;
for (int recur = 0; recur < nRecursos; recur++)
{
// comprobamos que haya recursos suficientes
aux = (maximos[proc][recur] - asignados[proc][recur] - disponibles[recur]) <= 0;
if (!aux)
{
break;
}
}
if (aux)
{
añadirYeliminar(ref disponibles, ref asignados, proc);
maximos.RemoveAt(proc);
nProcesos--;
proc = -1;
if (nProcesos == 0)
{
Console.WriteLine("Es estado seguro");
Console.ReadLine();
return;
}
}
}
Console.WriteLine("Es interbloqueo");
Console.ReadLine();
}
private static void añadirYeliminar(ref List<int> disponibles, ref List<List<int>> asignados, int proc)
{
for (int k = 0; k < asignados[proc].Count; k++)
{
disponibles[k] += asignados[proc][k];
}
asignados.RemoveAt(proc);
}
Faltaria solamente leer por consola el numero de procesos y de recursos que queremos testear, o introduccirlos manualmente
Algoritmo en Python
def comprueba_configuracion(asignados, maximos, disponibles):
finalizados = []
i = 0
while(i < len(asignados)):
if not i in finalizados and puede_progresar(asignados[i], disponibles, maximos[i]):
print('Finaliza P%s\nDisponibles: %s' % (i,disponibles))
libera_recursos(asignados[i], disponibles)
finalizados.append(i) # Marca el proceso Pi como finalizado
i = 0
else:
i += 1
if(len(asignados) == len(finalizados)): # Si todos los procesos finalizan
print('\nEstado seguro para la configuracion de procesos-recursos dada')
else:
print('\nSe produce un interbloqueo')
# Incrementamos la lista de disponibles con los que tenia asignados
def libera_recursos(asignados, disponibles):
for i in range(len(disponibles)):
disponibles[i] += asignados[i]
# Devuelve True si el nº de elementos asignados mas los disponibles son mayores o iguales a los requeridos para continuar
def puede_progresar(asignados, disponibles, maximos):
resultado = True
for i in range(len(maximos)):
if(asignados[i] + disponibles[i] < maximos[i]):
resultado = False
break
return resultado
asignados = [
[1,0,2,1,1],
[2,0,1,1,0],
[1,1,0,1,0],
[1,1,1,1,0]
]
maximos = [
[1,2,2,1,2],
[2,2,2,1,0],
[2,1,3,1,0],
[1,1,2,2,1]
]
disponibles = [0,0,2,1,1]
Para este ejemplo (visto en clase) la salida sería:
>>> comprueba_configuracion(asignados, maximos, disponibles)
Finaliza P3
Disponibles: [0, 0, 2, 1, 1]
Finaliza P2
Disponibles: [1, 1, 3, 2, 1]
Finaliza P0
Disponibles: [2, 2, 3, 3, 1]
Finaliza P1
Disponibles: [3, 2, 5, 4, 2]
Estado seguro para la configuracion de procesos-recursos dada
Algoritmo en Java
<pre>
public class Comprobaciones {
public static List<Proceso> devuelveLista(List<Proceso> asignados, List<Proceso> necesarios, Disponibles recursos){
List<Proceso> terminados = new ArrayList<Proceso>();
for(int i = 0; i < necesarios.size(); i++){
if(!(terminados.contains(asignados.get(i))) && ejecuta(asignados.get(i), necesarios.get(i), recursos)){
terminados.add(asignados.get(i));
System.out.println("Proceso " + asignados.get(i).getNombre() + " terminado");
for(int j = 0; j < recursos.getDisponibles().size(); j++){
recursos.setDisponible(recursos.getDisponibles().get(j) + asignados.get(i).getRecursosNecesarios().get(j), j);
}
System.out.println("Recursos disponibles: " + recursos.getDisponibles());
i = -1;
}
}
if(terminados.size() == asignados.size()){
System.out.println("Todos los procesos han sido ejecutados sin problemas.");
}
else{
System.out.println("Hay un interbloqueo, no se pueden seguir ejecutando procesos...");
}
return terminados;
}
public static Boolean ejecuta(Proceso asignados, Proceso necesarios, Disponibles disponibles){
// Devuelve True si tiene recursos suficientes...
Boolean ej = true;
for(int i = 0; i < necesarios.getRecursosNecesarios().size(); i++){
if((asignados.getRecursosNecesarios().get(i) + disponibles.getDisponibles().get(i)) < necesarios.getRecursosNecesarios().get(i)){
ej = false;
break;
}
}
return ej;
}
}
</pre>
<pre>
public static void main(String[] args) {
List<Proceso> asignados = creaAsignados();
List<Proceso> necesarios = creaNecesarios();
Disponibles disponibles = creaDisponibles();
Comprobaciones.devuelveLista(asignados, necesarios, disponibles);
}
</pre>
Resultado:
Proceso P4 terminado Recursos disponibles: [1, 1, 3, 2, 1] Proceso P3 terminado Recursos disponibles: [2, 2, 3, 3, 1] Proceso P1 terminado Recursos disponibles: [3, 2, 5, 4, 2] Proceso P2 terminado Recursos disponibles: [5, 2, 6, 5, 2] Todos los procesos han sido ejecutados sin problemas.
Nota: Las clases lo único que contienen son listas de enteros, y los procesos contienen además los nombres de los mismos.
6.4 Ejercicios
