Algoritmo para averiguar interbloqueo

Algoritmo del Banquero

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.