Lo que vas a aprender
- Qué hace el sistema operativo y qué es el núcleo.
- Qué son los procesos, sus estados y los hilos.
- Los algoritmos de planificación de la CPU y cómo compararlos.
- La memoria virtual, la paginación y el reemplazo de páginas.
- Los problemas de la concurrencia: condiciones de carrera, exclusión mutua e interbloqueo.
Fundamentos teóricos
El núcleo
El núcleo (kernel) se ejecuta en modo privilegiado y es el único que accede directamente al hardware. Los programas corren en modo usuario y piden servicios al núcleo mediante llamadas al sistema (open, read, fork…). Funciones principales: gestión de procesos, de memoria, de ficheros, de entrada/salida y seguridad.
Procesos y estados
Un proceso es un programa en ejecución, con su código, sus datos, su pila y su estado (registros, ficheros abiertos). El núcleo guarda esa información en el bloque de control de proceso (PCB).
Cambiar de un proceso a otro es un cambio de contexto: guardar los registros de uno y cargar los del otro. Cuesta microsegundos y no hace trabajo útil.
Hilos
Un hilo es una línea de ejecución dentro de un proceso. Los hilos de un mismo proceso comparten la memoria, así que crearlos y comunicarlos es más barato que con procesos, pero hay que sincronizarlos. Es la base de la programación paralela.Planificación de la CPU
Medidas para compararlos: tiempo de espera (en la cola de listos), tiempo de retorno (desde la llegada hasta el final) y tiempo de respuesta (hasta la primera vez que se ejecuta).
Memoria virtual y paginación
Cada proceso ve un espacio de direcciones virtual propio, como si tuviera toda la memoria para él. El hardware (la MMU) traduce cada dirección virtual a una física. Con paginación, la memoria virtual se divide en páginas y la física en marcos del mismo tamaño (por ejemplo, 4 KiB). La tabla de páginas dice en qué marco está cada página. Una dirección se divide en número de página y desplazamiento: Si una página no está en memoria, se produce un fallo de página y el sistema la trae del disco. Una caché de traducciones, la TLB, evita consultar la tabla en cada acceso.Reemplazo de páginas
Cuando no quedan marcos libres, hay que expulsar una página:Concurrencia
Cuando varios hilos acceden a los mismos datos, el resultado puede depender del orden en que se intercalen: es una condición de carrera. El trozo de código que accede a datos compartidos es la sección crítica, y debe ejecutarse en exclusión mutua.Interbloqueo
Varios procesos esperan, cada uno, un recurso que tiene otro, y ninguno avanza. Hacen falta las cuatro condiciones de Coffman a la vez:- Exclusión mutua: los recursos no se comparten.
- Retención y espera: se retiene un recurso mientras se espera otro.
- No expropiación: no se puede quitar un recurso a la fuerza.
- Espera circular: P1 espera a P2, que espera a… P1.
Ejemplos resueltos
Ejemplo 1 · FCFS frente a SJF
Ejemplo 1 · FCFS frente a SJF
Tres procesos llegan a la vez con ráfagas de 24, 3 y 3 ms (en ese orden).FCFS: esperan 0, 24 y 27 ms. Media: 17 ms.SJF: se ejecutan 3, 3, 24. Esperan 0, 3 y 6 ms. Media: 3 ms.
Ejemplo 2 · Round Robin
Ejemplo 2 · Round Robin
Los mismos procesos (P1 = 24, P2 = 3, P3 = 3) con cuanto de 4 ms:
Esperas: P1 = 6, P2 = 4, P3 = 7. Media: 5,67 ms. P2 y P3 empiezan mucho antes que en FCFS.
Ejemplo 3 · Traducción de una dirección
Ejemplo 3 · Traducción de una dirección
Páginas de 4 KiB (4096 bytes). Dirección virtual 20 000: página , desplazamiento .Si la tabla dice que la página 4 está en el marco 9: dirección física .
Ejemplo 4 · Reemplazo FIFO y LRU
Ejemplo 4 · Reemplazo FIFO y LRU
Referencias 7, 0, 1, 2, 0, 3, 0, 4 con 3 marcos:FIFO: fallos en 7, 0, 1, 2 (sale 7), 3 (sale 0), 0 (sale 1), 4 (sale 2): 7 fallos.LRU: fallos en 7, 0, 1, 2 (sale 7), 3 (sale 1), 4 (sale 2); el 0 se usa a menudo y nunca sale: 6 fallos.
Ejemplo 5 · Condición de carrera
Ejemplo 5 · Condición de carrera
Dos hilos ejecutan
contador = contador + 1 mil veces cada uno. La operación son tres pasos (leer, sumar, escribir); si los dos leen el mismo valor antes de que el otro escriba, se pierde un incremento. El resultado suele ser menor que 2000. Con un mutex alrededor de la línea, siempre da 2000.Errores frecuentes
- Confundir proceso y programa. El programa es el fichero; el proceso, su ejecución. Un mismo programa puede tener varios procesos.
- Confundir tiempo de espera con tiempo de retorno. El retorno incluye la ejecución.
- Pensar que más marcos siempre dan menos fallos. Con FIFO puede pasar lo contrario (anomalía de Belady).
- Proteger solo la escritura de un dato compartido y no la lectura que la precede.
- Pedir cerrojos en distinto orden en distintos hilos: receta para el interbloqueo.
Preguntas frecuentes
¿Qué planificador usa Linux?
¿Qué planificador usa Linux?
Desde la versión 6.6, el EEVDF (Earliest Eligible Virtual Deadline First), que sustituyó al CFS. Los dos reparten la CPU de forma proporcional a un peso que depende de la prioridad (nice), siguiendo cuánto tiempo de CPU “le toca” a cada proceso.
¿Por qué el ordenador va lento cuando se queda sin RAM?
¿Por qué el ordenador va lento cuando se queda sin RAM?
Porque empieza a mover páginas al disco (swap) constantemente. Si los procesos necesitan más memoria de la que hay, casi cada acceso produce un fallo de página y el sistema pasa más tiempo trayendo páginas que trabajando: es la hiperpaginación (thrashing).
Temas relacionados
Ley de Amdahl
Cuánto se acelera un programa con más núcleos.
Memoria y punteros en C
Pila, montón y direcciones.
Montículos
Colas de prioridad para el planificador.