Sistemas operativos

Introducción, conceptos y llamadas al sistema

Piensa en un restaurante. Tú (el programa del usuario) te sientas a una mesa. La cocina (el hardware) es peligrosa: cuchillos, fuego, aceite caliente. Nunca entras. Le dices al mesero lo que quieres, y el mesero habla con la cocina. El sistema operativo es el mesero y el gerente al mismo tiempo.

Hay dos maneras de mirar el sistema operativo, y las dos son verdaderas:

• Máquina extendida (mirando de arriba hacia abajo): el hardware real es incómodo. Un disco solo sabe 'leer el sector 4.821'. El SO esconde eso y te da ideas agradables como archivos y procesos. Hace que la computadora sea más fácil de usar.
• Administrador de recursos (mirando de abajo hacia arriba): la CPU, la memoria y los dispositivos los comparten muchos programas. El SO los reparte de forma justa y segura, en el tiempo (por turnos) y en el espacio (cada programa recibe su parte).

Modo kernel y modo usuario

El kernel debe protegerse de los errores de los programas comunes. Por eso la CPU tiene al menos dos modos, como una puerta con un guardia.

Las instrucciones peligrosas son las privilegiadas: apagar las interrupciones, hacer entrada y salida directamente en un dispositivo y cambiar las tablas de páginas (los mapas que deciden qué memoria ve un programa). Solo el kernel puede hacerlo. Las cuentas comunes, como sumar dos números, se permiten en cualquier modo.

Llamadas al sistema: pedirle un servicio al kernel

Un programa que quiere leer un archivo no puede tocar el disco. Hace una llamada al sistema (system call), que es una petición educada al kernel. Una instrucción especial (la trap) cambia la CPU a modo kernel y salta a un lugar fijo del SO. El SO hace el trabajo y luego vuelve al modo usuario.

programa:   read(fd, buf, n)           <- llamada normal
      |
biblioteca: pone el número de llamada en un registro
           TRAP  ------------------------+   <- el modo cambia AQUÍ
                                         v
kernel:    usa el número como índice en una tabla de rutinas
           hace el trabajo (lee el archivo)
           vuelve al modo usuario  ------+
      ^                                  |
el programa continúa  <------------------+

Fíjate en que llamar a read es solo una llamada de función normal a una biblioteca. El modo solo cambia en la instrucción trap dentro de esa función de la biblioteca.

fork, exec y el shell

En UNIX, crear un proceso nuevo y cargar un programa nuevo son dos pasos separados. fork hace una copia del proceso que lo llama. La copia continúa en el mismo punto, justo después del fork. fork devuelve 0 en el hijo y el número del hijo (su PID) en el padre, así cada uno sabe quién es. exec reemplaza el programa que el proceso está ejecutando por otro programa.

fork();
fork();
printf("hi\n");
/* 1 proceso -> 2 -> 4 procesos: 2^n después de n forks,
   así que esto imprime "hi" 4 veces */

Como los dos pasos están separados, el hijo puede cambiar cosas entre ellos, por ejemplo redirigir su entrada y su salida. Así es exactamente como un shell hace ls > archivo.txt y los pipes. Cada proceso también tiene su propio directorio actual, heredado del padre. Por eso los comandos que deben cambiar el propio shell, como cd y exit, están incorporados (builtins) en el shell: si cd se ejecutara en un hijo, solo el hijo cambiaría de carpeta.

Cómo se organiza el kernel

Un poco de historia

En los primeros sistemas por lotes (batch), la costosa CPU se quedaba inactiva cada vez que un trabajo esperaba una entrada o salida lenta. La multiprogramación lo arregló: la memoria se divide en partes, varios trabajos quedan cargados y, cuando uno se bloquea, la CPU pasa a otro. El tiempo compartido (timesharing) añadió cambios muy rápidos para que muchos usuarios trabajaran de forma interactiva al mismo tiempo.

Procesos y threads

Una receta de pastel está escrita en papel. Sola no hace nada. Cuando alguien realmente prepara el pastel, siguiendo la receta, midiendo y mezclando, esa actividad es lo importante. Un programa es la receta, una lista de instrucciones guardada. Un proceso es el acto de preparar el pastel: un programa en ejecución, con su paso actual (el contador de programa), sus variables y sus archivos abiertos. Ejecuta el mismo programa dos veces y tendrás dos procesos distintos, como dos cocineros preparando pasteles con la misma receta.

Los tres estados

En cada momento un proceso está en uno de tres estados:

• En ejecución (running): está usando la CPU ahora mismo.
• Listo (ready): podría ejecutarse, pero la CPU está ocupada con otro proceso. Espera su turno.
• Bloqueado (blocked): no puede ejecutarse hasta que ocurra algo externo, como pulsar una tecla o que un disco termine.

              1: espera un evento
   +-----------+ -----------------> +-----------+
   | EJECUCIÓN |                    | BLOQUEADO |
   +-----------+ <-+                +-----------+
     | ^           |                      |
 2:  | | 3:        |                      | 4: el evento
tiempo| | el planificador                 | ocurrió
se   | | lo elige                         |
acaba| |                                  |
     v |                                  |
   +---------+ <------------------------+
   |  LISTO  |
   +---------+

Listo y bloqueado se diferencian en el motivo por el que el proceso no se está ejecutando. Un proceso listo solo espera al planificador. Un proceso bloqueado espera un evento, así que darle la CPU sería inútil. La causa habitual de ejecución a listo es la interrupción del reloj que termina el turno del proceso.

Cómo empieza y termina un proceso

Un proceso termina de cuatro maneras. Dos son voluntarias: la salida normal y la salida por error que el propio programa detecta (por ejemplo 'archivo no encontrado'). Dos son involuntarias: un error fatal causado por un fallo (como dividir entre cero) y ser eliminado (killed) por otro proceso.

Cuando un proceso termina, el kernel libera sus recursos pero guarda su código de salida, para que el padre pueda leerlo con wait. Hasta que el padre lo haga, el hijo es un zombi: terminó, pero sigue ocupando una fila en la tabla de procesos. Un padre que nunca llama a wait acumula zombis.

Después de fork, el hijo tiene una copia de la memoria del padre. Desde entonces son independientes: si el hijo cambia una variable, el padre no lo ve. Para compartir datos hace falta algo explícito, como un pipe, un archivo o memoria compartida. Copiarlo todo sería lento, así que los sistemas modernos usan copy-on-write (copia al escribir): padre e hijo comparten las mismas páginas (marcadas como de solo lectura), y una página se copia solo cuando uno de los dos escribe en ella.

int x = 5;
pid_t pid = fork();
if (pid == 0) { x = 10; exit(0); }   /* el hijo cambia SU copia */
waitpid(pid, NULL, 0);
printf("%d\n", x);                    /* el padre sigue viendo 5 */

Threads

Un proceso es como una casa: es dueño de las habitaciones (espacio de direcciones), los muebles (variables globales) y las llaves (archivos abiertos). Un thread es una persona que vive en la casa haciendo su propia tarea. Varios threads comparten la casa, pero cada uno tiene su propio cuaderno de lo que está haciendo.

Cambiar entre dos threads del mismo proceso es más barato que cambiar entre dos procesos, porque el mapa de memoria sigue igual y la TLB y los cachés siguen siendo útiles. Los threads también son una buena forma de escribir programas que hacen varias cosas a la vez, por ejemplo un servidor web donde cada petición tiene su thread y puede esperar al disco mientras los demás siguen trabajando.

Threads de usuario, threads de kernel

Las scheduler activations intentan obtener lo mejor de ambos: el kernel da al proceso procesadores virtuales y hace un upcall a la biblioteca de usuario cuando ocurre algo importante (un thread se bloquea, termina una entrada o salida). La decisión de qué thread se ejecuta se queda en el espacio de usuario.

Tres formas de construir un servidor y una trampa del código antiguo

• Threads: paralelismo con llamadas bloqueantes simples.
• Un único flujo, bloqueante: simple pero sin paralelismo.
• Máquina de estados finitos con llamadas no bloqueantes y un bucle de eventos: paralelo, pero el programador debe simular a mano los threads y sus pilas, lo cual es difícil.

Comunicación entre procesos y sincronización

Imagina a dos niños escribiendo a la vez en la misma página de un cuaderno compartido. Si los dos escriben 'el marcador es' y luego cada uno añade un número, la página se vuelve un desastre. Cuando los programas comparten datos y al menos uno escribe, el resultado puede depender del momento exacto. Eso es una condición de carrera (race condition). Es molesta porque ocurre pocas veces y es casi imposible de repetir cuando se quiere.

La actualización perdida

La línea count = count + 1 parece un solo paso, pero son tres: cargar el valor en un registro, sumar uno, guardarlo de vuelta. Si ocurre un cambio entre cargar y guardar, una actualización puede desaparecer.

count = 0
Thread A            Thread B
load  (0)
                    load  (0)
add   (1)
                    add   (1)
store (1)
                    store (1)   <- count final = 1, ¡no 2!

Regiones críticas y las cuatro condiciones

La parte del código que toca datos compartidos es la región crítica. La cura es la exclusión mutua: solo un proceso dentro a la vez, como una llave para un baño. Una buena solución necesita cuatro cosas:

1. Nunca dos procesos dentro de la región crítica a la vez.
2. Ninguna suposición sobre la velocidad ni el número de CPU.
3. Un proceso fuera de su región crítica no puede bloquear a otro.
4. Nadie espera para siempre.

Observa que una promesa sobre el orden de entrada no está en la lista.

Soluciones con espera activa

• Alternancia estricta: una variable turn dice de quién es el turno. Garantiza la exclusión mutua, pero rompe la condición 3: un proceso rápido debe esperar a uno lento aunque el lento esté lejos de la región crítica. También gasta CPU dando vueltas en un bucle (espera activa).
• La solución de Peterson lo arregla añadiendo una bandera 'tengo interés' por proceso.
• Una simple variable de cerradura falla por el hueco entre probar la cerradura y marcarla: dos procesos pueden verla libre. Las instrucciones de hardware TSL (test and set lock) y XCHG hacen las dos acciones como un solo paso atómico, así el hueco desaparece. Una cerradura hecha así y esperada en un bucle es un spin lock.

Semáforos

Un semáforo es un contador con dos acciones atómicas. down (también llamada P o wait): si el contador es mayor que cero, resta uno y continúa; si es cero, se duerme. up (V o signal): si alguien duerme, despierta a uno; si no, suma uno. Como comprobar, cambiar y dormir son una acción indivisible, un despertar nunca se pierde.

Un semáforo que empieza en 1 funciona como mutex (una cerradura). Un semáforo que empieza en N deja pasar a N procesos, lo que controla un conjunto de N recursos idénticos. Si empieza en 3 y cinco procesos hacen down, tres pasan y dos duermen. Un up despierta a uno de los dos.

Productor y consumidor

Un productor pone elementos en un búfer de N espacios; un consumidor los saca. Tres semáforos lo resuelven: mutex (empieza en 1, protege el búfer), empty (empieza en N, cuenta los espacios libres) y full (empieza en 0, cuenta los espacios llenos).

productor:              consumidor:
  down(&empty);           down(&full);
  down(&mutex);           down(&mutex);
  put(item);              item = take();
  up(&mutex);             up(&mutex);
  up(&full);              up(&empty);

Monitores y variables de condición

Un monitor es un grupo de datos y procedimientos en el que el lenguaje garantiza que solo hay un proceso dentro a la vez. Para esperar una condición, un proceso hace wait sobre una variable de condición, lo que lo bloquea y deja entrar a otros. Un signal despierta a quien espera. Diferencia con el semáforo: un signal no se recuerda. Si nadie espera, se pierde. Por eso quien espera debe probar la condición (guardada en variables comunes) dentro del monitor, y el wait debe venir antes del signal.

Lectores y escritores

Muchos lectores pueden leer los mismos datos a la vez, pero un escritor necesita los datos para él solo. Si siempre se deja entrar a los lectores mientras otros leen, un escritor puede esperar para siempre (starvation, inanición). La alternativa justa hace que los lectores nuevos esperen detrás de un escritor que espera, con un poco menos de concurrencia.

Paso de mensajes

Los procesos también pueden hablar con send y receive, sin memoria compartida. Con buzones (mailboxes), los mensajes esperan en un búfer hasta que se leen. Sin ningún búfer (rendezvous, usado por MINIX 3), quien llega primero se bloquea hasta que el otro esté listo, y el mensaje se copia directamente. Es simple, pero ata el ritmo de los dos lados.

Planificación

Muchos procesos están listos, pero hay una sola CPU (o pocas). ¿A quién le toca? La parte del SO que decide es el planificador (scheduler), como un maestro que elige quién puede usar la única computadora del salón. Cada lugar quiere cosas distintas.

Los planificadores expropiativos (preemptive) pueden quitarle la CPU a un proceso usando la interrupción del reloj, para que nadie la acapare. Esto es vital en sistemas interactivos. Los planificadores no expropiativos dejan que un proceso se ejecute hasta que se bloquea o termina. Son más simples y tienen menos cambios de contexto, lo que va bien para el trabajo por lotes.

Palabras que hay que conocer

• Tiempo de retorno (turnaround): desde que llega un trabajo hasta que termina.
• Tiempo de espera: tiempo en la cola de listos, sin ejecutarse.
• Tiempo de respuesta: desde una petición hasta la primera respuesta.
• Quantum: la rebanada de tiempo que se da a un proceso en round-robin.

Primero en llegar, primero en ser atendido (FCFS)

Los trabajos se ejecutan hasta el final en orden de llegada, como una fila en la cafetería. El tiempo de espera de un trabajo es la suma de los tiempos de ejecución de los trabajos que están delante. Si un trabajo largo va primero, todos los cortos esperan detrás: el efecto convoy.

El trabajo más corto primero (SJF)

Si todos los trabajos están presentes desde el principio, ejecutar primero el más corto da el mejor tiempo promedio posible de retorno y de espera, porque el tiempo del primer trabajo se cuenta en todos los demás. El problema: hay que conocer o estimar los tiempos de ejecución.

Los trabajos llegan juntos con tiempos de CPU  A=6   B=3   C=3

FCFS  |AAAAAA|BBB|CCC|   esperas: A0 B6 C9 -> promedio 5
SJF   |BBB|CCC|AAAAAA|   esperas: B0 C3 A6 -> promedio 3

El menor tiempo restante primero (SRTN) es el SJF con expropiación: cuando llega un trabajo nuevo, compara su tiempo total con el tiempo restante del trabajo en ejecución. Si el recién llegado es más corto, toma la CPU. Favorece aún más a los trabajos cortos, pero puede retrasar mucho a los largos.

Round-robin

Cada proceso recibe un quantum y luego va al final de la cola. Un proceso que necesita menos de un quantum devuelve la CPU cuando termina. Para saber cuándo termina algo, simula la cola paso a paso.

X necesita 4, Y necesita 3, quantum = 2

tiempo: 0   2   4   6   7
        |XX |YY |XX |Y  |
                  X termina en 6, Y termina en 7

• Quantum demasiado pequeño: muy buena respuesta, pero la CPU pierde tiempo en cambios de contexto.
• Quantum demasiado grande (mayor que el tiempo que los procesos usan antes de bloquearse): el round-robin se vuelve casi FCFS y las peticiones cortas esperan.
• Un quantum de unos 20 a 50 ms es un compromiso habitual.

Prioridades e inanición

Cada proceso recibe una prioridad, y se ejecuta el listo de mayor prioridad. Pero si el trabajo de alta prioridad nunca se detiene, los de baja prioridad pueden sufrir inanición (starvation). La cura es cambiar las prioridades con el tiempo: bajar la prioridad de quien ha usado mucha CPU o subir la de quien ha esperado mucho (aging, envejecimiento).

Colas multinivel con retroalimentación

El sistema no sabe qué procesos son interactivos y cuáles devoran CPU. Así que deja que se revelen. Hay clases; la clase superior tiene un quantum de 1, la siguiente 2, luego 4, y así sucesivamente. Un proceso que usa todo su quantum baja una clase. Uno que se bloquea pronto se queda arriba y se atiende rápido. Los procesos pesados en CPU se hunden y se ejecutan menos veces pero por más tiempo. Un proceso que necesita mucha CPU se cambia solo unas log2 de esa cantidad de veces.

Tiempo real

Un sistema de tiempo real atiende eventos periódicos. Si un evento cuesta C milisegundos de CPU cada P milisegundos, usa la fracción C/P de la CPU. El conjunto solo se puede planificar si la suma de C/P es como máximo 1 (suponiendo que el cambio de contexto es gratis). Algoritmos como el EDF (earliest deadline first, plazo más cercano primero) pueden planificar cualquier conjunto que cumpla esto. Ejemplo: 20 ms cada 100 ms (0,2) y 100 ms cada 400 ms (0,25) dan 0,45, que cabe.

Gestión de memoria: paginación, TLB, reemplazo de páginas, segmentación

La memoria es donde viven los programas en ejecución. Dos grandes problemas: los programas no deben leer la memoria de los demás, y un programa no debería necesitar caber entero en la memoria real. La solución es la memoria virtual: cada proceso ve sus propias direcciones privadas (direcciones virtuales), y el hardware las traduce a direcciones reales (direcciones físicas).

Paginación

La memoria virtual se corta en trozos iguales llamados páginas; la memoria real se corta en trozos del mismo tamaño llamados marcos de página (page frames), como un estante con cajas todas del mismo tamaño. Una tabla de páginas dice qué marco guarda cada página. Una dirección virtual tiene dos partes: el número de página (bits altos) y el desplazamiento (offset, bits bajos, el lugar dentro de la página). La traducción cambia el número de página por el número de marco y copia el desplazamiento sin cambios.

Con páginas de 4096 bytes, el desplazamiento tiene 12 bits (2 elevado a 12 es 4096). Ejemplo: dirección virtual 8200. Dividiendo, página = 2 (2 x 4096 = 8192) y desplazamiento = 8. Si la página 2 está en el marco 7, la dirección física es 7 x 4096 + 8 = 28680.

dirección virtual 8200
+--------------------+----------------+
| número de página=2 | desplazamiento 8 |
+--------------------+----------------+
         |                |
 tabla de páginas: 2 -> 7 |
         v                v
+--------------------+----------------+
| número de marco=7  | desplazamiento 8 |  = 7*4096 + 8 = 28680
+--------------------+----------------+

¿Qué tan grande es la tabla de páginas?

Número de páginas virtuales = tamaño del espacio de direcciones dividido entre el tamaño de página. En bits: bits de la dirección menos bits del desplazamiento. Con direcciones de 32 bits y páginas de 4 KB, 32 - 12 = 20, así que 2^20 = 1.048.576 páginas. Una tabla de un nivel necesita una entrada por página virtual, se use o no, lo que da cerca de un millón de entradas por proceso (4 MB con 4 bytes cada una). Con direcciones de 64 bits se vuelve imposible.

Una tabla multinivel lo arregla. La tabla de primer nivel apunta a tablas de segundo nivel, y las entradas de las regiones no usadas simplemente se marcan como ausentes. Con 10 + 10 + 12 bits: descarta los 12 bits del desplazamiento; luego los 10 bits de arriba indexan la primera tabla y los 10 bits siguientes indexan la segunda. Para la dirección 0x00C02010: los 10 bits de arriba dan 3 (PT1 = 3), los 10 siguientes dan 2 (PT2 = 2) y el desplazamiento es 0x010 = 16. Cambiamos un poco de tiempo de traducción por un gran ahorro de memoria. Una tabla de páginas invertida va al revés: una entrada por marco físico, así que crece con la memoria real. El precio es que la búsqueda ya no es un índice directo, por lo que se usa un hash de la dirección virtual y la TLB hace la mayor parte del trabajo.

Fallos de página y la entrada de la tabla de páginas

Solo algunas páginas están en la memoria real. El bit presente/ausente de cada entrada dice si la página está cargada. Tocar una página ausente causa una trap llamada fallo de página (page fault). El SO elige un marco, carga la página desde el disco, actualiza la tabla y reinicia la instrucción. Otros bits ayudan: el bit R (referenciada: se activa cuando la página se lee o se escribe) y el bit M (modificada o sucia, dirty: se activa en la primera escritura). Una página sucia debe escribirse en el disco antes de reutilizar el marco, mientras que una página limpia puede simplemente descartarse, por eso los algoritmos prefieren víctimas limpias.

La TLB

Leer la tabla de páginas en memoria haría que cada acceso fuera el doble de lento. Pero los programas usan pocas páginas a la vez, así que un pequeño caché rápido de traducciones, la TLB (translation lookaside buffer), responde la mayoría de las preguntas. En un acierto de TLB (hit) la respuesta está ahí. En un fallo (miss) se lee la tabla de páginas y la entrada se carga en la TLB. El tiempo efectivo es un promedio ponderado: la consulta a la TLB siempre ocurre, y un fallo añade un acceso a memoria por nivel de tabla.

Ejemplo: acceso a memoria 100 ns, consulta a la TLB 10 ns, tasa de aciertos 90%, tabla de un nivel. Tiempo efectivo = 10 + 100 + 0,10 x 100 = 120 ns. Cuanto mayor la tasa de aciertos, más cerca de 110 ns (consulta más un acceso).

Reemplazo de páginas

Cuando la memoria está llena y se necesita una página nueva, alguna página debe salir. ¿Cuál?

Ejemplo con 3 marcos y referencias 1, 2, 3, 1, 4, 1. FIFO: las páginas 1, 2, 3 se cargan (3 fallos); el acierto en 1 no cambia nada; el 4 expulsa la página 1 (la más antigua) aunque acaba de usarse; luego el 1 vuelve a fallar. Total 5 fallos. LRU: el 4 expulsa la página 2 (sin uso desde hace más tiempo) y el último 1 es un acierto. Total 4 fallos.

En el algoritmo del reloj (clock) los marcos están en un círculo con una manecilla. En un fallo, si la página bajo la manecilla tiene R = 0, se reemplaza. Si R = 1, el bit se pone en 0 y la manecilla avanza. Una página solo sobrevive a una vuelta completa si se usa de nuevo mientras tanto.

Anomalía de Belady y thrashing

Esperarías que más marcos significaran menos fallos. Eso es cierto para los algoritmos de pila (LRU, óptimo): las páginas retenidas con n marcos siempre están dentro de las retenidas con n+1. El FIFO no es uno de ellos. En la cadena clásica 1,2,3,4,1,2,5,1,2,3,4,5 el FIFO da 9 fallos con 3 marcos y 10 con 4. Esta sorpresa es la anomalía de Belady.

El conjunto de trabajo (working set) de un proceso es el conjunto de páginas que usa en una ventana de tiempo reciente. Si la memoria no puede contener los conjuntos de trabajo de todos los procesos activos, se roban páginas unos a otros y la máquina pasa el tiempo intercambiando páginas en lugar de trabajar. Esto es thrashing. Señales típicas: poco uso de la CPU, un disco de paginación casi siempre ocupado, muchos procesos en memoria. Meter más procesos lo empeora; la cura es el control de carga, es decir, reducir el número de procesos que compiten por la memoria (o añadir memoria).

Segmentación y listas de memoria libre

Un segmento es una unidad de tamaño variable que coincide con lo que usa el programa (código, pila, una tabla). Encaja bien, pero con el tiempo la memoria se llena de huecos pequeños entre segmentos (efecto tablero de ajedrez, o fragmentación externa). La compactación une los huecos, pero es cara. La paginación usa trozos de tamaño fijo: cualquier marco libre sirve para cualquier página, y el desperdicio queda solo dentro de la última página de una región (fragmentación interna).

Para colocar una petición de tamaño variable en una lista de huecos: el first fit (primer ajuste) toma el primer hueco suficientemente grande (rápido). El best fit (mejor ajuste) toma el hueco más pequeño suficientemente grande (recorre todo y deja pedazos diminutos inútiles). El worst fit (peor ajuste) toma el hueco más grande, esperando que el resto siga siendo útil. Ejemplo: huecos de 10, 4, 25, 6, 15 KB en orden de dirección, petición de 5 KB. El first fit usa el de 10, el best fit usa el de 6, el worst fit usa el de 25. Las simulaciones muestran que el first fit suele ser tan bueno como los otros.

Sistemas de archivos

La memoria se olvida cuando se va la luz. Un sistema de archivos es la manera en que el disco guarda información durante mucho tiempo, como archivos (cajas con nombre llenas de bytes) dentro de directorios (carpetas). El sistema operativo esconde el disco real, que solo sabe 'dame el bloque número 4.000', y ofrece nombres y rutas en su lugar.

Abrir un archivo

Encontrar un archivo es la parte cara: recorrer cada directorio de la ruta, hallar la descripción del archivo y comprobar los permisos. Por eso el programa primero llama a open. El SO hace este trabajo una vez y guarda el resultado en tablas del kernel. Devuelve un número pequeño, el descriptor de archivo (file descriptor). Después, read y write usan el número, y la posición de lectura actual queda ligada a ese open.

El i-node: la descripción de un archivo

En los sistemas tipo UNIX cada archivo tiene un i-node (index node) con sus atributos (dueño, permisos, tamaño, fechas) y las direcciones de sus bloques. Un directorio es solo una tabla de pares: un nombre y un número de i-node. El nombre no está en el i-node. Separar nombre y descripción permite varios nombres para un archivo y hace que renombrar un archivo solo cambie el directorio.

rm llama a unlink: quita una entrada de directorio y resta 1 al contador. Solo cuando llega a cero, y ningún proceso tiene el archivo abierto, se liberan el i-node y los bloques. Si un archivo tiene dos nombres y quitas uno, el archivo sigue existiendo con el otro.

Cómo se encuentran los bloques de un archivo

• Asignación contigua: un archivo es una serie de bloques vecinos; se describe con el primer bloque y la longitud. Muy rápida de leer, pero borrar archivos deja huecos y hay que saber el tamaño final al crearlo. Por eso funciona en CD y DVD de una sola escritura (nunca se borra nada) pero no en discos normales.
• Lista enlazada con tabla en memoria (FAT): cada entrada de la tabla guarda el número del siguiente bloque del archivo. Hay una entrada por cada bloque del disco, así que la tabla crece con el disco. Ejemplo: un disco de 8 GB con bloques de 4 KB tiene 2^33 / 2^12 = 2.097.152 entradas; con 4 bytes cada una, son 8 MB de tabla, toda en memoria.
• I-node con punteros: algunos punteros directos para los primeros bloques y un puntero indirecto a un bloque lleno de direcciones. El número de direcciones en un bloque es el tamaño del bloque dividido entre el tamaño de la dirección. Los punteros indirectos dobles y triples repiten la idea.

Ejemplo: un i-node con 12 punteros directos y 1 puntero indirecto simple, bloques de 1 KB, direcciones de 4 bytes. Un bloque indirecto guarda 1024 / 4 = 256 direcciones. El archivo máximo tiene 12 + 256 = 268 bloques = 268 KB.

i-node
+---------+
| dueño ..|
| directo1|--> [datos]
| ...     |--> [datos]
| directo12-->[datos]
| indirecto|--> [bloque de 256 direcciones]
+---------+        |--> [datos]
                   |--> [datos] ...

Tamaño del bloque

Un compromiso. Los bloques grandes significan menos búsquedas y menos entradas, por tanto mayor tasa de datos, pero crece el espacio no usado al final del último bloque de cada archivo (slack). Como la mayoría de los archivos son pequeños, los bloques enormes desperdician mucho disco. Los bloques pequeños desperdician poco pero vuelven más lento el disco.

Caídas: journaling y fsck

Borrar un archivo requiere varios pasos en lugares distintos: quitar la entrada del directorio, liberar el i-node, devolver los bloques. Un corte de luz en medio deja el disco inconsistente. Con journaling, el sistema primero escribe en un registro (log) lo que va a hacer, y luego lo hace. Después de una caída reproduce el registro. Algunos pasos pueden haberse hecho ya, así que cada paso registrado debe ser idempotente: hacerlo dos veces da el mismo resultado que una.

Un verificador como fsck mantiene dos contadores por bloque: en cuántos archivos aparece y cuántas veces está en la lista de libres. Un bloque sano tiene exactamente 1 en un contador y 0 en el otro. Un bloque que no está en ninguno vuelve a la lista de libres. Un bloque en dos archivos es grave: borrar uno liberaría un bloque que el otro aún usa, así que el verificador hace una copia del bloque para cada archivo.

VFS y sistemas de archivos estructurados en registro

Un sistema UNIX puede montar muchos tipos de sistemas de archivos en un solo árbol. La capa VFS (virtual file system, sistema de archivos virtual) define objetos comunes (superblock, v-node, directorio) y una lista de operaciones que cada sistema de archivos real implementa. Los programas siempre usan las mismas llamadas POSIX y no les importa lo que hay debajo.

Los discos son lentos en escrituras pequeñas y dispersas. Un sistema de archivos estructurado en registro (LFS) junta todas las escrituras pendientes (datos, i-nodes, directorios) en memoria y las escribe juntas como un segmento largo al final de un registro. Un mapa de i-nodes dice dónde está la copia más nueva de cada i-node. Las copias viejas se acumulan, así que un limpiador (cleaner) copia lo que sigue siendo válido y libera segmentos.

Entrada y salida: interrupciones, drivers, discos, RAID

Teclados, pantallas, discos, impresoras, tarjetas de red: todos son muy distintos y mucho más lentos que la CPU. El sistema operativo debe hablar con todos de forma ordenada. Cada dispositivo tiene un controlador (un chip pequeño) con registros para comandos, estado y datos.

Llegar al controlador

• E/S mapeada en puertos (port-mapped I/O): los registros viven en un espacio de direcciones aparte, al que se llega con instrucciones especiales.
• E/S mapeada en memoria (memory-mapped I/O): los registros aparecen en direcciones de la memoria normal. La protección es simple: el SO solo no mapea esas páginas para los procesos de usuario, usando la gestión de memoria normal.

Tres formas de hacer E/S

Cada interrupción cuesta tiempo de CPU, así que para dispositivos rápidos es importante reducirlas. Esa es la ventaja del DMA.

Interrupciones

Una interrupción es una señal de un dispositivo que dice 'necesito atención'. La CPU deja lo que hace, guarda dónde estaba, ejecuta una rutina corta (el manejador) y luego vuelve. Una interrupción precisa (precise) deja la máquina como si se hubiera detenido exactamente entre dos instrucciones: el contador de programa se guarda en un lugar conocido, todo lo anterior terminó, nada posterior cambió nada. Eso hace fácil reanudar. Las CPU modernas ejecutan muchas instrucciones a la vez (pipelines, fuera de orden), así que necesitan lógica extra en el hardware para presentar esa imagen limpia; si no, el SO tendría que averiguar qué quedó a medias.

Capas del software de E/S

Gracias a los drivers, se puede añadir un dispositivo nuevo sin cambiar el resto del sistema operativo.

Planificación de disco

Un disco duro tiene un brazo que se mueve sobre cilindros. Mover el brazo (la búsqueda, seek) es lento, así que el orden de las peticiones importa.

• FCFS: atender en orden de llegada. Justo, pero el brazo salta de un lado a otro.
• SSTF (shortest seek time first, menor tiempo de búsqueda primero): atiende siempre la petición más cercana. Recorre mucho menos que el FCFS pero no siempre es el mínimo, y con un flujo de llegadas las peticiones de los bordes pueden esperar mucho tiempo.
• Ascensor (SCAN): el brazo va en una dirección atendiendo todo lo que encuentra y luego regresa, como un ascensor en un edificio.

Ejemplo: el brazo está en el cilindro 40 y llegan peticiones para 10, 45 y 12. FCFS: 30 + 35 + 33 = 98 cilindros. SSTF: va a 45 (5), luego 12 (33), luego 10 (2) = 40 cilindros.

RAID: muchos discos trabajando como uno

El RAID une discos para ganar velocidad, seguridad o ambas. El striping (reparto en franjas) distribuye los datos entre discos para que trabajen en paralelo. El espejado (mirroring) guarda una copia. La paridad guarda información extra para reconstruir datos perdidos.

Ejemplo: 4 discos de 1 TB en RAID 5 dan 3 TB para datos. La paridad es el XOR de los bloques de datos de la franja. El XOR es su propio inverso, así que cualquier bloque perdido es el XOR de todos los demás, paridad incluida. Ejemplo: D1 = 0101, D3 = 0011, paridad P = 1110. Si muere el disco con D2, D2 = 0101 XOR 0011 XOR 1110 = 1000. La reconstrucción debe leer todos los discos restantes.

Deadlocks

Dos autos llegan a un puente angosto por lados opuestos. Cada uno espera que el otro retroceda. Nadie se mueve nunca. Un deadlock (interbloqueo) es un grupo de procesos en el que cada uno espera algo que solo otro miembro del grupo puede dar. Todos quedan bloqueados para siempre.

Las cuatro condiciones

Un deadlock de recursos necesita estas cuatro a la vez:

1. Exclusión mutua: un recurso lo tiene un solo proceso a la vez.
2. Retención y espera (hold and wait): un proceso que retiene recursos puede pedir más.
3. Sin expropiación: los recursos no se pueden quitar por la fuerza.
4. Espera circular: un anillo de procesos, cada uno esperando un recurso que tiene el siguiente.

Rompe cualquiera y el deadlock se vuelve imposible. Esa es la idea detrás de la prevención.

Grafo de asignación de recursos

Dibuja los procesos como círculos y los recursos como cuadrados. Una flecha de un recurso a un proceso significa 'posee'. Una flecha de un proceso a un recurso significa 'solicita'. Cuando cada recurso tiene una sola instancia, hay deadlock exactamente cuando el grafo tiene un ciclo, y los procesos del ciclo son los que están en deadlock.

  A tiene R, quiere S
  B tiene S, quiere T
  C tiene T, quiere R

   A --quiere--> S --retenido por--> B
   ^                                 |
   |                               quiere
 retenido por                        v
   |                                 T
   R <--------quiere--------------- C   (C tiene T)

 El anillo A -> B -> C -> A nunca se abre: DEADLOCK

Cuatro maneras de tratar los deadlocks

Prevención en la práctica

La forma más práctica es ordenar los recursos: numera todas las cerraduras y exige que un thread pida solo una cerradura con un número mayor que todas las que ya tiene. Así un ciclo es imposible, porque siguiendo las flechas los números solo crecen. Esto niega la condición de espera circular. El precio es la disciplina: a veces hay que soltar y volver a tomar cerraduras para respetar el orden.

Otra idea es intentar la cerradura sin bloquear (trylock) y, si falla, soltar lo que se tiene y empezar de nuevo. Esto niega la retención y espera, pero puede causar livelock: dos procesos repitiendo el mismo baile para siempre, como dos personas que se mueven al mismo lado en un pasillo. Esperar un tiempo aleatorio antes de reintentar suele ayudar.

Estados seguros e inseguros

Un estado es seguro si existe algún orden en el que todos los procesos pueden terminar, incluso si cada uno pide su máximo. Un estado inseguro no significa que el deadlock ya ocurrió; significa que se perdió la garantía y el resultado depende de la suerte. El algoritmo del banquero funciona como un banquero cuidadoso con dinero limitado: solo concede una petición si el nuevo estado sigue siendo seguro, aunque haya recursos libres.

Para probar la seguridad: necesidad restante = máximo - asignado. Busca un proceso cuya necesidad restante quepa en lo que está libre. Finge que termina y devuelve todo. Repite. Si todos pueden terminar, el estado es seguro.

Virtualización y la nube

Imagina un edificio grande dividido en muchos apartamentos separados. Cada familia cree que es dueña de su casa, pero todas comparten las mismas paredes y tuberías. La virtualización hace eso con las computadoras: una máquina real finge ser varias. Cada máquina de mentira es una máquina virtual (VM) y tiene su propio sistema operativo, llamado invitado (guest). La nube lo usa mucho: una empresa te alquila una VM en lugar de una computadora entera.

El hypervisor

El programa que crea la ilusión es el hypervisor (o monitor de máquinas virtuales, VMM).

Trap y emulación

El SO invitado cree que está en modo kernel, pero en realidad se ejecuta en modo usuario, así que el hypervisor sigue al mando. Cuando el invitado intenta una instrucción privilegiada, la CPU hace una trap al hypervisor, que finge ejecutarla y regresa. Esto es trap and emulate.

Solo funciona si toda instrucción sensible (la que se comporta distinto según el modo o toca el estado privilegiado de la máquina) también es privilegiada (hace trap en modo usuario). Este es el criterio de Popek y Goldberg: las instrucciones sensibles deben ser un subconjunto de las privilegiadas. El x86 original lo incumplía: algunas instrucciones sensibles hacían silenciosamente otra cosa en modo usuario, sin trap. Las soluciones fueron la traducción binaria (reescribir el código del invitado al vuelo) y más tarde el soporte de hardware (Intel VT-x, AMD-V).

Virtualización completa y paravirtualización

Memoria con máquinas virtuales

Hay tres tipos de dirección: virtual del invitado, física del invitado y física de la máquina (la real). El invitado controla solo la primera traducción. Sin ayuda del hardware, el hypervisor mantiene tablas de páginas sombra (shadow page tables) que van directamente de virtual del invitado a física de la máquina, y debe interceptar cada escritura del invitado en sus propias tablas para mantenerlas sincronizadas, lo cual es caro. Las CPU modernas tienen tablas de páginas anidadas (EPT en Intel, NPT en AMD) que hacen las dos traducciones en hardware.

Sistemas con múltiples procesadores

Hoy incluso los teléfonos tienen varios núcleos de CPU. Con una CPU, los programas solo parecen ejecutarse juntos porque se turnan rápidamente. Con varias CPU, dos trozos de código realmente se ejecutan en el mismo instante, lo que crea problemas nuevos para el kernel.

Por qué apagar las interrupciones no basta

Con una CPU, todo lo que puede interrumpir un trozo de código del kernel viene de las interrupciones y de los cambios de contexto que provocan. Así que deshabilitar las interrupciones hace segura una región crítica corta. En un multiprocesador, deshabilitar las interrupciones afecta solo a esa CPU. Otra CPU puede entrar al mismo código en el mismo momento. Por eso necesitamos cerraduras construidas sobre instrucciones atómicas (como la TSL), normalmente combinadas con deshabilitar las interrupciones localmente.

¿Girar o bloquear?

Cuando un thread encuentra la cerradura tomada, puede girar (espera activa, seguir preguntando) o bloquearse (dormir y ceder la CPU).

Por eso las cerraduras alrededor de regiones críticas muy cortas del kernel son spin locks. Muchas implementaciones giran durante un tiempo limitado y luego se bloquean si la cerradura sigue tomada, acercándose a lo mejor de ambos.

Seguridad

Una escuela deja algunos salones abiertos y otros cerrados con llave, y da a cada persona solo las llaves que necesita. El sistema operativo hace lo mismo con los archivos, la memoria y los dispositivos. El objetivo es que un programa o usuario pueda hacer solo lo que se le permite.

La matriz de protección

Imagina una tabla. Cada fila es un dominio (un usuario o proceso). Cada columna es un objeto (un archivo, una impresora). Cada celda lista los derechos, como leer o escribir. La tabla es enorme y casi toda está vacía, así que se guarda en pedazos:

Una buena regla es el mínimo privilegio: dar a cada programa solo los derechos que realmente necesita.

Desbordamiento de búfer y sus defensas

Un desbordamiento de búfer (buffer overflow) ocurre cuando un programa copia más datos en una caja de tamaño fijo de los que caben, derramándose en la memoria vecina. En el ataque clásico los datos contienen código de máquina y sobrescriben la dirección de retorno en la pila para que el programa salte a ese código. Lo estudiamos solo para defendernos.

Con el DEP, los atacantes pasaron a reutilizar código ya cargado y ejecutable, y por eso combinamos canarios, DEP y ASLR.

Juntándolo todo

Todos los temas son partes de una sola historia. Un programa empieza como un proceso (con threads). Pide servicios al kernel con llamadas al sistema. Comparte datos con seguridad mediante la sincronización. El planificador le da la CPU. La memoria virtual le da las direcciones. Los archivos guardan sus datos. La E/S llega a los dispositivos. El SO debe evitar los deadlocks, puede ejecutarse dentro de una máquina virtual, maneja varias CPU y hace cumplir la seguridad.

Errores comunes

• Creer que un proceso listo y uno bloqueado son lo mismo. El listo espera la CPU; el bloqueado espera un evento.
• Creer que el modo cambia al llamar a read. Cambia en la trap que hay dentro.
• Creer que más memoria siempre reduce los fallos del FIFO (anomalía de Belady).
• Creer que un estado inseguro ya es un deadlock.
• Creer que deshabilitar las interrupciones basta en un multiprocesador.
• Olvidar que el nombre de un archivo se guarda en el directorio y no en el i-node.
• Confundir deadlock (todos bloqueados), inanición (a uno lo ignoran) y livelock (todos ocupados, sin progreso).