Recursos y funciones del sistema operativo

Modulo 4: Sincronización y comunicación entre procesos

Sincronización entre procesos

Ordenamiento de las operaciones en el tiempo debido a las condiciones de carrera. Permite que un proceso continúe su ejecución después de la ocurrencia de un determinado evento.

Comunicación entre procesos

Intercambio de datos. La comunicación permite que los procesos cooperen entre si en la ejecución de un objetivo global.

Problemas Concurrentes:

• Programas secuenciales:

  
  especifica una secuencia de instrucciones que se ejecutan sobre un procesador que definimos como proceso o tarea. No depende de otros procesos, ni del algoritmo de planificación.
• 
  

  Programas concurrentes:

  especifica dos o mas procesos secuenciales que pueden ejecutarse simultáneamente. Esta programación requiere de mecanismos de sincronización y comunicación entre los procesos.
• 
  

  Mutua Exclusión:

  significa que los recursos críticos deben ser accedidos solo por un proceso a la vez. Es uno de los problemas mas importantes que presenta la ejecución de los procesos concurrentes.

Grafos de precedencia:

Grafo sin ciclos donde cada nodo representa una única sentencia o un conjunto secuencial de instrucciones agrupadas.

Condiciones de concurrencia de Berntein:

condiciones q deben cumplir dos o mas procesos para q sean concurrentes

        Teniendo en cuenta que R(Si)-> Conjunto de Lectura y W(Si)-> conjunto de Escritura

1. R(Si)W(Sj)=
2. W(Si)R(Sj)=
3. W(Si)W(Sj)=

Si las tres condiciones producen el conjunto vacío, entonces podemos asegurar que no hay dependencia entre las sentencias.

Especificaciones concurrentes:

• Instrucciones FORK: indican el comienzo de la concurrencia(crea e inicia dos instrucciones concurrentes, una en la rotulada etiqueta y la otra es la continuación de la ejecución de la siguiente instrucción al fork. Es en esencia, un goto que simultáneamente bifurca y continua la ejecución.
• Instrucciones JOIN: recombina(junta) la concurrencia en una sola instrucción indicando que ha concluido la concurrencia.
• COBEGIN/COEND: todas las instrucciones insertadas entre cobegin y coend pueden ejecutarse concurrentemente.
• Implentacion:
• COBEGIN/COEND debe ser una construcción del lenguaje utilizado. Debe estar en el compilador.
• Notación FORK puede ser implementada mediante syscall.
• El proceso creador es llamado padre.
• El proceso creado se llama hijo, a su vez puede crear otros hijos.
• Cada proceso nuevo necesitara recursos(tiempo de CPU, memoria, archivos, dispositivos,etc).Puede obtenerlos:
• Tomándolos del SO.
• Obligando al padre a dividir recursos entre sus hijos o compartirlos, esto impide sobrecargas en el sistema.    
• Existen dos formas de activar el nuevo proceso:
• El padre ejecuta en forma concurrente con el hijo.
• El padre espera hasta que todos sus hijos terminen.

Relaciones entre procesos concurrentes y sus conflictos:

• Proceso independiente

  
  No puede afectar o ser afectado por otros procesos corriendo en el sistema. Su estado no es compartido por ningún otro proceso. Su ejecución es determinística, el resultado de la ejecución depende solo de las entradas, esta a su vez puede detenerse y reasumirse sin por eso causar efectos laterales al resto del sistema.
• 
  

  Proceso interactuante:

  puede afectar o ser afecatado por otros procesos. Su estado es compartido por otros procesos y el resultado de su ejecución no puede ser predicho ya que depende de la ejecución de otros procesos.
• 
  

  Race condition (condición de carrera):

  situación en la cual el resultado de la ejecución de dos o mas procesos interactuantes depende del orden de ejecución de los mismos.

Para solucionar una condición de concurso, necesitamos la mutua exclusión, que nos asegura que si un proceso esta utilizando un recurso, los demás procesos no puedan utilizarlo. Esto permite que los procesos accedan de forma ordenada al recurso compartido.

Se presentan otros conflictos con el uso de recursos:

• Inanición (Starvation):

  
  hecho de que uno o varios procesos nunca reciban el suficiente tiempo de ejecución para terminar su tarea.
• 
  

  Condición de espera circular

  Ocurre cuando uno o mas procesos forma una cadena de espera que los involucra a todos.
• 
  

  Condición de No expropiación

  Especifica que si un proceso tiene asignado un recurso, dicho recurso no puede arrebatársele por ningún motivo, y no estará disponible hasta que el proceso lo libere por su voluntad.
• 
  

  Condición de espera ocupada

  Consiste en que un proceso pide un recurso que ya esta asignado a otro proceso y la condición de no expropiación se debe cumplir, el proceso estará gastando el resto de su porción de tiempo verificando si el recurso fue liberado.
• 
  

  Condición de Mutua Exclusión

  Cuando un proceso usa un recurso del sistema realiza una serie de operaciones sobre el recurso y después lo deja de usar. A esa sección de código que usa ese recurso se le llama regíón critica.
  Esta condición establece que solo a un proceso se le permite estar dentro de la misma regíón critica.
• 
  

  Condición de ocupar y esperar por un recurso

  Consiste en que un proceso pide un recurso y se le asigna. Antes de soltarlo, pide otro recurso que otro proceso ya tiene asignado.

Labores del SO:

1. Seguir la pista de los distintos procesos activos.
2. Asignar y quitar los distintos recursos a cada proceso activo, estos recursos incluyen tiempo de procesador, memoria, archivos y dispositivos de E/S.
3. Prteger los datos y los recursos físicos de cada proceso contra injerencias no intencionadas de otros procesos.

Ventajas de la concurrencia

1. Trata de evitar los tiempos muertos del procesador.
2. Comparte y optimiza el uso de recursos.
3. Permite la modularidad en las diferentes etapas del proceso.
4. Acelera los cálculos.
5. Da mayor comodidad.

Desventajas de la concurrencia

1. Inanición e Interrupción de procesos.
2. Ocurrencia de interbloqueos(deadlocks)
3. Que dos o mas procesos compitan por el mismo recurso (No Apropiativo) complica su tratamiento.

Problema de la Región Critica:

• Región Critica: etapa en la vida de un proceso concurrente en la cual accede a un recurso critico para modificarlo o alterarlo. Es un trozo de código en el que se utiliza un recurso compartido y que se ejecuta de forma exclusiva.

 Wiki:

Región critica:

Se denomina sección crítica, en programación concurrente, a la porción de códigode un programa de computador en la cual se accede a un recurso compartido (estructura de datos o dispositivo) que no debe ser accedido por más de un proceso o hilo en ejecución.

Propiedades para usar la Región Critica:

1. Solo un proceso a la vez puede estar ejecutando en su RC (Mutua Exclusión).
2. Progreso: un proceso fuera de su RC no debe impedir la entrada de otro procesos a la misma. Solo los procesos que quieren entrar a la RC deben participar en la decisión.
3. Espera limitada: Un proceso debe poder entrar a la RC después de un numero limitado de intentos.
4. Abandono: debe dejar a la RC en un tiempo finito.
5. Penalidad: Un proceso no puede consumir tiempo de ejecución mientras espera por un recurso.
6. Privilegio: No debe haber ningún proceso privilegiado que monopolice la RC.

Algoritmos de sincronización con espera activa

Espera activa significa que el proceso sigue ocupando la CPU mientras no puede entrar a su RC(el proceso no se bloquea).

1. Solución Simple

   
   Utiliza un flag. Al entrar en la RC se fija si es uno o cero, si es cero lo pone en uno y entra a la RC, si es uno espera hasta que valga cero. Antes de salir de la RC iguala el flag a cero.
2. 
   

   Espera ocupada por turnos:

   Utiliza una variable global llamada turno. Si turno es igual a 1 entonces un P1 puede entrar. De esta manera se asegura que haya solo un proceso en la RC. Exige alternancia estricta. Si turno=0 y P1 esta listo para entrar entonces debe esperar aunque P0 no este en la regíón critica.
3. 
   

   Solución de Peterson:

   es igual a la de alternancia, nada mas que agrega un vector flag donde cada proceso indica si esta interesado en entrar a la regíón critica.
4. 
   

   Algoritmo de Dekker:

   resuelve el problema mediante una tabla unidimensional de dos elementos lógicos (switches). Es un algoritmo para la mutua exclusión de dos procesos, son dos variables booleanas, una para c/proceso, que indican la voluntad de acceder a la RC y una variable extra que indica que proceso tiene derecho a tratar de entrar.
5. 
   

   Algoritmo de Lamport o de la panadería

   Usa un sistema de “toma de boleto o turno”. Cada proceso recibe un “boleto” y se atiende primero al de menor valor, en el caso de empate, se atiende al proceso de menor nombre.
6. 
   

   Mecanismos provistos por el hardware:

7. 
   

   Deshabilitar interrupciones:

   impedir que un proceso sea interrumpido,  lo cual puede ofrecerse en forma de primitivas definidas por el kernel para inhabilitar o habilitar las interrupciones. El precio es alto y no funciona en multiprocesadores. Si ocurre una interrupción por dispositivos u otra causa y esta esta deshabilitada, su tratamiento se retrasara hasta que se rehabilite de nuevo. Cuando se deja la RC se rehabilitan las interrupciones.
8. 
   

   Instrucciones especiales del procesador:

9. Comparar y fijar (TAS o TSL): examina el valor de su argumento, si es cero lo cambia por uno y devuelve cierto, en caso contrario el valor no se modifica y devuelve falso. Se utiliza generalmente en multiprocesadores, puede producir inanición y deadlock.
   Es simple y fácil de verificar.

Su mutua exclusión funciona así, se da un valor inicial cero a una variable compartida cerrojo, el único proceso que puede entrar en su RC es el que encuentre cerrojo en cero, los demás procesos que intenten entrar pasan a modo espera activa. Cuando un proceso abandona su regíón critica vuelve a poner cerrojo en cero.

• Intercambiar(CAS): intercambia el contenido de un registro con el de una posición de memoria. La mutua exclusión funciona así, se da un valor inicial cero a una variable compartida cerrojo, el proceso intercambia el valor de cerrojo por el de una variable con valor uno, y repite esta operación hasta que el valor de la segunda variable sea creo, es decir que cerrojo valía cero antes del intercambio. En este caso el proceso entra en su RC y al salir de esta vuelve a realizar el intercambio para poner cerrojo en cero.

• Cola de espera:

  
  provee un ordenamiento explicito (secuenciamiento) en el uso de la RC. Si varios procesos requieren usar un recurso critico, el SO los coloca en una cola de espera. Reglas:
• Si un proceso no pudiera entrar en la RC se pondría en una cola de espera asociada a esa RC.
• Si un proceso sale de una RC activaría a uno de los procesos de la cola de espera si la cola no esta vacía.
• El valor inicial de la cola es vacía.
• 
  

  Semáforos:

  herramienta genérica de sincronización de procesos, permite el ordenamiento de las operaciones que realizan los procesos en el tiempo. Es una especia de flag que indica la posibilidad de acceder o no a un recurso. Es una función dentro del Kernel.Es una variable protegida cuyo valor puede ser accedido y alterado solo por las dos primitivas independientes y atómicas y una operación de inicialización de semáforos. Propiedades del valor del semáforo(variable):
• Puede tomar cualquier valor entero.
• Se crea mediante un syscall o una declaración, donde se especifica el valor inicial del semáforo.
• Solo es accesible por dos operandos primitivos atómicos down() y up(). Se las llama P(s) y V(s).

Varios tipos de semáforos, binarios(solo pueden tomar valores 0 y 1 ),mutex(pueden tomar valores 1,0 y negativos) y los contadores o generales (pueden tomar valores enteros no negativos, cero y negativos).

Algoritmos sin espera activa:

• Semáforos sin espera activa

  
  Se utiliza una estructura con dos elementos: La variable que indica el valor del semáforo y una cola de procesos asociada al semáforo.  El valor del semáforo indica la cantidad de puntos de entrada que tiene el recurso.

Comunicaciones entre procesos (IPC)

• Mensaje:

  
    porción discreta de datos (generalmente compuesto por un conjunto de bits). Pueden ser de tamaño fijo o variable. Tienen un header  y un cuerpo, la primera corresponde a la identificación del transmisor, la del receptor, longitud y tipo, mientras que el cuerpo tiene el contenido. Se usan dos primitivas: send y receive.
• 
  

  Comunicación directa:

  los procesos envían y reciben los mensajes entre si. Dependen de las velocidades relativas entre si. Se establece un vínculo automáticamente entre los procesos, solo deben conocerse mutuamente, se establece con dos procesos exactamente y dicho vínculo es bidireccional. Las desventajas que tiene son: poca modularidad, y que si se cambia el PID de un proceso, puede ser necesario revisar el  código de los otros.
• 
  

  Comunicación indirecta:

  los mensajes son enviados a un buzón o mailbox (interface entre procesos y S.O). Los mensajes van y vienen a buzones, cada buzón tiene su propia identificación. Propiedades:
• El vinculo se establece solo si ambos procesos comparten un mailbox.
• Entre cada par de procesos puede haber varios links distintos cada uno correspondiente a su mailbox, el link puede ser tanto uní como bidireccional.
• Generalmente la disciplina del mailbox es FIFO.
• 
  

  Comunicación Sincrónica:

  El proceso emisor es bloqueado hasta que el receptor este listo para recibir el mensaje. Cuando el proceso ejecuta el receive y el mensaje no se encuentra disponible queda bloqueado hasta la llegada del mismo. Una vez que se ha producido el intercambio de mensajes ambos procesos continúan su ejecución concurrentemente.
• 
  

  Comunicación Asincronica:

  no se bloquean a los procesos que ejecutan estas primitivas, así cada uno sigue su ejecución. El receptor sigue ejecutando por mas que no le llegue ningún mensaje.
• 
  

  Comunicación Semi-Sincrónica:

  se usa un send no bloqueante y receive bloqueantes. Es riesgoso ya que pueden acumular una gran cantidad de mensajes en colas.
• 
  

  Modelo productor-consumidor:

  usado para describir dos procesos ejecutando en forma concurrente.
• 
  

  Productor:

  genera un conjunto de datos necesarios para la ejecución de otro proceso.
• 
  

  Consumidor:

  Toma los datos generados por el productor y los utiliza para su procesamiento.

Protocolo de sincronización: Si el productor quiere poner un elemento en un buffer lleno entonces es demorado hasta que el consumidor saque uno. Si el consumidor intenta tomar mensajes de buffer vacío entonces es demorado hasta que el productor ingrese uno.

Algoritmos para el modelo productor-consumidor:

1. Con sleep() & wakeup(): usa una variable cont que indica la cantidad de lugares ocupados que tiene el buffer. Presenta al menos una condición de concurso.
2. Con contadores de eventos: un contador de eventos e es una variable especial que tiene 3 operaciones definidas en las siguientes primitivas, read(e) (devuelve el valor de e), advance(e)(Incrementa atómicamente el valor e en 1) y await(e,v)(espera hasta que e>=v). Solo incrementa el valor, nunca lo disminuye y siempre se inician en cero.
3. Con semáforos: Usa tres semáforos, semáforo mutex=1,vacío=N, lleno=0.

Deadlocks:

Se define como deadlock al estado en el que dos o mas procesos esperan por condiciones que no se dan y que deben producirse por los procesos de ese conjunto. Se dicen que dos o mas procesos están en estado de deadlock cuando están esperando por condiciones que nunca se van a cumplir. Seria un estado permanente de bloqueo de un conjunto de procesos. Puede ocurrir bajo dos situaciones:

Por petición de recursos: si un proceso solicita un recurso que no esta disponible este queda esperando. Si todos los procesos quedan esperando por un recurso que tiene asignado otro proceso del conjunto y que también esta a la espera de otro recurso, se produce deadlock.

por comunicación entre procesos: cuando cada proceso de un conjunto espera por un mensaje de otro miembro del grupo, y no existe un mensaje en transito, ocurre un deadlock.

Tipos de recursos:

Recursos reutilizables:

aquel que puede ser usado por un proceso y no se agota con el uso. Por ejemplo canales de E/S, MM centra y secundaria.

Recursos consumibles:

aquel que puede ser creado (producido) y destruido(consumido). Cuando un proceso adquiere un recurso este deja de existir. Por ejemplo, las interrupciones, señales, mensajes.

Condiciones necesarias y suficientes para que se produzca un estado de deadlock:

Mutua exclusión:

los recursos no deben ser compartibles, solo un proceso a la vez puede usar el recurso.

Retener y esperar:

el proceso retiene los recursos que ya tiene asignados mientras espera por nuevos a adquirir del conjunto de recursos del sistema.

No expropiación:

el proceso esta reteniendo los recursos concedidos y solo puede liberarlos y devolverlos al sistema como resultado de una acción voluntaria de ese proceso. El SO no puede obligarle a devolverlos.

Espera circular:

Existen un conjunto de procesos tal que P0 esta esperando un recurso de P1, P1 espera por otro de P2, hasta que PN espera por uno de P0.

Grafos de asignación de recursos:

otra manera de definir deadlocks. Están formados por dos elementos: un conjunto de vértices formado por los procesos y los recursos del sistema, y otro conjunto de arcos que representan la asignación o solicitud de recursos.

Estrategias para tratar deadlocks:

Ignorarlo:

es la forma mas simple, de costo muy bajo, utilizado generalmente cuando la frecuencia de ocurrencia de deadlocks es relativamente baja.

Prevenirlo:

una forma es ir actualizando el grafo de recursos cada vez que se solicita o se libera un recurso. Otra forma es imponiendo restricciones y limitaciones con el fin de evitar que una de las 4 condiciones ocurra, de esta forma se evitaría el deadlock:

Mutua exclusión:

que un proceso no quede esperando en caso de la falta de disponibilidad de dicho recurso.

Control y espera:

 tratar de garantizar que cuando un proceso tenga un recurso asignado, no pueda solicitar otro. Se logra de dos maneras, una es que los procesos soliciten todos los recursos en el momento previo a su ejecución. Otra es que el proceso primero debe liberar aquellos recursos que posee para poder solicitar otros.

No expropiaciones:

existen también dos métodos. El primero consiste en que si un proceso solicita que no esta disponible, este debe devolver todos los recursos que tenia asignados. La otra trata de que si un proceso pide un recurso que tiene otro proceso, el SO puede obligar al otro recurso a liberarlo.

Espera circular:

imponer un orden lineal de ejecución que evite las esperas circulares.

Detectar y recuperar:

abortar un proceso cuando se detecta o se presupone que puede ocurrir un deadlock. La ventaja que tiene es que no limita el acceso a los recursos, ni el accionar de los procesos. Pero presenta inconvenientes como el de decidir la frecuencia con que se llevara a cabo el algoritmo de detección y aplicación del sistema de recupero. Se pierde mucho tiempo, es puro overhead, aunque el algoritmo es muy simple y la identificación del deadlock es casi inmediata.  Existen varios métodos:

Abortar todos los procesos involucrados.

Hacer un backup de cada proceso en un punto anterior (Checkpoint).

Abortar los procesos uno a uno, hasta que el deadlock desaparezca.

Ir abortando sucesivamente procesos hasta que no haya mas deadlock.

Quitar un recurso a un proceso y entregárselo a otro que lo haya solicitado.