Ver el código de «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# ==

<source lang="csharp">            
            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);
        }
</source>

Faltaria solamente leer por consola el numero de procesos y de recursos que queremos testear, o introduccirlos manualmente


== Algoritmo en Python ==

<source lang="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]
</source>

Para este ejemplo (visto en clase) la salida sería:

<source lang="python">
>>> 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
</source>

== Algoritmo en Java ==
<source lang="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>
</source>
<source lang="java">
<pre>
public static void main(String[] args) {
		
		List<Proceso> asignados = creaAsignados();
		List<Proceso> necesarios = creaNecesarios();
		Disponibles disponibles = creaDisponibles();
		Comprobaciones.devuelveLista(asignados, necesarios, disponibles);
}
</pre>
</source>
Resultado:
<pre>
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.
</pre>
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 | Ejercicios]]