Cómo encarar el parcial
El examen suele ser multiple choice de 10 a 20 preguntas. Mirando los PDFs de preguntas, la mayoría se repite casi textual de un año a otro, así que conviene saber de memoria la "respuesta de cátedra" (abajo) y además entender el concepto para descartar distractores.
Plan sugerido
- Leé cada unidad de teoría (los recuadros amarillos son lo que más sale).
- Repasá la pestaña TPs y Linux: comandos, señales, semáforos POSIX.
- Hacé el banco de preguntas por tema hasta acertar todo.
- Practicá cálculos en Simuladores (Gantt, reemplazo de páginas, banquero).
- Hacé 2 o 3 simulacros de 15–20 preguntas al azar.
Qué entra
Teoría: cap. 4 Hilos, 5 Planificación de CPU, 6 Sincronización (concurrencia), 7 Interbloqueos (abrazo mortal), 8 Memoria principal y 9 Memoria virtual.
Práctica: TP hilos, administración de procesos, planificación, concurrencia (memoria compartida + fork), semáforos y abrazo mortal.
Las respuestas que más se repiten
Contadas en Parcial_2SO.pdf y Tercer_Parcial_Todas_las_preguntas.pdf. El número indica cuántas veces aparece la pregunta.
Algunas "respuestas correctas" del banco están redactadas raro (por ejemplo, la de "Linux antes no era expulsivo" define qué es expulsivo, y la de inversión de prioridad habla de "intercambiar prioridad"). En el multiple choice elegí la opción que coincide con esa redacción, aunque la explicación del libro sea más larga.
Los videos de la carpeta (≈ 6 horas) no se pudieron transcribir en este entorno, así que el resumen sale de las diapositivas, las consignas de los TPs, los PDFs de preguntas, las revisiones de Moodle, las fotos de parciales y el libro (Fundamentos de Sistemas Operativos, Silberschatz 7ma) en las secciones que indicó la cátedra.
En el banquero puede haber más de una secuencia segura válida (el simulador muestra la primera que encuentra recorriendo P0…Pn). Cualquiera sirve para decir que el estado es seguro.
Unidad 4 · Hilos
Silberschatz cap. 4. Lectura obligatoria: 4.2 (modelos multihilo) y 4.4.1 a 4.4.3.
Motivación: multiprocesamiento y multinúcleo
- SMP (multiprocesamiento simétrico): más de una CPU en el mother, comparten E/S y RAM.
- Multinúcleo: la CPU es el chip; puede contener uno o más núcleos. Cada núcleo ejecuta un hilo a la vez. Los primeros multinúcleo para PC salieron alrededor de 2005 (Pentium D).
- No confundir multiprocesamiento (varias CPUs/núcleos, hardware) con multiprogramación (varios procesos cargados en memoria compartiendo la CPU, software).
- Concurrencia: permite el progreso de más de una tarea a la vez (puede ser intercalando en un solo núcleo). Paralelismo: ejecutar más de una instrucción al mismo tiempo (requiere varios núcleos). Puede haber concurrencia sin paralelismo.
- Paralelismo de datos: la misma función sobre distintos datos (sumar mitades de un vector en dos núcleos). Paralelismo de tareas: distintas funciones en paralelo.
Proceso moderno vs hilo
Hilo: unidad básica de utilización de CPU (de núcleo). Es la parte activa: tiene identificador (TID), contador de programa, conjunto de registros, pila propia y estado. El planificador planifica hilos.
Proceso (con hilos): contenedor de recursos (RAM, archivos, dispositivos, programa). Es la parte "estática", como una cocina o un aula. El proceso clásico o pesado es un proceso con un solo hilo.
| Comparten los hilos de un proceso | Propio de cada hilo |
|---|---|
| Sección de código (programa) | ID de hilo (TID) |
| Sección de datos (variables globales) y heap | Contador de programa (PC) |
| Archivos abiertos, señales, otros recursos del SO | Registros de CPU (contexto) |
| Espacio de direcciones | Pila (stack) y estado; se describe en el TCB |
Si un hilo se bloquea (con hilos de kernel), los demás del proceso siguen ejecutando.
Crear un hilo vs crear un proceso
Crear proceso
- Asignar recursos y espacio en RAM
- Cargar el código
- Crear e inicializar el PCB
- (en
fork()) duplicar el espacio de direcciones
Crear hilo
- Ubicar su pila
- Inicializar un TCB (mucho más chico que el PCB)
- Nada de cargar código ni asignar memoria nueva
Eliminar un hilo también es más simple: no se recuperan recursos salvo que sea el último hilo. En Linux los hilos se crean con la LS clone().
Ventajas y desventajas
| Ventaja | Qué significa |
|---|---|
| Capacidad de respuesta (interactividad) | El programa sigue respondiendo aunque una parte esté bloqueada o haciendo algo largo. |
| Compartir recursos | Los hilos comparten memoria y recursos del proceso sin necesidad de memoria compartida ni paso de mensajes. |
| Economía | Crear hilos y cambiar de hilo es más barato que crear procesos y cambiar de contexto. Importa mucho en servidores. |
| Aprovechar multinúcleo (escalabilidad) | Un proceso puede ejecutar en paralelo en varios núcleos. Con un solo hilo usa un núcleo, tenga los que tenga. |
Desventajas: más complejidad de desarrollo; compartir recursos tan fácil exige más control (condiciones de carrera, se ve en concurrencia).
Ley de Amdahl
aceleración ≤ 1 / ( S + (1 − S) / N ) donde S es la fracción serial (no paralelizable) y N la cantidad de núcleos. Cuando N → ∞, la aceleración tiende a 1/S.
Ejemplo: S = 25 %, N = 2 → 1,6 ; N = 4 → 2,28 ; límite = 4.
Hilos de usuario, hilos de kernel y modelos (4.2)
| Modelo | Cómo funciona | Consecuencia | Ejemplos |
|---|---|---|---|
| Muchos a uno | Muchos hilos de usuario sobre un único hilo de kernel. El kernel no reconoce los hilos; una biblioteca en modo usuario los gestiona y planifica. | Si un hilo hace una LS bloqueante se bloquea todo el proceso. No aprovecha multinúcleo. | Green threads (Solaris), GNU Portable Threads |
| Uno a uno | Cada hilo de usuario se mapea a un hilo de kernel. El kernel reconoce, administra y planifica los hilos. | Más concurrencia y paralelismo. Desventaja: crear un hilo de usuario implica crear uno de kernel, por eso se limita la cantidad. | Linux, Windows, Solaris, macOS, iOS, Android |
| Muchos a muchos | Multiplexa muchos hilos de usuario sobre igual o menor número de hilos de kernel. | Se crean tantos hilos de usuario como se quiera y aun así hay paralelismo. | Solaris antes de la v9 |
| Dos niveles | Muchos a muchos que además permite ligar un hilo de usuario a uno de kernel. | Variante del anterior | IRIX, HP-UX, Tru64 |
Bibliotecas de hilos: Pthreads (estándar POSIX, es una especificación, no una implementación), Win32 y Java. En el modelo uno a uno, las bibliotecas de hilos contienen llamadas al sistema.
Aspectos de los hilos (4.4.1 a 4.4.3)
- fork() y exec(): si un hilo hace
fork(), algunos UNIX duplican todos los hilos y otros solo el que llamó. Si después se haceexec(), conviene duplicar solo el que llamó, porque exec reemplaza todo el proceso. - Cancelación de un hilo destino: asíncrona (se termina de inmediato, riesgo de dejar recursos o datos inconsistentes) o diferida (el hilo comprueba periódicamente si debe terminar, en puntos de cancelación seguros).
- Señales: las síncronas (división por cero, acceso ilegal) se entregan al hilo que las generó. Las asíncronas: algunas como SIGINT, SIGTERM y SIGKILL van a todo el proceso; también se puede dirigir una señal a un hilo específico. Puede haber consecuencias inesperadas: matar un hilo puede cerrar el proceso entero.
- Otros (lectura liviana): conjuntos compartidos de hilos (thread pools: atender con un hilo existente es más rápido y limita la cantidad), datos específicos del hilo, activaciones del planificador (LWP y upcalls).
Hilo de software vs hilo de hardware
Los hilos de software son las divisiones de un proceso. Con hyperthreading/SMT (multithreading de hardware) cada núcleo tiene más de un conjunto de registros, y se dice que tiene hilos de hardware (procesadores lógicos): optimiza el cambio de hilos. Un núcleo con HT no rinde como dos núcleos reales.
• Hilo SW vs HW → "Los de software son las divisiones de un proceso. Los hyperthreading se dice que tienen hilos de hardware".
• Multithreading → "capacidad de soportar más de un conjunto de registros para hilos, lo que optimiza el cambio de hilos".
• Multicore → "tienen los cores en un mismo chip. Se adaptan mejor a la ejecución de los hilos".
• Planificar procesos vs hilos → "los hilos relacionados deberían planificarse y ejecutarse como grupo. En general a los procesos no".
Unidad 5 · Planificación de CPU
Silberschatz cap. 5. No puede haber multiprogramación sin planificación de corto plazo: decidir, en un momento dado, qué proceso (hilo) usa una CPU.
Conceptos básicos
- Hay 3 planificadores: largo plazo (qué trabajos entran, grado de MP), mediano plazo (suspende/reanuda, swapping) y corto plazo (qué proceso listo usa la CPU; acá "el planificador").
- Ciclo de ráfagas: los procesos alternan ráfagas de CPU y de E/S. Limitado por CPU (CPU bound): pocas ráfagas de CPU y largas, alta utilización de CPU. Limitado por E/S: muchas ráfagas de CPU cortas.
- En una PC de escritorio la mayoría de los procesos son interactivos / limitados por E/S.
¿Cuándo actúa el planificador? (5.1.3)
| # | Situación | Origen |
|---|---|---|
| 1 | Un proceso pasa de ejecución a espera (pide E/S, hace wait()) | Llamada al sistema |
| 2 | Un proceso pasa de ejecución a listo (llega una interrupción, p. ej. del temporizador) | Interrupción |
| 3 | Un proceso pasa de espera a listo (termina su E/S) | Interrupción |
| 4 | Un proceso termina | Llamada al sistema |
Si solo se planifica en 1 y 4 → no apropiativa (non-preemptive, cooperativa, no expulsiva): el proceso retiene la CPU hasta liberarla voluntariamente (LS bloqueante o fin). Si también en 2 y 3 → apropiativa (preemptive, expulsiva): el planificador puede desalojar al proceso. Requiere hardware (temporizador) y trae problemas de concurrencia con datos compartidos, del proceso y del kernel. "El SO es un software impulsado por interrupciones" (las LS usan excepciones, que son interrupciones).
Despachador (5.1.4)
Módulo que aplica la decisión del planificador: guarda el contexto del proceso saliente (actualiza su PCB), restablece el del entrante, cambia a modo usuario y salta a la instrucción donde debe reanudar. Su tiempo es la latencia de despacho, que debe ser mínima (overhead). No siempre que corre el planificador hay cambio de proceso (si elige al mismo, no hay despacho).
Criterios / parámetros (5.2)
| Parámetro | Definición | Objetivo |
|---|---|---|
| Utilización de CPU | % del tiempo que la CPU está ocupada | Maximizar |
| Tasa de procesamiento (throughput) | Procesos completados por unidad de tiempo | Maximizar |
| Tiempo de ejecución (retorno, turnaround) | Desde que llega hasta que termina = fin − llegada | Minimizar |
| Tiempo de espera | Suma del tiempo en la cola de listos = retorno − ráfaga | Minimizar |
| Tiempo de respuesta | Desde que se hace un pedido hasta que se empieza a mostrar la primera parte de la respuesta | Minimizar |
| Consumo de energía | Importa en móviles y embebidos | Minimizar |
Los objetivos pueden estar en conflicto. Según el uso: lotes → throughput y utilización; servidor → throughput y respuesta; PC/smartphone → respuesta (y energía en el celular); tiempo real → cumplir plazos.
Algoritmos (5.3)
| Algoritmo | ¿Apropiativo? | Idea | Ventajas | Desventajas |
|---|---|---|---|---|
| FCFS (FIFO) | No | Se atiende por orden de llegada (cola FIFO) | Simple. Bueno para lotes | Efecto convoy (los cortos esperan detrás de uno largo). Malo para interactivos. Tiempo de espera promedio alto |
| SJF (trabajo más corto primero) | Puede ser ambos; la versión apropiativa es SRTF (menor tiempo restante) | Elige la ráfaga de CPU siguiente más corta | Óptimo en tiempo de espera promedio | No se puede saber la duración de la próxima ráfaga (se estima; la predicción no se ve). Inanición de los largos |
| Prioridades | Ambos | Elige el de mayor prioridad (en el libro, número menor = más prioridad). SJF es un caso de prioridad | Flexible. Prioridades internas (medibles) o externas (las fija el administrador) | Inanición (bloqueo indefinido). Solución: envejecimiento (aging), subir la prioridad de los que esperan mucho |
| Round Robin (turno rotatorio) | Sí | FCFS con cuanto de tiempo (q); al vencer, el proceso vuelve al final de la cola | Bueno para interactivos y tiempo compartido. Sin inanición | Sobrecarga por cambios de contexto. Espera promedio suele ser alta |
| Colas multinivel | Entre colas, normalmente sí | Varias colas por tipo (sistema, interactivos, lotes…), cada una con su algoritmo; entre colas prioridad fija o reparto de tiempo (p. ej. 80 % / 20 %) | Trata distinto a cada tipo de proceso | Rígido: el proceso queda fijo en su cola; inanición de colas bajas |
| Colas multinivel realimentadas | Sí | Los procesos se mueven entre colas (bajan si usan mucha CPU, suben si esperan mucho) | El más general y configurable | El más complejo: muchos parámetros (n.º de colas, algoritmo de cada una, cuándo subir/bajar, a qué cola entra) → difícil de ajustar y más overhead |
Si q es muy grande, RR se vuelve FCFS. Si es muy chico, todo el tiempo se va en cambios de contexto (overhead). Criterio del libro: el 80 % de las ráfagas de CPU deberían ser más cortas que q. Valores típicos: 10–100 ms. El tiempo restante del cuanto se guarda en el descriptor del proceso (PCB; en Linux 2.4, el campo counter).
Ejemplos clásicos del libro (para el Gantt)
| Caso | Datos (llegada, ráfaga) | Resultado |
|---|---|---|
| FCFS orden P1, P2, P3 | P1=24, P2=3, P3=3 (todos en 0) | Espera: 0, 24, 27 → promedio 17 |
| FCFS orden P2, P3, P1 | mismos | Espera: 6, 0, 3 → promedio 3 (efecto convoy) |
| SJF no apropiativo | P1=6, P2=8, P3=7, P4=3 (todos en 0) | Orden P4, P1, P3, P2 → promedio 7 (FCFS daría 10,25) |
| SRTF (SJF apropiativo) | P1 (0,8), P2 (1,4), P3 (2,9), P4 (3,5) | P1|P2|P4|P1|P3 → promedio 6,5 (SJF no apropiativo: 7,75) |
| Prioridad no apropiativa | ráfaga/prioridad: P1 10/3, P2 1/1, P3 2/4, P4 1/5, P5 5/2 | P2, P5, P1, P3, P4 → promedio 8,2 |
| Round Robin q = 4 | P1=24, P2=3, P3=3 | P1|P2|P3|P1… → espera 6, 4, 7 → promedio 5,66 |
Podés verificar todos en la pestaña Simuladores.
Multiprocesador (5.4)
- Asimétrico: un procesador maestro hace la planificación y E/S; los demás solo código de usuario. Simétrico (SMP): cada procesador se planifica solo (cola común o una cola por procesador). Los SO actuales usan SMP.
- Afinidad al procesador: conviene que el proceso siga en el mismo procesador porque la caché ya tiene sus datos y la reanudación es más rápida. Suave (el SO lo intenta) o dura (el proceso indica en qué CPUs puede correr).
- Equilibrado / balance de carga: repartir la carga entre CPUs. Migración comandada (push): una tarea revisa periódicamente y mueve procesos de CPUs cargadas a libres. Migración solicitada (pull): un procesador inactivo saca un proceso de uno ocupado. Linux usa ambas.
- Balance de carga y afinidad se contraponen: migrar para balancear pierde lo que hay en caché.
- Multithreading simétrico (SMT / hyperthreading): cada procesador físico se ve como varios lógicos. Si el SO lo sabe, evita poner dos hilos pesados en lógicos del mismo físico teniendo otro físico libre.
Planificación de hilos: ámbito de contienda (5.5.1, primer párrafo)
PCS · ámbito del proceso
En los modelos muchos-a-uno y muchos-a-muchos, la biblioteca planifica los hilos de usuario sobre los LWP disponibles. Compiten entre hilos del mismo proceso. Suele ser por prioridad.
SCS · ámbito del sistema
El kernel decide qué hilo de kernel va a la CPU; compiten todos los hilos del sistema. El modelo uno a uno (Linux, Windows) usa solo SCS.
Ejemplos de SO (5.6, sin Linux)
- Windows XP: el planificador se llama despachador (dispatcher). Apropiativo por prioridades, 32 niveles: variable 1–15, tiempo real 16–31 (0 = hilo de gestión de memoria). Clases: REALTIME, HIGH, ABOVE_NORMAL, NORMAL, BELOW_NORMAL, IDLE, con prioridad relativa dentro de cada clase. Al proceso en primer plano le aumenta el cuanto. Prioridad y afinidad se cambian desde el Administrador de tareas (Detalles → Establecer prioridad: Tiempo real, Alta, Por encima de lo normal, Normal, Por debajo de lo normal, Baja).
- Solaris: prioridades por clases (tiempo real, sistema, tiempo compartido, interactiva…), con tabla de despacho; los interactivos suben de prioridad.
Evaluación de algoritmos (5.7)
| Método | Ventaja | Desventaja |
|---|---|---|
| Modelado determinista (carga predeterminada, se calcula con Gantt) | Simple, rápido, da números exactos | Vale solo para esa carga |
| Modelos de colas (distribuciones de ráfagas y llegadas; fórmula de Little n = λ·W) | Analítico, permite comparar | Aproximación; supuestos poco realistas |
| Simulación (con números aleatorios o trazas reales) | Más exacta | Costosa (tiempo de cómputo, almacenamiento de trazas, programación) |
| Implementación (probarlo en el SO real) | La única completamente exacta | Costo alto; el entorno cambia y los usuarios adaptan su conducta al algoritmo |
• ¿Para qué se planifica? → "Para que se optimice tiempo de respuesta, rendimiento y eficiencia de la CPU".
• ¿Cuándo corre el short-term scheduler? → "Cada vez que hay un cambio de proceso/hilo".
• ¿Preemptive o no? → "Depende, para batch es mejor no preemptive, para interactivos preemptive".
• Kernel apropiativo / "Linux antes no era expulsivo" → "Que el código del kernel puede expulsar a cualquier código que se ejecute" (Linux se hizo apropiativo desde el 2.6).
• Monoprocesador vs multiprocesador → "En los multiprocesadores hay que cuidar la afinidad o el balance de carga".
• Afinidad → "los procesadores ya tienen los datos de los procesos/hilos cargados y es más rápida su reanudación".
Predicción de la siguiente ráfaga en SJF (promedio exponencial), 5.5.2 (planificación en Pthreads), 5.6.3 (Linux). De 5.7.1 solo los 2 primeros párrafos y el último; de 5.7.2 el primero.
Unidad 6 · Concurrencia (sincronización de procesos)
Silberschatz cap. 6. Todo lo que se dice de procesos vale también para hilos (y en hilos es todavía más fácil tener carreras porque comparten todo).
Por qué aparece
La concurrencia en el SO es un fenómeno causado por la multiprogramación: para maximizar el uso de recursos, se comparten entre procesos, y los procesos concurren hacia ellos. Hay recursos que solo se pueden usar de a n por vez (uso exclusivo) y ahí surgen los conflictos. Ejemplo de clase: varias compras simultáneas con $80 en una cuenta, se hacen más compras de las posibles.
Condición de carrera (CC)
Conjunto de factores que hacen que el resultado de la ejecución dependa del orden en que se ejecutan las instrucciones de los procesos que acceden al recurso compartido (intercaladas o en paralelo). Factores: concurrencia (MP) + recursos compartidos de uso exclusivo.
No son errores en sí: hacen posible el error (como manejar con niebla). Difíciles de detectar en pruebas; un programa con CC puede no fallar nunca. A nivel kernel siempre hay CC con MP (cola de listos, asignación de PID).
Sección crítica (SC)
Fragmento de código donde se usa un recurso compartido de uso exclusivo (no compartible). Es donde se dan las carreras y donde hay que lograr exclusión mutua. Su tamaño y duración afectan la probabilidad de inconsistencias.
Estructura: sección de entrada → SC → sección de salida → sección restante.
Requisitos de una solución al problema de la SC
| Requisito | Significado |
|---|---|
| Exclusión mutua | Si un proceso está en su SC, ningún otro puede estar en la suya. |
| Progreso | Si nadie está en la SC y alguien quiere entrar, la decisión la toman solo los que quieren entrar (no los que están en su sección restante) y no se posterga indefinidamente. |
| Espera limitada (acotada) | Hay un límite de veces que otros pueden entrar antes que un proceso que ya pidió entrar (sin inanición). |
Además: no se puede suponer nada sobre la velocidad relativa de los procesos.
Kernel apropiativo vs no apropiativo: uno no apropiativo está libre de carreras en sus estructuras (solo un proceso activo en modo kernel en monoprocesador); uno apropiativo responde mejor y sirve para tiempo real, pero hay que diseñarlo con cuidado.
Soluciones
Por software: Peterson (no se estudia en detalle, pero sale en el banco)
// proceso i (j = el otro)
flag[i] = true; turn = j;
while (flag[j] && turn == j) ; // espera activa
/* sección crítica */
flag[i] = false;Se llama solución por software porque no recibe ayuda del SO y se hace con un lenguaje de alto nivel. Desventajas: espera activa, variables compartidas, solo para 2 procesos y falla en las CPUs modernas (reordenan instrucciones). Las soluciones por software son complejas y lentas.
Por hardware
- Deshabilitar interrupciones: sirve en monoprocesador, pero en multiprocesador solo se inhibe en la CPU que ejecuta; las otras pueden entrar a la SC. Además es peligroso darle ese poder a procesos de usuario, afecta al reloj y si el proceso hace una LS bloqueante o se cuelga, el sistema queda sin interrupciones.
- Instrucciones atómicas (especiales de máquina): leen y modifican una variable en una sola instrucción no interrumpible. Test-and-Set (TAS), Swap/Compare-and-Swap (CAS). Ejemplo x86:
XCHG.
boolean TestAndSet(boolean *objetivo) { // se ejecuta ATÓMICAMENTE
boolean aux = *objetivo;
*objetivo = true;
return aux;
}
// uso: lock compartido inicializado en false
while (TestAndSet(&lock)) ; // espera activa (spinlock)
/* sección crítica */
lock = false;Que no puede ser interrumpida lógicamente, para que otro no interfiera con las operaciones propias.
Semáforos (6.5)
Herramienta de sincronización de más alto nivel, portable, provista por el SO, basada en las soluciones de hardware (solución mixta HW+SW). Es como un objeto: una variable entera S a la que solo se accede con 3 operaciones atómicas: inicialización, wait y signal. Para que wait y signal sean atómicas se protegen con instrucciones de HW (eso no aparece en el pseudocódigo).
wait(S) / P() / sem_wait(): si S == 0 → el proceso se bloquea; si S > 0 → S-- y sigue
signal(S)/ V() / sem_post(): S++ ; si hay procesos bloqueados, despierta uno
// uso para exclusión mutua (S inicializado en 1)
wait(S);
/* sección crítica */
signal(S);| Concepto | Detalle |
|---|---|
| Semáforo binario (mutex lock) | Solo valores 0 y 1. Para exclusión mutua. |
| Semáforo general / contador | Cualquier entero; modela n instancias de un recurso (30 bancos en un aula → S = 30). Binario y general tienen distinto código de wait/signal. |
| Con espera activa (spinlock) | wait hace un while(S<=0);. Gasta CPU; conviene solo en multiprocesador con SC muy cortas (evita el cambio de contexto). |
| Sin espera activa | Variable entera + cola de espera. wait bloquea al proceso (block) y signal lo despierta (wakeup). Depende del planificador. En esta implementación del libro S puede ser negativo: |S| = cantidad de procesos esperando. |
| Para sincronizar (ordenar) | Que S1 (en P1) se ejecute antes que S2 (en P2): sync = 0; P1: S1; signal(sync); P2: wait(sync); S2; |
| Mal uso | Invertir signal y wait viola la exclusión mutua; wait en lugar de signal → deadlock; omitir alguno → violación de EM o bloqueo; cola LIFO → inanición. |
| Orden de desbloqueo | No está garantizado FIFO: depende de la implementación de la cola. |
Mutex vs semáforo: un mutex es un lock con "dueño" (lo libera quien lo tomó) y vale 0/1; un semáforo contador no tiene dueño y cuenta instancias.
Inversión de prioridad: un proceso de baja prioridad tiene un recurso que necesita uno de alta prioridad, y uno de prioridad media expulsa al de baja; el de alta termina esperando al de media (como si se hubieran intercambiado las prioridades). Solución: herencia de prioridad (el que tiene el recurso hereda temporalmente la prioridad alta). Caso famoso: Mars Pathfinder.
Monitores (6.7)
Herramienta de nivel superior a los semáforos, no implementada por el SO sino por el lenguaje. Estructura tipo objeto (variables compartidas + procedimientos + inicialización) donde solo un proceso a la vez puede estar activo dentro del monitor, así que la exclusión mutua es automática y no hay carreras entre sus métodos.
monitor prueba {
// variables compartidas
procedure sumar(...) { ... }
procedure restar(...) { ... }
inicializacion(...) { ... }
}Variables condición (condition x): permiten sincronizar dentro del monitor por condiciones propias del problema. Tienen una cola de espera. x.wait() suspende al proceso; x.signal() reanuda exactamente un proceso suspendido, y si no hay ninguno no tiene efecto (a diferencia del signal de semáforo, que siempre suma 1). 6.7.4: se puede usar x.wait(c) con prioridad (despierta el de menor c), así que el orden no es necesariamente FIFO; y todos los procesos deben usar el monitor correctamente o no sirve.
Los SO no usan monitores porque se escriben en C/assembler (C no es orientado a objetos) y serían lentos.
Comparación de soluciones
| Hardware (TAS/CAS) | Semáforos | Monitores | |
|---|---|---|---|
| Nivel | Bajo, instrucción de CPU | Medio, provisto por el SO | Alto, provisto por el lenguaje |
| Espera | Activa (spinlock) | Bloqueada (sin espera activa) | Bloqueada |
| Ventaja | Rápido para SC cortas en multiprocesador | Portable, sirve para EM y sincronización | EM automática, menos errores |
| Desventaja | Consume CPU; inanición posible | Fácil usarlos mal (deadlock, violar EM) | Necesita soporte del lenguaje |
Las soluciones se apilan: los semáforos usan TAS, los monitores usan semáforos. Cualquiera sea la elegida, todos los procesos que acceden al recurso deben usarla. La solución más general (y peor) sería deshabilitar la multiprogramación. Definir una SC para todo el programa elimina la concurrencia (queda serializado).
Problemas clásicos (6.6, aparecen en el banco)
Buffer acotado (productor-consumidor)
Se cuida la exclusión mutua, el buffer lleno y el buffer vacío. mutex = 1, vacio = n, lleno = 0.
// productor // consumidor
wait(vacio); wait(lleno);
wait(mutex); wait(mutex);
agregar item sacar item
signal(mutex); signal(mutex);
signal(lleno); signal(vacio);Lectores y escritores
Pueden convivir varios lectores en el recurso, pero los escritores necesitan exclusión mutua (ni otros escritores ni lectores). mutex = 1, wrt = 1, cuentaLectores = 0. Riesgo de inanición de escritores.
Filósofos comensales
Cada filósofo es un proceso y los palillos son recursos que se toman de a uno. Si todos toman el izquierdo a la vez → deadlock. Soluciones: máximo 4 en la mesa, tomar ambos palillos solo si están libres, asimétrico (impares izquierdo primero, pares derecho).
Transacciones atómicas (6.9 a 6.9.3)
- Transacción: conjunto de instrucciones que realiza una única función lógica; se ejecuta todo o nada. Termina con commit (confirmada) o abort (abortada, y se hace rollback al estado anterior).
- Recuperación basada en registro (log): antes de modificar, se escribe en almacenamiento estable el registro (nombre de transacción, dato, valor viejo, valor nuevo): write-ahead logging. Tras un fallo:
undode las no confirmadas yredode las confirmadas. - Puntos de comprobación (checkpoints): se graban periódicamente para no recorrer todo el log al recuperar.
• Spinlock → "solución de espera activa que hacen los procesos cuando no pueden ingresar a SC". Se prefieren en SC cortas → "válido para multiprocesadores y que el recurso lo tenga un hilo en ejecución".
• Semáforo sin espera activa → "variable entera y una cola de espera".
• Semáforos con nombre vs sin nombre (POSIX) → "los con nombre se pueden usar entre procesos que no se conocen, los sin nombre no".
• Signal de semáforo vs de variable condición → "el de semáforo suma uno y puede liberar un proceso; el de variable condición puede liberar a un proceso".
• Protocolo para la SC → "solicitar acceso, usarla y anunciar su salida (liberarla)".
6.3 (solución de Peterson en detalle), Swap, 6.6 en detalle, 6.7.2, 6.7.3, 6.8 y 6.9.4 en adelante.
Unidad 7 · Abrazo mortal (interbloqueo, deadlock)
Silberschatz cap. 7, completo salvo: 7.4.2–7.4.4 en detalle, 7.5.3 solo los 2 primeros párrafos + video del banquero, y 7.6.1 / 7.6.2 (lectura liviana).
Conjunto de procesos bloqueados en espera circular, cada uno reteniendo recursos no compartibles y esperando uno que tiene otro del conjunto; ninguno puede avanzar. Uso de un recurso: solicitud (y espera si hace falta) → uso → liberación. Para recursos que no gestiona el SO, la solicitud y liberación se hacen con semáforos, mutex, etc.
Ejemplo de cátedra (lápiz y papel)
sem_init(lapiz, 1, 1); sem_init(papel, 1, 1);
/* hilo 1 */ /* hilo 2 */
sem_wait(&lapiz); sem_wait(&papel);
sem_wait(&papel); sem_wait(&lapiz); // orden inverso → posible AM
/* escribir */ /* escribir */
sem_post(&lapiz); sem_post(&lapiz);
sem_post(&papel); sem_post(&papel);Si el hilo 1 toma el lápiz y el 2 el papel, cada uno espera lo que tiene el otro. Se arregla pidiendo los recursos en el mismo orden (rompe la espera circular).
Las 4 condiciones necesarias (simultáneas)
| Condición | Significado | ¿Se puede negar para prevenir? |
|---|---|---|
| Exclusión mutua | Solo un proceso a la vez usa el recurso | No Hay recursos intrínsecamente no compartibles (impresora, mutex). Solo se evita para recursos compartibles (archivo de solo lectura). |
| Retención y espera (posesión y espera) | Un proceso que tiene al menos un recurso espera otros retenidos por otros | Sí Pedir todo antes de empezar, o pedir solo sin tener nada. Baja utilización de recursos e inanición posible. |
| Sin apropiación (no expropiación) | Un recurso solo se libera voluntariamente, cuando el proceso termina su tarea | Sí Si pide algo que no hay, se le quitan los que tiene. Solo sirve para recursos cuyo estado se puede guardar (CPU, memoria). |
| Espera circular | P0 espera a P1, P1 a P2, …, Pn a P0 | Sí La más práctica: numerar los tipos de recurso y pedirlos en orden creciente. |
Son necesarias pero no suficientes (con varias instancias pueden darse las 4 y no haber AM). Para que haya AM hace falta al menos 2 procesos y 2 recursos.
Grafo de asignación de recursos
- Vértices: procesos (círculos) y tipos de recurso (rectángulos con un punto por instancia). Grafo dirigido.
- Arista de solicitud P → R; arista de asignación R → P. En evitación, arista de declaración (reclamo) P ⇢ R en línea discontinua: indica que P podrá pedir R en el futuro.
- Sin ciclos → no hay AM. Con ciclo y una sola instancia por recurso → hay AM. Con ciclo y varias instancias → posibilidad de AM, no certeza.
Métodos para tratarlos (3 enfoques, uno se desdobla → 4)
| Enfoque | Idea | Costo |
|---|---|---|
| Prevención | Garantizar que una de las 4 condiciones nunca se cumpla | Impone al programador un modo de adquisición de recursos; baja utilización e inanición |
| Evitación (predicción) | Con información a priori (máximo que pedirá cada proceso), solo conceder pedidos que dejen al sistema en estado seguro | Hay que conocer las demandas futuras; los procesos pueden esperar mucho; cálculo en cada pedido |
| Detección y recuperación | Dejar que ocurra, detectarlo con un algoritmo y recuperarse | Costo del algoritmo y de la recuperación (procesos perdidos, rollback) |
| Ignorar (algoritmo del avestruz) | Hacer de cuenta que nunca ocurre | Si ocurre: el sistema se degrada y hay que reiniciar a mano. Es el más usado (UNIX, Linux, Windows) porque los AM son poco frecuentes y los otros métodos son caros. |
Ventaja de la evitación frente a prevención y detección: permite mayor concurrencia y no hay que hacer rollback.
Estado seguro
El sistema está en estado seguro si existe al menos una secuencia <P1, …, Pn> de todos los procesos tal que lo que cada Pi todavía puede pedir se puede satisfacer con lo disponible + lo que tienen los Pj anteriores (j < i). O sea, existe un orden en que todos terminan.
Seguro → no hay AM. Inseguro → posibilidad de AM (no todo estado inseguro es AM). Evitar = no entrar nunca en estado inseguro.
Algoritmos de evitación: con una sola instancia por recurso, el grafo con aristas de declaración (se concede si convertir la arista en asignación no forma ciclo). Con varias instancias, el algoritmo del banquero (el grafo no alcanza).
Algoritmo del banquero
Propósito: evitar el interbloqueo con recursos de múltiples instancias. Cada proceso declara su máximo; cuando pide, se simula la asignación y se corre el algoritmo de seguridad: los recursos se asignan solo si el estado resultante es seguro; si no, el proceso espera. Un proceso que recibe todo debe devolverlo en un tiempo finito.
| Estructura | Tamaño | Significado |
|---|---|---|
| Disponible | m | Instancias libres de cada tipo |
| Max | n × m | Lo máximo que puede pedir cada proceso |
| Asignación | n × m | Lo que tiene ahora |
| Necesidad | n × m | Necesidad = Max − Asignación |
Ejemplo del libro (A=10, B=5, C=7)
| Proc. | Asignación A B C | Max A B C | Necesidad A B C |
|---|---|---|---|
| P0 | 0 1 0 | 7 5 3 | 7 4 3 |
| P1 | 2 0 0 | 3 2 2 | 1 2 2 |
| P2 | 3 0 2 | 9 0 2 | 6 0 0 |
| P3 | 2 1 1 | 2 2 2 | 0 1 1 |
| P4 | 0 0 2 | 4 3 3 | 4 3 1 |
- Disponible = (3,3,2). Trabajo = 3,3,2 → P1 (1,2,2) entra → 5,3,2 → P3 → 7,4,3 → P4 → 7,4,5 → P2 → 10,4,7 → P0 → 10,5,7. Secuencia segura <P1, P3, P4, P2, P0>.
- P1 pide (1,0,2): ≤ Necesidad (1,2,2) y ≤ Disponible (3,3,2). Se simula: Disponible = (2,3,0), Asig. P1 = (3,0,2), Nec. P1 = (0,2,0). Secuencia segura <P1, P3, P4, P0, P2> → se concede.
- Luego P4 pide (3,3,0): supera lo Disponible (2,3,0) → no se concede, debe esperar.
- Luego P0 pide (0,2,0): hay recursos, pero quedaría Disponible = (2,1,0) y ningún proceso puede terminar con eso → estado inseguro → no se concede.
Detección
- Una instancia por recurso: grafo de espera (wait-for): solo procesos, Pi → Pj si Pi espera a Pj. Hay AM si hay ciclo. Buscar ciclos cuesta O(n²).
- Varias instancias: algoritmo parecido al banquero con Disponible, Asignación y Solicitud (lo que piden ahora). Los procesos que no se pueden "terminar" están en AM.
- ¿Cuándo invocarlo? Depende de la frecuencia de AM y de cuántos procesos afecta: en cada pedido (caro), cada cierto tiempo, o cuando el uso de CPU cae (p. ej. debajo del 40 %).
Recuperación
Manual (avisar al operador) o automática: terminar procesos o apropiarse de recursos. Ambas con consecuencias indeseadas, y los programas deben estar preparados (ejemplo de clase: copiar línea a línea uno.txt a dos.txt; si se mata a mitad queda un archivo a medias).
Terminación de procesos
Abortar todos los del AM (caro) o de a uno hasta romper el ciclo. Criterios: prioridad, cuánto ejecutó y cuánto le falta, recursos usados y necesarios, cuántos habrá que terminar, si es interactivo o por lotes.
Desventaja: hay que reiniciar los procesos y se pierde tiempo de CPU.
Apropiación de recursos
Seleccionar víctima (minimizar costo), rollback (volver a un estado seguro / punto de recuperación y reiniciar desde ahí) y evitar la inanición (no elegir siempre al mismo: contar los rollbacks en el costo).
Según el banco, la mejor técnica es volver a un punto de recuperación (rollback).
Preguntas guía resueltas
• Deadlock → "Una espera circular de procesos bloqueados con retención y espera de recursos no compartibles".
• ¿Cuál condición puede violarse? → "La espera circular, exigiendo un orden de asignación de recursos".
• Grafo con deadlock → "Cuando existe un ciclo cerrado y todos los recursos tienen una única instancia".
• Estado seguro → "existe al menos una secuencia de ejecución donde todos los procesos terminan".
• Banquero → "trata de evitar el interbloqueo".
• Desventaja de la evitación → "deben conocerse las demandas futuras y los procesos pueden bloquearse por largo tiempo".
Unidades 8 y 9 · Memoria principal y memoria virtual
Silberschatz caps. 8 y 9 (y 12.6 gestión del espacio de intercambio). Gestionar la RAM es clave porque la multiprogramación necesita varios procesos cargados a la vez.
8.1 Fundamentos
- La CPU solo accede directamente a registros y memoria principal. Registros: 1 ciclo; RAM: muchos ciclos (por eso hay caché en medio).
- Protección con registros base y límite: base = menor dirección física legal; límite = tamaño del rango. El HW compara cada dirección generada en modo usuario; si se sale → trap al SO (error de direccionamiento). Se cargan solo con instrucciones privilegiadas (modo kernel), así el usuario no puede cambiarlos. Están en la CPU; al cambiar de contexto, el despachador los guarda/restaura desde el PCB.
Reasignación (enlace) de direcciones
Direcciones simbólicas (variables del código fuente) → el compilador genera direcciones reubicables ("14 bytes desde el inicio del módulo") → el cargador/enlazador las convierte en absolutas (74014).
| Momento | Cómo | Ventaja | Desventaja |
|---|---|---|---|
| Compilación | Si se sabe dónde va a residir, se genera código absoluto | Velocidad de ejecución | Ubicación estática; si cambia, hay que recompilar |
| Carga | Se genera código reubicable; se fija al cargar | Flexibilidad: se carga donde haya lugar | Una vez cargado no se puede mover (las variables quedan fijas) |
| Ejecución | La traducción se difiere hasta cada acceso; necesita HW (MMU) | El proceso se puede mover durante la ejecución | Requiere hardware especial |
Dirección lógica (virtual): la genera la CPU. Dirección física: la que ve la unidad de memoria. Son iguales con enlace en compilación o carga; distintas con enlace en ejecución. La MMU es el dispositivo de HW que traduce en tiempo de ejecución (en el esquema más simple, suma el registro de reubicación = registro base). El programa de usuario nunca ve direcciones físicas. El espacio de direcciones de un proceso es el conjunto de direcciones lógicas que genera.
Carga dinámica
Las rutinas se cargan recién cuando se llaman (estando en disco en formato reubicable). Mejor uso de memoria. La implementa el programador (el SO puede dar bibliotecas). Útil cuando hay mucho código para casos poco frecuentes.
Montaje (enlace) dinámico
El enlace con las bibliotecas se pospone hasta la ejecución. En cada llamada se pone un stub: pequeño código que localiza la rutina residente en memoria (o la carga) y se reemplaza a sí mismo con su dirección. Bibliotecas compartidas entre procesos (DLL en Windows, .so en Linux). Facilita parches; requiere control de versiones. Necesita ayuda del SO.
8.3 Asignación contigua
- Memoria dividida en SO residente (memoria baja, con el vector de interrupciones) y procesos de usuario (memoria alta). Cada proceso ocupa una sección contigua. La cola de entrada la maneja el planificador de largo plazo.
- Particiones fijas: grado de MP limitado por la cantidad de particiones; generan fragmentación interna. Particiones variables: el SO lleva una lista de huecos; generan fragmentación externa.
- Asignación dinámica: primer ajuste (first-fit, el primer hueco que alcanza), mejor ajuste (best-fit, el más chico que alcanza; recorre toda la lista; deja huecos chiquitos), peor ajuste (worst-fit, el más grande). First y best son mejores que worst en velocidad y uso; first suele ser el más rápido.
Fragmentación externa
Hay espacio libre total suficiente pero no contiguo. Regla del 50 %: con first-fit, por cada N bloques asignados se pierden 0,5 N (1/3 de la memoria inutilizable). Solución: compactación (solo si la reubicación es dinámica, en ejecución) o permitir espacio no contiguo (paginación/segmentación).
Fragmentación interna
Memoria asignada a un proceso que no usa (la partición o el marco es más grande que lo pedido). No tiene solución, solo se reduce. En paginación: en promedio medio marco por proceso; peor caso 1 marco − 1 byte.
8.4 Paginación
La memoria física se divide en marcos (frames) de tamaño fijo (potencia de 2, de 512 B a 16 MB) y la lógica en páginas del mismo tamaño. El espacio físico de un proceso puede no ser contiguo. Evita la fragmentación externa (queda interna). Hay una tabla de páginas por proceso y una tabla de marcos única del SO (cuáles están libres y de quién son). La paginación es transparente para el programador.
Dirección lógica de m bits con páginas de 2n bytes: p = m − n bits altos (índice en la tabla de páginas), d = n bits bajos (desplazamiento). Física = marco(p) × tamaño + d.
| Ejemplo | Cálculo |
|---|---|
| Páginas de 4 KB, dirección lógica 20000, la página 4 está en el marco 7 | p = 20000 div 4096 = 4 ; d = 20000 mod 4096 = 3616 ; física = 7·4096 + 3616 = 32288 |
| Fragmentación interna: página 2048 B, proceso 72766 B | 35 páginas + 1086 B → 36 marcos ; se desperdician 2048 − 1086 = 962 B |
| 32 bits con páginas de 4 KB | 232/212 = 220 ≈ 1 millón de entradas × 4 B = 4 MB de tabla por proceso |
Soporte de hardware: TLB
La tabla de páginas está en memoria principal; el PTBR apunta a ella y el PTLR indica su tamaño. Así, cada acceso necesita dos accesos a memoria (tabla + dato). Se soluciona con la TLB: memoria asociativa (búsqueda por contenido en paralelo) que guarda las últimas traducciones página → marco. Pequeña (64–1024 entradas). En un fallo de TLB se busca en la tabla y se carga en la TLB. Algunas guardan ASID (identificador de proceso) para no vaciarla en cada cambio de contexto.
Con tasa de aciertos α y acceso a memoria de 100 ns: EAT = α·100 + (1−α)·200. Con α = 80 % → 120 ns; con α = 99 % → 101 ns. Si se suma la búsqueda en TLB (ε = 20 ns): EAT = α(100+ε) + (1−α)(200+ε) → 140 ns con 80 %. Alcance de la TLB = entradas × tamaño de página (ideal: que cubra el conjunto de trabajo).
Protección: bits de lectura/escritura/ejecución por marco y bit válido-inválido en cada entrada (válido = la página está en el espacio lógico del proceso). Una violación produce un trap. Páginas compartidas: código reentrante (de solo lectura) compartido entre procesos (editores, compiladores); cada uno con sus datos privados.
8.5 Estructura de la tabla de páginas
| Estructura | Idea | Ventaja / desventaja |
|---|---|---|
| Jerárquica (multinivel) | Se pagina la tabla de páginas. Ej. 32 bits, páginas de 1 KB: p1 (12 bits) | p2 (10) | d (10). Tabla "mapeada hacia adelante". | Solo se cargan las partes de la tabla que hacen falta. Con 64 bits, 2 o 3 niveles no alcanzan (x86-64 usa 4 niveles con direcciones de 48 bits); más accesos a memoria. |
| Con hash (no va 8.5.2, pero sale en el banco) | El número de página virtual se transforma con una función hash en un índice; cadena de elementos (pág. virtual, marco, siguiente). | Reduce el tamaño de la tabla, haciendo cálculos en el momento de la traducción. Útil para espacios mayores a 32 bits. |
| Invertida | Una entrada por marco físico (no por página lógica): <proceso, página>. Una sola para todo el sistema (es la tabla de marcos). | Ahorra memoria, pero buscar es más lento (se usa hash y TLB). Compartir memoria es difícil. |
8.6 Segmentación
Esquema que soporta la vista del usuario: el programa es una colección de segmentos de tamaño variable (programa principal, funciones, pila, tabla de símbolos, vectores, variables globales). Dirección lógica = <segmento, desplazamiento>. Tabla de segmentos por proceso con base y límite; STBR apunta a la tabla y STLR da la cantidad de segmentos (s válido si s < STLR). Protección y compartición a nivel de segmento (bit de validación, permisos r/w/x). Como los segmentos son de tamaño variable, hay fragmentación externa (asignación dinámica de almacenamiento).
| Paginación | Segmentación | |
|---|---|---|
| Tamaño de las porciones | Fijo (página = marco) | Variable (según la unidad lógica) |
| Optimiza | El espacio de la RAM | La estructura lógica del programa (módulos) |
| Fragmentación | Interna | Externa |
| Visible al programador | No | Sí |
Intel IA-32 combina ambas (segmentación paginada): la unidad de segmentación genera una dirección lineal y la de paginación la física. 8.7 no va.
9.1 Memoria virtual
Técnica implementada por el SO que permite ejecutar procesos sin que estén cargados completamente en memoria principal (código y datos). Es la evolución de la carga dinámica, pero transparente para el programador.
Ventajas: programas más grandes que la RAM disponible; más procesos en memoria (más MP, más uso de CPU y throughput); menos E/S para cargar e intercambiar; compartir memoria y archivos fácilmente; creación de procesos más rápida (COW). Desventajas: si se abusa, bajo rendimiento por fallos de página y thrashing; complejidad. Espacio de direcciones virtual: código, datos, heap (crece hacia arriba) y pila (crece hacia abajo), con un hueco en medio (espacio disperso).
9.2 Paginación bajo demanda
Se carga una página solo cuando se necesita (intercambiador perezoso o pager). El bit válido-inválido ahora también indica si la página está en memoria. Acceder a una página no cargada produce un fallo de página (page fault): una trap al SO. No es un error: es parte del funcionamiento normal (salvo que la referencia sea inválida).
- Se revisa una tabla interna (en el PCB) para ver si la referencia es válida.
- Si es inválida se termina el proceso; si es válida pero no está cargada, hay que traerla.
- Se busca un marco libre (de la lista de marcos libres).
- Se programa la lectura de la página desde disco (el proceso se bloquea y hay cambio de proceso).
- Al terminar la E/S se actualizan la tabla interna y la tabla de páginas.
- Se reinicia la instrucción interrumpida (no se empieza de nuevo el proceso, se continúa).
Paginación bajo demanda pura: arranca sin ninguna página cargada. Funciona bien gracias a la localidad de referencia. Algunas instrucciones necesitan varias páginas a la vez (código de operación y datos en páginas distintas).
9.2.2 Rendimiento (no se evalúan los cálculos, sí las conclusiones): EAT = (1 − p)·acceso_mem + p·tiempo_fallo. Con 200 ns de acceso y 8 ms de fallo, si 1 de cada 1000 accesos falla, la máquina se vuelve 40 veces más lenta. Conclusión: la tasa de fallos debe ser bajísima. Los 2 factores clave: tasa de fallos de página y tiempo de servicio del fallo (velocidad del área de intercambio: HDD >> SSD > NVMe). El espacio de intercambio es más rápido que el sistema de archivos.
9.3 Copia durante la escritura (COW)
Tras fork(), padre e hijo comparten las páginas, marcadas COW. Solo cuando alguno escribe se copia esa página. Resultado: fork() es mucho más rápido y se ahorra memoria (sobre todo si después viene exec()). vfork() ni siquiera usa COW.
9.4 Sustitución de páginas
Si hay un fallo y no hay marco libre (sobreasignación), se elige una página víctima: se escribe a disco solo si fue modificada (bit de modificación / dirty), se carga la nueva, se actualizan tablas y se reinicia. Dos problemas a resolver: el algoritmo de asignación de marcos y el algoritmo de sustitución.
| Algoritmo | Víctima | Comentario |
|---|---|---|
| FIFO | La que entró hace más tiempo | Simple y rápido, pero no tiene en cuenta la localidad. Sufre la anomalía de Belady. |
| Óptimo (OPT/MIN) | La que se va a usar dentro de más tiempo (futuro más lejano) | Menor tasa de fallos posible. Teórico: requiere conocer el futuro; se usa para comparar. |
| LRU | La usada hace más tiempo | Aproxima al óptimo mirando al pasado. Implementación con contadores (marca de tiempo) o pila; costosa, necesita HW. No sufre Belady (algoritmo de pila). |
| Segunda oportunidad / Reloj | FIFO con bit de referencia: si está en 1 se pone en 0 y se salta | Aproximación práctica a LRU (manecilla que gira). |
| LFU / MFU | Menos / más frecuentemente usada | Por conteo de referencias; poco usados. |
Con FIFO, aumentar la cantidad de marcos puede aumentar los fallos. Cadena 1,2,3,4,1,2,5,1,2,3,4,5: con 3 marcos 9 fallos, con 4 marcos 10 fallos.
Cadena del libro 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 con 3 marcos: FIFO 15, Óptimo 9, LRU 12 fallos. Buffers de páginas: mantener un pool de marcos libres y conservar en memoria las páginas elegidas como víctimas por si se vuelven a pedir. Bloquear marcos (kernel, buffers de E/S) impide que se expulsen a disco, lo que desestabilizaría el SO.
9.5 Asignación de marcos
- Mínimo de marcos por proceso: lo define la arquitectura (cuántas páginas puede tocar una sola instrucción). El máximo, la memoria disponible.
- Equitativa: m marcos / n procesos para todos igual. Proporcional: ai = (si/S)·m según el tamaño. También por prioridad.
- Global: la víctima puede ser de cualquier proceso (más throughput, más justa con los que no usan sus marcos; pero un proceso no controla su propia tasa de fallos). Local: solo de sus propios marcos.
9.6 Sobrepaginación (thrashing)
Un proceso pasa más tiempo paginando que ejecutando: tiene menos marcos que las páginas que usa activamente. Ciclo vicioso: mucha MP → muchos fallos → baja el uso de CPU → el planificador de largo plazo agrega procesos → más fallos. Condición: el conjunto de trabajo es mayor que el conjunto residente.
Conjunto de trabajo (9.6.2)
Páginas referenciadas en la ventana de las últimas Δ referencias (aproxima la localidad actual). Si D = Σ WSSi supera los marcos disponibles → thrashing → se suspende un proceso. Si Δ es chico no cubre la localidad; si es enorme abarca varias. Un proceso tiene un conjunto de trabajo que cambia en el tiempo (a cada fase, su localidad).
Conjunto residente
Las páginas del proceso que están cargadas en memoria en un momento dado.
Frecuencia de fallos de página (9.6.3, no va): si la tasa sube, se le dan marcos; si baja mucho, se le quitan.
9.9.2 Tamaño de página
| Páginas grandes | Páginas chicas |
|---|---|
| Tablas de páginas más chicas · menos fallos · E/S más eficiente (el tiempo de búsqueda y latencia del disco se amortiza) | Menos fragmentación interna · mejor resolución: se carga solo lo que se usa (mejor localidad) |
| Más fragmentación interna · se pierde localidad (se trae memoria que no se usa) | Tablas de páginas enormes · más fallos · más overhead de E/S |
La tendencia es a páginas más grandes. En Linux la página típica es de 4096 bytes (también huge pages de 2 MB). El SO no elige libremente: depende de lo que ofrece la CPU.
Gestión del espacio de intercambio (12.6): el swap puede ser una partición dedicada (más rápida) o un archivo dentro del sistema de archivos (más flexible). Swapping = traspaso total de la imagen de un proceso entre disco y memoria (8.2, no va; hoy se paginan partes).
• Memoria virtual → "técnica que permite la ejecución de procesos aunque no estén cargados totalmente en memoria principal". Ventaja → "ejecutar programas más grandes que la Mp asignada y da protección".
• TLB → "registros de memoria asociativa que guardan las últimas traducciones de direcciones lógicas a físicas".
• Cuántas tablas de páginas → "una por proceso". Marcos libres → "con una tabla de marcos de páginas o tabla invertida" (una por SO).
• Tabla de marcos vs tabla de páginas → "las tablas de páginas ven el aspecto lógico, la de marcos el físico".
• Thrashing → "conjunto de trabajo mayor que el conjunto residente".
• Tamaño de página adecuado → "si es grande pierde localidad; si es chica las tablas son muy grandes".
8.2 (intercambio de procesos completos), último párrafo de 8.3.1, 8.5.2 (hash, en detalle), 8.7 (Pentium). De 9.4 solo hasta "Debemos resolver dos problemas principales" + características de FIFO, óptimo, LRU y Belady. De 9.5.1 solo 3 párrafos. 9.6.3 y de 9.7 en adelante (salvo 9.9.2 y el resumen 9.11).
Práctica · TPs de laboratorio y Linux
Respuestas cortas a las consignas de cada TP. No se pudo bajar el código de los programas del servidor de la cátedra, así que las respuestas que dependen del código son generales.
Comandos que hay que saber
| Comando | Para qué |
|---|---|
ps a / u / x / aux | Foto instantánea de procesos (a: de todos los usuarios con terminal; u: formato orientado a usuario, con %CPU, %MEM, STAT; x: incluye los que no tienen terminal). Info sacada del PCB (vía /proc). |
ps -eLf / ps -L | Muestra los hilos (columnas LWP y NLWP). Si un PID tiene varios LWP, el kernel soporta hilos. |
top / htop | Uso de CPU y memoria en tiempo real (ps es una foto). Columnas: PID, USER, PR/NI (prioridad), VIRT/RES (memoria), S (estado), %CPU, %MEM, TIME+. En Windows: Administrador de tareas / Process Explorer. |
kill -SEÑAL pid, killall nombre, pkill | Enviar señales. killall sleep termina todos los sleep y nada más. |
sleep 1000 | Lanza un proceso que espera 1000 segundos y termina. |
comando &, jobs -l, fg, bg | Lanzar en segundo plano, listar trabajos, pasar a primer / segundo plano (sin parámetro actúan sobre el marcado con +). |
| Ctrl-c / Ctrl-z | SIGINT (interrumpe) / detiene el proceso en primer plano (el TP dice SIGSTOP; técnicamente es SIGTSTP). |
time ./a.out | real: tiempo cronológico; user: CPU en modo usuario; sys: CPU en modo kernel. |
chrt | Ver / cambiar la política de planificación y prioridad de un proceso (requiere root). -f FIFO, -r RR, -b BATCH, -i IDLE, -o OTHER, -p sobre un PID. |
man 2 signal, man 7 signal | Sección 2 = llamadas al sistema; 7 = conceptos. Para saber más de un comando: man ps, ps --help, info. |
free | Uso de memoria del sistema (RAM y swap). |
Señales
| Señal | Efecto |
|---|---|
| SIGSTOP / SIGTSTP | Detiene el proceso (estado T). SIGSTOP no se puede atrapar. |
| SIGCONT | Lo reanuda si está suspendido (queda en segundo plano). |
| SIGTERM (15) | Pedido de terminación; el proceso puede atraparla o ignorarla (obediencia opcional). Si el proceso está detenido, recién actúa cuando se lo reanuda con SIGCONT. |
| SIGKILL (9) | Mata sí o sí: no se puede atrapar ni ignorar (funciona aunque esté detenido). |
| SIGINT (2) | Ctrl-c, interrupción desde teclado. |
| SIGSEGV | Violación de segmento (acceso inválido a memoria). |
Estados en ps (STAT): R ejecutando o listo · S durmiendo interrumpible (esperando un evento, p. ej. sem_wait o sleep) · D durmiendo no interrumpible (E/S de disco) · T detenido · t detenido por depurador · Z zombie (terminó y el padre no hizo wait) · X muerto · I hilo del kernel inactivo. En el grafo de la teoría: R = listo/ejecución, S y D = bloqueado/espera, T = suspendido, Z = terminado.
TP Hilos
ps -eLf, ps -L, top -H o htop: si un mismo PID aparece con varios LWP/TID distintos planificados por el kernel (y en /proc/PID/task hay varias entradas), el SO los reconoce.TP Administración de procesos
fork() (y exec() para cambiar de programa). Windows: CreateProcess().kill -SIGCONT pid vuelve a S (sigue en segundo plano). SIGSTOP → T. SIGTERM con el proceso detenido: no termina hasta que se lo reanuda; al reanudarlo, sleep termina (obedece). SIGKILL lo mata inmediatamente.killall sleep o pkill sleep (o kill %1 %2 %3 con los números de jobs).ulimit -s). Con vector[100] cada marco es más grande → menos llamadas; con vector[1] más llamadas (si el compilador no elimina el vector sin uso).signal(SIGxxx, funcion) registra una función manejadora que se ejecuta al recibir esa señal. Con sleep(100) en el lazo el proceso casi no usa CPU (está en S); con sleep(0.1) se despierta mucho más seguido y sube el consumo. El manejo de señales es análogo a la rutina de servicio de interrupción (vector de interrupciones del SO).TP Planificación
TP Concurrencia (memoria compartida + fork)
sizeof(int)).int *) que recibe lo que devuelve shmat(). Se usa un puntero porque no sabemos de antemano qué ubicación tendrá.wait() (o waitpid()). El padre espera para poder mostrar el valor final del contador.shmctl(..., IPC_RMID), shmdt). Si se comenta, el segmento sigue existiendo y la próxima ejecución arranca con el valor viejo (se acumula).TP Semáforos y abrazo mortal
sizeof(sem_t): 32 bytes en Linux de 64 bits (16 en 32 bits).sem_init(sem, pshared, valor) inicializa (pshared ≠ 0 → entre procesos, y el semáforo debe estar en memoria compartida); sem_wait decrementa o bloquea; sem_post incrementa y despierta; sem_destroy lo destruye. Con nombre: sem_open, sem_close, sem_unlink. Compilar con -pthread.sem_trywait: como sem_wait pero si no puede decrementar no se bloquea, devuelve error EAGAIN. sem_timedwait: se bloquea como máximo hasta un tiempo límite y luego devuelve ETIMEDOUT.sleep dentro de la SC y mirando con ps: los que esperan aparecen en S (durmiendo / bloqueados, sin consumir CPU).sem_wait antes y sem_post después el resultado es correcto, pero tarda más (se serializa y hay overhead). Si se olvida un sem_post, los demás quedan bloqueados para siempre. Se pueden poner semáforos alrededor de cada acceso (más concurrencia, más overhead) o de todo el lazo (menos overhead, menos concurrencia): cambian los tiempos.sleep entre los dos wait para que el AM ocurra casi siempre.// esqueleto: semáforo POSIX compartido entre padre e hijos
sem_t *sem = mmap(NULL, sizeof(sem_t), PROT_READ|PROT_WRITE,
MAP_SHARED|MAP_ANONYMOUS, -1, 0); // o shmget + shmat
sem_init(sem, 1, 1); // pshared = 1 (entre procesos), valor 1
if (fork() == 0) { // hijo
sem_wait(sem); (*contador)++; sem_post(sem);
exit(0);
}
wait(NULL); // el padre espera al hijo
sem_destroy(sem);TP Memoria virtual (teórico)
Simuladores para practicar cálculos
Cargá tus propios ejercicios o probá con los del libro. Hacelo primero a mano y después verificá acá.
Planificación de CPU: diagrama de Gantt
Reemplazo de páginas
Algoritmo del banquero
Parciales reales resueltos
Las fotos del recuperatorio 2022 y del tercer parcial 2023 (tema 1, V2) y las revisiones de Moodle de 2020. En 2020 la respuesta correcta es la oficial; en las fotos no hay corrección, así que las respuestas son razonadas con el libro y el banco de preguntas.
Varias opciones resaltadas o encerradas en las fotos no coinciden con las respuestas oficiales del banco: en 2022 las preguntas 8 (gestión de módulos → segmentación, no paginación), 11 (evitación → "no es necesario rollback y permite más concurrencia"), 15 (espera ocupada → sí, si la espera es más corta que usar otras herramientas), 17 (hashing → reduce el tamaño de la tabla, no "agiliza"), 19 (hashing → función que convierte el número de página en uno más chico) y 20 (conjunto de trabajo → ventana de tiempo); en 2023 la 8 (cola de listos, no el PCB) y la 18 (determinar qué proceso usa cada CPU).
El formato 2023 cambia: preguntas más conceptuales y cortas (condiciones de carrera, quién las evita, recurso de uso exclusivo, enfoques del abrazo mortal), así que no alcanza con memorizar las frases del banco.
Banco de preguntas
Preguntas de los PDFs del parcial (con la redacción de cátedra como respuesta correcta) más preguntas del libro. Tocá una opción: te dice si acertaste, por qué tu opción está mal y cuál es la correcta. Las opciones se mezclan cada vez.
Simulacro de parcial
Preguntas al azar de las unidades que elijas, una por pantalla. Elegí una opción y tocá Comprobar: te dice si acertaste, por qué tu opción está mal y cuál es la correcta. Al final ves el resultado total.