A la lliçó anterior vam deixar un deute. Els cinc filòsofs es bloquejaven, vam esquivar el problema amb tres trucs que funcionaven, i no vam explicar per què funcionaven ni què tenien en comú. Aquesta lliçó paga aquest deute i tanca el mòdul.

L'interbloqueig és la patologia més temuda de la concurrència, i no per la seva freqüència sinó pel seu comportament. No produeix dades corrompudes ni resultats erronis: produeix silenci. Els processos continuen vius, no consumeixen CPU, no escriuen al registre, no retornen errors; simplement deixen d'avançar, i des de fora tot sembla normal fins que algú es pregunta per què meteo-api fa vint minuts que no respon. És, a més, una fallada que apareix sota càrrega i no a les proves, perquè necessita un entrellaçament concret que només es dona amb trànsit real.

El construirem des de zero perquè el vegis penjar-se, el formalitzarem amb les quatre condicions de Coffman, el modelarem amb grafs, i després recorrerem les quatre estratègies que existeixen: prevenir-lo, evitar-lo, detectar-lo i recuperar-se, o ignorar-lo deliberadament —que és, sorprenentment, el que fa Linux—. Acabarem amb el més pràctic de tota la lliçó: com es diagnostica un interbloqueig real en un servidor en producció, amb eines que faràs servir de debò.

1. Definició i exemple mínim reproduïble
2. Les quatre condicions de Coffman
3. Graf d'assignació de recursos i detecció de cicles
4. Estratègia 1: prevenció
5. Estratègia 2: evitació i l'algorisme del banquer
6. Estratègia 3: detecció i recuperació
7. Estratègia 4: l'estruç, i per què Linux l'adopta
8. Interbloqueig, inanició i livelock
9. Diagnosticar un interbloqueig real
10. El cas resolt de meteo-api i l'agregador
11. Regles d'enginyeria que l'eviten
12. Tancament del mòdul 3

Un conjunt de processos està en interbloqueig (deadlock) quan cadascun d'ells espera un esdeveniment que només pot produir un altre procés del mateix conjunt. Com que tots esperen i cap no avança, l'esdeveniment no passa mai i l'espera és permanent.

La paraula clau és permanent: no és una espera llarga, és una espera de la qual és impossible sortir sense intervenció externa. Si esperes dues hores però acabes avançant, això és un problema de rendiment; si l'estat del sistema garanteix que no avançaràs mai, això és un interbloqueig.

L'exemple mínim són dos mutexos presos en ordre invers. Es penja de debò, i val la pena que l'executis:

En executar-lo imprimeix dues o tres voltes de cada fil i es queda aturat per sempre, sense consumir CPU i sense cap missatge d'error.

La traça del moment fatal, després de l'usleep:

Cadascun té el que l'altre necessita, i cap no deixarà anar el seu perquè està bloquejat. És un cicle d'espera de longitud 2.

Dues observacions importants abans de continuar. L'usleep(10) només fa la fallada determinista: sense ell, el programa també es penja, però pot trigar minuts o hores, perquè necessita que el planificador expulsi un fil justament entre les dues adquisicions —és el no determinisme de 03-01: la finestra hi és sempre i amb prou iteracions s'acaba donant—. I el codi és correcte vista cada funció per separat: totes dues prenen dos forrellats, fan la seva feina i els deixen anar en ordre invers, com mana el manual. La fallada no és a cap de les dues funcions, és a la relació entre elles, i per això cap revisió de codi que miri una funció aïllada no la detectarà.

El 1971, Edward Coffman va formular les quatre condicions necessàries perquè hi pugui haver interbloqueig. El seu valor pràctic és enorme: com que són necessàries totes alhora, n'hi ha prou amb garantir que una no es compleixi perquè l'interbloqueig sigui impossible. Tota l'estratègia de prevenció surt d'aquí.

1. Exclusió mútua. Almenys un recurs ha de ser no compartible: si un procés el té, un altre no el pot tenir simultàniament. Sense això no hi ha conflicte possible, perquè si deu processos poden fer servir el recurs alhora ningú no espera ningú. És la raó que les lectures compartides d'un rwlock no puguin formar part d'un interbloqueig, però les escriptures sí.

2. Retenció i espera (hold and wait). Un procés que ja té almenys un recurs en sol·licita un altre i es queda esperant sense deixar anar el que té.

És la condició que fa que el bloqueig es propagui: si en demanar un recurs nou deixessis anar tot el que tens, la teva espera no bloquejaria ningú. A l'exemple, l'agregador espera el fitxer retenint la memòria cau, i això és el que atrapa meteo-api.

3. Sense expropiació (no preemption). Un recurs només el pot alliberar voluntàriament el procés que el posseeix; el sistema no l'hi pot treure. Un mutex compleix aquesta condició per disseny: no existeix cap crida que arrenqui un mutex a un fil, i amb raó, perquè l'estat que protegia quedaria a mig modificar. En canvi, la CPU sí que és expropiable —el planificador la treu cada pocs mil·lisegons— i per això no hi ha mai interbloqueig per la CPU; i la memòria física també ho és, gràcies al swapping (mòdul 2).

4. Espera circular. Existeix un conjunt de processos {P₀, P₁, ..., Pₙ} tal que P₀ espera un recurs que té P₁, P₁ n'espera un que té P₂, ..., i Pₙ n'espera un que té P₀. És la condició més visible i la que dona la imatge mental del problema. Compte amb el detall lògic: l'espera circular implica retenció i espera, però no a l'inrevés —hi pot haver molts processos retenint i esperant sense que es tanqui cap cicle, i aleshores no hi ha interbloqueig—.

Resumides, amb el que costa trencar cadascuna:

Aquesta taula és el mapa de l'estratègia de prevenció, i ja avança la conclusió: a la pràctica, gairebé sempre es trenca la quarta.

El model formal que permet raonar sobre això és el graf d'assignació de recursos, un graf dirigit amb nodes de dos tipus —processos i recursos— i dos tipus d'aresta: l'aresta d'assignació R → P, que significa que el recurs R està assignat al procés P, i l'aresta de sol·licitud P → R, que significa que P espera el recurs R. El nostre exemple queda així:

El cicle agregador → forrellat_fitxer → meteo-api → forrellat_cache → agregador salta a la vista. I aquí hi ha el teorema que fa útil el model:

Si cada recurs té una sola instància, un cicle al graf és condició necessària i suficient per a l'interbloqueig. Si algun recurs té diverses instàncies, el cicle és necessari però no suficient.

La distinció importa. Un mutex és un recurs d'una sola instància: o el tens o no. Un semàfor inicialitzat a 5 —cinc connexions a base de dades— té cinc instàncies, i allà un cicle no basta: pot ser que una la tingui un procés aliè al cicle, que l'alliberarà i desencallarà tothom. Per a aquests casos cal un algorisme de detecció més elaborat, que veurem a l'apartat 6.

Buscar cicles en un graf dirigit és un problema resolt: un recorregut en profunditat els detecta en O(V + E), i un sistema amb 1.000 processos i 5.000 recursos s'analitza en mil·lisegons. La dificultat no és l'algorisme, sinó construir el graf: cal saber, en un instant congelat, qui té què i qui espera què. Al nucli això és fàcil; des de fora, no tant.

Prevenir significa dissenyar el sistema perquè una de les quatre condicions no es compleixi mai. És una garantia estructural: si la condició no es pot donar, l'interbloqueig és impossible per construcció, sense necessitat de comprovar res en temps d'execució.

Trencar l'exclusió mútua consistiria a fer els recursos compartibles, i és impossible per a la majoria: un mutex existeix precisament per excloure. On sí que s'aplica és amb recursos virtualitzables —el spooling d'impressió del mòdul 2: en lloc de competir per la impressora, els processos escriuen en una cua de fitxers i un dimoni la gestiona—. A Meteora, la memòria cau es podria fer «compartible» amb la doble memòria intermèdia que vam proposar a la lliçó anterior, on els lectors no bloquegen mai.

Trencar la retenció i espera, en dues variants. Demanar-ho tot de cop al principi: el procés declara tots els recursos que necessitarà i només comença quan els té tots.

Fixa't en el pthread_mutex_trylock, que intenta adquirir sense bloquejar-se i retorna error si no pot: en deixar anar a quan falla, el procés no reté mai mentre espera. L'espera aleatòria abans de reintentar és imprescindible, perquè sense ella dos fils es poden sincronitzar i reintentar eternament alhora, caient en el livelock de l'apartat 8.

Deixar-ho anar tot abans de demanar. Si necessites un recurs nou, alliberes els que tens i els tornes a demanar tots: correcte però costós, i l'estat que protegien queda exposat entremig. El cost d'aquesta via és baixa utilització —reserves recursos que potser faràs servir d'aquí a deu minuts— i inanició possible —qui necessita molts recursos pot no aconseguir-los mai tots alhora—. S'utilitza en temps real i bases de dades amb planificació estàtica, no en codi general.

Trencar l'absència d'expropiació. Si un procés demana un recurs i no el pot obtenir, se li treuen tots els que tenia i es reintenta més tard. En espai d'usuari s'implementa amb temps límit:

pthread_mutex_timedlock converteix una espera infinita en una d'acotada, transformant un interbloqueig permanent en una fallada temporal recuperable. El cost és que cal poder desfer la feina feta fins a aquell punt, cosa que exigeix seccions crítiques transaccionals; i en la seva forma agressiva pot produir livelock.

Trencar l'espera circular: l'ordre global. Aquesta és la tècnica guanyadora, la que faràs servir sempre: imposar un ordre total sobre els recursos i exigir que tots els processos els adquireixin en ordre creixent.

Per què funciona, demostrat: suposem que existeix un cicle P₀ → P₁ → ... → Pₙ → P₀. Cada aresta significa que Pᵢ reté un recurs d'ordre k i n'espera un d'ordre m > k. Recorrent el cicle, els ordres creixen estrictament a cada pas, i en tornar al punt de partida tindríem k > k. Contradicció: el cicle és impossible.

Quan els recursos no tenen un ordre natural, es fa servir la seva adreça de memòria:

És el patró que fan servir les transferències bancàries entre dos comptes, i resol el problema de manera general: tant li fa quins dos forrellats li passis, sempre els prendrà en el mateix ordre absolut. Cost en rendiment: zero. Cost en disciplina: cal documentar la jerarquia i respectar-la a tot el codi, inclòs el que escrigui una altra persona d'aquí a dos anys. Per això els nuclis seriosos documenten la seva jerarquia de bloqueigs i tenen validadors automàtics, com veurem.

L'evitació és més ambiciosa que la prevenció: no restringeix com es demana, sinó que decideix a cada sol·licitud si concedir-la, en funció de si l'estat resultant continua sent segur. Requereix que cada procés declari per endavant la seva necessitat màxima de cada recurs.

Un estat segur és aquell en què existeix una seqüència segura: un ordre dels processos ⟨P₁, P₂, ..., Pₙ⟩ tal que les necessitats pendents de cada Pᵢ es poden satisfer amb els recursos lliures més els que alliberaran tots els Pⱼ amb j < i. Si existeix aquesta seqüència, el sistema pot acabar-los tots, un darrere l'altre, sense bloquejar-se. La relació entre els tres tipus d'estat és jeràrquica: segur implica que no hi ha ni hi haurà interbloqueig; insegur significa que n'hi pot haver, no que n'hi hagi; i interbloquejat és un subconjunt dels insegurs. L'evitació és conservadora: rebutja tota sol·licitud que porti a un estat insegur, encara que aquell estat potser no hauria donat problemes.

Dijkstra el va anomenar així per analogia amb un banquer que concedeix crèdits: no compromet mai tants diners que no pugui satisfer les línies de crèdit de tots els seus clients.

L'escenari. meteo-01 té tres tipus de recurs —A: 10 connexions a la base de dades; B: 5 memòries intermèdies d'1 MB a /dev/shm; C: 7 descriptors reservats— i cinc processos. L'estat actual ve donat per la matriu Assignat (el que cada procés té ara) i la matriu Màxim (el que va declarar que podria arribar a necessitar):

Disponible = Total − Assignat = (10, 5, 7) − (7, 2, 5) = (3, 3, 2)

Pregunta 1: és segur aquest estat? Recorrem la llista buscant qui es pot completar amb el que hi ha disponible; quan un acaba, retorna tot el que tenia assignat:

Al pas 1, P₀ no hi cabia perquè necessita 7 unitats d'A i només n'hi ha 3. L'estat és SEGUR, amb la seqüència ⟨P₁, P₃, P₄, P₂, P₀⟩; n'hi ha d'altres de vàlides, i n'hi ha prou amb trobar-ne una.

Pregunta 2: P₁ (agregador) sol·licita (1, 0, 2). Se li concedeix?

Tres comprovacions en cadena. Sol·licitud ≤ Necessitat? (1,0,2) ≤ (1,2,2), sí, no demana més del que va declarar. Sol·licitud ≤ Disponible? (1,0,2) ≤ (3,3,2), sí, hi ha recursos. L'estat resultant seria segur? Cal simular-ho: Disponible = (3,3,2) − (1,0,2) = (2, 3, 0); Assignat de P₁ = (3,0,2); Necessitat de P₁ = (0, 2, 0). Busquem una seqüència segura en aquest estat hipotètic:

Existeix la seqüència ⟨P₁, P₃, P₄, P₀, P₂⟩: l'estat resultant és segur i la sol·licitud es concedeix.

Pregunta 3: a l'estat original, què passa si P₀ (ingestor) sol·licita (0, 3, 0)? Demana dins del seu màxim i hi ha recursos ((0,3,0) ≤ (3,3,2)), però en simular la concessió, Disponible quedaria en (3, 0, 2): el recurs B s'esgota per complet. Només P₂ podria avançar —necessita (6,0,0), no hi cap: 6 > 3—, en realitat no hi cap ningú, perquè tots els altres necessiten almenys 1 unitat de B i no en queda cap. No existeix seqüència segura: estat insegur, sol·licitud DENEGADA, encara que en aquell instant hi hagués recursos suficients per satisfer-la.

Aquest cas il·lustra l'essència de l'algorisme: denegar una petició que es podria satisfer, perquè conduir el sistema a un estat insegur és un risc que no compensa.

L'algorisme és correcte i elegant, però a la pràctica gairebé ningú no l'aplica, per quatre raons acumulatives:

Aquesta última fila és demolidora: un pthread_mutex_lock costa 20 nanosegons; executar el banquer abans de cadascun costaria mil·lisegons. Seria cinc ordres de magnitud més lent.

On sí que s'utilitza: sistemes encastats de missió crítica amb un conjunt fix i conegut de tasques —aviònica, control industrial—, on el nombre de processos i recursos està congelat en temps de disseny i la certificació exigeix garanties formals. Per a tota la resta, el banquer és una eina conceptual valuosíssima —el concepte d'estat segur estructura el pensament— i una tècnica que no s'implementa.

Si prevenir és car i evitar és impracticable, la tercera via és deixar que passi, detectar-ho i sortir de l'embolic.

La detecció es fa amb el graf espera-per (wait-for graph), una simplificació del graf d'assignació en què s'eliminen els nodes de recurs i es connecta directament Pᵢ → Pⱼ quan Pᵢ espera un recurs que té Pⱼ:

Hi ha interbloqueig si i només si el graf espera-per té un cicle —per a recursos d'una sola instància—. La detecció és un recorregut en profunditat, O(V + E). Per a recursos amb diverses instàncies cal fer servir una variant de l'algorisme del banquer que, en lloc de la necessitat màxima declarada, fa servir la sol·licitud pendent real.

Amb quina freqüència executar-lo? És un compromís genuí:

Una heurística utilitzada en sistemes reals és la tercera: si l'ús de CPU és baix però hi ha molts processos en estat no executable, és sospitós. Linux fa una cosa semblant amb el detector de tasques penjades que veurem a l'apartat 9.

La recuperació té dues vies, i cap no és agradable. La primera és acabar processos: o tots els del cicle (ràpid i brutal) o un cada vegada, reavaluant (lent però menys destructiu). L'elecció de la víctima es fa amb criteris ponderats:

La segona via és el retrocés (rollback): tornar un procés a un punt de control anterior i reintentar-ho. És el que fan les bases de dades —quan PostgreSQL detecta un interbloqueig, avorta la transacció més jove i retorna l'error 40P01 al client, que la pot reintentar—. És la recuperació ideal perquè no es perd feina compromesa, però exigeix que tota la feina sigui transaccional, cosa que un programa en C amb mutexos no té. El perill de totes dues vies és la inanició: si l'algorisme tria sempre la mateixa víctima, aquell procés no acabarà mai, així que cal incloure al criteri quantes vegades ha estat sacrificat ja.

La quarta estratègia és no fer res: ignorar el problema i confiar que sigui prou infreqüent perquè no compensi el cost de tractar-lo. Es coneix com l'algorisme de l'estruç, per la imatge d'amagar el cap sota terra.

Sona a deixadesa, però és una decisió d'enginyeria conscient i és la que prenen Linux, Windows, macOS i pràcticament tots els sistemes operatius de propòsit general per als recursos d'espai d'usuari. Les raons, ordenades per pes:

1. El cost de les alternatives és desproporcionat. Prevenir amb ordre global exigeix coordinar tot el codi del sistema, inclòs el de tercers. Evitar amb el banquer és cinc ordres de magnitud més lent per cada lock. Detectar exigeix mantenir un graf actualitzat de qui espera què, amb la seva pròpia sincronització. Tot això per a una fallada que, ben programat, no passa —i la seva freqüència real és baixa, perquè els interbloqueigs són fallades de programació, no esdeveniments aleatoris del sistema—.

2. El sistema no pot saber què és un interbloqueig i què no. Aquest és l'argument decisiu i el menys obvi. Un procés bloquejat en read() sobre una FIFO buida és indistingible, des del nucli, d'un d'interbloquejat: tots dos esperen un esdeveniment que pot no arribar mai, i el nucli no sap si l'escriptor apareixerà. Distingir «espera legítima» d'«interbloqueig» requereix entendre la intenció del programa, i això el sistema no ho pot fer.

3. Reiniciar és acceptable en la majoria de contextos. Si un servei es penja, systemd el reinicia (mòdul 7) i el sistema continua. El cost d'un reinici ocasional és molt menor que el d'instrumentar tot el sistema.

Ara bé, l'estruç no és universal, i val la pena veure qui sí que actua:

La fila del nucli mereix una nota, perquè és el millor exemple de l'enfocament correcte: lockdep és un validador que s'activa amb CONFIG_PROVE_LOCKING i, durant l'execució, aprèn l'ordre en què es prenen els forrellats i avisa la primera vegada que algú l'inverteix, encara que l'interbloqueig no arribi a produir-se. És el ThreadSanitizer dels bloqueigs: detecta la causa, no el símptoma. El seu cost és alt —un 20-30 % de rendiment— i per això només s'utilitza en nuclis de desenvolupament, però ha evitat milers de penjades en producció.

Tres patologies que es confonen constantment. Convé distingir-les amb precisió, perquè el diagnòstic i la solució són diferents.

L'interbloqueig és l'exemple d'aquesta lliçó: dos fils en S, 0 % de CPU, per sempre. La inanició és un procés llest per executar-se que el planificador no tria mai, o que demana un recurs que sempre es concedeix a altres —l'escriptor de la v1 de lectors-escriptors, amb 3 escriptures en 30 segons—; la diferència clau amb l'interbloqueig és que no hi ha cicle, així que el procés famolenc podria avançar en qualsevol moment si tingués sort, i es resol amb envelliment (pujar la prioritat de qui fa temps que espera) o cues justes.

En el livelock, en canvi, els processos sí que executen instruccions però el seu estat no progressa. La imatge és la de dues persones en un passadís que s'aparten simultàniament al mateix costat, una vegada i una altra:

Si els dos fils executen això alhora i a la mateixa velocitat, poden alternar indefinidament: A pren a, B pren b, A falla a b i deixa anar a, B falla a a i deixa anar b, i tornem a començar. Els dos nuclis al 100 %, zero progrés. És pitjor que un interbloqueig en un sentit: almenys l'interbloqueig no consumeix recursos i és fàcil de veure a top.

La solució és l'espera aleatòria (backoff), la mateixa idea que fa servir Ethernet per resoldre col·lisions:

N'hi ha prou que els reintents no siguin simultanis perquè un dels dos guanyi. Afegir-hi creixement exponencial (espera *= 2 a cada fallada, amb un topall) ho fa robust també sota contenció alta.

Aquesta és la part que faràs servir a la teva feina. Són les tres de la matinada, meteo-api no respon, i cal esbrinar què passa. Els passos, en ordre.

Pas 1: confirmar que està aturat i no treballant.

0,0 % de CPU a tots els fils i estat S: no està calculant, està esperant. Si veiessis 100 % i estat R, seria un bucle infinit o un livelock, no un interbloqueig. Aquesta primera distinció estalvia molt temps.

Pas 2: veure en què està esperant cada fil, amb cat /proc/2841/task/*/wchan. Si la resposta és futex_wait_queue_me a tots, la firma és inconfusible: dormen esperant un futex, és a dir, un mutex, un semàfor o una variable de condició (03-04). Si veiessis pipe_write seria una canonada plena; sk_wait_data, un socket sense dades; io_schedule, E/S de disc pendent. WCHAN acota el tipus d'espera abans de mirar ni una sola línia de codi.

Pas 3: obtenir la pila de cada fil. Aquí gdb és insubstituïble:

El fil 3 està bloquejat al mutex 0x5581e4a2c0c0 des d'api.c:212; el fil 2, al 0x5581e4a2c100 des d'agregador.c:88. Dos fils bloquejats en dos mutexos diferents: el patró exacte de l'interbloqueig. Per confirmar-ho cal esbrinar qui té cada mutex, i l'estructura interna de pthread_mutex_t guarda el TID del propietari:

El cicle queda tancat i demostrat: el fil 2844 espera un mutex que té 2843, i el 2843 n'espera un que té 2844. Interbloqueig confirmat, amb noms de fitxer i números de línia.

Pas 4: el detector hung task del nucli. Per a processos en estat D (espera ininterrompible, típicament E/S), Linux té un vigilant que avisa sol:

Un fil del nucli (khungtaskd) recorre cada 120 segons les tasques en estat D i avisa de les que fa massa temps que hi són. Important: només vigila l'estat D, no S, així que no detecta interbloqueigs de mutex d'usuari —aquests deixen els fils en S—. Serveix per a bloqueigs al nucli: un NFS caigut, un disc que no respon, un forrellat del nucli mal utilitzat.

Pas 5: /proc/<pid>/stack mostra la pila de nucli d'un fil (futex_wait_queue_me → futex_wait → do_futex → __x64_sys_futex → do_syscall_64), confirmant des del costat del nucli el que gdb veu des del costat de l'usuari: el fil va entrar per la crida futex i és a la cua d'espera. Requereix CONFIG_STACKTRACE i permisos de root.

Resum de la caixa d'eines:

Amb les eines anteriors, l'incident complet de Meteora. Símptoma: a les 03:14, el monitoratge avisa que meteo-api retorna temps d'espera esgotats. El servei és viu, no ha reiniciat, no hi ha res nou a /var/log/meteora/meteo-api.log des de les 03:12:47.

Diagnòstic (els cinc passos anteriors, en tres minuts): 0 % de CPU i estat S a tots els fils → futex_wait_queue_me a tots els wchan → gdb revela dos fils bloquejats en mutexos diferents → els __owner d'aquests mutexos tanquen el cicle. Interbloqueig confirmat entre agregador.c:88 i api.c:212.

Causa arrel, en mirar el codi:

Ordres oposats: l'agregador fa memòria cau → fitxer; api_llegir_historic fa fitxer → memòria cau. És l'exemple mínim d'aquesta lliçó, escrit per dues persones diferents en dos fitxers diferents, cadascun perfectament raonable pel seu compte.

Per què va aparèixer justament aquella matinada. Van haver de coincidir tres factors: agg_cicle_horari() s'executa una vegada per hora i només aleshores existeix la finestra; api_llegir_historic() només es crida quan un client demana dades de més de 24 hores, unes 40 vegades al dia; i la finestra entre les dues adquisicions dura uns 200 µs, el que triga calcular_mitjanes_des_de_cache.

Probabilitat per hora ≈ (40/86400 crides/s) × 200 µs × 3600 s ≈ 0,00033: una vegada cada 3.000 hores, uns quatre mesos. Aquest número explica per què el codi va passar totes les proves, feia mesos que era en producció i va fallar una matinada de setembre. Un interbloqueig amb probabilitat ínfima és una certesa a mitjà termini, exactament com les condicions de carrera de 03-01.

Solució immediata (a les 03:20): systemctl restart meteo-api, que restaura el servei en dos segons però no arregla res. Solució definitiva: establir un ordre global de bloqueigs, documentar-lo, i corregir l'ordre a api.c:

Defensa addicional: un embolcall en mode depuració que verifica la jerarquia en temps d'execució, a l'estil de lockdep:

Aquest embolcall detecta la violació la primera vegada que passa, encara que no arribi a produir-se l'interbloqueig. És la mateixa filosofia que ThreadSanitizer i lockdep: buscar la causa, no esperar el símptoma. Compilat només a les proves, el cost en producció és zero.

Cap d'aquestes regles no és teòrica: totes surten d'incidents reals.

1. Defineix i documenta una jerarquia de bloqueigs. És la regla número u, i la que hauria evitat l'incident. Un fitxer de capçalera amb els nivells i un comentari a cada lock indicant el seu. Si tot el codi adquireix en ordre creixent, l'espera circular és matemàticament impossible.

2. Quan no hi hagi ordre natural, ordena per adreça de memòria. El patró if (a < b) lock(a), lock(b); else lock(b), lock(a); funciona per a qualsevol parell i no requereix cap convenció prèvia.

3. Fes servir temps límit en codi de llarga vida. pthread_mutex_timedlock amb 5 o 10 segons converteix una penjada permanent en un error registrat del qual et pots recuperar. Registra sempre la fallada: un temps límit esgotat és un avís que tens un problema de disseny, no una solució.

4. Mantén les seccions crítiques curtes i amb un sol forrellat sempre que puguis. Si no tens mai dos forrellats alhora, no hi ha mai cicle. Moltes vegades n'hi ha prou amb reorganitzar: llegir amb el forrellat, deixar-lo anar, calcular, i tornar-lo a prendre per escriure.

5. No cridis mai codi aliè amb un forrellat pres. És la regla més oblidada i una de les més perilloses. Si dins de la teva secció crítica invoques una callback, un connector, un gestor d'esdeveniments o una biblioteca de tercers, no tens ni idea de quins forrellats prendrà aquell codi. Pot prendre el teu (autobloqueig), pot prendre'n un altre en ordre invers (interbloqueig), pot fer E/S d'un segon. Prepara les dades, deixa anar el forrellat, i crida després.

6. No facis E/S ni reservis memòria dins d'una secció crítica. Un write() a disc pot trigar mil·lisegons i un malloc() pot prendre el seu propi forrellat intern de l'assignador: tots dos multipliquen per mil la finestra de perill. I compte amb PTHREAD_MUTEX_RECURSIVE, que permet prendre el mateix mutex diverses vegades: evita autobloqueigs, però sol delatar que no tens clar qui posseeix què.

7. Executa les proves amb detectors activats. ThreadSanitizer (-fsanitize=thread) detecta també ordres de bloqueig inconsistents, no només carreres. Al nucli, lockdep. Al teu codi, un embolcall com el de l'apartat anterior. Buscar la causa sempre guanya a esperar el símptoma.

8. Prefereix primitives de més alt nivell. Un canal, una cua de missatges o un model d'actors eliminen la classe sencera de problemes: si no prens forrellats, no hi ha cicle possible. La major part del codi d'aplicació es pot escriure sense ni un sol mutex explícit.

Suposar que «funciona a les proves» significa que no hi ha interbloqueig. El cas de Meteora tenia una probabilitat de 0,00033 per hora i va sobreviure mesos en producció abans de manifestar-se. Les proves no troben interbloqueigs; les anàlisis d'ordre de bloqueig, sí.

Revisar funcions aïllades. Cadascuna de les dues funcions de l'incident era impecable per separat. La fallada era a la relació entre elles, i només una revisió que miri tots els llocs on es prenen aquells dos forrellats la detecta.

Confondre interbloqueig amb inanició o amb livelock. Si hi ha CPU al 100 %, no és interbloqueig: és livelock o un bucle. Si un component avança però molt a poc a poc, és inanició. top -H els distingeix en cinc segons i evita hores de cerca en la direcció equivocada.

Afegir un forrellat recursiu per «arreglar» un autobloqueig. L'autobloqueig és el símptoma que no saps quins forrellats tens presos en arribar a aquella funció; RECURSIVE l'amaga i deixa el problema de disseny intacte.

Posar temps límit i no registrar-ne les fallades, o cridar una callback amb un forrellat pres. Un timedlock que expira en silenci converteix una penjada visible en una degradació invisible: registra sempre, amb el nom del forrellat. I cridar codi aliè dins d'una secció crítica és la via més ràpida a un interbloqueig entre el teu codi i una biblioteca que no controles.

Consell: dibuixa el graf quan dubtis. Davant de dos o tres forrellats i diversos fluxos, fer el graf d'assignació en un paper triga dos minuts i revela el cicle immediatament. És l'eina de raonament més rendible d'aquesta lliçó.

Consell: si necessites dos forrellats sovint, planteja't si haurien de ser un. Dos forrellats que gairebé sempre es prenen junts protegeixen, probablement, un mateix invariant. Fusionar-los elimina el problema d'arrel i sovint simplifica el codi.

Escriu el programa de dos fils amb dos mutexos en ordre invers i executa'l fins que es pengi. Diagnostica'l seguint els cinc passos de l'apartat 9: top -H, wchan, gdb amb les piles, i identificació del propietari de cada mutex. Documenta el que veus a cada pas. Després arregla'l amb l'ordre per adreça de memòria i verifica que ja no es penja en 10 milions d'iteracions. Finalment, elimina els usleep de la versió trencada i mesura quant triga a penjar-se sense ells, repetint la mesura cinc vegades.

Un sistema té 3 tipus de recurs amb (12, 8, 6) unitats totals i quatre processos:

Calcula la matriu de Necessitat i el vector Disponible. Determina si l'estat és segur i, si ho és, dona'n una seqüència segura. Després avalua dues sol·licituds per separat, sempre des de l'estat original: P₂ demana (1, 1, 0) i P₀ demana (3, 2, 1). Justifica cada decisió amb les matrius completes.

Per a cada situació, identifica si és interbloqueig, inanició, livelock o cap de les tres, indica què veuries a top -H i wchan, i proposa una solució.

• (a) Dos fils de meteo-api amb un 0 % de CPU en estat S; un espera el mutex A que té l'altre, i a l'inrevés.
• (b) L'agregador no aconsegueix escriure a la memòria cau des de fa 40 segons perquè els 4 treballadors llegeixen sense parar amb un rwlock.
• (c) Dos fils al 100 % de CPU en estat R; tots dos prenen un forrellat, veuen que l'altre està ocupat, deixen anar el seu i reintenten immediatament.
• (d) L'ingestor fa 5 minuts que està bloquejat en read() sobre /run/meteora/lectures.fifo perquè ningú no hi escriu.
• (e) Un fil crida dues vegades seguides pthread_mutex_lock sobre el mateix mutex no recursiu.

Solució 1

Diagnòstic pas a pas del programa penjat (PID 9412):

El primer pas descarta livelock i bucle infinit (0 % de CPU i estat S signifiquen aturat, no treballant); el segon acota l'espera a un futex, és a dir, a un mutex, semàfor o variable de condició; el tercer dona fitxer i línia de cada bloqueig; i el quart tanca el cicle: 9413 té la memòria cau i espera el fitxer, que el té 9414; 9414 té el fitxer i espera la memòria cau, que la té 9413. Interbloqueig confirmat entre deadlock.c:18 i deadlock.c:31.

Arranjament amb ordre per adreça:

Amb 10.000.000 d'iteracions i sense usleep, cap de les 20 execucions no es va penjar (0,71 s de mitjana). Els dos fils prenen sempre el mutex d'adreça més baixa primer, així que l'espera circular no es pot formar.

Sense els usleep, a la versió trencada, les iteracions que aguanta abans de penjar-se en cinc execucions van ser 47.219 (0,08 s), 3.106.884 (4,91 s), 812 (0,002 s), 18.443.201 (31,2 s) i 291.556 (0,47 s).

Quatre ordres de magnitud de diferència entre la més ràpida i la més lenta, sense canviar ni una sola línia. Aquesta és la naturalesa del problema: la finestra entre les dues adquisicions dura uns pocs nanosegons i l'interbloqueig requereix que el planificador expulsi justament allà. Amb prou iteracions sempre passa, però quan és impredictible. En producció, amb seccions crítiques de microsegons i operacions que passen unes desenes de vegades al dia, aquest «sempre» es tradueix en mesos.

Solució 2

Necessitat = Màxim − Assignat:

Disponible = (12, 8, 6) − (8, 6, 4) = (4, 2, 2)

És segur l'estat?

Estat SEGUR, amb la seqüència ⟨P₁, P₀, P₃, P₂⟩. (Al pas 1, P₃ també hi cabria —(3,2,2) davant de (4,2,2)—, així que hi ha més seqüències vàlides.)

Sol·licitud A: P₂ demana (1, 1, 0). Compleix les dues primeres comprovacions —(1,1,0) ≤ Necessitat (6,4,2) i ≤ Disponible (4,2,2)—, així que ho simulem: Disponible = (3,1,2), Assignat P₂ = (3,2,2), Necessitat P₂ = (5,3,2).

Seqüència segura ⟨P₁, P₀, P₃, P₂⟩. ES CONCEDEIX.

Sol·licitud B: P₀ demana (3, 2, 1). També compleix les dues primeres —(3,2,1) ≤ Necessitat (4,3,2) i ≤ Disponible (4,2,2)—, però en simular-ho, Disponible queda en (1, 0, 1) i Necessitat de P₀ en (1,1,1). Ara no hi cap ningú: P₀ necessita 1 de B i n'hi ha 0; P₁ necessita 2 d'A i 1 de B, i n'hi ha 1 i 0; P₂ i P₃ són molt més lluny. Cap procés no es pot completar, no existeix seqüència segura, l'estat resultant és insegur i LA SOL·LICITUD ES DENEGA.

Compara les dues: a A quedaven (3,1,2), suficient perquè P₁ acabés i alliberés els seus recursos, engegant la cadena. A B el recurs B s'esgota per complet, deixant els quatre processos incapaços d'assolir el seu màxim. Aquest és exactament l'escenari que el banquer existeix per impedir: no un interbloqueig actual, sinó la possibilitat d'un si tots demanessin el seu màxim.

Solució 3

Comentaris sobre els casos que més es confonen:

(b) davant d'(a). La diferència és que en la inanició el sistema en conjunt sí que progressa: els lectors completen milions d'operacions. Només un component està aturat, i podria avançar en qualsevol moment si hi hagués un forat. No hi ha cicle, i per això gdb mostraria l'agregador esperant un forrellat el propietari del qual canvia constantment, en lloc d'estar fix. Aquest és l'indici diferencial: si mirant dues vegades amb un segon de diferència l'__owner és diferent, és inanició, no interbloqueig.

(c) és el més fàcil d'identificar i el més fàcil de confondre de lluny. L'estat R i el 100 % de CPU el delaten immediatament: un interbloqueig mai no consumeix CPU. Si el servei no respon però els nuclis estan al màxim, no busquis un cicle de forrellats; busca un bucle de reintents o un bucle infinit.

(d) és la raó per la qual el sistema operatiu no pot detectar interbloqueigs automàticament. Des del nucli, aquest cas és indistingible d'(a): un procés en S esperant un esdeveniment que potser no arribarà mai. La diferència només existeix en la intenció del programa —hauria d'arribar algú a escriure en aquella FIFO?—, i aquesta informació el nucli no la té. És l'argument 3 de l'apartat sobre l'estruç, en forma concreta.

(e) produeix el mateix quadre clínic que (a) però amb un sol fil implicat, i a gdb es veu de seguida: l'__owner del mutex és el TID del mateix fil que espera. És un cicle de longitud 1.

Un interbloqueig és un conjunt de processos on cadascun espera un esdeveniment que només un altre del conjunt pot produir, i l'espera és permanent. L'hem construït en vint línies —dos mutexos presos en ordre invers— i hem vist que cada funció era correcta per separat: la fallada viu en la relació entre elles, que és per això que cap revisió de codi aïllada no la troba.

Les quatre condicions de Coffman —exclusió mútua, retenció i espera, absència d'expropiació i espera circular— són necessàries totes alhora, i aquest és el seu valor: n'hi ha prou amb trencar-ne una. La primera és gairebé sempre irrompible, la segona costa concurrència i inanició, la tercera exigeix poder desfer feina, i la quarta es trenca amb un ordre global d'adquisició a cost zero. El graf d'assignació de recursos dona el model formal: amb recursos d'una sola instància, un cicle és condició necessària i suficient.

De les quatre estratègies, la prevenció per ordre global és la que faràs servir sempre, i la seva demostració és de dues línies: si els ordres creixen estrictament al llarg d'un cicle, en tancar-lo tindríem k > k. L'evitació amb l'algorisme del banquer, que hem resolt amb matrius completes, formalitza la idea valuosa d'estat segur, però exigeix conèixer les necessitats màximes per endavant i costa O(n²m) per sol·licitud —cinc ordres de magnitud més que el lock que protegeix—, així que només s'utilitza en sistemes encastats crítics. La detecció i recuperació amb graf espera-per és la via de les bases de dades, que poden avortar transaccions sense perdre consistència, amb tot el problema de triar la víctima sense produir inanició. I l'estratègia de l'estruç és la que adopten Linux, Windows i macOS per a l'espai d'usuari, per una raó que va més enllà del cost: el sistema no pot distingir una espera legítima d'un interbloqueig, perquè això exigiria conèixer la intenció del programa. El nucli, en canvi, sí que es protegeix, amb lockdep verificant l'ordre dels forrellats.

Hem separat l'interbloqueig dels seus dos cosins: la inanició, on el sistema progressa però un component no, sense cicle i potencialment resoluble; i el livelock, on els processos executen al 100 % de CPU sense progressar, que es cura amb espera aleatòria. top -H els distingeix en cinc segons: 0 % i S és interbloqueig; 100 % i R és livelock.

I el més útil: el procediment de diagnòstic. top -H per confirmar que està aturat; wchan per saber el tipus d'espera (futex_wait_queue_me és la firma dels mutexos); gdb -p ... -ex "thread apply all bt" per a les piles de tots els fils; i print sobre l'estructura del mutex per llegir-ne l'__owner i tancar el cicle amb noms de fitxer i línies. El cas de Meteora es va resoldre així en tres minuts: agregador.c:88 prenia memòria cau→fitxer i api.c:212 fitxer→memòria cau, amb una probabilitat de coincidència d'una vegada cada quatre mesos, que explica per què va passar totes les proves. La solució va ser una jerarquia de bloqueigs documentada —config, memòria cau, fitxer, registre— més un embolcall que avorta en proves quan algú la viola.

Amb això s'acaba el mòdul, i val la pena veure el recorregut complet. Vas començar entenent què va malament (03-01): concurrència davant de paral·lelisme, l'entrellaçament com a model mental, i comptador++ descompost en tres instruccions màquina que perden mig milió d'increments. Allà van aparèixer la secció crítica i els seus tres requisits —exclusió mútua, progrés, espera limitada— que han servit de criteri a tot el mòdul, juntament amb la llei d'Amdahl i el seu sostre de 3,57× per a l'agregador.

Després vas conèixer els protagonistes (03-02): el fil com a flux amb només tres coses privades —comptador de programa, registres i pila—, la taula exhaustiva de què comparteix i què no, els 22 µs davant dels 180 µs que justifiquen la seva existència, i la revelació que Linux no implementa fils sinó clone(), amb el GIL de Python mesurat sense mites. A l'IPC (03-03) vas resoldre com parlen processos que no comparteixen memòria: canonades amb la seva memòria intermèdia de 65.536 bytes i la seva contrapressió, FIFO, cues POSIX amb prioritats, memòria compartida sobre /dev/shm/meteora-cache, sockets i senyals. I va quedar marcat l'asterisc: la memòria compartida transporta dades però no coordina ningú.

Aquest asterisc es va pagar a sincronització (03-04), la lliçó central: tres intents ingenus que fallen, Peterson i el seu límit en el maquinari real, compare-and-swap com a fonament de tot, i sobre ell spinlocks, mutexos, semàfors, variables de condició, rwlocks i barreres. Amb futex explicant per què un mutex costa 20 ns —841 crides al sistema per a dos milions d'adquisicions—, volatile desmuntat, i la granularitat mesurada en 7,25× amb particionat. Els problemes clàssics (03-05) et van donar el vocabulari: productor-consumidor amb els seus tres semàfors i el parany de l'ordre dels wait; lectors-escriptors amb la seva inanició mesurada en 3 escriptures per cada 30 segons; filòsofs i el seu cicle; barber dormilega com el grup de fils de meteo-api. I aquesta última lliçó va tancar el cercle explicant per què funcionaven les solucions dels filòsofs.

Si el mòdul 2 responia a com es reparteix un recurs escàs, el mòdul 3 ha respost a com es coordinen diversos fluxos sobre una dada compartida, i la resposta ha tingut sempre la mateixa forma: una operació indivisible que el maquinari garanteix, una primitiva del sistema construïda sobre ella, i una disciplina de disseny que el programador ha de respectar. Les tres capes són necessàries; cap no basta tota sola.

Però fixa't en una cosa. Tot aquest mòdul ha passat en memòria: comptadors, memòries cau, estructures compartides, tot volàtil, tot perdut si meteo-01 s'apaga. I tanmateix fa tres mòduls que anomenem /var/lib/meteora/lectures/2026-08-31.dat, /etc/meteora/meteora.conf i /var/log/meteora/meteo-api.log com si fossin obvis. Què és exactament un fitxer? Com sap el sistema en quins blocs del disc són els seus 17 MB? Què passa de debò quan obres una ruta com /var/lib/meteora/lectures/, i per què aquesta ruta s'assembla tan poc al que hi ha al SSD? I com sobreviu tot això a un tall de llum enmig d'una escriptura?

És el Mòdul 4: Estructures de Fitxers, i comença a Sistemes de Fitxers.