Sincronización de Procesos, Memoria y Gestión de Recursos en Sistemas Operativos

Sincronización de Procesos en Sistemas Operativos

La sincronización de procesos se refiere a una serie de métodos para resolver problemas que surgen entre procesos cooperativos en entornos de multiprogramación. Al compartir recursos, pueden presentarse problemas relacionados con el orden de ejecución, lo que puede llevar a resultados indeseados, comportamientos impredecibles, inconsistencias y/o incoherencia de datos.

Conceptos Clave en Sincronización de Procesos

• Sección Crítica: Es la parte del código de un programa donde se accede y modifica un recurso compartido. Solo un proceso puede acceder a la sección crítica a la vez.
• Condición de Carrera: Ocurre cuando un recurso es accedido por más de un proceso que compite por el mismo. El resultado de la operación depende del orden en que se ejecuten las instrucciones de los procesos.

Requisitos para la Solución del Problema de la Sección Crítica

Toda solución al problema de la sección crítica debe cumplir con las siguientes condiciones:

• Exclusión Mutua (MUTEX): Solo un proceso puede estar en la sección crítica a la vez.
• Progreso: Solo los procesos que están en la cola de espera, y no aquellos que están ejecutando sus secciones restantes, participan en la decisión de quién será el siguiente en entrar en la sección crítica.
• Espera Limitada: Ningún proceso puede esperar indefinidamente para entrar en la sección crítica. Además, ningún proceso puede entrar ilimitadamente a la sección crítica si existe al menos un proceso que haya solicitado entrar.

Soluciones al Problema de la Sección Crítica

• A nivel de Software (SW):
  • Algoritmo de Peterson
• A nivel de Hardware (HW) - Instrucciones a nivel de procesador:
  • Test and Set
  • Swap
• A nivel de Sistema Operativo (SO):
  • Semáforos: Son un tipo de variable especial, un tipo abstracto de dato protegido que pertenece al dominio de los enteros y es manejado por el SO.
  • Tipos de Semáforos:
    • Binarios (MUTEX)
    • Contador: Toman valores enteros. Tienen una cola donde la cantidad de procesos en la misma se representa por valores negativos del semáforo.
  • Tipos de Espera:
    • Espera Activa
    • Espera no activa: Los procesos quedan en una cola de espera, representados por valores negativos del semáforo.
• A nivel de compiladores de lenguajes de alto nivel:
  • Monitores: Son un tipo de variable abstracta y un método que se invoca (sucesión de sentencias). Encapsulan todas las operaciones que se hacen sobre un recurso compartido. Se usan cuando tenemos varios procesos con códigos distintos, sistemas hechos por distintos programadores.

Interbloqueos en Sistemas Operativos

Los interbloqueos son situaciones en las que dos o más procesos se encuentran bloqueados indefinidamente, esperando por un recurso que está siendo retenido por otro proceso en el mismo conjunto.

Condiciones Necesarias para un Interbloqueo

• Exclusión Mutua: Al menos un recurso debe estar retenido en modo no compartible.
• Retención y Espera: Al menos un proceso está reteniendo un recurso y está esperando adquirir otros recursos que están siendo retenidos por otros procesos.
• No Apropiación: Los recursos no pueden ser expropiados por la fuerza. Es decir, un recurso solo puede ser liberado voluntariamente por el proceso que lo retiene.
• Espera Circular: Debe existir un conjunto de procesos {P0, P1, ..., Pn} tal que P0 está esperando un recurso que está retenido por P1, P1 está esperando un recurso que está retenido por P2, ..., Pn-1 está esperando un recurso que está retenido por Pn, y Pn está esperando un recurso que está retenido por P0.

Estrategias para Manejar Interbloqueos

• Prevención:
  • En el caso de la exclusión mutua, no se puede hacer nada cuando los recursos no son compartibles.
  • Para la retención y espera, el sistema debe ser transaccional y permitir que se retrotraiga todo al principio.
  • En el caso de la no apropiación, el sistema debe ser transaccional y permitir la expropiación.
  • Para la espera circular, se debe evitar el surgimiento de ciclos implementando un algoritmo que recorra el grafo y anote los procesos que retienen ciertos recursos.
• Evitar:
  • Una forma de resolver esto es determinar si el proceso está en estado seguro o inseguro. Estar en estado inseguro no implica necesariamente que se produzca un interbloqueo. Para estar seguro, se deben asignar todos los recursos antes de solicitarlos, y no se empieza a ejecutar hasta que se tenga todo.
• Detección y Recuperación:
  • Detectar interbloqueos no es simple. Se necesita un algoritmo matemático que trabaje con grafos. Se puede hacer un grafo de asignación de recursos y tomar una de las siguientes decisiones:
    • Terminar todos los procesos involucrados.
    • Terminar los procesos de uno en uno y verificar qué sucede.
    • Decidir qué proceso terminar aplicando prioridades.
    • Modificar las condiciones del SO para permitir la expropiación de recursos.
    • Dejar la decisión en manos del usuario.
• Ignorar el Problema: En algunos casos, se puede optar por no hacer nada y reiniciar el equipo si ocurre un interbloqueo.

Gestión de la Memoria Principal

La memoria principal es el espacio de memoria donde residen tanto el código a ejecutar como los datos del proceso en ejecución. Es una memoria de trabajo de acceso aleatorio.

• Memoria Periférica: Donde se guardan, con mayor o menor grado de permanencia, programas, datos, código fuente, documentos de texto, etc.
• Espacio de Memoria: Conjunto de direcciones de memoria. Se divide en:
  • Espacio de Direccionamiento: Conjunto de todas las direcciones posibles. Define la cantidad de bits que tiene la longitud de palabra de direccionamiento (por ejemplo, con 4 bits de direccionamiento, se tienen 16 direcciones de memoria).
  • Espacio de Direcciones: Subconjunto del espacio de direccionamiento que representa las direcciones que se están usando.

Técnicas para Evitar la Fragmentación

• Primer Ajuste: Asigna el primer hueco lo suficientemente grande.
• Mejor Ajuste: Asigna el hueco más pequeño que sea lo suficientemente grande.
• Peor Ajuste: Asigna el hueco más grande.

Paginación Simple

La paginación simple es una técnica por la cual un proceso no está en forma contigua en la memoria. Su espacio de direcciones físicas no es contiguo, sino que está disperso en distintas partes de la memoria.

• Es una nueva forma de administrar la memoria que reemplazó a las particiones fijas y variables.
• La memoria lógica se divide en páginas de igual tamaño, y la memoria física se divide en marcos del mismo tamaño que las páginas.

Paginación Jerárquica

Cuando los procesos crecieron en tamaño junto con las memorias RAM, aumentó el tamaño de las páginas y, por lo tanto, el tamaño de las tablas de páginas. Esto generó huecos de memoria, reintroduciendo la fragmentación externa. La solución es dividir las páginas de forma jerárquica.

Segmentación

La segmentación es una técnica de gestión de memoria en la cual se divide la memoria en unidades lógicas de distintos tamaños, denominadas segmentos. Se utilizó en el paradigma estructurado para garantizar la modularidad de los programas.

• La fragmentación pasaba a un segundo plano debido al pequeño tamaño de los segmentos.
• La dirección lógica emitida por la CPU se compone del número de segmento y el desplazamiento dentro del segmento.

Segmentación Paginada o Jerárquica

Cuando los segmentos crecieron en tamaño (por ejemplo, en sistemas de 32 bits), se empezaron a dividir en páginas, dando lugar a la segmentación jerárquica. En esta técnica, cada segmento está dividido en páginas. La dirección lógica se compone del número de segmento, el número de página dentro del segmento y el desplazamiento.

• Se tiene un puntero a la tabla de segmentos, que contiene la dirección de inicio del segmento cargado en memoria.
• Se debe acceder a la tabla de páginas para obtener la dirección de inicio de la página en la memoria RAM. Luego, se suma la dirección de inicio del segmento a la dirección de inicio de la página. Al número de marco se le suma el desplazamiento para acceder a la memoria.

Memoria Virtual

La memoria virtual es una técnica que permite la ejecución de un proceso sin que esté completamente cargado en memoria. Parte del proceso reside en el disco. La principal desventaja es que debe estar bien administrada.

• Paquete de Software: Con el aumento de la memoria, en lugar de tener programas aislados, se empezaron a agrupar en paquetes de software (un programa con distintas rutinas). No era necesario tener todo el paquete cargado en memoria, por lo que parte se guardaba en la memoria virtual.

Ventajas de la Memoria Virtual

• Al cargar solo lo necesario:
  • Se pueden tener muchos procesos en ejecución.
  • Se puede ejecutar un proceso rápidamente.

Paginación Bajo Demanda

• A medida que se requieren páginas, se van cargando en memoria. Esto mejora la velocidad de procesamiento.
• En la práctica, los procesos tienen una predicción de qué páginas son las más usadas.

Bit de Validez

El bit de validez es un bit de control que indica si una página de un proceso está en memoria o no.

• 1: La página está en la memoria RAM.
• 0: La página no está en la memoria RAM.

Si el proceso solicita una página y esta no está en la memoria RAM, se produce un fallo de página. Esto ocurre cuando el bit de validez de una página solicitada es 0.

• Si ocurre un fallo de página, se debe buscar la página en el disco. Se utiliza la pila de marcos libres, que contiene la dirección de comienzo de cada marco en la memoria física.
• Se toma un marco libre de la pila y se carga la página del disco a la RAM. Luego, se actualiza la tabla de páginas cambiando el estado del bit de validez. Todo esto se realiza a través de una rutina.

Página Víctima

Cuando se cargan muchos procesos, la pila de marcos libres puede vaciarse. En ese caso, se debe sacrificar una página de las que están en memoria, denominada página víctima. La idea es minimizar la cantidad de fallos de página. Los SO y la programación estructurada/modelo de objetos toman medidas para que los fallos no sean recurrentes.

• Una técnica es sacrificar páginas del propio proceso.
• Otra es sacrificar páginas de cualquier otro proceso.

Algoritmos de Selección de Página Víctima

• FIFO (First-In, First-Out): La primera página que entró es la primera en ser sacrificada.
• Anomalía de Belady: A veces, asignar más marcos puede empeorar el rendimiento.
• Óptimo: Es un algoritmo teórico que sirve como referencia para evaluar la eficiencia de otros algoritmos. La idea es reemplazar la página que se usará más tarde en el tiempo.
• LRU (Least Recently Used): Se sacrifica la página que no se haya utilizado recientemente, la que se usó más lejos en el tiempo.
• LRU por Aproximación:
  • Algoritmos de Bits de Referencias Adicionales: Se usan registros de desplazamiento de 8 bits.
• Segunda Chance o Reloj:
  • Se usa un bit por página.
  • Es una cola circular, no una FIFO, para evitar la anomalía de Belady.
  • Cada página que se carga pone su bit de referencia en cero.
  • Cuando hay que sacrificar una página, se le da a la usada recientemente una segunda oportunidad, poniendo su bit de referencia en 1, y se busca la siguiente.
• Algoritmo de Segunda Chance o Reloj Mejorado: Usa 2 bits: (0,0) - Ni usada ni modificada; (0,1) - No usada, sí modificada; (1,0) - Sí usada, no modificada; (1,1) - Sí usada, sí modificada.
• Algoritmos con Base de Conteo: Tienen un contador que indica la cantidad de veces que se usó una página. LFU (se sacrifica la menos usada) y MFU (se sacrifica la más usada). No se implementaron por ser costosos.

Asignación de Marcos

• Equitativa (interactivo): Se asigna a todos los procesos la misma cantidad de marcos.
• Proporcional (batch): Se asignan marcos dependiendo del tamaño y la demanda del proceso.

Sustitución de Marcos

• Local (interactivo): Si un proceso quiere cargar páginas, se sacrifican marcos de ese proceso.
• Global (batch): Si un proceso quiere cargar páginas, se sacrifican marcos de otro proceso.

Inconvenientes de la Memoria Virtual

• Sobrepaginación: Ocurre cuando los procesos pasan más tiempo paginando que procesando. Los procesos dedican más tiempo a asignar y sustituir marcos que a realizar sus tareas (procesos batch). No hay suficientes recursos para lo que se quiere hacer.
• Criterio de Localidad: Los procesos tienden a trabajar dentro de una rutina. Si se usa este criterio, el compilador sabe de antemano cuántos marcos necesita la rutina, y si usa variables locales, sabe los marcos que necesita para el almacenamiento de datos.
• Modelo de Localidad: A medida que se ejecuta un proceso, este se mueve entre localidades, que son conjuntos de páginas que se usan juntas dentro de una rutina.
• Modelo de Conjunto de Trabajo: Se basa en la suposición de localidad.
• Otro Modelo: Establecer un límite superior e inferior a la cantidad de fallos de página. Si hay muchos fallos de página, se asignaron pocos marcos; si hay pocos, se asignaron demasiados.
• Prepaginación: Se cargan todas las páginas de código de una rutina, ya que se sabe cuáles se utilizarán.
• Presacrificio: Para evitar quedarse con la pila de marcos libres vacía, se marcan páginas víctimas para ser sacrificadas, pero sin sacarlas de la RAM.