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 de 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.

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 3 2 1]
    Lo consideramos terminado y añadimos sus recursos a los disponibles
 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

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;
	}
	
}

public static void main(String[] args) {
		
		List<Proceso> asignados = creaAsignados();
		List<Proceso> necesarios = creaNecesarios();
		Disponibles disponibles = creaDisponibles();
		Comprobaciones.devuelveLista(asignados, necesarios, disponibles);
}

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.