Comunicación entre Procesos

Los procesos necesitan comunicarse entre sí para coordinar sus acciones y compartir información.

Condiciones de Competencia

Las condiciones de competencia surgen cuando dos o más procesos comparten recursos como la memoria o archivos.

Variables Compartidas:

• Out: Apunta al siguiente archivo por imprimir.
• In: Apunta a la siguiente ranura libre del spool.

Concepto: Se presenta cuando dos o más procesos intentan acceder y modificar un mismo recurso simultáneamente.

Nota: Si no existe sincronización, pueden ocurrir problemas al acceder al recurso compartido.

Sección Crítica

Es el área de código donde un proceso accede a la memoria o variables compartidas, o realiza tareas que pueden generar una condición de competencia.

Para evitar esto: Se utiliza la exclusión mutua.

Exclusión Mutua

Garantiza que solo un proceso pueda acceder a un recurso compartido a la vez.

Concepto: Prohibir que más de un proceso lea y escriba simultáneamente en los datos compartidos.

Condiciones de Solución

1. Dos procesos nunca pueden estar simultáneamente dentro de sus secciones críticas.
2. No se puede asumir nada sobre la velocidad o el número de CPUs.
3. Ningún proceso fuera de su sección crítica puede bloquear a otros procesos.
4. Ningún proceso debe esperar indefinidamente para entrar en su sección crítica.

Exclusión Mutua con Espera Activa

1. Inhabilitación de Interrupciones

   1. El proceso deshabilita las interrupciones al entrar en su sección crítica y las habilita al salir.
   2. Con las interrupciones desactivadas, la CPU no puede cambiar de proceso.
   3. No es recomendable que los procesos de usuario deshabiliten interrupciones.
   4. En sistemas multiprocesador, la deshabilitación solo afecta a la CPU que ejecuta la instrucción.

2. Variables de Candado

   1. Es una variable compartida que indica si un proceso está en su sección crítica.
      1. Si el candado es = 1, el proceso entra en su sección crítica y el candado cambia a 0.
      2. Al salir de la sección crítica, el candado vuelve a 1.

3. Alternancia Estricta

   1. Trabaja con variables tipo turnos.

4. Peterson

Dormir y Despertar

Dormir: Es una llamada al sistema que bloquea o desactiva un proceso.

Despertar: Es una llamada que activa un proceso. Tiene un parámetro, una dirección de memoria, para asociar las llamadas a sleep con las llamadas a wakeup.

Código

#define N 4
int count = 0;

void producer(void){
    while (true) {
        produce_intem();
        if (count == N) sleep();
        enter_item();
        count = count + 1;
        if (count == 1) wakeup(consumer);
    }
}

void consumer(void){
    while (true) {
        if (count == 0) sleep();
        remove_item();
        if (count == N - 1) wakeup(producer);
        consume_item();
     }
}

Variable entera para contar el número de señales de despertar, almacenadas para su uso posterior.

Operaciones UP y DOWN (llamadas al sistema) para inhabilitar brevemente las interrupciones mientras se prueba el semáforo, se actualiza y se pone el proceso a dormir si es necesario.

Down                                    UP
Si  s > 0                             Si la cola de procesos está vacía
s = s - 1;                                 s = s + 1;
Else                                   Else
Bloquear proceso                        Desbloquear Proceso

Monitores

Colección de procedimientos y datos agrupados en un módulo especial llamado módulo monitor.

Propiedad importante: Solo un proceso puede estar activo en un monitor a la vez (exclusión mutua).

Los monitores proveen un nuevo tipo de variables de condición con dos operaciones:

• Wait -> wait(a): Interrumpe el proceso que ejecuta la instrucción y lo remueve de la cola de listos hasta que otro proceso lo habilite con signal().
• Signal -> signal(a): Habilita la ejecución de algún proceso en espera por wait() con la misma variable de condición.

Se diseñaron para resolver la exclusión mutua en CPUs con acceso a memoria común. En sistemas distribuidos con memoria propia, estas primitivas no funcionan.

Interbloqueos

Impiden que un conjunto de procesos completen sus tareas.

Entorno Multiprogramación

Cuando varios procesos compiten por un número finito de recursos.

La falta de sincronización puede generar dos condiciones: interbloqueo e inanición.

Modelo del Sistema

El sistema tiene un número finito de recursos como espacio de memoria, ciclos de CPU, disco duro, etc.

Cada recurso tiene instancias. Un proceso puede usar un recurso en la siguiente secuencia:

• Solicitud: Si la solicitud no se puede atender, el proceso debe esperar.
• 
• 
• Uso: El proceso opera sobre el recurso.
• Liberación: El proceso libera el recurso.

Definición de Interbloqueo

Un conjunto de procesos está en interbloqueo cuando cada uno posee un recurso y espera obtener un recurso poseído por otro proceso del conjunto.

Características para que se produzca un Interbloqueo

1. Exclusión Mutua

   Solo un proceso puede usar un recurso a la vez. Si otro proceso lo solicita, debe esperar a que se libere.

2. Retención y Espera

   Cuando un proceso que ya tiene recursos asignados solicita recursos adicionales que están siendo retenidos por otros procesos.

3. Sin Desalojo

   No se le puede quitar un recurso a un proceso a la fuerza, solo lo libera voluntariamente.

4. Espera Circular

   Ocurre cuando dos o más procesos forman una cadena circular de espera, donde cada proceso espera por un recurso retenido por el siguiente proceso en la cadena.

Grafos de Asignación de Recursos

• Arcos
  • P1 → Rj: Solicitud
  • Rj → Pi: Asignación
• Ciclos: Indican la existencia de un interbloqueo.

Condiciones necesarias para que se produzca un interbloqueo

Que el recurso se haya liberado. En este caso, todos los automóviles desean seguir sus rutas al mismo tiempo, no tienen orden para turnarse.

Retención y espera: Debe existir un proceso que por lo menos esté reteniendo un recurso y esté esperando adquirir recursos adicionales que en ese momento están siendo retenidos por otro proceso.

Todos los pasos posibles en que los automóviles puedan hacer uso de su vía están siendo bloqueados por otros, es así que ambos tienen que esperar a que otro de ellos cambie su estado y como no existe modo de desbloqueo se han quedado en retención.

No apropiación: Un recurso solo puede ser liberado voluntariamente por el proceso que lo está reteniendo.

Se están reteniendo todos los automóviles porque no existe una condición para eliminar el interbloqueo, esta es la razón para que ninguno de ellos pueda continuar con su ruta, si se establecieran condiciones para evitar el bloqueo de estos automóviles entonces existiría un modelo de paso y priorización.

Espera Circular: Debe existir un conjunto de procesos {P0, P1, P2,….,Pn} de procesos que esperan, tal que P0 esté esperando un recurso que está retenido por P1, P1 espera por un recurso retenido por P2,… y Pn-1 espera por un recurso retenido por Pn y Pn espera por un recurso retenido por P0.

Los automóviles se encuentran bloqueados unos entre otros. El uno impide el paso a otros y viceversa.

En esta gráfica existe un ciclo, y el P3 está solicitando una instancia del recurso R2 y ya no están disponibles más instancias en ese momento.

¿Existe interbloqueo? La respuesta es no, ya que P4 puede liberar una instancia del recurso R2 y ser asignado a P3, con lo cual se rompería el ciclo.

Estrategias para Enfrentar Interbloqueos

1. Utilizar un protocolo para asegurar que el sistema nunca entre en un estado de interbloqueo.
2. Permitir que el sistema entre en un estado de interbloqueo y luego hacer una recuperación.
3. Ignorar el problema y pretender que los interbloqueos nunca ocurren en el sistema (usado por la mayoría de los sistemas operativos, incluyendo a UNIX y Windows).

Para asegurarnos de que nunca ocurra un interbloqueo podemos usar estrategias de:

1. Prevención de Interbloqueos

   1. Retención y Espera

      Debemos garantizar que, siempre que un proceso solicite un recurso, no retenga otro.

   2. Retener y Esperar

      PROTOCOLO 1: Requiere que a cada proceso se le asignen todos sus recursos antes de iniciar su ejecución (en el momento de la creación – llamadas al sistema).

      PROTOCOLO 2: Permitir que un proceso solicite recursos solo cuando no tenga ninguno asignado.

      DESVENTAJAS:

      1. Baja utilización de recursos.
      2. Posibilidad de inanición.

   3. Sin Desalojo

      PROTOCOLO 1: Si un proceso que está reteniendo algunos recursos solicita otro recurso que no le puede ser asignado inmediatamente, entonces todos los recursos que tenía actualmente son liberados (se liberan implícitamente).

      PROTOCOLO ALTERNO: Si un proceso solicita algunos recursos, verificamos si están disponibles; si es así se los asigna. Caso contrario verificamos si están asignados a algún otro proceso que está esperando recursos adicionales; de ser así el proceso solicitante se apropia de los recursos deseados.

   4. Espera Circular

      Ordenamiento total de todos los tipos de recurso y requerir que cada proceso solicite dichos recursos en orden.

2. Evasión de Interbloqueos

   Requiere que el SO tenga información sobre los recursos que un proceso solicitará.

   El sistema debe distinguir si se puede otorgar un recurso sin peligro, y solo efectuar la asignación si no hay peligro.

   Estado Seguro

   Un SO está seguro solo si no existen interbloqueos y cuando existe una «secuencia segura».

   Además de las aristas de solicitud y asignación tenemos un nuevo tipo de aristas llamada: arista de declaración o demanda.

   Arista de declaración Pi → Rj indica que el proceso Pi puede solicitar el recurso Rj en algún momento en el futuro; representada por una línea punteada. Semejante a una arista de solicitud.

   Una arista de demanda se convierte en arista de solicitud cuando un proceso solicita un recurso.

   Cuando un recurso es liberado por un proceso, una arista de asignación se convierte en arista de demanda.

   Gráfica de Asignación de Recursos para Evasión de Interbloqueos

   Una solicitud solo puede atenderse si la conversión de la arista de solicitud Pi → Rj en una arista de asignación Rj → Pi no da como resultado un ciclo en la gráfica.

   Se utiliza un algoritmo de detección de ciclos.

   Si no existe un ciclo, entonces la asignación del recurso al Pi dejará al sistema en un estado seguro.

   Si existe al menos un ciclo el sistema estará en un estado inseguro; y por lo tanto la asignación al Pi no podrá realizarse.

   Estado Inseguro en Gráfica de Asignación de Recursos

Detección de Interbloqueos

Permitir al sistema entrar en interbloqueo y luego recuperarlo

1. Algoritmo de Detección
2. Esquema de Recuperación

Este esquema de detección y recuperación implica un gasto extra (overhead).

Este algoritmo es una variante de la gráfica de asignación de recursos llamado: gráfica de espera.

Recuperación de Interbloqueos

Es el proceso de determinar si existe un interbloqueo e identificar los procesos o recursos implicados. Una manera de identificar es monitorear periódicamente el estado de los recursos para detectar si hay espera circular.

Recuperación de Interbloqueo

Terminación de Procesos

• Abortar todos los procesos interbloqueados: Es una de las soluciones más comunes que adopta el SO.
• Abortar un proceso en cada ocasión hasta eliminar el ciclo de interbloqueo.

Apropiación de Recursos

1. Seleccionar una víctima: Qué recursos y de qué procesos se van a apropiar.
2. Retroceso o anulación: Regresar a los procesos a los que se les quitó los recursos a un estado seguro. Se puede dar un retroceso total o parcial.
3. Inanición: Garantizar que no siempre el mismo proceso será la víctima. Incluir los retrocesos en el factor costo.

Concepto: La inanición se presenta cuando un proceso nunca logra acceder a un recurso crítico, y por tanto no pudiendo continuar con su normal ejecución.

Gestión de Memoria

Hardware básico

La memoria principal y los registros del procesador son las únicas áreas de almacenamiento a las que la CPU puede acceder directamente.

Si las instrucciones o datos no están en memoria, deben cargarse antes de que la CPU pueda operar con ellos.

El acceso a memoria puede requerir muchos ciclos de reloj.

Entre la memoria y la CPU se suele añadir una memoria rápida llamada caché.

Memoria caché

Es una memoria que almacena datos para un acceso rápido.

Reasignación de Direcciones

Un programa reside en disco como un archivo binario.

Para ejecutarse, el programa necesita cargarse en memoria.

Cuando un proceso se ejecuta, accede a instrucciones y datos de la memoria.

Las direcciones pueden representarse en el programa fuente mediante direcciones simbólicas, en el compilador mediante direcciones relocalizables y en el editor de enlaces en direcciones absolutas.

Pasos de un Programa

1. Tiempo de compilación
2. Tiempo de carga
3. Tiempo de ejecución

Espacio de Direcciones Lógico y Físico

Una dirección generada por la CPU se conoce como dirección lógica, mientras que una dirección vista por la unidad de memoria se conoce como dirección física.

En la compilación y la carga, las direcciones lógicas y físicas son las mismas.

Dirección Lógica = Dirección virtual.

El conjunto de todas las direcciones lógicas generadas por un programa es un espacio de direcciones lógicas.

El conjunto de todas las direcciones físicas correspondientes a estas direcciones lógicas es el espacio de direcciones físicas.

El mapeo en tiempo de ejecución de direcciones virtuales en direcciones físicas lo realiza la unidad de administración de memoria (MMU), un dispositivo de hardware.

El programa de usuario maneja direcciones lógicas. El hardware de mapeo de memoria convierte las direcciones lógicas en direcciones físicas.

El programa de usuario no ve las direcciones físicas.

La MMU convierte direcciones lógicas en físicas.

Carga Dinámica

El tamaño de un programa puede estar limitado por el tamaño de la RAM.

La carga dinámica sirve para una mejor utilización del espacio de memoria física.

Las rutinas no se cargan hasta que se invocan.

Una rutina no utilizada nunca se carga.

Las rutinas se mantienen en disco en formato relocalizable.

Es responsabilidad de los usuarios diseñar sus programas para aprovechar este método.

Sin embargo, los SO pueden brindar rutinas de biblioteca para implementar la carga dinámica.

Enlace Dinámico y Bibliotecas Compartidas

Es cuando una biblioteca de código se enlaza al ejecutarse un programa, extrayéndola de la RAM.

Ventaja: El programa es más ligero y se evita la duplicación de código.

El tiempo de carga de los programas (latencia) es menor.

Las rutinas de enlace dinámico cargadas en memoria se comparten.

Superposición: Mantener en memoria solo las instrucciones y datos que se necesiten en un momento determinado.

Intercambio

Un proceso debe estar en memoria para ejecutarse, pero puede intercambiarse temporalmente a un almacenamiento auxiliar y luego volver a memoria para continuar su ejecución.

El intercambio consiste en trasladar el código y los datos de un proceso completo de memoria al almacenamiento secundario, para cargar otro previamente almacenado.

Condiciones para Intercambio

• Si deseamos intercambiar un proceso, debemos asegurarnos de que esté completamente ocioso.
• No debe tener E/S pendientes.

Asignación Contigua

Un espacio de memoria se divide generalmente en dos: una para el Sistema Operativo residente (núcleo) y otra para procesos del usuario. El sistema operativo puede estar en memoria alta o baja.

Existen dos esquemas de manejo:

• Asignación con una sola partición

  En este caso, en el espacio correspondiente a los procesos de usuario se carga un solo proceso a la vez.

• Asignación con varias particiones

  Uno de los esquemas consiste en dividir la memoria en varias particiones de tamaño fijo, ubicando un proceso en cada partición.

  El SO tiene una tabla que indica qué partes de la memoria están ocupadas y cuáles desocupadas.

  Cuando no hay espacio para un proceso, el SO puede esperar por huecos suficientemente grandes o buscar otro proceso más pequeño que quepa en los huecos libres.

  Para la asignación de huecos existen tres estrategias:

  1. Primer ajuste: Asignar el primer hueco que tenga el tamaño suficiente. Podemos dejar de buscar tan pronto como encontremos un hueco lo suficientemente grande.
  2. Mejor ajuste: Asignar el hueco más pequeño que tenga tamaño suficiente. Es preciso examinar toda la lista, a menos que esté ordenada por tamaño.
  3. Peor ajuste: Asignar el hueco más grande.

  Fragmentación Externa: Se cuenta con el suficiente espacio de memoria total para satisfacer una solicitud pero el espacio no es contiguo.

  Fragmentación Interna: Memoria que está dentro de una partición pero no se usa.

  Solución Fragmentación Externa:

  Compactación: El objetivo es desplazar el contenido de la memoria hasta tener toda la memoria libre en un solo hueco.

Paginación

Es una forma de disminuir la fragmentación externa.

Es usada por casi todas las arquitecturas de hardware y por los SO.

Las direcciones lógicas no se disponen continuamente en la memoria física.

Consiste en dividir la memoria física en secciones de memoria, llamadas marcos, y dividir la memoria lógica en secciones del mismo tamaño, llamadas páginas.

El tamaño es fijo, y determinado por el hardware (4kb, 2Mb y 4Mb en i386).

La paginación consiste en considerar el espacio de direcciones lógicas de cada proceso como un conjunto de bloques de tamaño consistente llamados páginas. Cada dirección lógica manejada para un proceso estará conformada por un par de valores.

Segmentación

La segmentación es un esquema de administración de la memoria que soporta la visión que el usuario tiene de la misma.

Un espacio de direcciones lógicas es una colección de segmentos.

Cada segmento tiene un nombre y una longitud.

Las direcciones especifican tanto el nombre del segmento como el desplazamiento dentro del segmento.

Por lo tanto, el usuario especifica cada dirección mediante dos cantidades: un nombre de segmento y un desplazamiento.

Fragmentación

El sistema operativo tiene que encontrar y asignar memoria para todos los segmentos de un programa de usuario. Esta situación es similar a la paginación, excepto en el hecho de que los segmentos son de longitud variable; las páginas son todas del mismo tamaño. La segmentación puede ocasionar entonces fragmentación externa, cuando todos los bloques libres de memoria son demasiado pequeños para acomodar a un segmento.