Wiki de Sistemas Operativos - Contribuciones del usuario [es]

Evaluame mis contribuciones a la wiki

2013-01-18T15:45:24Z

Olgmormar:

A continuación, indica tu nombre y apellidos:

* Juan Carlos Roldán Salvador
* Daniel Ayala Hernández
* Daniel de los Reyes Leal
* Olga Minerva Moreno Martín IS-G1

Ejercicios Gestión L/E

2013-01-17T14:44:37Z

Olgmormar: /* Ejercicio 6 */

== Ejercicio 1 ==
''[Este ejercicio formó parte del cuarto Control de Evaluación Contínua del Curso 2010/11, del 8 de junio de 2011]''

''[En el temario de 2012/13 no aparece NC-SCAN por lo que se ha simplificado a C-SCAN]''

Dados la siguiente secuencia de solicitud de accesos a sectores en disco:

3, 80, 15, 45, 1, 79, 4, 20, 21, 67, 19, 23

Indique el orden de accesos, considerando que inicialmente el cabezal se encuentra en la pista 0, para los siguientes criterios. Se considera un orden preferente ascendente:

{| border="2" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 0; background: #f9f9f9; width:800px; border: 1px #aaa solid; border-collapse: collapse; font-size: 95%;"
| 4-scan
|
|
|
|
|
|
|
|
|
|
|
|
|-
| sstf
|
|
|
|
|
|
|
|
|
|
|
|
|-
| c-scan
|
|
|
|
|
|
|
|
|
|
|
|
|}

Las soluciones son algo confusas puesto que el cabezal empieza en la pista 0 y por esto no se puede apreciar realmente el efecto de los criterios.
(''[[Solución de los ejercicios de gestión de L/E#Ejercicio 1|Ver solución]]'')

== Ejercicio 2 ==
En un momento dado, un gestor de disco tiene pendiente la siguiente lista de accesos a cilindros: 17,24,20,32,12,37,8,30. Suponiendo que las cabezas lectoras se encuentran actualmente sobre el cilindro 22, indique en qué orden se atenderán estas peticiones si las cabezas se planifican por SCAN,SCAN circular(C-SCAN), o N-SCAN con N=4. Considere como preferente el sentido ascendente.

{| border="2" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 0; background: #f9f9f9; width:800px; border: 1px #aaa solid; border-collapse: collapse; font-size: 95%;"
| scan
|
|
|
|
|
|
|
|
|-
| c-scan
|
|
|
|
|
|
|
|
|-
| 4-scan
|
|
|
|
|
|
|
|
|}

SOLUCIÓN(falta revisión profesor)

{| border="2" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 0; background: #f9f9f9; width:800px; border: 1px #aaa solid; border-collapse: collapse; font-size: 95%;"
| scan
| 24
| 30
|32
| 37
| 20
|17
| 12
| 8
|-
| c-scan
| 24
| 30
|32
| 37
| 8
|12
| 17
| 20
|-
| 4-scan
|24
| 32
|20
| 17
| 30
|37
| 12
| 8
|}

== Ejercicio 3 ==
(NO ESTÁN REVISADOS POR PABLO NEIRA, PERO ESTÁN PUBLICADOS COMO SOLUCIONES DE EXÁMENES ANTIGUOS, ESTÁN HECHOS POR ALGÚN OTRO PROFESOR)
En un momento dado, un gestor de disco tiene pendiente la siguiente lista de accesos a cilindros: 16, 7, 23, 42, 47, 5, 21 y 49. Suponiendo que las cabezas lectoras se encuentran
actualmente sobre el cilindro 17, y que para los algoritmos SCAN y sus derivados, cada ciclo comienza preferiblemente en sentido ascendente, indique en qué orden se atenderán estas peticiones si las cabezas se planifican por menor tiempo de búsqueda (SSTF), algoritmo del ascensor (SCAN), algoritmo SCAN circular (C-SCAN), o NSCAN con N=4.

SSTF 16 21 23 7 5 42 47 49

SCAN 21 23 42 47 49 16 7 5

C-SCAN 21 23 42 47 49 5 7 16

4-SCAN 23 42 16 7 21 47 49 5

== Ejercicio 4 ==
(NO ESTÁN REVISADOS POR PABLO NEIRA, PERO ESTÁN PUBLICADOS COMO SOLUCIONES DE EXÁMENES ANTIGUOS, ESTÁN HECHOS POR ALGÚN OTRO PROFESOR)
En un momento dado, un gestor de disco tiene pendiente la siguiente lista de accesos a cilindros:
50, 47, 1, 40, 2, 52, 72, 75. Suponiendo que las cabezas lectoras se encuentran actualmente sobre el cilindro 45, y que para los algoritmos SCAN y sus derivados, cada ciclo comienza preferiblemente en sentido ascendente, indique en qué orden se atenderán estas peticiones si las cabezas se planifican por menor tiempo de búsqueda (SSTF), algoritmo del ascensor (SCAN), algoritmo SCAN circular (C-SCAN), o N-SCAN con N=4.

SSTF 47 50 52 40 72 75 2 1

SCAN 47 50 52 72 75 40 2 1

C-SCAN 47 50 52 72 75 1 2 40

4-SCAN 47 50 40 1 2 52 72 75

== Ejercicio 5 ==
(NO ESTÁN REVISADOS POR PABLO NEIRA, PERO ESTÁN PUBLICADOS COMO SOLUCIONES DE EXÁMENES ANTIGUOS, ESTÁN HECHOS POR ALGÚN OTRO PROFESOR)

En un momento dado, la cabeza lectora de un disco se encuentra en el cilindro 91 del disco, y el gestor tiene pendientes de atender peticiones de acceso sobre los siguientes cilindros: 90, 80, 85, 94, 5, 88, 87, 92, 93, 95, 81, 82, 83 Sin necesidad de desarrollar paso por paso el algoritmo, ¿cuál de ellas se atendería la última, si el gestor planifica los desplazamientos la cabeza lectora mediante algoritmo SSTF? ''La última en atenderse sería la petición sobre el cilindro 5, pues es el que queda más lejos de la zona en la que inicialmente se encuentra el brazo.
''
== Ejercicio 6 ==
(NO ESTÁN REVISADOS POR PABLO NEIRA, PERO ESTÁN PUBLICADOS COMO SOLUCIONES DE EXÁMENES ANTIGUOS, ESTÁN HECHOS POR ALGÚN OTRO PROFESOR)

En un momento dado, la cabeza lectora de un disco se encuentra en el cilindro 45 del disco, y el gestor tiene pendientes de atender peticiones de acceso sobre las siguientes pistas: 2, 35, 46, 23, 90, 102, 3, 34 ¿En qué orden se atenderán si el gestor planifica los desplazamientos la cabeza lectora mediante algoritmo SSTF? ''En cada momento atenderá la petición que haga referencia al cilindro más cercano al actual. Por tanto, si la cabeza se encuentra inicialmente en el cilindro 45, el orden en que se atenderán las peticiones será: 46, 35, 34, 23, 3, 2, 90, 102.
''

== Ejercicio 7 ==
(NO ESTÁN REVISADOS POR PABLO NEIRA, PERO ESTÁN PUBLICADOS COMO SOLUCIONES DE EXÁMENES ANTIGUOS, ESTÁN HECHOS POR ALGÚN OTRO PROFESOR)

¿Es lo mismo el cargador software de un sistema operativo que el cargador hardware? En caso negativo, ¿en qué se diferencian?
''No es lo mismo. El cargador hardware es llamado así porque lo proporciona el fabricante del hardware (viene empotrado en la memoria no volátil del sistema) y tiene como función primordial determinar la ubicación, cargar y transferir el control al cargador software, llamado así porque es proporcionado por el fabricante del sistema operativo, que es quien tiene la responsabilidad de cargar el sistema operativo pues es quien conoce las particularidades necesarias para la carga.''

== Ejercicio 8 ==
(NO ESTÁN REVISADOS POR PABLO NEIRA, PERO ESTÁN PUBLICADOS COMO SOLUCIONES DE EXÁMENES ANTIGUOS, ESTÁN HECHOS POR ALGÚN OTRO PROFESOR)

En un sistema se dispone de un disco duro con una velocidad de rotación de 10.000 rpm y 100 sectores por pista. Se comprueba empíricamente que cuando los programas procesan información secuencialmente, transcurren aproximadamente 80 microseg entre dos peticiones de sectores consecutivos. ¿Cuántos sectores intercalaría para evitar rotaciones innecesarias? ''Si el disco gira a una velocidad 10.000 rpm, su velocidad de rotación en rps es 10.000/60 = 166,67 rps. El tiempo que tarda en dar una revolución es por tanto 1/166,67 = 5,9*10^-3, y por tanto el tiempo que tarda en pasar un sector es 5,9*10^-3/100= 5,9*10^-5, es decir, 59 microseg. Dado que hemos de intercalar n sectores de manera que n sea el menor tal que n*59 microseg > 80 microseg, hemos de tomar n=2. Dicho de otra manera, un intercalado de un sector sería insuficiente, pues tarda menos tiempo en pasar de lo que se supone que tarda en realizarse la siguiente petición. Por tanto, se intercalan dos sectores
''

Ejercicios de Entrada/Salida

2013-01-14T21:53:34Z

Olgmormar: /* Ejercicio 2 */

== Ejercicio 1 ==
''[Este ejercicio formó parte del cuarto control de Evaluación Continua del curso 2010/11, del 8 de junio de 2011]''

''[Este ejercicio formó parte del cuarto control de Evaluación Continua del curso 2011/12, del 23 de Enero de 2012]''

Suponiendo que el procesador está asignado a un proceso en ejecución, por tanto, es estado activo, qué sucede cuando un dispositivo indica al procesador mediante una interrupción que dispone de datos a ser tratados? Marque la opción pertinente.

A) Se continúa con la ejecución del proceso activo hasta que éste pase a estado bloqueado, entonces se realizar el tratamiento de la interrupción, que consistirá en invocar al gestor de dispositivo para que realice el tratamiento oportuno.

B) Se retira el proceso activo, que pasará a estado preparado, y se ejecutará el código del gestor de dispositivos.

C) Se invoca al planificador de procesos para que evalúe si tiene mayor prioridad la interrupción o el proceso.

''([[Solución de los ejercicios de Entrada/Salida#Ejercicio 1|Ver solución]])''

== Ejercicio 2 ==
''[Este ejercicio formó parte del cuarto control de Evaluación Continua del curso 2010/11, del 8 de junio de 2011]''

''[Este ejercicio formó parte del cuarto control de Evaluación Continua del curso 2011/12, del 23 de Enero de 2012]''

Represente gráficamente el diseño modular basado en capas de E/S de un sistema operativo. Incluya una breve descripción de cada capa junto con flechas que reflejen el flujo de comunicación entre cada una de ellas.

''([[Solución de los ejercicios de Entrada/Salida#Ejercicio 2|Ver solución]])''

== Ejercicio 3 ==
(FALTA REVISIÓN DE PROFESOR)
¿Es lo mismo el cargador software de un sistema operativo que el cargador hardware? En caso negativo, ¿en qué se diferencian? ''No es lo mismo. El cargador hardware es llamado así porque lo proporciona el fabricante del hardware (viene empotrado en la memoria no volátil del sistema) y tiene como función primordial determinar la ubicación, cargar y transferir el control al cargador software, llamado así porque es proporcionado por el fabricante del sistema operativo, que es quien tiene la responsabilidad de cargar el sistema operativo pues es quien conoce las particularidades necesarias para la carga.''

Ejercicios Gestión L/E

2013-01-14T21:51:16Z

Olgmormar: /* Ejercicio 4 */

== Ejercicio 1 ==
''[Este ejercicio formó parte del cuarto Control de Evaluación Contínua del Curso 2010/11, del 8 de junio de 2011]''

Dados la siguiente secuencia de solicitud de accesos a sectores en disco:

3, 80, 15, 45, 1, 79, 4, 20, 21, 67, 19, 23

Indique el orden de accesos, considerando que inicialmente el cabezal se encuentra en la pista 0, para los siguientes criterios. Se considera un orden preferente ascendente:

{| border="2" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 0; background: #f9f9f9; width:800px; border: 1px #aaa solid; border-collapse: collapse; font-size: 95%;"
| 4-scan
|
|
|
|
|
|
|
|
|
|
|
|
|-
| sstf
|
|
|
|
|
|
|
|
|
|
|
|
|-
| 6c-scan
|
|
|
|
|
|
|
|
|
|
|
|
|}

(''[[Solución de los ejercicios de gestión de L/E#Ejercicio 1|Ver solución]]'')

== Ejercicio 2 ==
En un momento dado, un gestor de disco tiene pendiente la siguiente lista de accesos a cilindros: 17,24,20,32,12,37,8,30. Suponiendo que las cabezas lectoras se encuentran actualmente sobre el cilindro 22, indique en qué orden se atenderán estas peticiones si las cabezas se planifican por SCAN,SCAN circular(C-SCAN), o N-SCAN con N=4. Considere como preferente el sentido ascendente.

{| border="2" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 0; background: #f9f9f9; width:800px; border: 1px #aaa solid; border-collapse: collapse; font-size: 95%;"
| scan
|
|
|
|
|
|
|
|
|-
| c-scan
|
|
|
|
|
|
|
|
|-
| 4-scan
|
|
|
|
|
|
|
|
|}

SOLUCIÓN(falta revisión profesor)

{| border="2" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 0; background: #f9f9f9; width:800px; border: 1px #aaa solid; border-collapse: collapse; font-size: 95%;"
| scan
| 24
| 30
|32
| 37
| 20
|17
| 12
| 8
|-
| c-scan
| 24
| 30
|32
| 37
| 8
|12
| 17
| 20
|-
| 4-scan
|24
| 32
|20
| 17
| 30
|37
| 12
| 8
|}

== Ejercicio 3 ==
(NO ESTÁN REVISADOS POR PABLO NEIRA, PERO ESTÁN PUBLICADOS COMO SOLUCIONES DE EXÁMENES ANTIGUOS, ESTÁN HECHOS POR ALGÚN OTRO PROFESOR)
En un momento dado, un gestor de disco tiene pendiente la siguiente lista de accesos a cilindros: 16, 7, 23, 42, 47, 5, 21 y 49. Suponiendo que las cabezas lectoras se encuentran
actualmente sobre el cilindro 17, y que para los algoritmos SCAN y sus derivados, cada ciclo comienza preferiblemente en sentido ascendente, indique en qué orden se atenderán estas peticiones si las cabezas se planifican por menor tiempo de búsqueda (SSTF), algoritmo del ascensor (SCAN), algoritmo SCAN circular (C-SCAN), o NSCAN con N=4.

SSTF 16 21 23 7 5 42 47 49

SCAN 21 23 42 47 49 16 7 5

C-SCAN 21 23 42 47 49 5 7 16

4-SCAN 23 42 16 7 21 47 49 5

== Ejercicio 4 ==
(NO ESTÁN REVISADOS POR PABLO NEIRA, PERO ESTÁN PUBLICADOS COMO SOLUCIONES DE EXÁMENES ANTIGUOS, ESTÁN HECHOS POR ALGÚN OTRO PROFESOR)
En un momento dado, un gestor de disco tiene pendiente la siguiente lista de accesos a cilindros:
50, 47, 1, 40, 2, 52, 72, 75. Suponiendo que las cabezas lectoras se encuentran actualmente sobre el cilindro 45, y que para los algoritmos SCAN y sus derivados, cada ciclo comienza preferiblemente en sentido ascendente, indique en qué orden se atenderán estas peticiones si las cabezas se planifican por menor tiempo de búsqueda (SSTF), algoritmo del ascensor (SCAN), algoritmo SCAN circular (C-SCAN), o N-SCAN con N=4.

SSTF 47 50 52 40 72 75 2 1

SCAN 47 50 52 72 75 40 2 1

C-SCAN 47 50 52 72 75 1 2 40

4-SCAN 47 50 40 1 2 52 72 75

== Ejercicio 5 ==
(NO ESTÁN REVISADOS POR PABLO NEIRA, PERO ESTÁN PUBLICADOS COMO SOLUCIONES DE EXÁMENES ANTIGUOS, ESTÁN HECHOS POR ALGÚN OTRO PROFESOR)

En un momento dado, la cabeza lectora de un disco se encuentra en el cilindro 91 del disco, y el gestor tiene pendientes de atender peticiones de acceso sobre los siguientes cilindros: 90, 80, 85, 94, 5, 88, 87, 92, 93, 95, 81, 82, 83 Sin necesidad de desarrollar paso por paso el algoritmo, ¿cuál de ellas se atendería la última, si el gestor planifica los desplazamientos la cabeza lectora mediante algoritmo SSTF? ''La última en atenderse sería la petición sobre el cilindro 5, pues es el que queda más lejos de la zona en la que inicialmente se encuentra el brazo.
''
== Ejercicio 6 ==
(NO ESTÁN REVISADOS POR PABLO NEIRA, PERO ESTÁN PUBLICADOS COMO SOLUCIONES DE EXÁMENES ANTIGUOS, ESTÁN HECHOS POR ALGÚN OTRO PROFESOR)

En un momento dado, la cabeza lectora de un disco se encuentra en el cilindro 45 del disco, y el gestor tiene pendientes de atender peticiones de acceso sobre las siguientes pistas: 2, 35, 46, 23, 90, 102, 3, 34 ¿En qué orden se atenderán si el gestor planifica los desplazamientos la cabeza lectora mediante algoritmo SSTF? ''En cada momento atenderá la petición que haga referencia al cilindro más cercano al actual. Por tanto, si la cabeza se encuentra inicialmente en el cilindro 45, el orden en que se atenderán las peticiones será: 46, 35, 34, 23, 3, 2, 90, 102.
''

Ejercicios Gestión L/E

2013-01-14T21:47:17Z

Olgmormar: /* Ejercicio 2 */

Algoritmo para averiguar interbloqueo

2012-12-03T18:55:22Z

Olgmormar: /* Algoritmo del Banquero */ Se ha añadido la introducción a este apartado. (Olga M.M.M.)

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

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

Condiciones para el interbloqueo y estrategias de resolución

2012-12-03T18:47:19Z

Olgmormar: /* Detección y Recuperación */ Se han insertado modificaciones en el documento. Lo más significativo son los tipos de matrices de relación recursos-procesos (Olga M. M.M)

== Condiciones para que se produzca interbloqueo ==

Según [http://en.wikipedia.org/wiki/Edward_G._Coffman,_Jr. Coffman], para que se pueda producir un interbloqueo se tienen que dar las siguientes cuatro condiciones:

* '''Exclusión mutua''': cada recurso está asignado a un único proceso de manera exclusiva.
* '''Retención y espera''': los procesos que tienen, en un momento dado, recursos asignados con anterioridad, pueden solicitar nuevos recursos y esperar a que se le asignen sin liberar antes alguno de los recursos que ya tenia asignados.

* '''No apropiación''': los recursos otorgados con anterioridad no pueden ser forzados a dejar un proceso. El proceso que los posee debe liberarlos en forma explícita. Ni siquiera el sistema operativo puede expropiárselo.

* '''Espera circular''': debe existir una cadena circular de dos o más procesos, cada uno de los cuales espera un recurso poseído por el siguiente miembro de la cadena. Esta condición es una consecuencia potencial de las tres primeras, es decir, dado que se producen las tres primeras condiciones, puede ocurrir una secuencia de eventos que desemboque en un círculo vicioso de espera irresoluble.

Las tres primeras condiciones son necesarias, pero no suficientes para que exista interbloqueo. Sólo las cuatro condiciones en conjunto constituyen una condición necesaria y suficiente para el interbloqueo.

== Estrategias ==

Existen diversas estrategias frente a los interbloqueos, que se pueden agrupar en:

* Omisión
* Detección y recuperación
* Prevención
* Predicción

Que se detallan a continuación.

=== Omisión ===

Considera que la probabilidad de un interbloqueo es muy baja, de modo que se confía en que no se van a producir. Por sorprendente que parezca, los sistemas operativos modernos convencionales suelen aplicar esta estrategia. Por justificar la decisión de los fabricantes de sistemas operativos cabe incidir en que las estrategias de resolución y prevención de interbloqueos tienen un coste alto desde el punto de vista del consumo de recursos de procesamiento y memoria.

=== Detección y Recuperación ===

Esta estrategia permite la detección de una situación de interbloqueo y su consiguiente resolución. De entre las medidas de detección consideramos las siguientes:

* ''Grafo de relación recursos-procesos'': Consiste en la representación gráfica de los recursos asignados a los procesos y los recursos que dichos procesos requieren para finalizar su ejecución.Esta técnica se basa en recorrer el grafo yendo de un nodo a otro, por lo que si se consigue volver al nodo de partida estaremos en un recorrido circular. Para que este tipo de error sea detectado usamos algoritmos de detección, se lanzan cuando se solicita un recurso ocupado, es decir, hay una nueva arista dentro de nuestro grafo y debemos comprobar que no da lugar a un recorrido cíclico.

* ''Matrices de relación recursos-procesos'': Consiste en la representación matricial de los recursos asignados a los procesos y los recursos que dichos procesos requieren para finalizar su ejecución.
2 Tipos:

-''Matrices binarias de relación:''
Una matriz binaria de relación es aquella que representa una relación R entre dos conjuntos, en la cual el primero de estos dos tiene múltiples asignaciones a elementos del segundo.

Si aplicamos este concepto a procesos y recursos obtenemos distintos tipos de matrices:

Matrices de espera (W): los procesos esperan uno o varios recursos.

Matrices de asignaciones(A): los procesos tienen asignados uno o varios recursos.

Matrices de procesos a la espera de procesos (T= W•A): un proceso espera a otro, bien porque tiene asignados recursos que necesita, o bien, porque son procesos dependientes.

Tras obtener W, A, y T:
Hemos de calcular el cierre transitivo de la matriz T: por lo que aplicamos el Algoritmo de Warshall, es un algoritmo de análisis sobre grafos para encontrar el camino mínimo entre todos los pares de vértices en una única ejecución. Luego, debemos analizar el resultado que obtenemos, mirando la diagonal de la matriz para saber si los procesos forman parte de un ciclo de interbloqueo.

Esta técnica es un método potente y eficiente, pero hay recursos que tienen varias instancias equivalentes, ¿qué hacemos con ellos?(Sigamos leyendo)

-''Detección matricial'':
Método matricial que trata aquellos casos en los que hay múltiples instancias equivalentes de un mismo tipo de recurso. Aísla grupos de procesos que no pueden proseguir la ejecución porque no pueden ver satisfechas sus peticiones pendientes.
Usan un método iterativo que:

1-Marca procesos cuyas peticiones puedan satisfacerse con el actual vector de recursos disponibles.

2-Suma al vector de disponibles los recursos asignados a los procesos marcados.

3-Si todos los procesos están marcados: no hay interbloqueo.

4-Si en una iteración no se marcan procesos: los procesos que quedan están interbloqueados.

Tras la detección de un interbloqueo, se pueden aplicar algunas de las siguientes estrategias para resolverlo:

* ''Eliminación'': El sistema operativo selecciona a uno de los procesos que forma parte del interbloqueo y elimina el ciclo acabando con la ejecución de dicho proceso, si no es suficiente se eliminarán procesos hasta que se rompa el ciclo. La selección del proceso se realiza en base a un cierto criterio, por ejemplo, aquel proceso que lleve menos tiempo en ejecución o aquel que sea más voraz consumiendo recursos.Sin embargo, de una manera u otra el trabajo realizado por el proceso se pierde. Aunque parezca una medida drástica, es la empleada en sistemas operativos convencionales. Aplicar el criterio de selección y eliminar procesos cuando el número de procesos es relativamente bajo puede solucionar el interbloqueo, pero si se da un bloqueo de por ejemplo, centenares de procesos, es una situación prácticamente inmanejable.

* ''Apropiación temporal'': Se retira la asignación de un recurso a un proceso (durante el tiempo necesario) para deshacer el interbloqueo(hemos de asegurarnos de que el proceso no se desbloquea al romperse el interbloqueo). Por ejemplo, supongamos que el recurso es una impresora: podríamos retirarle la asignación a un proceso P1 cuando este terminase de imprimir una página, asignarle la impresora a otro proceso P2 y volver a asignársela a P1 cuando P2 haya terminado su ejecución.Solo nos surge un único inconveniente, ¿y si los recursos no permiten la apropiación temporal?

* ''Puntos de conformidad'',''sincronismo'' o ''checkpoints'': Consiste en tomar una imagen del estado del proceso, ya sea periódicamente o a instancia del propio proceso, de manera que si se produce un interbloqueo se vuelve a un estado de la ejecución anterior. Son muy poco usados ya que tienen un elevado coste en memoria y existe la posibilidad de que un proceso permanezca indefinidamente sin progresar.

=== Prevención ===

La prevención apunta a una serie de estrategias que eviten el interbloqueo. Concretamente, son cuatro las estrategias de prevención posibles en base a los principios que [http://en.wikipedia.org/wiki/Edward_G._Coffman,_Jr. Coffman] estableció como interbloqueo. Dichas estrategias son:

* ''Supresión de exclusión mutua'': un proceso no puede tener acceso exclusivo a un recurso.
* ''Supresión de retención y espera'' (1ª estrategia de Havender): El proceso debe tener asignado todos los recursos necesarios al inicio y no liberarlos hasta que éste finalice. Esto presenta un inconveniente: si un recurso sólo se utiliza al final, estará ocupado durante toda la ejecución, no permitiendo ser usado por otros procesos. El aprovechamiento de recursos puede mejorarse mediante una programación más elaborada, dividiendo la ejecución del proceso en distintas fases y gestionando los recursos para cada una de ellas.
* ''Supresión de no apropiación'' (2ª estrategia de Havender): Si un proceso está en ejecución y no puede obtener un recurso, dicho proceso libera todos los recursos que está usando y espera a que todos los que necesita estén disponibles. Problemas: se puede perder trabajo, además de presentar una carga extra la realización de peticiones
* ''Supresión de espera circular'' (3ª estrategia de Havender): Si todos los recursos comunes a varios procesos se solicitan siempre en el mismo orden no se producen interbloqueos.

=== Predicción ===

El sistema operativo observa la evolución que siguen los procesos, y predice una posible situación de interbloqueo. Si detecta una alta probabilidad de que suceda, adopta una trayectoria de ejecución nueva para los procesos involucrados de manera que se garantice que no va a suceder un interbloqueo.