Algoritmo para averiguar interbloqueo

2011-12-09T10:16:35Z

Juaservaz: /* Algoritmo del Banquero */ corrección en suma de los vectores del paso 1

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

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

}
</source>
<source lang="java">
public static void main(String[] args) {

List<Proceso> asignados = creaAsignados();
List<Proceso> necesarios = creaNecesarios();
Disponibles disponibles = creaDisponibles();
Comprobaciones.devuelveLista(asignados, necesarios, disponibles);
}
</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.

Wiki de Sistemas Operativos - Contribuciones del usuario [es]

Algoritmo para averiguar interbloqueo