Formulario (cheat sheet)

Esta página se imprime bien (Ctrl + P). Cada bloque enlaza a su tema.

Procesos y threads

Llamada	Qué hace	Trampa típica
`fork()`	Clona el proceso: memoria, descriptores, semáforos y mutex con su estado. Retorna 0 al hijo y el pid del hijo al padre.	Solo se copia el hilo que llamó. Un mutex tomado por otro hilo queda tomado para siempre en el hijo.
`execv(path, argv)`	Reemplaza la imagen del proceso. No retorna si tiene éxito.	Lo que viene después de `execv` en el código original no se ejecuta. `argc` cambia.
`exit(0)`	Termina el proceso (y todos sus hilos).	Cuidado con los prints que venían después.
`pthread_create(&t, NULL, f, arg)`	Nuevo hilo que comparte memoria.	Pasar `&local` compartido entre iteraciones produce una race sobre los argumentos.
`pthread_join(t, NULL)`	Espera a que termine el hilo.	Sin join, `main` puede salir antes.

Modelos de threads (detalle):

Many-to-One (ULT): una syscall bloqueante bloquea todo el proceso y no hay paralelismo real.
One-to-One (Linux, Windows): cada hilo de usuario es un hilo del kernel.
Many-to-Many: se multiplexan M hilos de usuario sobre N hilos del kernel.

Exclusión mutua

Requisitos (Stallings 5.1):

Solo uno en la SC a la vez.
Un proceso que se detiene fuera de la SC no debe interferir.
Sin deadlock ni starvation.
Si la SC está libre, se entra sin demora.
Sin supuestos sobre velocidades ni número de CPUs.
Se permanece en la SC un tiempo finito.

Propiedades a demostrar: mutex (safety), deadlock-free (progreso) y starvation-free (espera acotada). Starvation-free implica deadlock-free.

Algoritmo	Mutex	Deadlock-free	Starvation-free
Peterson / PC1 2021	✔	✔	✔ (espera ≤ 1)
Peterson con turn antes que flag	✘	✔	—
Dekker	✔	✔	✔ (sin cota numérica)
Dijkstra 1965 real (b, c, k)	✔	✔	✘
Filtro (N) / torneo (liberar raíz → hoja)	✔	✔	✔ (filtro sin espera acotada)
Hyman (E1 2026-1)	✘	✔	✘
Flaky (E1 2024-I)	✔	✘	✘
Bakery / Lamport lexicográfico	✔	✔	✔ (FCFS)
Dijkstra 1965 (N procesos)	✔	✔	✘
TAS / CAS spinlock	✔	✔	✘

Prueba de exclusión mutua en 3 líneas (detalle): supón ambos en la SC → toma al último en escribir la variable de desempate → encadena $W(\text{flag}) \to W(\text{turn}) \to W_{\text{último}}(\text{turn}) \to R(\text{flag})$ → contradicción. «turn tiene un solo valor» prueba deadlock-freedom, no exclusión mutua.

POSIX y futex (ir)

futex_wait(&x, v): duerme solo si x == v (atómico en el kernel; si no, EAGAIN). futex_wake(&x, n). Siempre en un while.
Mutex de futex con 3 estados: 0 libre, 1 tomado, 2 con esperadores. Sin contención, cero syscalls.
pthread_mutex: tiene dueño. Relock: NORMAL → deadlock, ERRORCHECK → EDEADLK, RECURSIVE → ok. trylock → EBUSY. Retorna el error (sin errno).
sem_t: sin dueño (sirve para señalizar). Entre procesos: sem_open o sem_init(p, 1, v) en memoria compartida. sem_wait puede dar EINTR; sem_getvalue ≥ 0 en Linux.
pthread_cond_wait(c, m): suelta m atómicamente y lo retoma; siempre con while.

Deadlock: 4 condiciones necesarias (Coffman)

Exclusión mutua: el recurso lo usa uno a la vez.
Hold and wait: se retiene un recurso mientras se espera otro.
No preemption: no se le puede quitar el recurso a quien lo tiene.
Espera circular.

Las tres primeras son de diseño; la cuarta aparece durante la ejecución. trylock rompe hold and wait y evita el deadlock, pero puede generar livelock o starvation.

Semáforos

semWait(s):   s.count--; if (s.count < 0) { encolar; bloquear; }
semSignal(s): s.count++; if (s.count <= 0) { desencolar P; ready(P); }

count < 0 ⇒ |count| procesos en cola.
Fuerte = cola FIFO (sin starvation). Débil = orden no especificado.
Regla de oro: primero el semáforo de conteo (vacios/llenos) y después mutex. Invertirlo produce deadlock.

Monitores

Un lock protege el estado y las condition variables son colas.
wait(c, m): libera el lock atómicamente, duerme y readquiere el lock antes de retornar.
Hoare: signal transfiere el monitor de inmediato, así que basta un if.
Mesa (pthreads, Java): signal solo marca listo, así que se usa while (también cubre los spurious wakeups).

Registros (Herlihy)

Tipo	Si la lectura NO se solapa	Si se solapa con escrituras
Safe	último valor escrito	cualquier valor del dominio
Regular	último valor	viejo o alguno de los nuevos
Atomic	último valor	como regular + linealizable (sin inversión nuevo→viejo)

Las dimensiones son: lectores/escritores (SRSW, MRSW, MRMW) × tamaño (booleano, m-valuado) × fuerza (safe, regular, atomic).

Memoria

Fragmentación interna: el bloque asignado es más grande que lo pedido (particiones fijas, buddy, páginas).
Fragmentación externa: hay memoria libre total pero no contigua (particiones dinámicas, segmentación). Se resuelve compactando, lo que requiere relocalización dinámica.
Placement: best-fit (hueco más ajustado), first-fit (primero desde el inicio), next-fit (primero desde la última asignación). First-fit suele ser el mejor y el más rápido.
Regla del 50 %: con first-fit, N bloques asignados pierden ≈ 0.5 N por fragmentación (≈ ⅓ de la memoria).
Buddy: bloques de $2^k$ ; para pedir, redondear hacia arriba y dividir; al liberar, fusionar con el buddy (dirección start XOR size).
Segmentación: física = base[seg] + offset si offset < limit; si no, segfault.

Paginación (calculadora):

\text{offset} = \log_2(\text{página}) \quad \text{VPN} = n_{virt} - \text{offset} \quad \text{PFN} = n_{fís} - \text{offset}

\#\text{entradas} = 2^{\text{VPN}} \qquad \text{tamaño tabla} = 2^{\text{VPN}} \cdot \left\lceil \tfrac{\text{PFN} + \text{bits de estado}}{8} \right\rceil \text{ B}

Para multinivel con tablas de 1 página: bits por nivel $= \log_2(\text{página}/\text{PTE})$ y niveles $= \lceil \text{VPN} / \text{bits por nivel} \rceil$ .

Hardware y fundamentos (ir)

Interrupción: el hardware termina la instrucción actual, reconoce la interrupción, guarda PSW y PC y salta al handler. El handler guarda los registros, procesa, restaura y regresa. Hay 4 clases: program, timer, E/S y falla de hardware. Con varias interrupciones se deshabilitan (secuencial) o se anidan por prioridad.
$T_s = T_1 + (1-H)\,T_2$ ; la eficiencia es $T_1/T_s$ . Todo funciona gracias a la localidad (temporal y espacial).
E/S: programada (polling) → por interrupciones → DMA (una interrupción al final; la CPU solo cede ciclos de bus).
Evolución: serial → batch (monitor, JCL; requiere protección, timer, instrucciones privilegiadas e interrupciones) → multiprogramado (requiere interrupciones de E/S y DMA) → tiempo compartido (minimizar la respuesta).

Procesos (ir)

5 estados: New → Ready ⇄ Running → Exit, y Running → Blocked → Ready. 7 estados: + Ready/Suspend y Blocked/Suspend (en disco). SVR4 (9): User y Kernel running, Preempted, Zombie, Created…
PCB: identificación, estado del procesador (registros, PC, PSW, SP) y control del proceso.
Cambio de proceso: lo causa una interrupción (reloj, E/S, fallo de memoria), un trap o una supervisor call. Un mode switch es barato; un process switch tiene 7 pasos: guardar contexto, actualizar el PCB, moverlo a una cola, elegir otro proceso, actualizar su PCB, actualizar la memoria y restaurar el contexto.
fork en SVR4: entrada en la tabla, PID, copia de la imagen (salvo memoria compartida), incrementar contadores de archivos, Ready, y retorna PID al padre y 0 al hijo.

Deadlock (ir)

Prevención: hold and wait → pedir todo de una vez; no preemption → soltar lo que se tiene o expropiar; espera circular → orden lineal. La exclusión mutua no se puede quitar.
Evitación (banquero): conceder solo si el estado resultante es seguro (existe una secuencia en que todos terminan con $C_k - A_k \le$ disponible). Inseguro ≠ deadlock.
Detección: marcar los procesos sin nada asignado; W = V; marcar cada $P_i$ con $Q_i \le W$ y hacer W += $A_i$ . Los que quedan sin marcar están en deadlock. Recuperación: abortar a todos (lo más común), rollback, abortar uno por uno o expropiar uno por uno.

Mensajes (ir)

send / receive, bloqueantes o no (ambos bloqueantes = rendezvous; send no bloqueante + receive bloqueante es lo más útil). Direccionamiento directo o indirecto (mailbox; puerto = muchos a uno). Exclusión mutua = un mailbox con 1 token.

TLB y tablas (ir)

$\text{EAT} = h\,(t_{TLB} + t_m) + (1-h)\,(t_{TLB} + k\,t_m + t_m)$ para k niveles.
Dos niveles en 32 bits con páginas de 4 KB y PTE de 4 B: 10 | 10 | 12, con una raíz de 4 KB siempre en RAM.
Invertida: una entrada por marco y búsqueda por hash de (página, PID).
PTE: P (presente), M (modificado), R (referenciado), protección y marco.

Memory layout de un proceso

text/code (instrucciones) → data (globales y estáticas) → heap (↑ malloc) … stack (↓ locales, direcciones de retorno). En el PCB: estado, registros, PC, prioridad e información de memoria.

Microkernel vs monolítico

Monolítico (Linux): todo corre en modo kernel. Es rápido, pero un fallo tira todo el sistema.
Microkernel (Mach, QNX): solo IPC, planificación y memoria básica; los servicios corren en espacio de usuario. Es más robusto porque un servicio que cae no tumba el sistema, pero es más lento por la IPC. Si piden robustez ante fallas, la respuesta es microkernel.