Unidad 05 Comunicación y Sincronización de Procesos
Los procesos que ejecutan de forma concurrente en un sistema se pueden clasificar como procesos independientes o cooperantes. Un proceso independiente es aquel que ejecuta sin requerir la ayuda o cooperación de otros procesos. Un claro ejemplo de procesos independientes son los diferentes intérpretes de mandatos que se ejecutan de forma simultánea en un sistema. Los procesos son cooperantes cuando están diseñados para trabajar conjuntamente en alguna actividad, para lo que deben ser capaces de comunicarse e interactuar entre ellos.
Tanto si los procesos son independientes como cooperantes, pueden producirse una serie de interacciones entre ellos. Estas interacciones pueden ser de dos tipos:
- Interacciones motivadas porque los procesos comparten o compiten por el acceso a recursos físicos o lógicos. Esta situación aparece en los distintos tipos de procesos anteriormente comentados. Por ejemplo, dos procesos totalmente independientes pueden competir por el acceso a disco. En este caso, el sistema operativo deberá encargarse de que los dos procesos accedan ordenadamente sin que se cree ningún conflicto. Esta situación también aparece cuando varios procesos desean modificar el contenido de un registro de una base de datos. Aquí es el gestor de la base de datos el que se tendrá que encargar de ordenar los distintos accesos al registro.
- Interacción motivada porque los procesos se comunican y sincronizan entre sí para alcanzar un objetivo común. Por ejemplo, un compilador se puede construir mediante dos procesos: el compilador propiamente dicho, que se encarga de generar código ensamblador, y el proceso ensamblador, que obtiene código en lenguaje máquina a partir del ensamblador. En este ejemplo puede apreciarse la necesidad de comunicar y sincronizar a los dos procesos.
Estos dos tipos de interacciones obligan al sistema operativo a incluir mecanismo y servicios que permitan la comunicación y la sincronización entre procesos.
Editado por Jorge R. Figueroa
4.2- Manejo de la exclusión mutua
Los mutex y las variables condicionales son mecanismos especialmente concebidos para la sincronización de procesos ligeros. Un mutex es el mecanismo de sincronización de procesos ligeros más sencillo y eficiente. Los mutex se emplean para obtener acceso exclusivo a recursos compartidos y para asegurar la exclusión mutua sobre secciones críticas. Sobre un mutex se pueden realizar dos operaciones atómicas básicas:
- lock: intenta bloquear el mutex. Si el mutex ya está bloqueado por otro proceso, el proceso que realiza la operación se bloquea. En caso contrario, se bloquea el mutex sin bloquear al proceso.
- unlock: desbloquea el mutex. Si existen procesos bloqueados en él, se desbloqueará a uno de ellos, que será el nuevo proceso que adquiera el mutex. La operación unlock sobre un mutex debe ejecutarla el proceso ligero que adquirió con anterioridad el mutex mediante la operación lock. Esto es diferente a lo que ocurre con las operaciones wait y signal sobre un semáforo.
El siguiente segmento de seudocódigo utiliza un mutex para proteger el acceso a una sección crítica.
 |
| Figura 4.2.1 |
< sección crítica >
unlock(m); /* salida de la sección crítica */
En la Figura 4.2.1 se representa de forma gráfica una situación en la que dos procesos ligeros intentan acceder de forma simultánea a ejecutar código de una sección crítica utilizando un mutex para protegerla.
Dado que las operaciones lock y unlock son atómicas, sólo un proceso conseguirá bloquear el mutex y podrá continuar su ejecución dentro de la sección crítica. El segundo proceso se bloqueará hasta que el primero libere el mutex mediante la operación unlock.
Una variable condicional es una variable de sincronización asociada a un mutex que se utiliza para bloquear a un proceso hasta que ocurra algún suceso. Las variables condicionales tienen dos operaciones atómicas para esperar y señalizar:
- c_wait: bloquea al proceso que ejecuta la llamada y le expulsa del mutex dentro del cual se ejecuta y al que está asociado la variable condicional, permitiendo que algún otro proceso adquiera el mutex. El bloqueo del proceso y la liberación del mutex se realiza de forma atómica.
- c_signal: desbloquea a uno o varios procesos suspendidos en la variable condicional. El proceso que se despierta compite de nuevo por el mutex.
A continuación se va a describir una situación típica en la que se utilizan los mutex y las variables condicionales de forma conjunta. Supóngase que una serie de procesos compiten por el acceso a una sección crítica. En este caso es necesario un mutex para proteger la ejecución de dicha sección crítica. Una vez dentro de la sección crítica, puede ocurrir que un proceso no pueda continuar su ejecución dentro de la misma debido a que no se cumple una determinada condición; por ejemplo, se quiere insertar elementos en un buffer común y éste se encuentra lleno. En esta situación, el proceso debe bloquearse, puesto que no puede continuar su ejecución. Además, debe liberar el mutex para permitir que otro proceso entre en la sección crítica y pueda modificar la situación que bloqueó al proceso, en este caso eliminar un elemento del buffer común para hacer hueco.
Para conseguir este funcionamiento es necesario utilizar una o más variables compartidas que se utilizarán como predicado lógico y que el proceso consultará para decidir su bloqueo o no. El fragmento de código que se debe emplear en este caso es el siguiente:
lock(m);
/* código de la sección crítica */
while (condición == FALSE)
c_wait(c, m);
/* resto de la sección crítica */
unlock(m);
En el fragmento anterior, m es el mutex que se utiliza para proteger el acceso a la sección crítica y c la variable condicional que se emplea para bloquear el proceso y abandonar la sección crítica. Cuando el proceso que está ejecutando dentro de la sección evalúa la condición y ésta es falsa, se bloquea mediante la operación c_wait y libera el mutex permitiendo que otro proceso entre en ella.
El proceso bloqueado permanecerá en esta situación hasta que algún otro proceso modifique alguna de las variables compartidas que le permitan continuar. El fragmento de código que debe ejecutar este otro proceso debe seguir el modelo siguiente:
lock(m);
/* código de la sección crítica */
/* se modifica la condición y ésta se hace TRUE */
condición = TRUE;
c_signal(c);
unlock(m);
En este caso, el proceso que hace cierta la condición ejecuta la operación c_signal sobre la variable condicional despertando a un proceso bloqueado en dicha variable. Cuando el proceso ligero que espera en una variable condicional se desbloquea, vuelve a competir por el mutex. Una vez adquirido de nuevo el mutex, debe comprobar si la situación que le despertó y que le permitía continuar su ejecución sigue cumpliéndose, de ahí la necesidad de emplear una estructura de control de tipo while. Es necesario volver a evaluar la condición, ya que entre el momento en el que la condición se hizo cierta y el instante en el que comienza a ejecutar de nuevo el proceso bloqueado en la variable condicional puede haber ejecutado otro proceso que, a su vez, puede haber hecho falsa la condición. En la Figura 4.2.2 se representa de forma gráfica el uso de mutex y variables entre dos procesos tal y como se ha descrito anteriormente.
 |
| Figura 4.2.2 |
Iniciar un «mutex»
Esta función permite iniciar una variable de tipo mutex. Su prototipo es el siguiente:
int pthread_mutex_init(pthread_mutex_t *mutex,
pthread_mutexattr_t *attr);
El segundo argumento especifica los atributos con los que se crea el mutex inicialmente; en caso de que este segundo argumento sea NULL, se tomarán los atributos por defecto.
Destruir un «mutex»
Permite destruir un objeto de tipo mutex. El prototipo de la función que permite invocar este servicio es:
int pthread_mutex_destroy(pthread_mutex_t *mutex);
Operación lock:
Este servicio se corresponde con la operación lock descrita en la sección anterior. Esta función intenta obtener el mutex. Si el mutex ya se encuentra adquirido por otro proceso, el proceso ligero que ejecuta la llamada se bloquea. Su prototipo es:
int pthread_mutex_lock(pthread_mutex_t *mutex);
Operación unlock:
Este servicio se corresponde con la operación unlock y permite al proceso ligero que la ejecuta liberar el mutex. El prototipo es:
int pthread_mutex_unlock(pthread_mutex_t *mutex);
Iniciar una variable condicional
Para emplear en un programa una variable condicional es necesario declarar una variable de tipo "pthread_cond_t" e iniciarla antes de usarla mediante el servicio pthread_cond_init, cuyo prototipo se muestra a continuación:
int pthread_cond_init(pthread_cond_t *cond,
pthread_condattr_t *attr);
Esta función inicia una variable de tipo condicional. El segundo argumento especifica los atributos con los que se crea inicialmente la variable condicional. Si el segundo argumento es NULL, la variable condicional toma los atributos por defecto.
Destruir una variable condicional
Permite destruir una variable de tipo condicional. Su prototipo es:
int pthread_cond_destroy(pthread_cond_t *cond);
Operación "c_wait" sobre una variable condicional
Este servicio se corresponde con la operación c_wait sobre una variable condicional. Su prototipo es:
int pthread_cond_wait(pthread_cond_t *cond,
pthread_mutex_t_ *mutex);
Esta función suspende al proceso ligero hasta que otro proceso ejecute una operación "c_signal" sobre la variable condicional pasada como primer argumento. De forma atómica, se libera el mutex pasado como segundo argumento. Cuando el proceso se despierte volverá a competir por el mutex.
Operación c_signal sobre una variable condicional
Este servicio se corresponde con la operación c_signal sobre una variable condicional. Su prototipo es:
int pthread_cond_signal(pthread_cond_t *cond);
Se desbloquea a un proceso suspendido en la variable condicional pasada como argumento a esta función. Esta función no tiene efecto si no hay ningún proceso ligero esperando sobre la variable condicional. Para desbloquear a todos los procesos ligeros suspendidos en una variable condicional se emplea el servicio:
int pthread_cond_broadcast(pthread_cond_t *cond);
Editado por Jorge R. Figueroa
4.4- Definiciones de Dijkstra:
Algoritmo empleado en la obtención de la trayectoria más corta en grafos. Llamado así por su creador Edsger Wybe Dijkstra, holandés nacido en 1930.
El algoritmo de Dijkstra para ruta más corta, en términos generales, encuentran la ruta más corta entre dos nodos, inicial a y final z, de la siguiente manera:
Los nodos de la red son etiquetados con números. Al principio, todos tienen la etiqueta 00 excepto el nodo inicial a que tiene la etiqueta 0. Los arcos tienen un peso wij que representa la distancia del enlace (i, j). El algoritmo de Dijkstra reenumera los nodos, de manera que cuando el nodo z tiene una etiqueta permanente, se ha obtenido la solución final.
Editado por Jorge R. Figueroa
4.5- Condición de carrera:
Es una expresión usada en electrónica y en programación para Sistemas Operativos con capacidad de multiprocesamiento. Procede del inglés race condition (si bien sería mejor hablar de estado de carrera, igual que se habla de estado de espera). Múltiples procesos están en condición de carrera si el resultado de los mismos depende del orden en que se ejecute. Si los procesos que están en condición de carrera no son correctamente sincronizados, puede producirse un error de corrupción de datos.
Este tipo de errores de programación pueden ser aprovechados por exploits locales para vulnerar los sistemas.
La Condición de carrera se da principalmente cuando varios procesos acceden al mismo tiempo a un recurso compartido, por ejemplo una variable, cambiando su estado y obteniendo de esta forma un valor no esperado de la misma.
Editado por Jorge R. Figueroa
4.6.1- Semáforos
En 1965 Dijkstra sugirió usar una variable entera para contar el número de señales de despertar guardadas para uso futuro. En esta propuesta se introdujo un nuevo tipo de variable, llamada semáforo. Un semáforo podía tener el valor 0, indicando que no habia señales de despertar guardadas, o algun valor positivo si habia una o más señales de despertar pendientes.Dijkstra propuso tener dos operaciones: DOWN y UP. La operación DOWN aplicada a un semáforo verifica si el valor es mayor que 0; de ser así, decrementa el valor(esto es, gasta una señal de despertar almacenada) y continúa. Si el valor es 0, el proceso se pone a dormir sin completar la operacion DOWN por el momento. La verificación del valor, su modificación y la acción de dormirse, si es necesaria, se realizan como una sola acción atómica indivisible. Se garantiza que una vez que una operación de semáforo se haya completado o bloqueado. Esta atomicidad es absolutamente indispensable para resolver los problemas de sincronización y evitar condiciones de competencia.
La operación UP incrementa el valor del semáforo direccionado. Si uno o más procesos están durmiendo en espera de ese semáforo, imposibilitados de completar una operación DOWN previa, el sistema escoge uno de ellos (por ej. al azar) y le permite completar su DOWN. Así despues de un UP con un semáforo que tiene procesos durmiendo esperando, el semáforo seguira siendo 0, pero habrá un proceso menos que se halle en fase durmiendo. La operación de incrementar el semáforo y despertar un proceso también es indivisible. Ningún proceso se bloquea durante un UP.
Como acotación en su artículo original Dijkstra usó las letras P y V en lugar de DOWN y UP.
4.6.2- Monitores
Un monitor es una colección de procedimientos, variables y estrucuturas de datos que se agrupan en un tipo especial de módulo o paquete. Los procesos pueden invocar los procedimientos de un monitor en el momento en que deseen, pero no pueden acceder directamente a las estrucuturas de datos internas del monitor desde procedimientos declarados afuera del mismo.Los monitores poseen una propiedad especial que los hace útiles para lograr la exclusión mutua: solo un proceso puede estar activo en un monitor en un momento dado. Los monitores son una construcción de lenguaje de programación, asi que el compilador sabe que son especiales y puede manejar las llamadas a procedimientos de monitos de una forma diferente a como maneja otras llamadas a procedimientos. Por lo regular, cuando un proceso invoca un procedimiento de monitor, las primeras instrucciones del procedimiento verifican si hay algun otro proceso activo en ese momento dentro del monitor. Si así es, el proceso invocador se suspende hasta que el otro proceso abandona el monitor. Si ningún otro proceso está usando el monitor, el proceso invocador puede entrar.
Es responsabilidad del compilador implementar la exclusión mutua en las entradas a monitores, pero una forma común es usar un semáforo binario. Puesto que el compilador, no el programador, se esta encargando de la exclusion mutua, es mucho menos probable que algo salga mal. En cualquier caso, la persona que escribe el monitor no tiene que saber como el compilador logra la exclusión mutua; le basta con saber que si convierte todas las regiones criticas en procedimientos de monitor, dos procesos nunca podrán ejecutar sus regiones criticas al mismo tiempo.
Cuando un procedimiento de monitor descubre que no puede continuar (por ejemplo, si encuentra lleno el buffer) ejecuta WAIT (esperar) con alguna variable de condición digamos full! (lleno). Esta acción hace que el proceso invocador se bloquee, y también permite la entrada de otro proceso al que antes se le había impedido entrar en el monitor.
Este otro proceso puede despertar a su "compañero" dormido ejecutando SIGNAL (señal) con la variable de condición que su compañero está esperando. A fin de evitar la presencia de dos procesos activos en el monitor al mismo tiempo, necesitamos una regla que nos diga qué sucede después de ejecutarse SIGNAL. Hoare propuso dejar que el proceso recién despertado se ejecute, suspendiendo el otro. Brinch Hansen propuso sortear el problema exigiendo al proceso que ejecutó SIGNAL salir inmediatamente del monitor. Dicho de otro modo, una instrucción SIGNAL sólo puede aparecer como última instrucción de un procedimiento de monitor.
Editado por Marcelo G. Sánchez
=
4.8- Pasaje de mensajes
Este método de comunicación entre procesos utiliza dos primitivas SEND y RECEIVE que, al igual que los semáforos y a diferencia de los monitores, son llamadas al sistema y no construcciones del lenguaje. Como tales, es fácil colocarlas en procedimientos de biblioteca, como
send(destino, &mensaje);
y
receive(origen,&mensaje);
La primera llamada envía un mensaje a un destino dado, y la segunda recibe un mensaje de un origen dado (o de cualquiera [ANY] si al receptor no le importa). Si no hay un mensaje disponible, el receptor podría bloquearse hasa que uno llegue. Como alternativa, podría regresar de inmediato con un código de error.
Los sistemas de transferencia de mensajes tienen muchos problemas y aspectos de diseño complicados que no se presentan con los semáforos ni con los monitores, sobre todo si los procesos en comunicación están en diferentes máquinas conectadas por una red. Por ejemplo, ese pueden perder mensajes en la red. Para proteferse contra la pérdida de mensajes, el emisor y el receptor pueden convenir que, tan pronto como se reciba un mensaje, el receptor enviará de regreso un mensaje especial de acuse de recibo o confirmación. Si el emisor no recibe el acuse dentro de cierto intervalo de tiempo, retransmitirá el mensaje.
Por otro lado, si el mensaje en sí se recibe correctamente, pero se pierde el acuse de recibo, el emisor retransmitirá el mensaje, de modo que el receptor lo recibirá dos veces. Es indispensable que el receptor pueda distinguir un mensaje nuevo de la retransmisión de uno viejo. Por lo genera, este problema se resuelve incluyendo números de secuencia consecutivos en cada mensaje original. Si el receptor recibe un mensaje que tiene el mismo número de secuencia que uno anterior, sabrá que el mensaje es un duplicado y podrá ignorarlo.
La verificación de autenticidad es otro problema en los sitemas de mensajes: ¿Cómo puede el cliente saber que se está comunicando con el verdadero serividor de archivos y no con un impostor?
En el otro extremo del expectro, hay aspectos de diseño que son importantes cuando el emisor y el receptor están en la misma máquina. Uno de éstos es el rendimiento. El copiado de mensajes de un proceso a otro siempre es más lento que efectuar una operación de semáforo o entrar en un monitor.
Editado por Marcelo G. Sánchez
=
=
4.11- Problemas clásicos de concurrencia:
4.11.2- El problema de los lectores-escritores:
En este problema existe un determinado objeto (véase Figura 4.11.2), que puede ser un archivo, un registro dentro de un archivo, etc., que va a ser utilizado y compartido por una serie de procesos concurrentes. Algunos de estos procesos sólo van a acceder al objeto sin modificarlo, mientras que otros van a acceder al objeto para modificar su contenido. Esta actualización implica leerlo, modificar su contenido y escribirlo. A los primeros procesos se les denomina lectores y a los segundos se les denomina escritores. En este tipo de problemas existe una serie de restricciones que han de seguirse:
• Sólo se permite que un escritor tenga acceso al objeto al mismo tiempo. Mientras el escritor esté accediendo al objeto, ningún otro proceso lector ni escritor podrá acceder a él.
• Se permite, sin embargo, que múltiples lectores tengan acceso al objeto, ya que nunca van a modificar el contenido del mismo.
En este tipo de problemas es necesario disponer de servicios de sincronización que permitan a los procesos lectores y escritores sincronizarse adecuadamente en el acceso al objeto.
 |
| Figura 4.11.2 |
4.11.3- Problema del productor-consumidor:
El problema del productor-consumidor es uno de los problemas más habituales que surge cuando se programan aplicaciones utilizando procesos concurrentes. En este tipo de problemas, uno o más procesos, que se denominan productores, generan cierto tipo de datos que son utilizados o consumidos por otros procesos, que se denominan consumidores. Un claro ejemplo de este tipo de problemas es el del compilador que se describió anteriormente. En este ejemplo el compilador hace las funciones de productor al generar el código ensamblador que consumirá proceso ensamblador para generar el código máquina. En la Figura 4.11.3 se representa la estructura clásica de este tipo de procesos.
=
 |
| Figura 4.11.3 |
=
En esta clase de problemas es necesario disponer de algún mecanismo de comunicación que permita a los procesos productor y consumidor intercambiar información. Ambos procesos, además, deben sincronizar su acceso al mecanismo de comunicación para que la interacción entre ellos no sea problemática: cuando el mecanismo de comunicación se llene, el proceso productor se deberá quedar bloqueado hasta que haya hueco para seguir insertando elementos. A su vez, el proceso consumidor deberá quedarse bloqueado cuando el mecanismo de comunicación este vacío, ya que en este caso no podrá continuar su ejecución al no disponer de información a consumir. Por tanto, este tipo de problema requiere servicios para que los procesos puedan comunicarse y servicios para que se sincronicen a la hora de acceder al mecanismo de comunicación.
No hay comentarios.:
Publicar un comentario