Algoritmo para averiguar interbloqueo

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