Wiki de Sistemas Operativos - Contribuciones del usuario [es]

Subidas de notas

2014-02-27T10:55:27Z

Danababar:

Pérez Asién, Manuel (manperasi)

Rojas Fernández, Alberto (albrojfer1)

Poley González, Cristian (cripolgon)

González Tornay, Ángeles (anggontor1)

Viejo Morales, Francisco Javier (fraviemor)

Abadín Barrantes, Daniel José (danababar)

Mejoras de tiempos de desplazamiento

2014-01-09T11:31:44Z

Danababar: /* Solución 3-SCAN */

La mayor parte del tiempo que se tarda en realizar una búsqueda en un disco magnético corresponde al de desplazamiento, es decir, el tiempo que el cabezal tarda en moverse al cilindro en el que se encuentra su objetivo. Si se debe de atender varias peticiones, el orden en el que se atienden puede ser tal que el recorrido total sea más corto (aunque también es importante que haya una varianza pequeña y no se les de demasiada preferencia a algunos cilindros). Esta sección recoge varios de los criterios posibles.

== FCFS (por orden de llegada "FIFO") ==

Las peticiones se atienden en el mismo orden en que se reciben. Tiene el inconveniente de que se realizan muchos desplazamientos del cabezal, especialmente si se realizan accesos consecutivos a bloques muy alejados entre sí.

== SSTF (Shortest Seek Time First) ==

También conocido como atención por menor tiempo de búsqueda: Ordena todas las solicitudes y selecciona el lote de las ''n'' primeras. Si no se llega a las ''n'' peticiones tras un tiempo se realiza la búsqueda. Su mayor desventaja es que aplaza las peticiones lejanas indefinidamente cuando ''n'' tiende a infinito (''n'' -> ∞).

== N-SCAN (criterio del ascensor) ==

Se escoge un sentido preferente: ascendente o descendente. El cabezal, en ese sentido, atiende todas las peticiones que puede, una detrás de otra, en orden ascendente/descendente hasta llegar a la última de las peticiones del lote. Luego, el cabezal hace lo mismo en el otro sentido, hasta llegar a la última.

|
| /\ | /\
| / \ | / \
| / \ | / \
___|/______\|/______\__
|

Como se puede observar, el cabezal pasa con más frecuencia por la parte central, y el tiempo máximo que puede tardar en llegar a estas es menor que el de los extremos. Por tanto, hay una descompensación a favor de las partes centrales, que puede ser remediada con el siguiente criterio.

Nota: La gráfica resultante no tiene por qué ser simétrica, dependerá de los sectores a los que accedamos.

Nota2: El número de sectores integrantes de cada lote será el indicado por la N, ejemplo: 3-SCAN, 4-SCAN, etc.

== C-SCAN (Circular-Scan) ==

La primera parte es igual: se escoge un sentido y se van atendiendo las peticiones que se pueden en ese sentido una detrás de otra hasta llegar a la última. Al llegar a la última, en vez de recorrer en el sentido opuesto, el cabezal se mueve a la más lejana en el sentido y vuelve a realizar el recorrido en el sentido preferente. Así se elimina el trato favorable a las partes centrales, con el coste de reducir el tiempo medio de atención del conjunto de peticiones

| |
| /. /. /. |\ .\ .\ .
| / . / . / . ó | \ . \ . \ .
| / . / . / . | \ . \ . \ .
___|/___./___._/___._ ___|___\.__ \.___\._
| |

Algún alma caritativa sube los ejemplos de clase antes del parcial??

No copié los datos, pero eran algo similar a esto:

== Ejemplos ==

Orden de acceso: 3, 80, 15, 45, 1, 79, 4

=== Solución FCFS ===

80 x
| / \ x
| / \ / \
50 / \ / \
| / \ x / \
| / \ / \ / \
20 / x \ / \
| x \ / x
___|/___________________x______________
|
| 3 80 15 45 1 79 4

=== Solución 3-SCAN ===

80 x| |
| / |x |
| / | \ |
50 / | \ |
| / | x |
| / | \ |
20 x | \ |
| x | \ |x
___|/________|_______x|__
|
| 3 15 80|79 45 1|4

Evaluame mis contribuciones a la wiki

2013-12-23T17:51:06Z

Danababar:

A continuación, indica tu nombre y apellidos:

* Juan Carlos Roldán Salvador IS-G1
* Daniel Ayala Hernández IS-G1
* Daniel de los Reyes Leal IS-G1
* Olga Minerva Moreno Martín IS-G1
* Vanessa Chipirrás Navalón IC
* Alejandro Sánchez Medina IS-G1
* Francisco Javier Borrego Cejudo IC-G2
* Samuel Martin Arenas IC-G2
* Álvaro Fernández García IS-G1
* Rafael Gomez Galbarro GIC2
* María Pérez Reina IS-G1
* José Antonio Rojo Vidal IS-G1

Evaluame mis contribuciones a la wiki

2013-12-23T17:50:03Z

Danababar:

Criterios de reemplazo

2013-12-12T12:08:45Z

Danababar: /* Aproximación discreta LRU */

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.

<math>tasa fallos pagina = \frac{total fallos de pagina}{total accesos a pagina}</math>

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

[[Archivo:FIFO.jpg]]

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

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

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

Segmentación

2013-11-27T15:59:01Z

Danababar: /* Características */

=Definición=
Un segmento es un espacio de memoria de tamaño variable, compuesto por:
*Descriptor: Identificador único del segmento (dentro del espacio de memoria del proceso).
*Tamaño del segmento

=Funcionamiento=

[[Archivo:Segmentos.png|725px]]

=Características=
*Cada proceso en ejecución (esté activo, bloqueado o preparado) tiene su tabla de segmentos.

*Solapamiento: Se puede hacer que 2 segmentos se superpongan de manera que compartan direcciones de memoria física con direcciones lógicas diferentes. Para evitar problemas de concurrencia, debe de indicarse explícitamente que una porción de memoria puede ser compartida. De esta manera, procesos diferentes pueden compartir información y código usando la memoria común.

*Protección de memoria: añadir 3 bits a la tabla de descriptores de segmentos para los permisos ( r w x ).

*Cuando un proceso requiere más memoria se crea un nuevo segmento.

*Dos instancias de un mismo proceso pueden compartir segmentos de memoria de instrucciones/código, pero no para datos ya que esto complicaría la gestión.

*Es posible la redimensión de un segmento siempre que haya posiciones libres contiguas.

*Gestión compleja, sobretodo por su tamaño variable

*Permite la carga de segmentos a petición, de manera que no se disponga de todos los segmentos en memoria principal, que se puedan descargar a disco (en la zona de intercambio o swap) en base a un cierto criterio (ver [[Intro | Memoria virtual]]). Esta zona de intercambio puede ser:
**Un lugar fijo en el disco (Linux, Unix). El administrador de memoria decide qué segmento se va a descargar
**Un fichero oculto de tamaño fijo o variable dependiendo de la configuración dada por el usuario (Windows).

*La segmentación se hizo para equipos con poca memoria, no está pensada para sistemas modernos.

=Mecanismos=
Los diferentes mecanismos que nos ofrece la segmentación de memoria son los siguientes.
==Carga de segmentos a petición==
Es un mecanismo que permite a un proceso no disponer de todos sus segmentos en memoria principal, se pueden descargar a disco (en la zona de intercambio o swap) segmentos en base a un cierto criterio (ver [[Intro | Memoria virtual]]).

Esta zona de intercambio puede ser:

* Un lugar fijo en el disco (Linux, Unix). El administrador de memoria decide qué segmento se va a descargar

* Un fichero oculto de tamaño fijo o variable dependiendo de la configuracion dada por el usuario (Windows).

==Formas de uso de los descriptores==
En cuanto a aspectos materiales, se plantea el problema de que no es habitual que la tabla de segmentos quepa en el dispositivo de traducción (MMU), por lo que se almacena la tabla en memoria, y el MMU contiene su dirección. El problema es que esta técnica hace que el tiempo de acceso se duplique, al haber un primer acceso al MMU y un segundo acceso a la dirección efectiva. Se plantean dos soluciones no excluyentes:
* '''Uso de registros descriptores de segmento en MMU:'''
<blockquote>
En MMU nos encontraremos varios registros que pueden contener descriptores, en los que se copiarán los que se vayan a usar en un futuro inmediato. Hay dos tipos de registros:
*Registros de propósito general:
Registros sobre los que se cargan los próximos descriptores a usar, y dos tipos de direcciones:
 - Las que hacen referencia a un descriptor en la tabla de memoria (y necesitan más bits para hacer referencia al descriptor)
 - Las que hacen referencia a un descriptor en MMU (y necesitan menos bits para referir al descriptor)
*Registros especializados:
Registros capaces de albergar a un descriptor concreto, como el DS (Para manejo de datos), SS (Para manipulación de pila) o el CS (Para instrucciones de salto y llamadas a rutinas). También existen dos tipos de direcciones:
 - Las que hacen referencia a un descriptor en la tabla de memoria
 - Las que no hacen referencia a ningún descriptor, y emplean descriptores de MMU, según el tipo de instrucción
</blockquote>

* '''Uso de descriptores en memoria asociativa (Cache):'''
<blockquote>
La MMU contiene una memoria asociativa indexada por número de descriptor. Para cada acceso, se busca en la memoria asociativa el número de descriptor, y si no está, se carga a esta (Si se llena la memoria asociativa se lleva a cabo reemplazo). Este tipo de memoria es transparente, por lo que se puede usar en conjunción con registros descriptores de segmento en MMU.
</blockquote>

=Superposición de segmentos=
Varios segmentos pueden estar parcial o totalmente solapados en memoria. Una dirección física se puede corresponder con múltiples direcciones lógicas. Los segmentos superpuestos pueden tener incluso distintos permisos (segmento 0 y 1 ). Si son totalmente superpuestos se denominan segmentos alias.

Se aplica para implementar la técnica de "copy on write" (animación). Se crea inicialmente un segmento de datos, con permiso de lectura y escritura. Al crear el segmento de COW, este se crea con la misma dirección y tamaño (totalmente solapado), pero nótese que se quita el permiso de escritura en ambos segmentos. Si se intenta escribir en uno de los dos, se produce un fallo de protección. Entonces se copia el segundo segmento sobre una nueva ubicación, actualizándose su dirección y restituyéndose en ambos el permiso de escritura.
Otra aplicación: en un micro que no permita modificar segmento de código, se puede crear un segmento alias de dato para modificarlo.

=Crecimiento de proceso=
Existen dos formas de crecimiento: Asignando nuevos segmentos al proceso, y haciendo crecer algún segmento asignado.
Para crecer un segmento: si hay suficiente espacio libre detrás, se cambia el tamaño en el descriptor; si no hay suficiente espacio: se copia al hueco libre (compactando si es necesario) y se cambia el tamaño ( y dirección base, claro está).
Existe la posibilidad de crecimiento automático, a cada segmento se asocia un atributo "permitir crecer"; Si se sobrepasa el límite en un segmento que puede crecer, el tratamiento de la excepción es el que hará crecer al segmento.
Gracias a la segmentación, todas las direcciones son reubicables.

Segmentación

2013-11-27T15:54:03Z

Danababar: /* Características */

=Definición=
Un segmento es un espacio de memoria de tamaño variable, compuesto por:
*Descriptor: Identificador único del segmento (dentro del espacio de memoria del proceso).
*Tamaño del segmento

=Funcionamiento=

[[Archivo:Segmentos.png|725px]]

=Características=
*Cada proceso en ejecución (esté activo, bloqueado o preparado) tiene su tabla de segmentos.

*Solapamiento: Se puede hacer que 2 segmentos se superpongan de manera que compartan direcciones de memoria física con direcciones lógicas diferentes. Para evitar problemas de concurrencia, debe de indicarse explícitamente que una porción de memoria puede ser compartida. De esta manera, procesos diferentes pueden compartir información y código usando la memoria común.

*Protección de memoria: añadir 3 bits a la tabla de descriptores de segmentos para los permisos ( r w x ).

*Cuando un proceso requiere más memoria se crea un nuevo segmento.

*Dos instancias de un mismo proceso pueden compartir segmentos de memoria de instrucciones/código, pero no para datos ya que esto complicaría la gestión.

*Es posible la redimensión de un segmento siempre que haya posiciones libres contiguas.

*Gestión compleja, sobretodo por su tamaño variable

*Permite la carga de segmentos a petición, de manera que no se disponga de todos los segmentos en memoria principal, que se puedan descargar a disco (en la zona de intercambio o swap) en base a un cierto criterio (ver [[Intro | Memoria virtual]]). Esta zona de intercambio puede ser:
**Un lugar fijo en el disco (Linux, Unix). El administrador de memoria decide qué segmento se va a descargar
**Un fichero oculto de tamaño fijo o variable dependiendo de la configuración dada por el usuario (Windows).

=Mecanismos=
Los diferentes mecanismos que nos ofrece la segmentación de memoria son los siguientes.
==Carga de segmentos a petición==
Es un mecanismo que permite a un proceso no disponer de todos sus segmentos en memoria principal, se pueden descargar a disco (en la zona de intercambio o swap) segmentos en base a un cierto criterio (ver [[Intro | Memoria virtual]]).

Esta zona de intercambio puede ser:

* Un lugar fijo en el disco (Linux, Unix). El administrador de memoria decide qué segmento se va a descargar

* Un fichero oculto de tamaño fijo o variable dependiendo de la configuracion dada por el usuario (Windows).

==Formas de uso de los descriptores==
En cuanto a aspectos materiales, se plantea el problema de que no es habitual que la tabla de segmentos quepa en el dispositivo de traducción (MMU), por lo que se almacena la tabla en memoria, y el MMU contiene su dirección. El problema es que esta técnica hace que el tiempo de acceso se duplique, al haber un primer acceso al MMU y un segundo acceso a la dirección efectiva. Se plantean dos soluciones no excluyentes:
* '''Uso de registros descriptores de segmento en MMU:'''
<blockquote>
En MMU nos encontraremos varios registros que pueden contener descriptores, en los que se copiarán los que se vayan a usar en un futuro inmediato. Hay dos tipos de registros:
*Registros de propósito general:
Registros sobre los que se cargan los próximos descriptores a usar, y dos tipos de direcciones:
 - Las que hacen referencia a un descriptor en la tabla de memoria (y necesitan más bits para hacer referencia al descriptor)
 - Las que hacen referencia a un descriptor en MMU (y necesitan menos bits para referir al descriptor)
*Registros especializados:
Registros capaces de albergar a un descriptor concreto, como el DS (Para manejo de datos), SS (Para manipulación de pila) o el CS (Para instrucciones de salto y llamadas a rutinas). También existen dos tipos de direcciones:
 - Las que hacen referencia a un descriptor en la tabla de memoria
 - Las que no hacen referencia a ningún descriptor, y emplean descriptores de MMU, según el tipo de instrucción
</blockquote>

* '''Uso de descriptores en memoria asociativa (Cache):'''
<blockquote>
La MMU contiene una memoria asociativa indexada por número de descriptor. Para cada acceso, se busca en la memoria asociativa el número de descriptor, y si no está, se carga a esta (Si se llena la memoria asociativa se lleva a cabo reemplazo). Este tipo de memoria es transparente, por lo que se puede usar en conjunción con registros descriptores de segmento en MMU.
</blockquote>

=Superposición de segmentos=
Varios segmentos pueden estar parcial o totalmente solapados en memoria. Una dirección física se puede corresponder con múltiples direcciones lógicas. Los segmentos superpuestos pueden tener incluso distintos permisos (segmento 0 y 1 ). Si son totalmente superpuestos se denominan segmentos alias.

Se aplica para implementar la técnica de "copy on write" (animación). Se crea inicialmente un segmento de datos, con permiso de lectura y escritura. Al crear el segmento de COW, este se crea con la misma dirección y tamaño (totalmente solapado), pero nótese que se quita el permiso de escritura en ambos segmentos. Si se intenta escribir en uno de los dos, se produce un fallo de protección. Entonces se copia el segundo segmento sobre una nueva ubicación, actualizándose su dirección y restituyéndose en ambos el permiso de escritura.
Otra aplicación: en un micro que no permita modificar segmento de código, se puede crear un segmento alias de dato para modificarlo.

=Crecimiento de proceso=
Existen dos formas de crecimiento: Asignando nuevos segmentos al proceso, y haciendo crecer algún segmento asignado.
Para crecer un segmento: si hay suficiente espacio libre detrás, se cambia el tamaño en el descriptor; si no hay suficiente espacio: se copia al hueco libre (compactando si es necesario) y se cambia el tamaño ( y dirección base, claro está).
Existe la posibilidad de crecimiento automático, a cada segmento se asocia un atributo "permitir crecer"; Si se sobrepasa el límite en un segmento que puede crecer, el tratamiento de la excepción es el que hará crecer al segmento.
Gracias a la segmentación, todas las direcciones son reubicables.

Condiciones para el interbloqueo y estrategias de resolución

2013-11-21T18:05:05Z

Danababar: /* 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 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, 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. 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 procesos 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;"|'''A:'''
| align="center" style="background:#f0f0f0;"|'''B:'''
|-
| 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 A, se conmuta a B 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;"|'''A:'''
| align="center" style="background:#f0f0f0;"|'''B:'''
|-
| 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

2013-11-21T17:55:10Z

Danababar: /* 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 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, 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. Todos los recursos necesarios del proceso serán protegidos por un mismo semáforo. 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. 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 procesos 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;"|'''A:'''
| align="center" style="background:#f0f0f0;"|'''B:'''
|-
| 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 A, se conmuta a B 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;"|'''A:'''
| align="center" style="background:#f0f0f0;"|'''B:'''
|-
| 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

2013-11-21T17:20:56Z

Danababar: /* Condiciones para que se produzca interbloqueo */

== 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 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, 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. 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. 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 procesos 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;"|'''A:'''
| align="center" style="background:#f0f0f0;"|'''B:'''
|-
| 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 A, se conmuta a B 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;"|'''A:'''
| align="center" style="background:#f0f0f0;"|'''B:'''
|-
| 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.