Bloque 1: Concurrencia - Bloqueo Mutuo (Deadlock)

1.1 Principios del Bloqueo Mutuo

El Deadlock (Bloqueo Mutuo) es el bloqueo permanente de un conjunto de procesos que compiten por recursos del sistema o se comunican entre sí. Ocurre cuando cada proceso del conjunto está bloqueado esperando un evento que solo puede ser activado por otro proceso bloqueado del mismo conjunto.

Tipos de Recursos involucrados:

● Recursos Keutilizables (Reusable): Pueden ser usados por un proceso a la vez y no se agotan ni destruyen con el uso. Ejemplos: Procesador, marcos de memoria principal, canales de E/S, archivos y semáforos. El deadlock tipicamente ocurre cuando dos procesos retienen un recurso reutilizable y solicitan otro.

- Recursos Consumibles (Consumable): Son creados (producidos) y destruidos (consumidos) dinámicamente por el sistema. Ejemplos: Mensajes en buffers de comunicación, señales o interrupciones. Un deadlock aquí ocurre si un proceso se bloquea esperando un mensaje que el otro proceso nunca enviará debido a su propio bloqueo.

Diagrams de Progreso Conjunto (Joint Progress Diagrams):

Muestran la velocidad de ejecución relativa de dos procesos en ejes cartesianos (X e Y). Si las trayectorias de ejecución entran en una región fatal (fatal region), el deadlock se vuelve inevitable, independientemente de cómo planifique el sistema operativo los hilos de ahí en adelante.

1.2 Las 4 Condiciones Necesarias y Suficientes para el

Deadlock

Para que exista un bloqueo mutuo, deben cumplirse simultáneamente las siguientes cuatro condiciones:

1. Exclusión Mutua (Mutual Exclusion): Solo un proceso puede usar un recurso a la vez. Ningún otro puede acceder a él mientras esté asignado.

2. Retención y Espera (Hold and Wait): Un proceso puede retener recursos ya asignados mientras espera la asignación de nuevos recursos.

3. No Apropiación (No Preemption): Los recursos no pueden ser retirados por la fuerza a un proceso que los retiene; deben ser liberados voluntariamente por este.

4. Espera Circular (Circular Wait): Existe una cadena cerrada de procesos en la cual cada uno de ellos retiene uno o más recursos que son necesitados por el siguiente proceso en la cadena.

Nota técnica para el examen: Las condiciones 1 a 3 son decisiones de diseño o políticas del sistema operativo. La condición 4 (Espera Circular) es una circunstancia que surge en la ejecución debido a la combinación de las tres primeras.

1.3 Estrategias de Gestión del Deadlock A) Prevención del Deadlock (Deadlock Prevention)

Consiste en diseñar el sistema de manera que se elimine preventivamente la posibilidad de que ocurra al menos una de las cuatro condiciones necesarias.

• Evitar la Retención y Espera: Exigir que un proceso solicite y reciba todos sus recursos necesarios al mismo tiempo antes de iniciar su ejecución. Inconveniente: Ineficiente; los recursos se retienen sin usarse durante mucho tiempo.

- Permitir la Apropiación: Si un proceso que retiene recursos solicita otro que no se le puede asignar inmediatamente, se le obliga a liberar todos sus recursos actuales.

• Evitar la Espera Circular: Definir un ordenamiento lineal estricto de todos los tipos de recursos. Si a un proceso se le asigna el recurso de tipo R i , solo puede solicitar posteriormente recursos que pertenezcan a índices superiores R j donde j > i. Esto rompe matemáticamente la posibilidad de un ciclo cerrado.

B) Evitación del Deadlock (Deadlock Avoidance)

A diferencia de la prevención (que restringe la estructura de las peticiones de forma estática) , la evitación permite las peticiones pero analiza dinámicamente si conceder el recurso mantendrá al sistema en un Estado Seguro.

• Requisito fundamental: Cada proceso debe declarar de antemano el número máximo de recursos que llegará a necesitar en su vida útil (su matriz de demandas o claim matrix).

• Estado Seguro (Safe State): Existe al menos una secuencia de ejecución en la que todos los procesos pueden terminar sus demandas máximas sin caer en deadlock.

- Algoritmo del Banquero: Es el algoritmo clásico para sistemas con múltiples instancias de recursos. Cuando un proceso solicita un recurso, el sistema simula la asignación. Si el estado resultante es seguro, se concede el recurso; de lo contrario, el proceso se suspende en espera.

C) Detección del Deadlock (Deadlock Detection)

No restringe las solicitudes de recursos ni limita las acciones del usuario; concede los recursos siempre que estén disponibles. Periódicamente, el sistema operativo ejecuta un algoritmo para comprobar si existe una espera circular activa.

• Algoritmo de Detección: Utiliza una matriz de asignación (Allocation), un vector de recursos disponibles (Available) y una matriz de solicitudes actuales (Q). Va marcando los procesos que pueden terminar dado lo disponible actual; si al final quedan procesos sin marcar, están en Deadlock.

- Recuperación (Recovery): Una vez detectado el deadlock, el sistema debe intervenir rompiéndolo mediante:

1. Abortar (matar) todos los procesos en deadlock o uno por uno hasta disolver el ciclo.

2. Rebobinar (rollback) los procesos hasta un punto de control (checkpoint) seguro previamente guardado.

Bloque 2: Gestión de Memoria y Bases de Memoria Virtual [Stallings 7.1 - 7.4]

Para entender la memoria virtual, debemos dominar primero cómo organiza el hardware de la MMU los espacios lógicos:

1. Reubicación (Relocation): Capacidad de cargar y ejecutar un programa en cualquier región de la memoria física RAM. El procesador maneja direcciones lógicas, que la MMU traduce dinámicamente sumándoles un Registro Base.

2. Protección: Asegurar que un proceso no acceda (por error o malicia) al espacio de memoria de otro proceso o del Sistema Operativo. La MMU valida las direcciones contra un Registro Límite.

Comparativa: Paginación Simple vs. Segmentación Pura

Table summary: La tabla compara la paginación simple y la segmentación pura, destacando que la primera utiliza bloques de tamaño fijo y presenta fragmentación interna sin requerir contigüidad física, mientras que la segunda emplea bloques de tamaño variable, genera fragmentación externa y exige que los segmentos se almacenen de manera contigua en la memoria.

Bloque 3: Memoria Virtual y

Algoritmos de Reemplazo de Páginas [Stallings 8.1 - 8.2]

3.1 Conceptos Clave de Memoria Virtual

- Paginación en Memoria Virtual: A diferencia de la paginación simple, no es necesario que todas las páginas de un proceso estén cargadas en la RAM para que este pueda ejecutarse. Las páginas se mantienen en almacenamiento secundario (Disco duro / Swap) y se traen a la RAM solo cuando se necesitan.

- Fallo de Página (Page Fault): Interruptción de hardware generada cuando la CPU intenta acceder a una dirección lógica cuya página correspondiente no está cargada en la memoria física (su Bit de Presencia está en 0). El SO suspende el proceso, lee la página desde el disco, la aloja en un marco libre de la RAM, actualiza la tabla de páginas a 1 y reanuda la instrucción de la CPU.

• Hiperpaginación (Thrashing): Fenómeno adverso en el que el sistema operativo pasa más tiempo intercambiando páginas entre el disco y la RAM que ejecutando instrucciones útiles del programa. Ocurre cuando el tamaño de la memoria física asignada a un proceso es menor que su Conjunto de Trabajo (Working Set) actual.

Estructura Ampliada de una Entrada en la Tabla de Páginas (PTE):

Además del número de marco físico (Frame Number), contiene bits de control cruciales:

- Bit de Presencia/Validez (P): Indica si la página está en la RAM (1) o en el disco duro (0).

- Bit de Modificación/Dirty Bit (M): Indica si el proceso ha escrito o modificado datos en esa página desde que se cargó (1). Si está en 1, la página debe reescribirse obligatoriamente en el disco antes de ser desalojada (limpieza bajo demanda); si está en 0, se puede sobrescribir directamente en la RAM sin guardar nada.

3.2 Algoritmos de Reemplazo de Páginas (Page

Replacement)

Cuando ocurre un fallo de página y la RAM está completamente llena, el sistema operativo debe elegir una página residente para desalojarla y hacer espacio a la nueva.

1. Algoritmo Óptimo (Optimal)

- Lógica: Reemplaza la página que tardará más tiempo en volver a ser referenciada en el futuro.

• Rendimiento: Garantiza matemáticamente la menor cantidad posible de fallos de página.

- Viabilidad: Imposible de implementar en la realidad, ya que requiere que el sistema operativo conozca con precisión el futuro del programa. Se usa únicamente como métrica base de comparación teórica.

2. LRU (Least Recently Used - Menos Recientemente Utilizada)

Lógica: Reemplaza la página en memoria que no ha sido referenciada por el mayor periodo de tiempo. Se basa en el Principio de Localidad Temporal (lo que no se usó hace mucho, probablemente no se use pronto).

• Rendimiento: Muy cercano al óptimo, pero requiere soporte de hardware costoso (como guardar una marca de tiempo o gestionar una pila en cada lectura/escritura de memoria).

3. FIFO (First-In, First-Out)

- Lógica: Trata los marcos asignados al proceso como un buffer circular. Reemplaza la página que ha estado en memoria durante más tiempo, independientemente de qué tanto se use ahora.

- Desventaja: Puede desalojar páginas muy populares (por ejemplo, el bucle principal de un programa). Además, sufre de la Anomalía de Belady (en ciertos escenarios, aumentar la cantidad de marcos físicos asignados incrementa el número de fallos de página).

4. Algoritmo del Reloj (Clock Replacement Policy)

- Lógica: Una aproximación de bajo costo a LRU. Utiliza un único bit adicional por página llamado Bit de Uso (Use Bit).

• Funcionamiento:

- Cuando una página se carga o es referenciada posteriormente, su bit de uso se pone en 1.

- o Un puntero recorre circularmente los marcos de página como la manecilla de un reloj.

- o Al buscar una página para reemplazar: si el bit es 1, lo cambia a 0 y avanza al siguiente marco. Si encuentra un bit en 0, elige esa página para reemplazo, coloca el puntero en la posición inmediatamente posterior y termina la búsqueda.

Bloque de Ejercicios Prácticos Resueltos (Paso a Paso)

Ejercicio 1: Algoritmo del Banquero (Evitación de Deadlock)

Un sistema tiene 3 procesos (P 1, P 2, P 3) y 3 tipos de recursos (A, B, C). Las existencias totales en el sistema son: Vector Total equals [10, 5, 7]. Se nos presenta el siguiente estado del sistema:

Table summary: La tabla presenta una comparación entre los recursos asignados y la demanda máxima solicitada para diversos procesos.

Table summary: La tabla muestra una comparación entre dos conjuntos de vectores para tres puntos distintos, donde se observa que los valores en el segundo grupo son consistentemente más elevados que los del primero.

Paso 1: Calcular los recursos ya asignados y el Vector Disponible (Available)

Code summary: Este algoritmo calcula la cantidad de recursos restantes en un sistema. Toma como entrada una matriz de asignaciones actuales y el total de recursos disponibles, suma las asignaciones por cada tipo de recurso y resta dicho resultado del total general para obtener el vector de recursos libres.

Paso 2: Calcular la matriz de Necesidad Actual (Need = Claim - Allocation)

Code summary: El algoritmo calcula la diferencia entre varios pares de vectores. Recibe conjuntos de coordenadas como entrada y devuelve los resultados de las restas elementales para obtener nuevos puntos.

Paso 3: Evaluar la seguridad del estado buscando una secuencia segura

Code summary: Este algoritmo implementa la lógica del Banco para evitar interbloqueos en un sistema operativo. Recibe como entrada la cantidad de recursos disponibles y las necesidades de varios procesos, y determina el orden de ejecución seguro. El resultado es una secuencia de procesos que pueden completarse exitosamente al liberar sus recursos para los demás.

- ¿zeta punto P 3? Necesita [6, 0, 0]. Sí se puede ( 6 menor o igual a 7, 0 menor o igual a 5, 0 menor o igual a 5).

Simulamos que P 3 termina y devuelve sus recursos:

Final Available = [7, 5, 5] + [3, 0, 2] = [10, 5, 7] (Igual al vector total inicial)

Conclusión del ejercicio: El estado es SEGURO porque existe al menos una secuencia válida de finalización: secuencia de P 2, P 1, P 3. Cualquier solicitud que lleve a este estado puede ser aceptada.

Ejercicio 2: Reemplazo de Páginas (Simulación

Práctica)

Considera un proceso con 3 marcos físicos asignados en la RAM (inicialmente vacios). La cadena de referencia de páginas es la siguiente: 2, 3, 2, 1, 5, 2, 4. Vamos a resolverlo utilizando FIFO, LRU y Reloj (Clock).

A) Simulación con FIFO

FIFO reemplaza la página que entró primero.

1. Referencia 2: Fallo → RAM: abierto 2, guion, guion cerrado

2. Referencia 3: Fallo flecha RAM: corchete 2, 3, guion corchete

3. Referencia 2: Acierto (Ya está en memoria) → RAM: corchete 2, 3, guion corchete

4. Referencia 1: Fallo → RAM: [2, 3, 1] (La memoria está llena; la página más antigua es la 2)

5. Referencia 5: Fallo flecha Reemplaza al 2 flecha RAM: corchete 5 coma 3 coma 1 corchete

6. Referencia 2: Fallo → Reemplaza al 3 (Siguiente más antiguo) → RAM:

7. Referencia 4: Fallo → Reemplaza al 1 (Siguiente más antiguo) → RAM:

● Total de Fallos de Página (FIFO): 6 fallos.

B) Simulación con LRU

LRU reemplaza la página que lleva más tiempo sin ser accedida en el pasado reciente.

1. Referencia 2: Fallo flecha RAM: vacío

2. Referencia 3: Fallo flecha RAM:

3. Referencia 2: Acierto. (El historial de uso reciente se actualiza: el 2 es el más fresco, el 3 el más antiguo)

4. Referencia 1: Fallo flecha RAM: (La memoria está llena)

5. Referencia 5: Fallo → ¿Quién se va? Historical hacia atrás: 1 (reciente), 2 (medio), 3 (el más lejano). Reemplaza al 3. → RAM:

6. Referencia 2: Acierto → RAM: (Historial actual: 2 es el más fresco, luego 5, luego 1)

7. Referencia 4: Fallo → ¿Quién se va? El más lejano es el 1. Reemplaza al 1. → RAM:

● Total de Fallos de Página (LRU): 5 fallos.

C) Simulación con Reloj (Clock)

El Reloj rastrea marcos cílicamente con un bit de uso. Representamos el bit como Página(Bit). El puntero * indica qué marco se evalúa.

1. Referencia 2: Fallo. Se aloja en el marco 0 flecha RAM: vacío

2. Referencia 3: Fallo. Se aloja en el marco 1 flecha RAM: vacío

3. Referencia 2: Acierto. El bit de uso de 2 ya era 1, se mantiene en 1. Puntero no se mueve.

4. Referencia 1: Fallo. Se aloja en el marco 2 → RAM: vacío

5. Referencia 5: Fallo (Memoria llena).

○ El puntero escanea desde el marco 0:

○ Evalúa 2 abierto 1 cerrado flecha Cambia bit a 0 flecha 2 abierto 0 cerrado.

○ Evalúa 3 abierto 1 cerrado flecha Cambia bit a 0 flecha 3 abierto 0 cerrado.

○ Evalúa uno (uno) → Cambia bit a cero → uno (cero).

○ Dio la vuelta completa y regresa al inicio 2 (0). Como su bit ahora es 0, lo reemplaza.

RAM resultante: vacío (El puntero avanza a la siguiente posición).

6. Referencia 2: Fallo.

○ El puntero evalúa el marco 1: 3 (0). Como está en 0, lo reemplaza de inmediato.

o RAM resultante: vacío (El puntero avanza a la siguiente posición).

7. Referencia 4: Fallo.

○ El puntero evalúa el marco 2: 1 (0). Como está en 0, lo reemplaza de inmediato.

o RAM resultante: vacío (El puntero avanza al marco O).

• Total de Fallos de Página (Reloj): 6 fallos.

Consejos prácticos de última hora para el examen:

1. En el Banquero: Asegúrate siempre de escribir la matriz completa de Need al inicio del desarrollo; los profesores penalizan severamente omitir este paso en la calificación.

2. En las Tablas de Páginas de ejercicios: Recuerda que las direcciones de memoria virtual se dividen en bits de página y bits de desplazamiento (offset). Si te dicen que las páginas miden 4 KB, el offset ocupa exactamente 12 bits porque 2 superscript 12 = 4096 . El tamaño de la página nunca altera el tamaño del offset durante la traducción física de la MMU. Éxitos en tu examen teórico!

Ha llegado al final del documento.