Wiki de Sistemas Operativos - Contribuciones del usuario [es]

Semáforos

2013-01-19T15:00:47Z

Dandelea:

= Planificador de procesos: Diagrama de estados simplicado =

Para comprender apropiadamente cómo funcionan los semáforos es importante recordar cómo funciona el [[Estados de los procesos|diagrama de estados de los procesos]]

= Semáforos =

Los semáforos son un mecanismo de sincronización de procesos inventados por [http://es.wikipedia.org/wiki/Edsger_Dijkstra Edsger Dijkstra] en 1965. Los semáforos permiten al programador '''asistir al planificador del sistema operativo en su toma de decisiones''' de manera que permiten sincronizar la ejecución de dos o más procesos. A diferencia de los [[cerrojos]], los semáforos nos ofrecen un mecanismo de espera no ocupada.

Los semáforos son un tipo de datos que están compuestos por dos atributos:

* Un contador, que siempre vale >= 0.
* Una lista de procesos(lista formada por el PCB de cada proceso), inicialmente vacía.

Y disponen de dos operaciones básicas que pasamos a describir en pseudocódigo:

<source lang="c">
down(semáforo s)
{
si s.contador == 0:
añade proceso a s.lista
proceso a estado bloqueado
sino:
s.contador--
}
</source>

En el pseudocódigo anterior, se puede añadir a la lista un proceso o un hilo.

Nótese que siempre que queramos forzar una transición de un proceso a estado bloqueado, tenemos que hacer que dicho proceso realice una operación ''down'' sobre un semáforo cuyo contador vale cero.

<source lang="c">
up(semáforo s)
{
si hay procesos en s.lista
retira proceso de s.lista
proceso a estado preparado
sino:
s.contador++
}
</source>

Nótese que una operación ''up'' sobre un semáforo en el que hay procesos en su lista resulta en que se retire uno de los procesos (el que más tiempo lleva en la lista), realizando éste la transición a estado preparado. Es un error frecuente pensar que una operación ''up'' resulte en que el proceso retirado de la lista pase a estado activo. Recuerde que las transiciones de estado activo a preparado y viceversa son siempre controladas por el planificador del sistema operativo.

Además, se disponen de un constructor y un destructor que permiten la creación y la liberación de un semáforo.

=== Ejemplo de uso de semáforos ===

Suponga el siguiente ejemplo en el que se quieren sincronizar dos hilos de un proceso, de manera que se dé la siguiente secuencia de ejecución: A, B, A, B, ... y así sucesivamente. El siguiente código resolvería el problema:

<source lang="c">
semaforo a = semaforo.create(1);
semaforo b = semaforo.create(0);

/* código del hilo A */
while (1) {
a.down();
printf("hilo A\n");
b.up();
}

/* código del hilo B */
while (1) {
b.down();
printf("hilo B\n");
a.up();
}
</source>

=== Tipos de semáforos ===

Dependiendo de la función que cumple el semáforo, vamos a diferenciar los siguientes tipos:

* Semáforo de exclusión mutua, inicialmente su contador vale 1 y permite que haya un único proceso simultáneamente dentro de la sección crítica.
* Semáforo contador, permiten llevar la cuenta del número de unidades de recurso compartido disponible, que va desde 0 hasta N.
* Semáforo de espera, generalmente se emplea para forzar que un proceso pase a estado bloqueado hasta que se cumpla la condición que le permite ejecutarse. Por lo general, el contador vale 0 inicialmente, no obstante, podría tener un valor distinto de cero.

=== Ventajas e inconvenientes ===

La principal ventaja de los semáforos frente a los [[cerrojos]] es que permiten sincronizar dos o más procesos de manera que no se desperdician recursos de CPU realizando comprobaciones continuadas de la condición que permite progresar al proceso.

Los inconvenientes asociados al uso de semáforos son los siguientes:

* Los programadores tienden a usarlos incorrectamente, de manera que no resuelven de manera adecuada el problema de concurrencia o dan lugar a interbloqueos.
* No hay nada que obligue a los programadores a usarlos.
* Los compiladores no ofrecen ningún mecanismo de comprobación sobre el correcto uso de los semáforos.
* Son independientes del recurso compartido al que se asocian.

Debido a estos inconvenientes, se desarrollaron los [[Monitores|monitores]].

=== Granularidad ===
Número de recursos controlados por cada semáforo. Hay de dos tipos:
* Granularidad fina: Un recurso por semáforo. Hay un mayor grado de paralelismo, lo que puede mejorar la rapidez de ejecución de la protección. Aunque a mayor número de semáforos existe una mayor probabilidad de que se de un interbloqueo entre semáforos, que no sería una mejora de lo que intentamos evitar.
* Granularidad gruesa: Un semáforo para todos los recursos. Caso totalmente inverso al anterior: Ahora al tener un semáforo no se produce interbloqueo entre ellos, aunque los tiempos de ejecución son excesivamente largos.

Tipos de Sistemas Operativos

2013-01-19T09:55:28Z

Dandelea: /* Características que pueden presentar: */

= 1.3. Tipos de Sistemas Operativos =
== 1.3.1. Según cuántas aplicaciones pueda ejecutar a la vez ==

=== '''Monoprogramables'''===
*En un determinado instante de tiempo, '''sólo hay un único proceso en ejecución que monopoliza todos los recursos''' del sistema.
*Principal ventaja: su sencillez.
* Generalmente, no tienen mecanismos de protección de memoria (esta característica los hace más proclives a virus).
*Dos subtipos:
**Ofrece intérprete de órdenes.
**Ofrece entrada a través de cinta/switches (SSOO históricos).
*Ejemplo: DOS.

=== '''Multiprogramables''' ===

*Permiten ejecutar '''múltiples procesos en un único procesador'''. Se tienen varios programas cargados simultáneamente en la memoria, así que el SO debe controlar los accesos y los espacios de la misma.
*Tienen mecanismos de protección del espacio de memoria (el SO impide que una aplicación acceda al espacio de memoria de otra).

====Características que pueden presentar:====

*Multiprogramación: se ejecutan varios procesos simultáneamente de manera que se reparte el uso del procesador. A esta característica también se le llama (de forma imprecisa) "Multitarea".
**Multiusuario: admite múltiples usuarios trabajando simultáneamente.
**Multiacceso: el sistema ofrece varios terminales (mecanismos) para acceso concurrente a él.
**Multiprocesamiento o multiprocesadores: soporta más de un procesador y hace uso de todos ellos.
***Tipos de sistemas multiprocesadores: Podemos diferencias 3 tipos: especializados, con acoplamiento débil y con acoplamiento fuerte:
****Sistemas multiprocesadores con procesadores especializados: Son sistemas que cuentan con un procesador de propósito general y varios procesadores especializados (como por ejemplo coprocesadores aritméticos o el procesador de una tarjeta gráfica). Dichos procesadores especializados solo son capaces de ejecutar un conjunto de operaciones especificas y funcionan únicamente cuando el procesador general se lo solicita, en ese momento colaboran con el procesador general.
****Sistemas multiprocesadores con acoplamiento débil: Son sistemas con procesadores relativamente independientes, cada uno tiene su propia memoria y sus propios canales de E/S.
****Sistemas multiprocesadores con acoplamiento fuerte: Son sistemas con varios procesadores de propósito general independientes entre sí pero que comparten la memoria y trabajan bajo un sistema operativo común.
**Tiempo real: intenta garantizar que determinadas tareas se ejecuten en un plazo de tiempo determinado. Atendiendo al nivel de exigencia, se subdividirían en dos: '''soft''' (suave) o '''flexible''' y hard(duro) o '''estricto'''.Un ejemplo puede ser el sistema operativo de tiempo real instalado en el procesador de un teléfono móvil; si llega una llamada tiene que pasarla en ese momento, sino ese proceso deja de ser importante.
**Distribuido: permite la ejecución de múltiples procesos en diferentes máquinas comunicadas por un enlace de red. El primer SO en soportar esta característica fue [http://es.wikipedia.org/wiki/Plan_9_from_Bell_Labs Plan 9] de ''Bell Labs''.

== 1.3.2. Según cómo se presta el servicio ==

Clasificación no excluyente:

* Sistemas operativos de servidor
* Sistemas operativos de ordenador personal
* Sistemas operativos en tiempo real
* Sistemas operativos embarcados / integrados / "embebidos", ejemplos, dispositivos móviles o smartcard.
* Sistemas operativos web

2.1 [[Organización básica de un ordenador]]

Tipos de Sistemas Operativos

2013-01-19T09:54:05Z

Dandelea: /* Características que pueden presentar: */

= 1.3. Tipos de Sistemas Operativos =
== 1.3.1. Según cuántas aplicaciones pueda ejecutar a la vez ==

=== '''Monoprogramables'''===
*En un determinado instante de tiempo, '''sólo hay un único proceso en ejecución que monopoliza todos los recursos''' del sistema.
*Principal ventaja: su sencillez.
* Generalmente, no tienen mecanismos de protección de memoria (esta característica los hace más proclives a virus).
*Dos subtipos:
**Ofrece intérprete de órdenes.
**Ofrece entrada a través de cinta/switches (SSOO históricos).
*Ejemplo: DOS.

=== '''Multiprogramables''' ===

*Permiten ejecutar '''múltiples procesos en un único procesador'''. Se tienen varios programas cargados simultáneamente en la memoria, así que el SO debe controlar los accesos y los espacios de la misma.
*Tienen mecanismos de protección del espacio de memoria (el SO impide que una aplicación acceda al espacio de memoria de otra).

====Características que pueden presentar:====

*Multiprogramación: se ejecutan varios procesos simultáneamente de manera que se reparte el uso del procesador. A esta característica también se le llama (de forma imprecisa) "Multitarea".
**Multiusuario: admite múltiples usuarios trabajando simultáneamente.
**Multiacceso: el sistema ofrece varios terminales (mecanismos) para acceso concurrente a él.
**Multiprocesamiento o multiprocesadores: soporta más de un procesador y hace uso de todos ellos.
***Tipos de sistemas multiprocesadores: Podemos diferencias 3 tipos: especializados, con acoplamiento débil y con acoplamiento fuerte:
****Sistemas multiprocesadores con procesadores especializados: Son sistemas que cuentan con un procesador de propósito general y varios procesadores especializados (como por ejemplo coprocesadores aritméticos o el procesador de una tarjeta gráfica). Dichos procesadores especializados solo son capaces de ejecutar un conjunto de operaciones especificas y funcionan únicamente cuando el procesador general se lo solicita, en ese momento colaboran con el procesador general.
****Sistemas multiprocesadores con acoplamiento débil: Son sistemas con procesadores relativamente independientes, cada uno tiene su propia memoria y sus propios canales de E/S.
****Sistemas multiprocesadores con acoplamiento fuerte: Son sistemas con varios procesadores de propósito general independientes entre sí pero que comparten la memoria y trabajan bajo un sistema operativo común.
**Tiempo real: intenta garantizar que determinadas tareas se ejecuten en un plazo de tiempo determinado. Atendiendo al nivel de exigencia, se subdividirían en dos: soft (suave) o '''flexible''' y hard(duro) o '''estricto'''. Un ejemplo puede ser el sistema operativo de tiempo real instalado en el procesador de un teléfono móvil; si llega una llamada tiene que pasarla en ese momento, sino ese proceso deja de ser importante.
**Distribuido: permite la ejecución de múltiples procesos en diferentes máquinas comunicadas por un enlace de red. El primer SO en soportar esta característica fue [http://es.wikipedia.org/wiki/Plan_9_from_Bell_Labs Plan 9] de ''Bell Labs''.

== 1.3.2. Según cómo se presta el servicio ==

Clasificación no excluyente:

* Sistemas operativos de servidor
* Sistemas operativos de ordenador personal
* Sistemas operativos en tiempo real
* Sistemas operativos embarcados / integrados / "embebidos", ejemplos, dispositivos móviles o smartcard.
* Sistemas operativos web

2.1 [[Organización básica de un ordenador]]

Solución de los ejercicios de fundamentos

2013-01-19T09:51:15Z

Dandelea: /* Ejercicio 2 */

== Ejercicio 1 ==

Se puede responder a esta pregunta con el contenido de [[Modelos_de_Diseño_de_Sistemas_Operativos|este artículo]]. --[[Usuario:Pneira|Pneira]] 17:05 1 dic 2011 (UTC)

*Monolíticos: son núcleos de '''gran tamaño''' (muchas líneas de código) con un '''alto número de funcionalidades'''.

*Micronúcleos: son núcleos de '''pequeño tamañ'''o que fueron compilados sólo con las '''necesidades más básicas''' del sistema operativo

== Ejercicio 2 ==

Se puede responder a esta pregunta con el contenido de [[Componentes básicos de un sistema operativo|este artículo]]. --[[Usuario:Pneira|Pneira]] 17:05 1 dic 2011 (UTC).
No es conveniente que se haga un Sistema operativo sin ninguna llamada a sistema ya que el sistema no se podría comunicar con el hardware y no valdría para nada. No es útil.--[[Usuario:fraborcej|fraborcej]] 19:49 11 nov 2012 (UTC)

Solución de los ejercicios de fundamentos

2013-01-19T09:51:02Z

Dandelea:

== Ejercicio 1 ==

Se puede responder a esta pregunta con el contenido de [[Modelos_de_Diseño_de_Sistemas_Operativos|este artículo]]. --[[Usuario:Pneira|Pneira]] 17:05 1 dic 2011 (UTC)

*Monolíticos: son núcleos de '''gran tamaño''' (muchas líneas de código) con un '''alto número de funcionalidades'''.

*Micronúcleos: son núcleos de '''pequeño tamañ'''o que fueron compilados sólo con las '''necesidades más básicas''' del sistema operativo

== Ejercicio 2 ==

Se puede responder a esta pregunta con el contenido de [[Componentes básicos de un sistema operativo|este artículo]]. --[[Usuario:Pneira|Pneira]] 17:05 1 dic 2011 (UTC)
No es conveniente que se haga un Sistema operativo sin ninguna llamada a sistema ya que el sistema no se podría comunicar con el hardware y no valdría para nada. No es útil.--[[Usuario:fraborcej|fraborcej]] 19:49 11 nov 2012 (UTC)

Mejoras en la demora de rotación

2013-01-18T15:10:38Z

Dandelea:

Para mejorar los tiempos de espera asociados a la demora de rotación se pueden intercalar los sectores que forman parte de una pista. Se aplican los métodos siempre que estemos en un mismo cilindro del disco. A continuación, las diferentes estrategias:
==Intercalado de sectores==
Esto se basa en que los tiempos de lectura/escritura y transmisión de los datos no son despreciables, con lo que cuando el dispositivo lee unos datos en un sector, mientras que espera a que se transmitan, el disco ha seguido girando y posiblemente se encuentre en otro sector. Por tanto, si los colocamos consecutivamente tendremos que esperar toda una vuelta para acceder al siguiente. Sin embargo, colocándolos de manera alterna, podemos evitar dar la vuelta completa al disco, y esperar una fracción del disco. Esto puede lograrse partiendo de la numeración natural e insertando un escalado de valor n, el cual puede llevarse a cabo durante el formateo o por software en el propio gestor.
Cuando el intercalado es de valor n, significa que hay una distancia de n sectores entre los anteriores sectores consecutivos.

===Ejemplo===
[[Archivo:Sdf.png]]

Si el intercalado se implementa en el gestor mediante software, se debe utilizar una tabla que convierta la dirección lógica del sector (NLS) en su dirección física (NFS). Esta tabla es dependiente del dispositivo, y por tanto debería estar almacenada en el mismo.

==Ordenación circular==
De manera parecida al método anterior vamos a alterar el orden en que vamos a leer los sectores. Si bien una petición más urgente o más antigua nos interesa satisfacerla antes, se dispondrán al principio del orden de lectura/escritura. Es imprescindible saber la posición inicial del cabezal para saber qué sectores se visitarán antes, y en función de este, se organiza el orden.

===Ejemplo===
[[Archivo:SSOOrot2.jpg]]
==Transferencia de pista completa==
La mayor parte de las veces que se accede a un sector en una pista, se accede después a otro sector que tenga adyacente en la pista. Para solucionar este retraso ocasionado por dar una vuelta completa al disco se planea que nada mas llegue el cabezal a la pista deseada empiece a transferir hasta que acabe la pista completa.
Los datos no solicitados se guardan en caché hasta que en un futuro próximo sean pedidos.
De este modo, nos anticipamos a la petición del sector n+1.
Este método es sólo útil para lectura, ya que es una información que se guarda en memoria.

Mejoras en la demora de rotación

2013-01-18T15:10:16Z

Dandelea:

Para mejorar los tiempos de espera asociados a la demora de rotación se pueden intercalar los sectores que forman parte de una pista. Se aplican los métodos siempre que estemos en un mismo cilindro del disco. A continuación, las diferentes estrategias:
==Intercalado de sectores==
Esto se basa en que los tiempos de lectura/escritura y transmisión de los datos no son despreciables, con lo que cuando el dispositivo lee unos datos en un sector, mientras que espera a que se transmitan, el disco ha seguido girando y posiblemente se encuentre en otro sector. Por tanto, si los colocamos consecutivamente tendremos que esperar toda una vuelta para acceder al siguiente. Sin embargo, colocándolos de manera alterna, podemos evitar dar la vuelta completa al disco, y esperar una fracción del disco. Esto puede lograrse partiendo de la numeración natural e insertando un escalado de valor n, el cual puede llevarse a cabo durante el formateo o por software en el propio gestor.
Cuando el intercalado es de valor n, significa que hay una distancia de n sectores entre los anteriores sectores consecutivos.

===Ejemplo===
[[Archivo:Sdf.png]]

Si el intercalado se implementa en el gestor mediante software, se debe utilizar una tabla que convierta la dirección lógica del sector (NLS) en su dirección física (NFS). Esta tabla es dependiente del dispositivo, y por tanto debería estar almacenada en el mismo.

==Ordenación circular==
De manera parecida al método anterior vamos a alterar el orden en que vamos a leer los sectores. Si bien una petición más urgente o más antigua nos interesa satisfacerla antes, se dispondrán al principio del orden de lectura/escritura. Es imprescindible saber la posición inicial del cabezal para saber qué sectores se visitarán antes, y en función de este, se organiza el orden.

[[Archivo:SSOOrot2.jpg]]
==Transferencia de pista completa==
La mayor parte de las veces que se accede a un sector en una pista, se accede después a otro sector que tenga adyacente en la pista. Para solucionar este retraso ocasionado por dar una vuelta completa al disco se planea que nada mas llegue el cabezal a la pista deseada empiece a transferir hasta que acabe la pista completa.
Los datos no solicitados se guardan en caché hasta que en un futuro próximo sean pedidos.
De este modo, nos anticipamos a la petición del sector n+1.
Este método es sólo útil para lectura, ya que es una información que se guarda en memoria.

Archivo:SSOOrot2.jpg

2013-01-18T15:07:30Z

Dandelea:

Semáforos

2013-01-18T15:06:07Z

Dandelea:

= Planificador de procesos: Diagrama de estados simplicado =

Para comprender apropiadamente cómo funcionan los semáforos es importante recordar cómo funciona el [[Estados de los procesos|diagrama de estados de los procesos]]

= Semáforos =

Los semáforos son un mecanismo de sincronización de procesos inventados por [http://es.wikipedia.org/wiki/Edsger_Dijkstra Edsger Dijkstra] en 1965. Los semáforos permiten al programador '''asistir al planificador del sistema operativo en su toma de decisiones''' de manera que permiten sincronizar la ejecución de dos o más procesos. A diferencia de los [[cerrojos]], los semáforos nos ofrecen un mecanismo de espera no ocupada.

Los semáforos son un tipo abstracto de datos que están compuestos por dos atributos:

* Un contador, que siempre vale >= 0.
* Una lista de procesos(lista formada por el PCB de cada proceso), inicialmente vacía.

Y disponen de dos operaciones básicas que pasamos a describir en pseudocódigo:

* down(s): si contador = 0, proceso se bloquea en semáforo y decrementa contador.
* up(s): Incrementa contador y si había algún proceso bloqueado en semáforo, reanuda uno.

<source lang="c">
down(semáforo s)
{
si s.contador == 0:
añade proceso a s.lista
proceso a estado bloqueado
sino:
s.contador--
}
</source>

En el pseudocódigo anterior, se puede añadir a la lista un proceso o un hilo.

Nótese que siempre que queramos forzar una transición de un proceso a estado bloqueado, tenemos que hacer que dicho proceso realice una operación ''down'' sobre un semáforo cuyo contador vale cero.

<source lang="c">
up(semáforo s)
{
si hay procesos en s.lista
retira proceso de s.lista
proceso a estado preparado
sino:
s.contador++
}
</source>

Nótese que una operación ''up'' sobre un semáforo en el que hay procesos en su lista resulta en que se retire uno de los procesos (el que más tiempo lleva en la lista), realizando éste la transición a estado preparado. Es un error frecuente pensar que una operación ''up'' resulte en que el proceso retirado de la lista pase a estado activo. Recuerde que las transiciones de estado activo a preparado y viceversa son siempre controladas por el planificador del sistema operativo.

Además, se disponen de un constructor y un destructor que permiten la creación y la liberación de un semáforo.

=== Ejemplo de uso de semáforos ===

Suponga el siguiente ejemplo en el que se quieren sincronizar dos hilos de un proceso, de manera que se dé la siguiente secuencia de ejecución: A, B, A, B, ... y así sucesivamente. El siguiente código resolvería el problema:

<source lang="c">
semaforo a = semaforo.create(1);
semaforo b = semaforo.create(0);

/* código del hilo A */
while (1) {
a.down();
printf("hilo A\n");
b.up();
}

/* código del hilo B */
while (1) {
b.down();
printf("hilo B\n");
a.up();
}
a.destroy();
b.destroy();
</source>

=== Tipos de semáforos ===

Dependiendo de la función que cumple el semáforo, vamos a diferenciar los siguientes tipos:

* Semáforo de exclusión mutua, inicialmente su contador vale 1 y permite que haya un único proceso simultáneamente dentro de la sección crítica.
* Semáforo contador, permiten llevar la cuenta del número de unidades de recurso compartido disponible, que va desde 0 hasta N.
* Semáforo de espera, generalmente se emplea para forzar que un proceso pase a estado bloqueado hasta que se cumpla la condición que le permite ejecutarse. Por lo general, el contador vale 0 inicialmente, no obstante, podría tener un valor distinto de cero.

=== Ventajas e inconvenientes ===

La principal ventaja de los semáforos frente a los [[cerrojos]] es que permiten sincronizar dos o más procesos de manera que no se desperdician recursos de CPU realizando comprobaciones continuadas de la condición que permite progresar al proceso.

Los inconvenientes asociados al uso de semáforos son los siguientes:

* Los programadores tienden a usarlos incorrectamente, de manera que no resuelven de manera adecuada el problema de concurrencia o dan lugar a interbloqueos.
* No hay nada que obligue a los programadores a usarlos.
* Los compiladores no ofrecen ningún mecanismo de comprobación sobre el correcto uso de los semáforos.
* Son independientes del recurso compartido al que se asocian.

Debido a estos inconvenientes, se desarrollaron los [[Monitores|monitores]].

== Granularidad ==

Número de recursos controlados por cada semáforo. Hay de dos tipos:
* Granularidad fina: Un recurso por semáforo. Hay un mayor grado de paralelismo, lo que puede mejorar la rapidez de ejecución de la protección. Aunque a mayor número de semáforos existe una mayor probabilidad de que se de un interbloqueo entre semáforos, que no sería una mejora de lo que intentamos evitar.
* Granularidad gruesa: Un semáforo para todos los recursos. Caso totalmente inverso al anterior: Ahora al tener un semáforo no se produce interbloqueo entre ellos, aunque los tiempos de ejecución son excesivamente largos.

Mensajería

2013-01-18T15:01:31Z

Dandelea:

Un mensaje es un contenedor que se emplea para intercambiar información entre dos o más procesos. Los mensajes tienen un cierto formato generalmente compuesto por una cabecera, que contiene información sobre la fuente y el destinatario, y un cuerpo, que contiene información específica.

Los mecanismos de mensajería se refiere al conjunto de funcionalidades que permiten al sistema operativo realizar la entrega de un mensaje a uno o varios procesos. Mediante dicho mecanismo también es posible resolver problemas de concurrencia.

Los sistemas operativos generalmente ofrecen dos llamadas al sistema para que un proceso pueda enviar y recibir mensajes:

* '''send(mensaje, destino)''': Para enviar un mensaje
* '''recv(mensaje)''': Para recibir un mensaje
* '''sendrecv (mensaje, destino)''': Envía un mensaje a un destino y recoge la respuesta.

Cualquier proceso que necesite comprobar si tiene mensajes para ser procesados por él debe invocar la llamada al sistema '''recv'''.

== Formas de identificación ==

Para identificar la fuente y el destino de nuestro mensaje se pueden emplear dos estrategias.

=== Denominación Directa ===

En este caso se emplea un ID que permite identificar a la fuente y al destinatario de manera unívoca en el sistema, por ejemplo, el PID de un proceso. La denominación directa permite tres configuraciones:

* ''Unicast'', de manera que la comunicación sucede entre una fuente y un destinatario.
* ''Broadcast'', el emisor envía un mensaje a '''todos''' los procesos existentes en el sistema.
* ''Multicast'', el emisor envía un mensaje a un grupo de procesos, siendo un grupo un subconjunto de procesos existentes en el sistema. El sistema operativo debe ofrecer llamadas al sistema que permitan a los procesos crear grupos y suscribirse a ellos. Un proceso puede suscribirse a tantos grupos como le sea necesario.

El principal inconveniente de la denominación directa es que se pierde el mensaje si el destino no se encuentra.

=== Denominación Indirecta ===

Se emplea un elemento intermediario denominado ''buzón''. El sistema operativo ofrece llamadas al sistema que permiten la creación y destrucción de buzones, por ejemplo, '''CreateMailbox''' y '''DestroyMailbox'''. Una vez creado el buzón, se emplea éste para realizar la comunicación entre procesos.

Con los buzones se pueden emplear cuatro formas diferentes de comunicación:
*Buzón limitado : De un proceso a otro.
*Buzón de entrada: De varios a uno.
*Buzón de salida: De uno a varios.
*Buzón múltiple: Varios procesos entre sí con el mismo buzón.

El receptor no conoce la identidad de quien envía el mensaje, a menos que el SO se haya encargado de ello. El problema surge cuando un proceso intruso y éste lee los mensajes de los buzones. Para remediarlo el SO establece permisos de acceso o contraseñas. O para evitar que el proceso infiltrado manipule los mensajes se puede también implementar firmas de certificación. y así garantizar la identidad de los remitentes.

== Formas de transmisión ==

Distinguimos tres formas de transmisión: Transmisión por copia, transmisión por referencia y transmisión por copia en caso de escritura.

=== Transmisión por copia ===

Si se emplea ''denominación directa'', al invocar el receptor la llamada ''recv'', el mensaje se copia del espacio de memoria del emisor al espacio de receptor. Esta forma de implementar la transmisión tiene un coste de orden lineal <math>O(n)</math>.

Si se emplea ''denominación indirecta'', al invocar ''send'' el emisor, el mensaje se copia del espacio de emisor al espacio del buzón, que se encuentra en el espacio de memoria del sistema operativo. Una vez que el receptor invoca ''receive'', se copia el mensaje al espacio de memoria que el receptor ha habilitado para almacenar el mensaje.

[[Archivo:SSOOMensajeria1.jpg]]

=== Transmisión por referencia ===

Es una mejora frente al mecanismo de transmisión por copia. Básicamente, en lugar de copiar el mensaje, lo que supone un coste de <math>O(n)</math>, se le devuelve al receptor una dirección de memoria en la que se encuentra el mensaje, lo que supone únicamente 4 u 8 bytes dependiendo del tamaño de palabra del procesador (si es de 32-bits o 64-bits).

Si se emplea junto a la '''denominación directa''', el sistema operativo le devuelve al receptor un puntero a la dirección en la que se encuentra el mensaje. Si el mensaje está en el espacio del emisor, son necesarios mecanismos explícitos de compartición de memoria entre procesos, ya que dos procesos cualquiera no comparten memoria. Si el mensaje está en el espacio del sistema operativo, éste debe ofrecer a los procesos mecanismos para acceder a su espacio de memoria-

Si se emplea junto a la '''denominación indirecta''', el emisor crea un mensaje en el espacio del sistema operativo y se le ofrece un puntero al receptor.
[[Archivo:SSOOMensajeria2.jpg]]

=== Transmisión por copia de escritura ===

El mensaje sólo se copia si se modifica por emisor o receptor.

== Formas de comunicación ==

* Comportamiento del emisor, '''send()'''
** ''Síncrona'': el proceso emisor que realiza el send() queda bloqueado hasta que el receptor llama a recv() y el proceso bloqueado pasa a estado preparado.
** ''Asíncrona'': suponemos una estructura de datos con capacidad de almacenamiento limitada, dependiente del proceso destinatario o en el buzón del SO. Al ser enviados, los mensajes irán encolándose para que el proceso receptor pueda gestionarlos cuando pueda. De esta manera se aumenta el rendimiento pero se requiere de políticas adicionales de tratamiento de los mensajes si la capacidad de almacenamiento de la estructura de datos se ve sobrepasada(PE, eliminación de mensajes, realocalización de memoria, etc..)

* Comportamiento del receptor, '''recv()'''
** ''Bloqueante'': una llamada a recv() sin mensajes a procesar pasa el proceso llamante a estado bloqueado. Un send() de otro proceso que añada un mensaje a la cola del proceso bloqueado hace que éste pase a estado preparado.
** ''No bloqueante'': una llamada a recv() sin mensajes a procesar devuelve un mensaje de error, pero la ejecución del proceso llamante continúa.

Entendemos por proceso llamante a aquel que hace uso de las llamadas send() y recv().

== Formato de los mensajes ==

=== Fijo ===

Los procesos acuerdan emplear un formato fijo para sus mensajes.

'''Ejemplo''': Simple Network Time Protocol.<ref> Véase http://tools.ietf.org/html/rfc4330, sección 4, Message Format.</ref>

1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|LI | VN |Mode | Stratum | Poll | Precision |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Root Delay |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Root Dispersion |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reference Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Reference Timestamp (64) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Originate Timestamp (64) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Receive Timestamp (64) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Transmit Timestamp (64) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Key Identifier (optional) (32) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| |
| Message Digest (optional) (128) |
| |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

=== Variable ===

* Type-Length-Value

'''Ejemplo''': Usado en Netlink para la codificación de atributos de un mensaje.<ref>Ver Communicating between the kernel and user-space in Linux using Netlink Sockets (http://1984.lsi.us.es/~pablo/docs/spae.pdf)</ref>
{| border="2" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 0; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; font-size: 95%;"
|+ align="center" style="background:DarkSlateBlue; color:white"|'''Type-Length-Value'''
! width="15 px" style="background:#efefef;" | 0
! width="15 px" style="background:#efefef;" | 1
! width="15 px" style="background:#efefef;" | 2
! width="15 px" style="background:#efefef;" | 3
! width="15 px" style="background:#efefef;" | 4
! width="15 px" style="background:#efefef;" | 5
! width="15 px" style="background:#efefef;" | 6
! width="15 px" style="background:#efefef;" | 7
! width="15 px" style="background:#efefef;" | 8
! width="15 px" style="background:#efefef;" | 9
! width="15 px" style="background:#efefef;" | 10
! width="15 px" style="background:#efefef;" | 11
! width="15 px" style="background:#efefef;" | 12
! width="15 px" style="background:#efefef;" | 13
! width="15 px" style="background:#efefef;" | 14
! width="15 px" style="background:#efefef;" | 15
! width="15 px" style="background:#efefef;" | 16
! width="15 px" style="background:#efefef;" | 17
! width="15 px" style="background:#efefef;" | 18
! width="15 px" style="background:#efefef;" | 19
! width="15 px" style="background:#efefef;" | 20
! width="15 px" style="background:#efefef;" | 21
! width="15 px" style="background:#efefef;" | 22
! width="15 px" style="background:#efefef;" | 23
! width="15 px" style="background:#efefef;" | 24
! width="15 px" style="background:#efefef;" | 25
! width="15 px" style="background:#efefef;" | 26
! width="15 px" style="background:#efefef;" | 27
! width="15 px" style="background:#efefef;" | 28
! width="15 px" style="background:#efefef;" | 29
! width="15 px" style="background:#efefef;" | 30
! width="15 px" style="background:#efefef;" | 31

|-
| colspan=16, align="center"| Length
| colspan=16, align="center"| Type
|-
| colspan=32, align="center"| Value
|}

* Text-based human-readable.

#Comma-Separated Value (CSV). http://en.wikipedia.org/wiki/Comma-separated_values
#Extensible Markup Language (XML). http://en.wikipedia.org/wiki/XML
#JavaScript Object Notation (JSON). http://en.wikipedia.org/wiki/JSON

=== Mixto ===

Los procesos acuerdan emplear mensaje con partes cuyo formato es fijo, como por ejemplo una cabecera inicial, seguido de partes de tamaño variable.

'''Ejemplo''': Internet Protocol (IPv4).<ref>Ver http://www.ietf.org/rfc/rfc791.txt, sección 3.1.</ref>

0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Version| IHL |Type of Service| Total Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Identification |Flags| Fragment Offset |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Time to Live | Protocol | Header Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Options | Padding |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
/ /
/ Payload /
/ /
/////////////////////////////////////////////////////////////////

== Mensajería a través de la red ==

* Unicidad del destinatario
* Fiabilidad en la transmisión
* Formato de los datos (http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Data/endian.html): Enviar un entero a través de la red puede ser un problema debido a la forma en el que se representan los datos en la memoria dependiente de la arquitectura. Por ejemplo, un PC con arquitectura Intel x86 emplea formato little-endian, mientras que un SPARC de Sun Microsystems (ahora Oracle) emplea big-endian.

** Little Endian: Bytes menos significativo al principio.

<source lang="c">
int main(void)
{
int a = 10, i;
char *p = &a;

for (i=0; i<sizeof(a); i++) {
printf("posición %d: %.2x\n", i, p[i]);
}
}
</source>

Muestra el siguiente resultado en un PC:

posición 0: 0a (n+3)
posición 1: 00 (n+2)
posición 2: 00 (n+1)
posición 3: 00 (n)

** Big Endian: Bytes menos significativo al final.

posición 0: 00 (n)
posición 1: 00 (n+1)
posición 2: 00 (n+2)
posición 3: 0a (n+3)

En Internet se sigue la convención de expresar datos en Big Endian, habría que hacer la conversión. Habría que usar '''ntohl''' (network to host long).

En little-endian, la implementación de ntohl es la siguiente:

#define __constant_ntohl(x) ___constant_swab32((__be32)(x)

Ver /usr/include/linux/byteorder/little_endian.h

mientras que en big-endian es:

#define __constant_ntohl(x) ((__u32)(__be32)(x))

Si empleamos formato textuales, como CSV, XML o JSON, que codifican la información en bytes, no tenemos este problema.

==Referencias==
<references/>

Archivo:SSOOMensajeria2.jpg

2013-01-18T14:59:39Z

Dandelea:

Archivo:SSOOMensajeria1.jpg

2013-01-18T14:59:03Z

Dandelea:

Estados de los procesos

2013-01-18T14:55:45Z

Dandelea: /* Diagrama de Estados Ampliado */

= 3.2 Estados de los procesos =

Todo proceso en un sistema operativo presenta un estado que indica la situación de la ejecución en que se encuentra. El número de posibles estados varía de un sistema operativo a otro.

== Diagrama de estados simplificado ==

Consideramos que todo proceso puede estar, como mínimo, en uno de los siguientes tres estados:

* '''Activo''': el proceso está empleando la CPU, por tanto, está ejecutándose. Pueden haber tantos procesos activos como procesadores haya disponibles. Por tanto, si el sistema dispone de un único procesador, únicamente puede haber un proceso activo a la vez.
* '''Preparado''': el proceso no está ejecutándose pero es candidato a pasar a estado activo. Es el planificador el que, en base a un criterio de planificación, decide qué proceso selecciona de la lista de procesos preparados para pasar a estado activo.
* '''Bloqueado''': el proceso está pendiente de un evento externo que le ha hecho bloquear, tales como una operación de lectura/escritura, la espera de finalización de un proceso hijo, una señal o una operación sobre un semáforo. El dispositivo/hecho externo "avisa" al S.O. cuando ha terminado la acción que realizaba mediante una INTERRUPCIÓN, dejando el S.O. lo que está haciendo para atender a esta última. Tras esto, el S.O. comprueba cuales son los procesos que fueron bloqueados por ese evento externo, cambiándolos al estado de preparado.

La transición de activo a preparado y viceversa depende de decisiones tomadas por el '''planificador del sistema operativo''' en base a un cierto criterio. La transición de activo a bloqueado, y de bloqueado a preparado puede inducirlas el programador mediante llamadas al sistema.

[[Archivo:SSOO2.jpg]]

== Diagrama de Estados Ampliado ==
* '''En espera / Preparación''': Estado por el que pasan los procesos antes de pasar a estar preparados por primera vez. Los procesos, cuando comienzan a existir, no están preparados para comenzar a ejecutar instrucciones hasta que el sistema no ha llevado a cabo una serie de actividades. Una vez que el proceso está completamente cargado, ya se puede producir la primera transición al estado preparado.
* '''Terminado''': La transición de activo a este estado ocurre cuando el proceso realiza una llamada al sistema solicitando su propia terminación. En estas circunstancias, hay estructuras de datos correspondientes al proceso que no pueden ser liberadas hasta que el proceso padre del que está terminando recoja el código de terminación del mismo. Hasta que esto ocurra, estas estructuras se mantendrán y el proceso seguirá existiendo en estado terminado.
* '''Transición''': cuando se completa la operación que mantiene a un proceso en estado bloqueado termina, el proceso puede haber perdido parte de los recursos que necesita para proseguir su ejecución.

[[Archivo:SSOOProc.jpg]]

Hay tres posibles situaciones en las que se ejecutará el planificador del sistema operativo:
* El proceso que se encuentra en el estado activo hace una llamada al sistema que, por su naturaleza, resulta en una transición al estado bloqueado. Este es el caso de las llamadas read(), write(), wait(), pause(), entre muchas otras. Al pasar a estado bloqueado, se invoca al planificador para que decida que otro proceso se asignará al procesador.
* Si el proceso que se encuentra en el estado activo excede el tiempo máximo de asignación, en caso de que lo hubiere.
* Si el proceso que hasta ese momento se encontraba en estado activo termina de ejecutar su código.

Además, algunos sistemas operativos disponen de un estado terminado en el que los procesos pasan antes de terminar su ejecución.

En el caso del núcleo de Linux, existen tres tipos de estados bloqueado y dos estados terminado: http://www.ibm.com/developerworks/linux/library/l-task-killable/

Archivo:SSOOProc.jpg

2013-01-18T14:55:04Z

Dandelea: Imagen de Procesos

Imagen de Procesos

Estados de los procesos

2013-01-18T14:52:56Z

Dandelea:

= 3.2 Estados de los procesos =

Todo proceso en un sistema operativo presenta un estado que indica la situación de la ejecución en que se encuentra. El número de posibles estados varía de un sistema operativo a otro.

== Diagrama de estados simplificado ==

Consideramos que todo proceso puede estar, como mínimo, en uno de los siguientes tres estados:

* '''Activo''': el proceso está empleando la CPU, por tanto, está ejecutándose. Pueden haber tantos procesos activos como procesadores haya disponibles. Por tanto, si el sistema dispone de un único procesador, únicamente puede haber un proceso activo a la vez.
* '''Preparado''': el proceso no está ejecutándose pero es candidato a pasar a estado activo. Es el planificador el que, en base a un criterio de planificación, decide qué proceso selecciona de la lista de procesos preparados para pasar a estado activo.
* '''Bloqueado''': el proceso está pendiente de un evento externo que le ha hecho bloquear, tales como una operación de lectura/escritura, la espera de finalización de un proceso hijo, una señal o una operación sobre un semáforo. El dispositivo/hecho externo "avisa" al S.O. cuando ha terminado la acción que realizaba mediante una INTERRUPCIÓN, dejando el S.O. lo que está haciendo para atender a esta última. Tras esto, el S.O. comprueba cuales son los procesos que fueron bloqueados por ese evento externo, cambiándolos al estado de preparado.

La transición de activo a preparado y viceversa depende de decisiones tomadas por el '''planificador del sistema operativo''' en base a un cierto criterio. La transición de activo a bloqueado, y de bloqueado a preparado puede inducirlas el programador mediante llamadas al sistema.

[[Archivo:SSOO2.jpg]]

== Diagrama de Estados Ampliado ==
* '''En espera / Preparación''': Estado por el que pasan los procesos antes de pasar a estar preparados por primera vez. Los procesos, cuando comienzan a existir, no están preparados para comenzar a ejecutar instrucciones hasta que el sistema no ha llevado a cabo una serie de actividades. Una vez que el proceso está completamente cargado, ya se puede producir la primera transición al estado preparado.
* '''Terminado''': La transición de activo a este estado ocurre cuando el proceso realiza una llamada al sistema solicitando su propia terminación. En estas circunstancias, hay estructuras de datos correspondientes al proceso que no pueden ser liberadas hasta que el proceso padre del que está terminando recoja el código de terminación del mismo. Hasta que esto ocurra, estas estructuras se mantendrán y el proceso seguirá existiendo en estado terminado.
* '''Transición''': cuando se completa la operación que mantiene a un proceso en estado bloqueado termina, el proceso puede haber perdido parte de los recursos que necesita para proseguir su ejecución.

Hay tres posibles situaciones en las que se ejecutará el planificador del sistema operativo:
* El proceso que se encuentra en el estado activo hace una llamada al sistema que, por su naturaleza, resulta en una transición al estado bloqueado. Este es el caso de las llamadas read(), write(), wait(), pause(), entre muchas otras. Al pasar a estado bloqueado, se invoca al planificador para que decida que otro proceso se asignará al procesador.
* Si el proceso que se encuentra en el estado activo excede el tiempo máximo de asignación, en caso de que lo hubiere.
* Si el proceso que hasta ese momento se encontraba en estado activo termina de ejecutar su código.

Además, algunos sistemas operativos disponen de un estado terminado en el que los procesos pasan antes de terminar su ejecución.

En el caso del núcleo de Linux, existen tres tipos de estados bloqueado y dos estados terminado: http://www.ibm.com/developerworks/linux/library/l-task-killable/

Condiciones para el interbloqueo y estrategias de resolución

2013-01-18T14:44:32Z

Dandelea:

== Condiciones para que se produzca interbloqueo ==

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

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

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

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

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

== Estrategias ==

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

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

Que se detallan a continuación.

=== Omisión ===

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

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

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

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

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

Evaluame mis contribuciones a la wiki

2013-01-18T14:39:00Z

Dandelea:

A continuación, indica tu nombre y apellidos:

* Juan Carlos Roldán Salvador
* Daniel Ayala Hernández
* Daniel de los Reyes Leal