Wiki de Sistemas Operativos - Contribuciones del usuario [es]

SO multiprogramables con particiones fijas

2015-12-19T10:36:48Z

Paubalmar: /* Mejor ajuste dinámico */

En la administración de memoria con particiones de tamaño fijo consideramos que la memoria se encuentra dividida en porciones fijas de diferente tamaño. La división se realizaría durante la instalación del sistema operativo, y para modificar el esquema de particionamiento necesitaríamos reiniciar el sistema para que surtan efecto los cambios. Por cada partición sólo puede haber un único proceso. Por lo tanto, se pueden ejecutar tantos procesos como particiones haya.

Esta aproximación tiene dos limitaciones importantes, que son:

* Si un proceso necesita más memoria que la partición más grande puede ofrecer, entonces éste no se puede ejecutar.
* Alto desperdicio de memoria, particularmente en el caso de que un proceso ocupe una partición de tamaño mayor al que necesita.

= Criterios de asignación =

Cuando se lanza un programa, el administrador de memoria tiene que decidir en qué partición de memoria va a cargar el proceso recién creado. Para ello se emplean diferentes criterios.

== Mejor ajuste estático ==

Se adjudica a cada proceso a la menor partición en la que quepa. Si la menor partición en la que cabe estuviera ocupada, dicho proceso tiene que esperar a que se libere. Esta estrategia evita el desperdicio de memoria. Sin embargo, puede retrasar la ejecución de un proceso estando libre otras particiones sin usarse. Este mecanismo se puede implementar con una cola por partición. El orden de complejidad computacional sería Ꝋ(1).

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 1 | 4 | 7 |
P3 | 2 | 5 | 8 |
P4 | 3 | 5 | 15 |
P5 | 4 | 3 | 3 |
P6 | 5 | 2 | 17 |

Y la siguiente configuración de memoria:
_____
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 <---|---|---|---|---|---|---> | | | | | | | | | | | | | P1-->M1
M2
P2 | <---|---|---|---> | | | | | | | | | | | | | | | P2-->M2
M2
P3 | | < | | |---|---|---|---|---> | | | | | | | | | | P3-->M2
M3
P4 | | | <---|---|---|---|---> | | | | | | | | | | | | P4-->M3
M1
P5 | | | | < | | |---|---|---> | | | | | | | | | | P5-->M1
M4
P6 | | | | | <---|---> | | | | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

=== Otro ejemplo ===

Tenemos los siguientes procesos: m(P1) = 6KB, m(P2) = 1KB, m(P3) = 3KB, m(P4) = 31KB, m(P5) = 30KB;
suponemos que la decisión sobre la asignación de procesos a particiones se hace ordenadamente de manera
consecutiva según el número del proceso y una memoria de 64 KB divididos en 4 huecos como sigue:

[[solución mejor ajuste estático|Ver solución]]

== Primer ajuste ==

Igual que el anterior, sólo que nuestro proceso pasa a la primera partición libre en la que menor desperdicio de memoria se produzca. Por tanto, los procesos nunca esperan siempre que hay alguna partición libre. Complejidad: O(1)

[[solución primer ajuste|Ver solución]]
=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 1 | 4 | 7 |
P3 | 2 | 5 | 8 |
P4 | 3 | 5 | 15 |
P5 | 4 | 3 | 3 |
P6 | 5 | 2 | 17 |

Y la siguiente configuración de memoria:
_____
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 <---|---|---|---|---|---|---> | | | | | | | | | | | | | P1-->M1
M2
P2 | <---|---|---|---> | | | | | | | | | | | | | | | P2-->M2
M3
P3 | | <---|---|---|---|---> | | | | | | | | | | | | | P3-->M3
M4
P4 | | | <---|---|---|---|---> | | | | | | | | | | | | P4-->M4
M2
P5 | | | | < |---|---|---> | | | | | | | | | | | | P5-->M2
M4
P6 | | | | | < | | |---|---> | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

== Mejor ajuste dinámico ==

De entre todos los procesos que pueden asignarse a una partición, se asigna el mayor proceso que quepa en ella. Por tanto, se itera sobre todos los procesos que se quieren cargar en memoria para ver cuál de ellos es el que menor desperdicio produce. Tal y como sucedía con el mejor ajuste estático, los procesos tienen que esperar a que quede libre la partición en la que menor desperdicio se produce. --[[Usuario:Pneira|Pneira]] 13:40 13 dic 2011 (UTC)

El principal inconveniente de este criterio es que los procesos que mayor desperdicio generan van a ser postergados indefinidamente. Complejidad: Ꝋ(n).

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 0 | 4 | 7 |
P3 | 0 | 5 | 8 |
P4 | 1 | 5 | 15 |
P5 | 1 | 3 | 3 |
P6 | 1 | 2 | 17 |

Y la siguiente configuración de memoria:
_____
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 < | | | | |---|---|---|---|---|---|---> | | | | | | | | P1-->M1
M2
P2 <---|---|---|---> | | | | | | | | | | | | | | | | P2-->M2
M1
P3 <---|---|---|---|---> | | | | | | | | | | | | | | | P3-->M1
M3
P4 | <---|---|---|---|---> | | | | | | | | | | | | | | P4-->M3
M2
P5 | < | | |---|---|---> | | | | | | | | | | | | | P5-->M2
M4
P6 | <---|---> | | | | | | | | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

== Mejor ajuste dinámico con aplazamiento limitado ==

Es una variante del criterio anterior que evita el aplazamiento indefinido. Cuando queda una partición libre, se selecciona el mayor proceso que quepa en ella, pero se cuenta el nº de veces que un proceso se aplaza. Si se superan esas '''n''' veces (umbral), se le da paso.

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 0 | 4 | 7 |
P3 | 0 | 5 | 8 |
P4 | 1 | 5 | 6 |
P5 | 1 | 3 | 7 |
P6 | 1 | 2 | 5 |

Suponiendo que todo proceso puede ser aplazado como máximo una sola vez.

Y la siguiente configuración de memoria:
_____
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M2
P1 < | | | |---|---|---|---|---|---|---> | | | | | | | | |
M2
P2 <---|---|---|---> | | | | | | | | | | | | | | | |
M1
P3 <---|---|---|---|---> | | | | | | | | | | | | | | |
M1
P4 | < | | | | | | |---|---|---|---|---> | | | | | | |
M1
P5 | < | | | |---|---|---> | | | | | | | | | | | |
M2
P6 | < | | | | | | | | | |---|---> | | | | | | |
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

== Subparticiones ==

No es un criterio como tal sino que viene a complementar a los anteriores. Si no hay un proceso que pueda aprovechar la partición madre: se asignan las subparticiones a procesos pequeños (para que el desperdicio interno sea lo menor posible). Si llega un proceso grande: los procesos pequeños se vuelcan a disco hasta que haya sitio para ellos y se asigna la partición madre al proceso grande.

Partición madre: tipo especial de partición que se puede dividir en múltiples particiones menores.

[[Otro ejemplo|Otro ejemplo]]

= Métodos de colocación en memoria =

En el momento de lanzamiento hay que realizar la carga del código del proceso en memoria. Hay diferentes estrategias de colocación, que son:

*'''Montaje absoluto''': El compilador genera un ejecutable que sólo pueda ser cargado en una cierta posición de memoria. Básicamente, las instrucciones de memoria emplean direccionamiento fijo. Se asigna una dirección de memoria fija en tiempo de compilación de manera que cuando se lance el programa tiene que cargarse obligatoriamente en la posición de memoria para la que fue compilada. Por tanto, se trata de un método poco flexible pues requiere la recompilación del programa para ejecutar el proceso en una posición de memoria diferente. Se emplea para la carga del ejecutable en el que se encuentra el sistema operativo nada más comenzar el arranque.

* '''Carga con reubicación''': Es un mecanismo más flexible al anterior. Básicamente, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Luego, en el momento de lanzamiento, se reajustan las instrucciones de acceso a memoria que hay en el código del proceso al cargarlo en una cierta partición. Este reajuste consiste en sumar a la dirección de memoria que hay en el código de cada instrucción de memoria la dirección de comienzo de la partición en la que se va a cargar el procesos. Aunque es un método más flexible que el anterior, no permite migrar de una partición a otra una vez cargado el proceso en memoria.

* '''Reubicación dinámica''': Es el mecanismo más flexible de los tres. De nuevo, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Se supone la existencia de un registro en la arquitectura en el que se carga la posición de memoria de comienzo de la partición. En '''tiempo de ejecución''' se va a sumar a la posición de memoria a la que se quiere acceder la dirección de memoria del registro que contiene el lugar en el que comienza la partición. A diferencia de la carga con reubicación, permite la migración de un proceso de una partición a otra, para ello lo que hay que hacer es modificar el registro y mover el código del proceso a la nueva partición en la que se quiere colocar.

* '''Reubicación dinámica parcial''': Es una variante del anterior, en la que existe también un registro límite.

= Mecanismos de protección de memoria =

Es necesario proteger el SO frente a procesos; y proteger a los procesos entre sí.

* '''Bits de protección''' : Se le asigna a cada zona/partición de la memoria principal una zona con información sobre el propietario y los permisos de lectura/escritura

* '''Ampliación registros valla''' : De esta manera se conocen la posición inicial y final, de manera que si no está entre esas dos posiciones no se permite el acceso a memoria. Los registros de posición inicial y final sólo pueden ser modificados en modo supervisor, por tanto, es el sistema operativo en que durante la conmutación de procesos establece el valor de estos registros.

SO multiprogramables con particiones fijas

2015-12-19T10:32:10Z

Paubalmar: /* Mejor ajuste estático */

En la administración de memoria con particiones de tamaño fijo consideramos que la memoria se encuentra dividida en porciones fijas de diferente tamaño. La división se realizaría durante la instalación del sistema operativo, y para modificar el esquema de particionamiento necesitaríamos reiniciar el sistema para que surtan efecto los cambios. Por cada partición sólo puede haber un único proceso. Por lo tanto, se pueden ejecutar tantos procesos como particiones haya.

Esta aproximación tiene dos limitaciones importantes, que son:

* Si un proceso necesita más memoria que la partición más grande puede ofrecer, entonces éste no se puede ejecutar.
* Alto desperdicio de memoria, particularmente en el caso de que un proceso ocupe una partición de tamaño mayor al que necesita.

= Criterios de asignación =

Cuando se lanza un programa, el administrador de memoria tiene que decidir en qué partición de memoria va a cargar el proceso recién creado. Para ello se emplean diferentes criterios.

== Mejor ajuste estático ==

Se adjudica a cada proceso a la menor partición en la que quepa. Si la menor partición en la que cabe estuviera ocupada, dicho proceso tiene que esperar a que se libere. Esta estrategia evita el desperdicio de memoria. Sin embargo, puede retrasar la ejecución de un proceso estando libre otras particiones sin usarse. Este mecanismo se puede implementar con una cola por partición. El orden de complejidad computacional sería Ꝋ(1).

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 1 | 4 | 7 |
P3 | 2 | 5 | 8 |
P4 | 3 | 5 | 15 |
P5 | 4 | 3 | 3 |
P6 | 5 | 2 | 17 |

Y la siguiente configuración de memoria:
_____
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 <---|---|---|---|---|---|---> | | | | | | | | | | | | | P1-->M1
M2
P2 | <---|---|---|---> | | | | | | | | | | | | | | | P2-->M2
M2
P3 | | < | | |---|---|---|---|---> | | | | | | | | | | P3-->M2
M3
P4 | | | <---|---|---|---|---> | | | | | | | | | | | | P4-->M3
M1
P5 | | | | < | | |---|---|---> | | | | | | | | | | P5-->M1
M4
P6 | | | | | <---|---> | | | | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

=== Otro ejemplo ===

Tenemos los siguientes procesos: m(P1) = 6KB, m(P2) = 1KB, m(P3) = 3KB, m(P4) = 31KB, m(P5) = 30KB;
suponemos que la decisión sobre la asignación de procesos a particiones se hace ordenadamente de manera
consecutiva según el número del proceso y una memoria de 64 KB divididos en 4 huecos como sigue:

[[solución mejor ajuste estático|Ver solución]]

== Primer ajuste ==

Igual que el anterior, sólo que nuestro proceso pasa a la primera partición libre en la que menor desperdicio de memoria se produzca. Por tanto, los procesos nunca esperan siempre que hay alguna partición libre. Complejidad: O(1)

[[solución primer ajuste|Ver solución]]
=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 1 | 4 | 7 |
P3 | 2 | 5 | 8 |
P4 | 3 | 5 | 15 |
P5 | 4 | 3 | 3 |
P6 | 5 | 2 | 17 |

Y la siguiente configuración de memoria:
_____
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 <---|---|---|---|---|---|---> | | | | | | | | | | | | | P1-->M1
M2
P2 | <---|---|---|---> | | | | | | | | | | | | | | | P2-->M2
M3
P3 | | <---|---|---|---|---> | | | | | | | | | | | | | P3-->M3
M4
P4 | | | <---|---|---|---|---> | | | | | | | | | | | | P4-->M4
M2
P5 | | | | < |---|---|---> | | | | | | | | | | | | P5-->M2
M4
P6 | | | | | < | | |---|---> | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

== Mejor ajuste dinámico ==

De entre todos los procesos que pueden asignarse a una partición, se asigna el mayor proceso que quepa en ella. Por tanto, se itera sobre todos los procesos que se quieren cargar en memoria para ver cuál de ellos es el que menor desperdicio produce. Tal y como sucedía con el mejor ajuste estático, los procesos tienen que esperar a que quede libre la partición en la que menor desperdicio se produce. --[[Usuario:Pneira|Pneira]] 13:40 13 dic 2011 (UTC)

El principal inconveniente de este criterio es que los procesos que mayor desperdicio generan van a ser postergados indefinidamente. Complejidad: O(n).

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 0 | 4 | 7 |
P3 | 0 | 5 | 8 |
P4 | 1 | 5 | 15 |
P5 | 1 | 3 | 3 |
P6 | 1 | 2 | 17 |

Y la siguiente configuración de memoria:
_____
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 < | | | | |---|---|---|---|---|---|---> | | | | | | | | P1-->M1
M2
P2 <---|---|---|---> | | | | | | | | | | | | | | | | P2-->M2
M1
P3 <---|---|---|---|---> | | | | | | | | | | | | | | | P3-->M1
M3
P4 | <---|---|---|---|---> | | | | | | | | | | | | | | P4-->M3
M2
P5 | < | | |---|---|---> | | | | | | | | | | | | | P5-->M2
M4
P6 | <---|---> | | | | | | | | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

== Mejor ajuste dinámico con aplazamiento limitado ==

Es una variante del criterio anterior que evita el aplazamiento indefinido. Cuando queda una partición libre, se selecciona el mayor proceso que quepa en ella, pero se cuenta el nº de veces que un proceso se aplaza. Si se superan esas '''n''' veces (umbral), se le da paso.

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 0 | 4 | 7 |
P3 | 0 | 5 | 8 |
P4 | 1 | 5 | 6 |
P5 | 1 | 3 | 7 |
P6 | 1 | 2 | 5 |

Suponiendo que todo proceso puede ser aplazado como máximo una sola vez.

Y la siguiente configuración de memoria:
_____
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M2
P1 < | | | |---|---|---|---|---|---|---> | | | | | | | | |
M2
P2 <---|---|---|---> | | | | | | | | | | | | | | | |
M1
P3 <---|---|---|---|---> | | | | | | | | | | | | | | |
M1
P4 | < | | | | | | |---|---|---|---|---> | | | | | | |
M1
P5 | < | | | |---|---|---> | | | | | | | | | | | |
M2
P6 | < | | | | | | | | | |---|---> | | | | | | |
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

== Subparticiones ==

No es un criterio como tal sino que viene a complementar a los anteriores. Si no hay un proceso que pueda aprovechar la partición madre: se asignan las subparticiones a procesos pequeños (para que el desperdicio interno sea lo menor posible). Si llega un proceso grande: los procesos pequeños se vuelcan a disco hasta que haya sitio para ellos y se asigna la partición madre al proceso grande.

Partición madre: tipo especial de partición que se puede dividir en múltiples particiones menores.

[[Otro ejemplo|Otro ejemplo]]

= Métodos de colocación en memoria =

En el momento de lanzamiento hay que realizar la carga del código del proceso en memoria. Hay diferentes estrategias de colocación, que son:

*'''Montaje absoluto''': El compilador genera un ejecutable que sólo pueda ser cargado en una cierta posición de memoria. Básicamente, las instrucciones de memoria emplean direccionamiento fijo. Se asigna una dirección de memoria fija en tiempo de compilación de manera que cuando se lance el programa tiene que cargarse obligatoriamente en la posición de memoria para la que fue compilada. Por tanto, se trata de un método poco flexible pues requiere la recompilación del programa para ejecutar el proceso en una posición de memoria diferente. Se emplea para la carga del ejecutable en el que se encuentra el sistema operativo nada más comenzar el arranque.

* '''Carga con reubicación''': Es un mecanismo más flexible al anterior. Básicamente, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Luego, en el momento de lanzamiento, se reajustan las instrucciones de acceso a memoria que hay en el código del proceso al cargarlo en una cierta partición. Este reajuste consiste en sumar a la dirección de memoria que hay en el código de cada instrucción de memoria la dirección de comienzo de la partición en la que se va a cargar el procesos. Aunque es un método más flexible que el anterior, no permite migrar de una partición a otra una vez cargado el proceso en memoria.

* '''Reubicación dinámica''': Es el mecanismo más flexible de los tres. De nuevo, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Se supone la existencia de un registro en la arquitectura en el que se carga la posición de memoria de comienzo de la partición. En '''tiempo de ejecución''' se va a sumar a la posición de memoria a la que se quiere acceder la dirección de memoria del registro que contiene el lugar en el que comienza la partición. A diferencia de la carga con reubicación, permite la migración de un proceso de una partición a otra, para ello lo que hay que hacer es modificar el registro y mover el código del proceso a la nueva partición en la que se quiere colocar.

* '''Reubicación dinámica parcial''': Es una variante del anterior, en la que existe también un registro límite.

= Mecanismos de protección de memoria =

Es necesario proteger el SO frente a procesos; y proteger a los procesos entre sí.

* '''Bits de protección''' : Se le asigna a cada zona/partición de la memoria principal una zona con información sobre el propietario y los permisos de lectura/escritura

* '''Ampliación registros valla''' : De esta manera se conocen la posición inicial y final, de manera que si no está entre esas dos posiciones no se permite el acceso a memoria. Los registros de posición inicial y final sólo pueden ser modificados en modo supervisor, por tanto, es el sistema operativo en que durante la conmutación de procesos establece el valor de estos registros.

Criterios de reemplazo

2015-12-18T10:32:59Z

Paubalmar:

La evaluación se hace en base a la '''tasa de fallos de página''', que es el número de fallos de página entre el número de accesos totales a página, con lo que su valor oscila en el rango [0,1].

El fallo de página se produce cuando se accede a una posición de memoria que pertenece a una página de memoria que esta descargada en disco.

Tasa fallos pagina = total fallos de pagina/total accesos a pagina

También hay que tener en cuenta el contexto, si estamos en arranque en frío o en caliente, así como el cumplimiento del principio de localidad espacial y temporal.

* Arranque en frío: se dan muchos fallos de página al principio, ya que los procesos se acaban de lanzar y ninguno está cargado en memoria principal.
* Arranque en caliente: se suponen ya cargadas las páginas de los procesos en memoria principal.

== Criterio de página óptima (OPT, MIN) ==

Este es un criterio teórico que viene a establecer la cota inferior de la tasa de ''fallos de página''. Consiste en escoger la página que mayor tiempo va a tardar en utilizarse. Este es el mejor caso, pero se necesita conocimiento de futuro, de ahí que sea un criterio teórico.

Ejemplo: Secuencia de acceso a página : 2,2,3,1,1,3,4,5,1,1,2,3,4
Suponiendo arranque en frío
Marco Marco Marco Marco
1 2 3 4
Memoria principal +-----+-----+-----+-----+
de 4 marcos | | | | |
+-----+-----+-----+-----+

*[[sol_1|Solución]]

Otra forma de evaluar la eficiencia de un criterio de selección de página víctima es observando su curva paracorde, que relaciona el nº de fallos de página con el nº de marcos. La de un buen criterio se aproximará a la curva del criterio óptimo, y la de uno malo, a la del criterio al azar, o incluso pésimo.

[[Archivo:Curvas paracordes.jpg]]

En el siguiente ejemplo real se compara la efectividad de varios criterios en varios programas:

[[Archivo:img26.png]]

== Criterio de página pésima (MAX)==

Este también es teórico y viene a establecer la cota superior de la ''tasa de fallos de página'', para ver lo peor que podría comportarse un criterio. Consiste en seleccionar la página que menor tiempo tardará en usarse. También implica tener conocimiento de futuro, por lo que no es implementable en la práctica.

*[[sol_2|Solución]]

== Criterio de selección estocástica (aleatoria) ==

Se trata también de un criterio teórico, serviría para aproximar la cota media de la ''tasa de fallos de página''. Consiste en seleccionar una página al azar.

Dado que su implementación es trivial, cualquier algoritmo que de resultados similares a este será un mal criterio, pues seguro que su eficiencia será menor que la de no implementar ningún criterio y seleccionar una página al azar.

== Criterio MRU('''M'''ost '''R'''ecently '''U'''sed) ==

Se selecciona la última página a la que se ha accedido. Podría implementarse con una LIFO por orden de acceso. Es una aproximación implementable en la práctica del criterio MAX, pudiendo así compararlo con otros criterios. Según el principio de localidad, mientras más recientemente se haya accedido a una página, más probable es que vuelva a accederse a ella. Por ello, este criterio es muy deficiente, siendo su curva cercana a la pésima:

[[Archivo:MRU.jpg]]

*[[sol_3|Solución]]

== Criterio por orden de carga FIFO ==

Se selecciona la página que más tiempo lleva cargada en memoria principal. Se implementa con una FIFO por orden de carga, es decir, a medida que se cargan en memoria principal las páginas son añadidas a la cola.

El inconveniente de este criterio es que las páginas más usadas son las que más tiempo deberían permanecer en memoria, y son las más atacadas. No se debe suponer que, si las páginas “dejarán de ser necesarias”, implica que “ya no sean necesarias”.
Además, se produce la anomalía de Belady, efecto que consiste en la posibilidad de tener más fallos de página al aumentar el número de marcos en la memoria física:

*[[sol_5|Solución]]

== Criterio NRU ('''N'''ot '''R'''ecently '''U'''sed) ==

Ofrece dos bits para cada página:
* Bit R : Se pone a 1 si la página ha sido usada (tanto para lectura como para escritura).
* Bit M : Se pone a 1 si la página es modificada (escritura).

En resumen, el bit R se pondrá a 1 ante cualquier tipo de acceso, y el bit M se pondrá a 1 sólo ante eventos de escritura.

Para seleccionar la página víctima iteramos sobre los marcos cargados en memoria (comenzando por el primero de ellos) buscando el que cumpla lo siguiente, en este orden:

# R=0, M=0
# R=0, M=1
# R=1, M=0
# R=1, M=1

Periódicamente se pone a cero el bit R.

[[Archivo:LRU.jpg]]

*[[sol_6|Solución]]

== Criterio de 2ª oportunidad ==

Se trata de la combinación de los criterios FIFO y NRU, pero sin emplear el bit M de NRU. Cuando hay que seleccionar una página víctima, se recorre la lista de páginas por orden de carga en memoria hasta encontrar alguna que tenga el bit R a 0. Durante la iteración, si se encuentra una cuyo bit R valga 1, se pone a 0, se retira de la lista y se añade al final (para darle una segunda oportunidad). Cuando se añade una nueva página, se añade al final de la cola con el bit R a 1.
Añadir que, en este caso, no se pone el bit R a 0 periódicamente, ya que se hace directamente con la 2ª oportunidad.

[[Archivo:Segunda Oportunidad.jpg]]

*[[sol_7|Solución]]

;Criterio del reloj: Es una variante en la manera de implementar la 2ª oportunidad. Se emplea una lista circular. En lugar de eliminar y añadir elementos al final de la FIFO, mantenemos un puntero a la página siguiente a la última página víctima seleccionada, de manera que para dar la 2ª oportunidad a una página, sólo hemos de poner su bit R a 0 y pasar al siguiente.

*[[sol_reloj|Solución]]

==Criterio de la 3ª oportunidad (Método Multics)==
Es otra variante del criterio NRU, en la que se mantiene una lista ordenanda por orden de carga. Ante una sustitución, la primera candidata es la más antigua.

Si dicha página tiene el bit R a 1, se pone a 0 y se pasa al final de la lista (recibe una segunda oportunidad).

Si dicha página tiene el bit R a 0, existen dos casos:
*Si tiene el bit M a 1, se pone a 0 y se pasa al final de la lista.
*Si tiene el bit M a 0, se selecciona como página víctima.

[[Archivo:Tercera oportunidad.jpg]]

*[[sol_tercera_oportunidad|Solución]]

== Criterio LRU ('''L'''east '''R'''ecently '''U'''sed) ==

Es justamente el criterio contrario al MRU. En LRU elegimos la página que más tiempo lleve sin ser accedida. Se implementa mediante una FIFO que mantiene el '''orden de acceso''' a las páginas. Es decir, cada vez que se accede a una página, en caso de estar ya en la FIFO, se retira de la cola y se añade al final.

*[[sol_8|Solución]]

== Criterio LFU ('''L'''east '''F'''recuently '''U'''sed) ==

Se selecciona a la página que haya sido accedida con menor frecuencia. Se implementa mediante un contador. Básicamente, por cada acceso se incrementa el contador de uso de la página. La página víctima será aquella con menor contador. Cuando una página es expulsada a disco su contador pasa a ser cero. Es inviable en la práctica, pues supone mantener contadores de tamaños muy grande, uno por cada página en memoria, y por cada acceso a memoria podría ser necesario ejecutar una rutina que actualice la lista.

*[[sol_9|Solución]]

== Aproximación discreta LRU ==

Se tiene un bit R y un contador por cada página. Cuando una página es cargada a un marco, se carga con su bit R a 1 y su contador inicial a 0. Cuando pasa un período determinado de tiempo (viene dado en el enunciado) se itera sobre toda la lista de páginas, y pueden ocurrir dos cosas:
* '''Si su bit R está a 1''': Se ponen su bit R a cero y su contador se incrementa.
* '''Si su bit R está a 0''': No se hace nada.

Cuando hay que seleccionar una página víctima, se escoge aquella cuyo contador sea más pequeño. En caso de empate, habrá que establecer un criterio de desempate.

*[[sol_9.2|Solución]]

== Sustitución por envejecimiento ==

Se emplea un registro R de N bits, asociado a cada página. Por cada acceso se pone a 1 el bit más significativo. Periódicamente se desplaza hacia la derecha el registro R. La página víctima será la que tenga el menor valor en el registro R (en caso de empate se emplea otro criterio). La información que contienen los bits menos significativos se pierden al realizar desplazamientos. Este criterio permite mantener un historial de acceso a las páginas, para seleccionar como víctima aquella que lleve más tiempo sin ser accedida.

*[[sol_10|Solución]]

= Implementaciones =

En el [[Algoritmos de criterios de reemplazo|Portal de la comunidad]] se encuentran implementados algunos de los anteriores criterios como ayuda para ver su funcionamiento.
Creo que los algoritmos están bien (coinciden con las soluciones), pero si alguien decide probarlos no estaría mal que los revisase por encima. --[[Usuario:Alexrdp|Alexrdp]] 16:24 6 jun 2011 (UTC)

Condiciones para el interbloqueo y estrategias de resolución

2015-11-29T15:38:23Z

Paubalmar: /* Prevención */

= 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 tenía 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.

Un ejemplo de grafo en el que se detecta un ciclo es el siguiente:

[[Archivo:deteccion_ciclo.png]]

* ''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. Se distinguen dos tipos, el '''método mediante matrices binarias de relación''', y el '''método de detección matricial''':

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

El método consiste en, aplicando matrices binarias de relación, utilizar el cierre transitivo para determinar si algún proceso está relacionado consigo mismo a través de otros, señalando así la existencia de ciclos. El procedimiento sería:

1.- Formar la matriz de espera (W: P->R): Los procesos P están a la espera de recursos R.

2.- Formar la matriz de asignación (A: R->P): Los recursos R están asignados a procesos P.

3.- Formar la matriz de procesos a la espera de procesos (T: WxA): Producto cartesiano de ambas matrices.

4.- Hallar el cierre transitivo de la matriz T: Que se puede obtener, por ejemplo, aplicando el Algoritmo de Warshall (algoritmo de análisis sobre grafos para encontrar el camino mínimo entre todos los pares de vértices en una única ejecución). El algoritmo es el siguiente:

Warshall(T, n){
for (k=1 to n){
for (i=1 to n){
for (j=1 to n){
Tij = Tij ⋁ (Tik ⋀ Tkj)
}
}
}
}

Donde n es la dimensión de la matriz T

5.- Si hay procesos que tengan un 1 en la diagonal principal, forman parte de algún ciclo.

Se trata de un método fácil de implementar, ya que solo se realizan operaciones con matrices y bucles, algo muy sencillo para una máquina. Sim embargo, tiene dos inconvenientes:
* El número de operaciones a realizar es muy alto teniendo en cuenta el tamaño que pueden alcanzar las matrices de recursos
* Solo se puede usar cuando solo existe una instancia de cada recurso.

=== Detección matricial ===
Método matricial que trata aquellos casos en los que existen múltiples instancias de un mismo 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.

== Resolución de interbloqueo ==

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, algo que en algunos casos resulta inadmisible, como en sistemas en tiempo real. 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. El problema es que este método solo es posible dependiendo de la naturaleza del proceso. Con frecuencia es imposible recuperarse de esta manera ya que los recursos no pueden ser apropiados.

* ''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, y no todos los recursos permiten almacenar y recuperar su estado. Además, puede darse el caso de que el estado del proceso sea externo al sistema (Como en el caso de una conexión a Base de Datos)

== 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. No siempre es posible, y puede que lo único que haga sea cambiar el problema de sitio. Es una solución drástica, inviable. Por ejemplo, permitir que dos procesos usaran a la vez una impresora sería caótico.
* ''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, se consigue utilizando un mismo semáforo para todos los recursos necesarios por el proceso. 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. Sin embargo, muchos procesos no saben cuántos recursos necesitarán hasta que hayan empezado a ejecutarse. No obstante, esta estrategia presenta unos inconvenientes: la posibilidad de aplazamiento indefinido por parte de aquellos procesos que usan más recursos, que siempre cuando no le falta uno le falta otro, lo que concluye en un mal aprovechamiento de recursos, obligando a los procesos a solicitar los recursos antes de que les haga falta y atentando contra el objetivo eficiente que nos proponemos.
* ''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. Es una estrategia optimista, usada cuando la probabilidad de que se produzca un interbloqueo en el sistema es baja. 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. De esta manera, se ordenan los recursos y se solicitan en ese orden. Por ejemplo: tenemos un proceso P1 y otro P2, de manera que ambos hacen uso de los recursos X e Y. En el siguiente caso, no pedirían los recursos en el mismo orden:

{| {{table}}
| align="center" style="background:#f0f0f0;"|'''P1:'''
| align="center" style="background:#f0f0f0;"|'''P2:'''
|-
| down(X)||down(Y)
|-
| down(Y)||down(X)
|-
| …||…
|-
| up(Y)||up(X)
|-
| up(X)||up(Y)
|}

Si se ejecuta la instrucción down(X) de P1, se conmuta a P2 y se ejecuta down(Y), se producirá un interbloqueo, ya que ambos estarán esperando a que el otro libere el recurso que necesitan.
Sin embargo, si pedimos los recursos siempre en el mismo orden de la siguiente forma:

{| {{table}}
| align="center" style="background:#f0f0f0;"|'''P1:'''
| align="center" style="background:#f0f0f0;"|'''P2:'''
|-
| down(X)||down(X)
|-
| down(Y)||down(Y)
|-
| …||…
|-
| up(Y)||up(Y)
|-
| up(X)||up(X)
|-
|
|}

Se puede comprobar que es imposible que se de un interbloqueo como en el caso anterior, ocurriendo lo mismo con cualquier número de procesos y recursos.

El principal inconveniente radica en que a veces, debido a la variedad y al número de recursos y procesos, es muy engorroso mantener un criterio de orden para todos los procesos de todo tipo.

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

Si tuviéramos de antemano información sobre cómo los procesos van a usar los recursos, tal vez podríamos forzar un entrelazado de las asignaciones que nunca llevase a interbloqueo. Es un ejemplo el algoritmo del banquero. El inconveniente de este tipo de técnicas es que son poco realistas, ya que en sistemas reales no tenemos forma de predecir a la perfección el futuro de accesos a recursos.

Condiciones para el interbloqueo y estrategias de resolución

2015-11-29T15:37:44Z

Paubalmar: /* Prevención */ cambio A, B por p1 p2

= 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 tenía 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.

Un ejemplo de grafo en el que se detecta un ciclo es el siguiente:

[[Archivo:deteccion_ciclo.png]]

* ''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. Se distinguen dos tipos, el '''método mediante matrices binarias de relación''', y el '''método de detección matricial''':

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

El método consiste en, aplicando matrices binarias de relación, utilizar el cierre transitivo para determinar si algún proceso está relacionado consigo mismo a través de otros, señalando así la existencia de ciclos. El procedimiento sería:

1.- Formar la matriz de espera (W: P->R): Los procesos P están a la espera de recursos R.

2.- Formar la matriz de asignación (A: R->P): Los recursos R están asignados a procesos P.

3.- Formar la matriz de procesos a la espera de procesos (T: WxA): Producto cartesiano de ambas matrices.

4.- Hallar el cierre transitivo de la matriz T: Que se puede obtener, por ejemplo, aplicando el Algoritmo de Warshall (algoritmo de análisis sobre grafos para encontrar el camino mínimo entre todos los pares de vértices en una única ejecución). El algoritmo es el siguiente:

Warshall(T, n){
for (k=1 to n){
for (i=1 to n){
for (j=1 to n){
Tij = Tij ⋁ (Tik ⋀ Tkj)
}
}
}
}

Donde n es la dimensión de la matriz T

5.- Si hay procesos que tengan un 1 en la diagonal principal, forman parte de algún ciclo.

Se trata de un método fácil de implementar, ya que solo se realizan operaciones con matrices y bucles, algo muy sencillo para una máquina. Sim embargo, tiene dos inconvenientes:
* El número de operaciones a realizar es muy alto teniendo en cuenta el tamaño que pueden alcanzar las matrices de recursos
* Solo se puede usar cuando solo existe una instancia de cada recurso.

=== Detección matricial ===
Método matricial que trata aquellos casos en los que existen múltiples instancias de un mismo 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.

== Resolución de interbloqueo ==

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, algo que en algunos casos resulta inadmisible, como en sistemas en tiempo real. 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. El problema es que este método solo es posible dependiendo de la naturaleza del proceso. Con frecuencia es imposible recuperarse de esta manera ya que los recursos no pueden ser apropiados.

* ''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, y no todos los recursos permiten almacenar y recuperar su estado. Además, puede darse el caso de que el estado del proceso sea externo al sistema (Como en el caso de una conexión a Base de Datos)

== 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. No siempre es posible, y puede que lo único que haga sea cambiar el problema de sitio. Es una solución drástica, inviable. Por ejemplo, permitir que dos procesos usaran a la vez una impresora sería caótico.
* ''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, se consigue utilizando un mismo semáforo para todos los recursos necesarios por el proceso. 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. Sin embargo, muchos procesos no saben cuántos recursos necesitarán hasta que hayan empezado a ejecutarse. No obstante, esta estrategia presenta unos inconvenientes: la posibilidad de aplazamiento indefinido por parte de aquellos procesos que usan más recursos, que siempre cuando no le falta uno le falta otro, lo que concluye en un mal aprovechamiento de recursos, obligando a los procesos a solicitar los recursos antes de que les haga falta y atentando contra el objetivo eficiente que nos proponemos.
* ''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. Es una estrategia optimista, usada cuando la probabilidad de que se produzca un interbloqueo en el sistema es baja. 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. De esta manera, se ordenan los recursos y se solicitan en ese orden. Por ejemplo: tenemos un proceso A y otro B, de manera que ambos hacen uso de los recursos X e Y. En el siguiente caso, no pedirían los recursos en el mismo orden:

{| {{table}}
| align="center" style="background:#f0f0f0;"|'''P1:'''
| align="center" style="background:#f0f0f0;"|'''P2:'''
|-
| down(X)||down(Y)
|-
| down(Y)||down(X)
|-
| …||…
|-
| up(Y)||up(X)
|-
| up(X)||up(Y)
|}

Si se ejecuta la instrucción down(X) de P1, se conmuta a P2 y se ejecuta down(Y), se producirá un interbloqueo, ya que ambos estarán esperando a que el otro libere el recurso que necesitan.
Sin embargo, si pedimos los recursos siempre en el mismo orden de la siguiente forma:

{| {{table}}
| align="center" style="background:#f0f0f0;"|'''P1:'''
| align="center" style="background:#f0f0f0;"|'''P2:'''
|-
| down(X)||down(X)
|-
| down(Y)||down(Y)
|-
| …||…
|-
| up(Y)||up(Y)
|-
| up(X)||up(X)
|-
|
|}

Se puede comprobar que es imposible que se de un interbloqueo como en el caso anterior, ocurriendo lo mismo con cualquier número de procesos y recursos.

El principal inconveniente radica en que a veces, debido a la variedad y al número de recursos y procesos, es muy engorroso mantener un criterio de orden para todos los procesos de todo tipo.

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

Si tuviéramos de antemano información sobre cómo los procesos van a usar los recursos, tal vez podríamos forzar un entrelazado de las asignaciones que nunca llevase a interbloqueo. Es un ejemplo el algoritmo del banquero. El inconveniente de este tipo de técnicas es que son poco realistas, ya que en sistemas reales no tenemos forma de predecir a la perfección el futuro de accesos a recursos.