Aquesta és la lliçó central del mòdul. En portem tres deixant asteriscos: un comptador++ que perd increments, un n_ultimes++ a /dev/shm/meteora-cache que fa el mateix entre processos, una struct Lectura de 24 bytes que es pot llegir a mitges. Sabem què és una secció crítica i quins tres requisits ha de complir una solució. Sabem muntar el canal entre processos. El que encara no tenim és el protocol que impedeix que dos fluxos hi entrin alhora.

Aquí el construïm de baix a dalt, perquè és l'única manera d'entendre per què les primitives són com són. Començarem intentant resoldre'l només amb variables normals —fracassant de tres maneres diferents, cadascuna instructiva—; veurem per què el problema és irresoluble sense ajuda del maquinari; coneixerem les instruccions atòmiques que la CPU ofereix per a això; i sobre elles aixecarem spinlocks, mutexos, semàfors, variables de condició, bloqueigs de lectura/escriptura i barreres. Acabarem mirant com ho implementa Linux amb futex, per què volatile no serveix per a res d'això, i quant costa realment la contenció en microsegons mesurats.

1. El problema de la secció crítica, formalitzat
2. Intents ingenus que fallen
3. La solució de Peterson i els seus límits reals
4. Suport del maquinari: test-and-set i compare-and-swap
5. Un comptador atòmic per a meteo-api
6. Espera activa i spinlocks
7. Bloqueig amb suspensió i el paper del planificador
8. Mutex POSIX: el comptador de Meteora arreglat
9. Semàfors comptadors i binaris
10. Variables de condició i monitors
11. Bloqueigs de lectura/escriptura i barreres
12. Com ho implementa Linux: futex
13. Barreres de memòria i per què volatile no serveix
14. Granularitat del bloqueig i cost de la contenció

Recordem el plantejament amb precisió. Tenim n fluxos que repeteixen el cicle entrada(); seccio_critica(); sortida(); resta();, i cal dissenyar entrada() i sortida() de manera que es compleixin els tres requisits de Conceptes de Concurrència:

1. Exclusió mútua: mai dos fluxos dins de la secció crítica alhora.
2. Progrés: si està lliure i algú vol entrar, la decisió no es posposa indefinidament, i els que són a resta() no hi participen.
3. Espera limitada: hi ha un límit al nombre de vegades que altres entren abans que et toqui.

I dos supòsits que no es poden violar: no es pot suposar res sobre la velocitat relativa dels fluxos (un pot anar mil vegades més ràpid, o quedar-se aturat un segon sencer per una expulsió del planificador) ni sobre el nombre de nuclis. Intentarem resoldre'l amb el que tenim —variables compartides normals—, fracassant tres vegades; cada fracàs ensenya alguna cosa que necessitarem després.

La idea més natural: una variable ocupat que poso a 1 mentre sóc a dins.

Falla l'exclusió mútua, el requisit més important. La traça: a t1 el fil A llegeix ocupat → 0 i surt del while; a t2 el planificador l'expulsa abans que escrigui, i B llegeix ocupat → 0 i també surt; a t3 B escriu ocupat = 1 i entra; a t4 A escriu ocupat = 1 i entra també.

Tots dos a dins. El motiu és el que ja coneixem: comprovar i actuar són dues operacions separades, amb una finestra entre elles. És el check-then-act de 03-01 aplicat al forrellat mateix, i la ironia és notable: el mecanisme destinat a protegir una secció crítica conté ell mateix una secció crítica sense protegir. Aquesta és la raó de fons per la qual el problema és irresoluble amb lectures i escriptures normals: necessitem comprovar i modificar en un sol pas indivisible, i cap variable de C no ens ho dona.

Alternem rigorosament, amb una variable que diu de qui és el torn:

Ara sí que hi ha exclusió mútua: torn té un sol valor, així que només un passa el while, i com que l'escriptura d'un int alineat és atòmica no hi ha cap finestra. Però falla el progrés, i de manera greu. Si el fil A surt de la seva secció crítica posant torn = 1, i el fil B decideix no tornar a entrar perquè està ocupat a resta(), aleshores B no posarà mai torn = 0 i A espera per sempre amb la secció crítica lliure. Això viola directament la clàusula que diu que un flux que és a resta() no ha de participar en la decisió. I a la pràctica és un desastre de rendiment: si A hi entra mil vegades per segon i B una vegada per minut, A queda limitat a una entrada per minut. El torn estricte imposa a tothom el ritme del més lent.

Separem «vull entrar» de «sóc a dins», amb una bandera per fil:

Ara sí que hi ha exclusió mútua (si tots dos fossin a dins, tots dos haurien hagut de veure la bandera de l'altre a 0 després de posar la seva a 1, cosa impossible) i sí que hi ha progrés davant d'un fil inactiu. Però falla d'una manera nova i pitjor: si A posa vol[0] = 1 i, abans d'arribar al seu while, B posa vol[1] = 1, aleshores tots dos entren al seu bucle d'espera i cap no en surt mai. Cadascun espera que l'altre renunciï, i cap no renuncia perquè està bloquejat esperant. És un interbloqueig, el tema d'Interbloquejos, fabricat aquí en cinc línies.

Una variant temptadora és «si veig que l'altre també vol, retiro la meva bandera un moment i ho torno a provar». Això evita l'interbloqueig però introdueix un livelock: tots dos poden retirar i reposar les seves banderes sincronitzadament per sempre, cadascun cedint educadament a l'altre sense que cap avanci. És la versió informàtica de dues persones que es creuen en un passadís i s'aparten al mateix costat una vegada i una altra. Resum dels tres intents:

Gary Peterson va publicar el 1981 la solució més elegant al problema per a dos fluxos, combinant les dues idees anteriors: les banderes diuen qui vol entrar, i el torn desempata.

La línia (2) és la genial, i és contraintuïtiva: cedeixo el torn a l'altre justament quan jo vull entrar. Per què funciona, requisit per requisit:

Exclusió mútua. Perquè tots dos fossin a dins, tots dos haurien sortit del while. A surt si vol[B] == 0 o si torn == A; B surt si vol[A] == 0 o si torn == B. Si tots dos són a dins, tots dos van posar la seva bandera a 1, per tant les dues primeres condicions són falses i quedaria torn == A i torn == B alhora: impossible, perquè torn és una sola variable. Contradicció. Progrés. Si B no vol entrar, la seva bandera és a 0 i A passa directament; si tots dos volen, torn té un sol valor i un dels dos passa. Espera limitada. Quan A surt i vol tornar a entrar, posa torn = B, així que si B esperava, ara passa: A pot avançar-se a B com a molt una vegada, el millor límit possible.

Si intercanviessis les línies (1) i (2) la solució deixaria de ser correcta. I si tots dos executen (2) gairebé alhora, el segon a escriure guanya el desempat —la seva escriptura de torn és la que queda— i el primer passa: un desempat que es resol tot sol, sense cap operació atòmica composta.

Peterson és un resultat teòric preciós que a la pràctica no s'utilitza mai, per tres raons que expliquen tot el que ve després. Només funciona per a dos fils: existeix una generalització a n —l'algorisme del filtre, o el del forn de Lamport— però requereix n passos d'espera i arrays de mida n, així que no escala. És espera activa pura: aquest while (...) ; crema un nucli sencer, cosa que és catastròfica amb més fils que nuclis, perquè el que espera consumeix el seu quantum sense avançar mentre el que té el forrellat no es pot executar.

I la tercera, la raó definitiva: la reordenació de memòria. Peterson és correcte sobre un model de memòria seqüencialment consistent, on tots els nuclis veuen les escriptures en el mateix ordre. Cap processador modern no compleix això. A x86-64 una escriptura passa primer pel store buffer del nucli abans de fer-se visible a la resta, i el processador pot avançar una lectura posterior a una escriptura anterior a una altra adreça. Al codi de dalt, el processador pot executar la lectura de vol[altre] abans que l'escriptura de vol[jo] hagi sortit del store buffer i sigui visible per a l'altre fil. Si tots dos fan el mateix simètricament, tots dos llegeixen la bandera del contrari a 0 i tots dos entren. L'exclusió mútua es trenca, no per una fallada de l'algorisme, sinó perquè el maquinari no executa el que el codi diu, sinó una cosa equivalent per a un sol fil.

Perquè Peterson funcioni en maquinari real cal inserir una barrera explícita, __atomic_thread_fence(__ATOMIC_SEQ_CST);, entre l'escriptura de torn i el bucle d'espera. I aquesta línia és la porta d'entrada a tot el que segueix: la sincronització correcta necessita suport del maquinari, no n'hi ha prou amb escriure codi llest. Tornarem sobre les barreres de memòria a l'apartat 13.

El problema de fons de tots els intents era el mateix: comprovar i modificar són dues operacions i hi ha una finestra entre elles. La solució és que el processador ofereixi una instrucció que faci les dues coses de manera indivisible, i totes les arquitectures modernes la tenen en dues variants.

CAS és estrictament més potent que test-and-set i és la primitiva sobre la qual es construeix pràcticament tot. A x86-64 s'implementa amb lock cmpxchg; el prefix lock és el que fa la màgia: durant aquesta instrucció, el nucli obté la línia de memòria cau en estat exclusiu i cap altre no la pot modificar.

En C11 no cal escriure assemblador: GCC i Clang ofereixen les funcions __atomic_* i l'estàndard defineix <stdatomic.h>:

Això ja sí que compleix l'exclusió mútua, sense trucs ni barreres manuals, i per a qualsevol nombre de fils: el bucle ho torna a provar mentre un altre tingui el forrellat, i tan bon punt el deixa anar un CAS té èxit i només un guanya, perquè la comparació i l'escriptura són indivisibles.

Dos detalls del CAS de C11 que confonen la primera vegada. atomic_compare_exchange_weak modifica esperat quan falla, deixant-hi el valor real que ha trobat, i per això cal reposar-lo a 0 dins del bucle; la versió _strong no pot fallar espúriament però és una mica més lenta en algunes arquitectures, així que en un bucle de reintent fes servir sempre _weak. I existeix atomic_flag_test_and_set, la primitiva de test-and-set, garantida com a lliure de bloqueigs a totes les plataformes.

Comparant-les: totes dues serveixen per a forrellats i totes dues costen el mateix (~20 ns sense contenció, ~500 ns amb 8 nuclis barallant-s'hi), però només CAS serveix per a comptadors, piles i cues sense forrellats, perquè pot condicionar l'escriptura al valor previ. A canvi, CAS arrossega el conegut problema ABA en estructures amb punters. Aquests 20 nanosegons davant de l'~1 ns d'una escriptura normal són el preu de l'atomicitat: la instrucció negocia la propietat exclusiva de la línia de memòria cau amb la resta de nuclis a través del protocol de coherència. 20 vegades més car que una escriptura normal, i aquest número és la raó de tot l'apartat 14 sobre granularitat.

Amb això ja podem arreglar el primer asterisc del mòdul: peticions_totals++ a /dev/shm/meteora-cache.

Tres coses per aprendre d'aquest exemple.

atomic_fetch_add és l'operació que necessitàvem: llegir-sumar-escriure de manera indivisible, en una sola instrucció (lock xadd a x86-64). Ja no hi ha finestra entre la lectura i l'escriptura, i per tant no hi ha increments perduts. Mai.

memory_order_relaxed és una optimització conscient i aquí és correcta. Per defecte, les operacions atòmiques de C11 fan servir memory_order_seq_cst, que a més de ser atòmiques imposen un ordre global entre totes les operacions de tots els fils, cosa que obliga a barreres costoses. Per a un comptador d'estadístiques no necessitem cap ordre: només que la suma sigui correcta, no que el seu valor coordini res més. relaxed dona atomicitat sense ordenació i és notablement més ràpid:

Compte: relaxed només és correcte quan el valor no s'utilitza per deduir res sobre altres variables; si el comptador fos una bandera del tipus «les dades ja són llestes», seria un error greu, i en cas de dubte el mode per defecte és més lent però mai incorrecte. Fixa't a més que un comptador atòmic és molt més barat que un mutex: 0,192 s davant de 0,687 s, 3,6 vegades més ràpid. Regla general: si la secció crítica és una sola operació sobre una sola variable, fes servir un atòmic, no un forrellat. I per a Meteora, amb processos i no fils, els tipus atòmics funcionen igual entre processos quan la variable és a memòria compartida, sempre que atomic_is_lock_free() sigui cert —si no ho fos, la implementació faria servir un forrellat intern de la biblioteca, privat de cada procés i per tant inútil—. Per a tipus de 8 bytes o menys a x86-64, sempre ho és.

El forrellat que hem construït amb CAS té una característica que cal examinar: l'espera activa (busy waiting o spinning). El fil que no aconsegueix el forrellat es queda donant voltes en un bucle, consumint CPU sense avançar, i aquest tipus de forrellat s'anomena spinlock (forrellat giratori).

Aquesta instrucció pause li diu al processador «sóc en un bucle d'espera»: redueix el consum d'energia, evita la penalització per especulació fallida en sortir del bucle i, amb hyperthreading, cedeix recursos d'execució al fil germà. Un spinlock sense pause pot ser 2 o 3 vegades més lent que un que en tingui. És una línia que la gent oblida constantment.

Quan té sentit cremar CPU esperant? La decisió es redueix a comparar dos números: adormir-se i despertar-se costa ~2-5 µs (dos canvis de context més la gestió de la cua d'espera), i girar costa el que duri la secció crítica. Si la secció crítica dura menys que el cost d'adormir-se, girar surt més barat; si dura més, guanya dormir.

L'última fila descriu el desastre clàssic: amb un sol nucli, el fil A amb el forrellat i el fil B girant, B consumeix el seu quantum sencer —mil·lisegons— sense avançar, perquè A no es pot executar per deixar-lo anar. L'spinlock ha convertit una espera de 50 nanosegons en una de diversos mil·lisegons: un factor de 100.000. Existeix a més la inversió de prioritat: un fil de baixa prioritat té el forrellat, un d'alta gira esperant-lo, i el planificador no executa mai el de baixa perquè el d'alta està llest, així que el sistema es penja. Va ser la causa de la famosa fallada del Mars Pathfinder el 1997, que es reiniciava periòdicament a Mart, i la solució és l'herència de prioritat —el posseïdor hereta temporalment la prioritat del que espera—, que a POSIX s'activa amb pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT).

A Linux, spin_lock() és la primitiva estàndard del nucli, precisament perquè en context d'interrupció no hi ha alternativa: no es pot dormir. En espai d'usuari existeix pthread_spinlock_t, però el seu ús correcte és rar.

L'alternativa a girar és dormir: si el forrellat està ocupat, el flux demana al nucli que el suspengui i el desperti quan estigui lliure. El mecanisme complet, connectant amb el mòdul 2: el fil intenta adquirir el forrellat amb una operació atòmica i falla; crida el nucli, que el posa en estat S (adormit interrompible) i l'encua a la cua d'espera associada al forrellat; el planificador el treu de la cua de llestos i en tria un altre, amb zero CPU consumida; quan el posseïdor l'allibera, el nucli treu un fil d'aquella cua i el posa en R; i el planificador l'executarà quan li toqui segons el seu vruntime.

Comparades, girar consumeix el 100 % d'un nucli mentre espera i dormir el 0 %; girar és desastrós amb més fils que nuclis i dormir és impossible en context d'interrupció; girar desperta a l'instant i dormir depèn del planificador. Però l'observació decisiva és una altra: quan no hi ha contenció, totes dues costen el mateix (~20 ns), perquè totes dues es redueixen a una operació atòmica que té èxit a la primera. Aquesta és l'observació que dona lloc al disseny de futex i la que explica per què un mutex POSIX és gairebé gratis en el cas comú.

Un mutex (de mutual exclusion) és la primitiva estàndard d'exclusió mútua en espai d'usuari. Les seves dues propietats definitòries són que és binari (lliure o ocupat, sense estats intermedis) i que té propietari: només el fil que el va bloquejar el pot desbloquejar.

La sortida és Esperat: 2000000 Obtingut: 2000000 Temps: 0.412 s. Ara sí que està resolt el problema complet: no només el comptador, sinó l'escriptura de la struct Lectura de 24 bytes, que cap tipus atòmic no pot fer indivisible per si sol. Un mutex protegeix una regió de codi arbitràriament complexa, i aquest és el seu avantatge davant dels atòmics.

Dues decisions de disseny de l'exemple que convé copiar. El forrellat viu dins de l'estructura que protegeix, la convenció que fa el codi mantenible: qui vegi struct cache_meteora sap immediatament quin forrellat protegeix quines dades, mentre que un mutex global solt en un altre fitxer és una font inesgotable d'oblits. I la secció crítica és com més curta millor: tot el que no necessiti protecció (calcular l, preparar la resposta HTTP, escriure al registre) va fora, perquè com més temps es tingui el forrellat, més esperen els altres i pitjor escala.

Per a processos diferents, com els treballadors de meteo-api que comparteixen /dev/shm/meteora-cache, cal declarar-lo compartit entre processos explícitament, o no funcionarà:

PTHREAD_MUTEX_ROBUST resol un problema específic dels processos: si un treballador mor amb el forrellat pres, sense robust el forrellat queda bloquejat per sempre i tots els altres es pengen; amb robust, el següent que ho intenti rep EOWNERDEAD, pot reparar l'estat inconsistent i cridar pthread_mutex_consistent() per reactivar-lo. És la diferència entre un servei que es recupera de la mort d'un treballador i un que es queda penjat fins que algú el reinicia a mà.

Els números anteriors mereixen mirar-se junts. Amb 4 fils incrementant el mateix comptador 500.000 vegades cadascun:

Dues lliçons quantitatives: el mutex costa uns 200 ns per operació amb contenció moderada, unes 30 vegades més que l'operació desprotegida; i, més important, el cost per operació creix amb el nombre de fils —de 4 a 16 fils, el cost unitari es multiplica per 2,6—. No només no escala: empitjora. És l'escalabilitat negativa que anticipàvem a 03-01 en parlar de la llei d'Amdahl, i la raó que l'apartat 14 tracti sobre granularitat.

Un semàfor, inventat per Dijkstra el 1965, és un comptador enter no negatiu amb dues operacions atòmiques: wait() (històricament P, de proberen) decrementa el comptador i, si queda negatiu, bloqueja el flux; post() (històricament V, de verhogen) l'incrementa i, si hi havia algú bloquejat, en desperta un. La interpretació intuïtiva és directa: el comptador representa quantes unitats del recurs queden disponibles.

En executar-lo es veu l'efecte: les peticions 0, 1 i 2 comencen immediatament; la 3 no comença fins que una de les tres acaba, uns 200 ms després. Deu peticions triguen 800 ms (quatre tandes de 200 ms) en lloc dels 200 ms que trigarien totes alhora. El semàfor ha imposat un límit de concurrència de 3, que és exactament el que volíem. Un semàfor inicialitzat a 1 s'anomena semàfor binari i sembla equivalent a un mutex. No ho és, i la diferència importa:

La propietat separa els dos usos, i d'aquí surt la regla pràctica: per protegir dades compartides, mutex —la propietat converteix en error detectable el desbloqueig per un altre fil, permet herència de prioritat i expressa millor la intenció—; per senyalitzar que alguna cosa ha passat o comptar recursos, semàfor —un productor fa sem_post i un consumidor sem_wait: són fluxos diferents per disseny, i allà un mutex seria incorrecte—. L'última fila de la taula hi afegeix un detall útil: sem_post() és de les poquíssimes funcions segures dins d'un gestor de senyal (ho vam veure a la lliçó d'IPC), cosa que la converteix en la manera canònica que un gestor desperti el bucle principal.

Els semàfors POSIX vénen sense nom (sem_init, per a fils, o per a processos si és a memòria compartida i el segon argument és 1) i amb nom (sem_open("/meteora-places", ...), que crea /dev/shm/sem.meteora-places i serveix per a processos sense parentiu).

Els mutexos resolen «només un alhora» i els semàfors «com a molt N alhora». Falta un tercer problema, molt diferent: esperar que es compleixi una condició sobre les dades. El cas típic: un treballador de meteo-api vol respondre amb dades fresques, però l'agregador encara no ha actualitzat la memòria cau, així que necessita esperar que n_ultimes > 0. Sense eines, l'única opció seria girar comprovant, i girar amb un mutex pres és un interbloqueig garantit.

Una variable de condició és una cua d'espera associada a una condició lògica, amb tres operacions: wait(cond, mutex) deixa anar el mutex atòmicament, dorm, i en despertar-se el torna a prendre; signal(cond) en desperta un dels que esperen; broadcast(cond) els desperta tots.

Aquesta paraula «atòmicament» és la clau de tot el mecanisme: si deixar anar el mutex i adormir-se fossin dos passos, un altre fil s'hi podria colar entremig, canviar la condició i fer signal abans que dormíssim, amb la qual cosa la senyal es perdria i dormiríem per sempre. És el problema de la senyal perduda (lost wakeup), i l'atomicitat de wait és el que ho impedeix.

La regla més important d'aquesta lliçó: pthread_cond_wait va SEMPRE dins d'un bucle while, mai d'un if. Hi ha tres raons independents i n'hi ha prou amb una per justificar-ho. Despertars espuris: POSIX permet explícitament que pthread_cond_wait retorni sense que ningú hagi fet signal —no és una fallada d'implementació, permetre-ho la fa més simple i ràpida, i a Linux passa de debò quan una senyal interromp l'espera—. Un altre fil pot haver-se avançat: amb broadcast es desperten tres consumidors però només hi ha una lectura disponible; el primer a recuperar el mutex la consumeix i els altres dos troben la condició falsa una altra vegada. I la condició pot haver canviat per una altra via, perquè en codi real més d'un lloc modifica l'estat.

Amb while, qualsevol d'aquests casos simplement torna a dormir; amb if, produeix corrupció silenciosa. Aquest error és probablement el més comú de tota la programació concurrent, i el que surt més car perquè falla poques vegades. Entre signal i broadcast, l'elecció és: signal en desperta un i és més barat, però mal utilitzat pot despertar el fil equivocat i deixar-los tots adormits; broadcast els desperta tots, és més car (tempesta de despertars) i no pot fallar. Fes servir broadcast si tens dubtes; signal només quan tots els que esperen comprovin la mateixa condició i hi hagi una sola unitat disponible.

Un monitor empaqueta les dades, el mutex i les variables de condició en una unitat on l'exclusió mútua és automàtica. Java el té amb synchronized; Python l'ofereix amb threading.Condition, que incorpora el seu propi forrellat:

La correspondència és exacta: with self._cond és el parell lock/unlock, wait() deixa anar el forrellat atòmicament i el recupera en despertar-se, notify()/notify_all() són signal/broadcast, i la regla del while es manté idèntica perquè Python també admet despertars espuris. El que guanya el monitor és que el with garanteix que el forrellat s'allibera encara que hi hagi una excepció, eliminant d'arrel l'oblit de l'unlock.

Un mutex tracta igual lectors i escriptors: només un alhora. Però diversos lectors simultanis no es destorben —si ningú no modifica la dada, llegir-la des de deu fils alhora és segur—, i un mutex desaprofita aquesta oportunitat. Un bloqueig de lectura/escriptura (pthread_rwlock_t) distingeix lectura compartida (molts lectors alhora) d'escriptura exclusiva (un escriptor sol, sense lectors):

La pregunta és quan compensa, perquè un rwlock no és gratis: la seva estructura interna és més complexa que la d'un mutex i adquirir-lo costa més. Amb seccions crítiques curtes (~100 ns) el mutex guanya o empata fins a proporcions de 99/1, i només a partir de 99,9/0,1 convé plantejar-se alguna cosa millor —RCU o doble memòria intermèdia—. Amb seccions llargues (~10 µs), en canvi, el rwlock guanya ja des de 90/10 i guanya molt a partir de 99/1.

La regla resumida: el rwlock compensa quan les lectures dominen clarament i la secció crítica és prou llarga perquè el paral·lelisme entre lectors compensi el seu cost d'adquisició més gran; amb seccions de nanosegons, el sobrecost es menja l'avantatge. El cas de Meteora hi encaixa de sobres: meteo-api llegeix 1.200 vegades per segon i l'agregador escriu una vegada per hora, una proporció de 4.320.000 a 1. Això sí, el rwlock té un problema que cal conèixer: la inanició d'escriptors. Si arriben lectors contínuament, pot ser que no hi hagi mai un instant sense lectors i l'escriptor esperi indefinidament. Linux ofereix pthread_rwlockattr_setkind_np(&attr, PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP) per donar-los preferència. Aquest compromís entre afavorir uns o altres és justament el problema de lectors-escriptors, que desenvoluparem a Problemes Clàssics de Concurrència.

Una barrera sincronitza un grup de fils en un punt: cap no passa fins que tots hi hagin arribat.

És la primitiva natural per a càlculs per fases, quan la fase N+1 necessita els resultats complets de la fase N: a l'agregador, amb 4 fils calculant mitjanes parcials per rang d'estacions, garanteix que ningú no fusioni abans que tots els parcials existeixin. El seu cost és el del fil més lent —una barrera fa que tots vagin al ritme del pitjor—, així que el repartiment equilibrat de la feina importa molt més en codi amb barreres que sense.

Ja podem respondre la pregunta que va quedar oberta a l'apartat 7: si girar és dolent amb contenció i dormir costa 2-5 µs sempre, com aconsegueix un pthread_mutex_lock ser barat? La resposta és futex (fast userspace mutex), la crida al sistema que Linux va introduir el 2002 i sobre la qual es construeixen tots els mutexos, semàfors i variables de condició de glibc. La seva idea és tan simple com brillant:

El cas comú —no hi ha contenció— es resol enterament en espai d'usuari amb una operació atòmica, sense cridar el nucli. Només quan hi ha contenció real es paga el preu d'una crida al sistema.

El mutex és, en essència, un int a memòria compartida. La lògica simplificada:

Els tres valors de l'enter codifiquen tot l'estat: 0 lliure, 1 ocupat sense ningú esperant, 2 ocupat amb almenys un esperant. Aquest tercer valor és el que permet que unlock sàpiga si necessita despertar algú o pot sortir sense cridar el nucli. Els números ho diuen tot: un lock sense contenció costa ~20 ns sense cap crida al sistema i un unlock sense ningú esperant ~15 ns, també sense syscall; només quan hi ha contenció apareixen FUTEX_WAIT (~2-5 µs) i FUTEX_WAKE (~1-2 µs).

I en un programa ben dissenyat la immensa majoria de les adquisicions no tenen contenció, per la qual cosa un mutex POSIX gairebé mai no arriba a parlar amb el nucli. Es comprova amb strace, i el resultat és revelador:

841 crides a futex per a 2.000.000 d'adquisicions: una per cada 2.378 bloqueigs, amb el 99,96 % resolt íntegrament en espai d'usuari. Si cada adquisició hagués implicat una crida al sistema, el programa hauria trigat uns 4 segons en lloc de 0,412. Dos detalls més: els futex funcionen entre processos perquè operen sobre l'adreça física de la pàgina —per això els mutexos a /dev/shm/meteora-cache funcionen amb PTHREAD_PROCESS_SHARED—, i el nucli indexa les cues d'espera per aquesta adreça en un hash global. Per veure la contenció en viu, perf lock contention o el mateix strace -c.

Queda una peça que ha anat apareixent des de l'apartat 3 i que cal tancar: la reordenació de memòria. Ni el compilador ni el processador no executen les teves instruccions en l'ordre en què les vas escriure; tots dos les reordenen lliurement, amb una única garantia: el resultat ha de ser el mateix des del punt de vista d'un sol fil. Aquesta clàusula és el parany, perquè tan bon punt hi ha un altre fil mirant, la reordenació es torna observable.

Per a un sol fil totes dues versions són equivalents: ningú no mira llest entremig. Però un altre fil que faci while (!llest); usar(dades.temperatura); pot veure llest == 1 i llegir una temperatura escombraria. Hi ha dos nivells de reordenació, i cal combatre'ls tots dos:

I aquí hi ha la resposta a la pregunta del títol:

volatile impedeix la reordenació del compilador, però no la del processador, i no fa atòmica cap operació.

Resol dos dels cinc problemes —que el compilador guardi la variable en un registre i que el compilador reordeni els accessos— i deixa intactes els tres que importen: que el processador reordeni, que l'operació sigui llegir-modificar-escriure, i que un altre nucli vegi un valor obsolet. Per això volatile long comptador; comptador++; continua perdent increments exactament igual que sense volatile: es llegeix de memòria, s'incrementa en un registre i s'escriu, amb la mateixa finestra de sempre.

L'ús correcte de volatile és molt estret: registres de maquinari mapejats en memòria (on cada lectura té efectes laterals) i la bandera volatile sig_atomic_t d'un gestor de senyal, correcta perquè el gestor s'executa al mateix fil i no hi ha dos nuclis implicats. Per a tota la resta, la resposta és _Atomic / <stdatomic.h>, els tipus del qual porten incorporades les barreres necessàries segons l'ordre de memòria que demanis:

El patró release/acquire resol l'exemple de dalt i mereix memoritzar-se: l'escriptor prepara les dades i després fa una escriptura release de la bandera; el lector fa una lectura acquire i, si la veu posada, té garantit que veu tot el que l'escriptor va fer abans. És la base de la publicació segura de dades entre fils.

Bona notícia final: si fas servir mutexos, semàfors o variables de condició, tot això està resolt per tu, perquè pthread_mutex_lock inclou una barrera acquire i pthread_mutex_unlock una release. Només necessites entendre les barreres si escrius codi sense forrellats, i és allà on la majoria de la gent s'equivoca.

Última qüestió, de disseny: quant ha de protegir un forrellat? L'elecció determina el rendiment del sistema sencer:

Un exemple sobre la memòria cau de Meteora. Amb un forrellat global per a ultimes[1024], els 4 treballadors competeixen sempre, encara que toquin entrades diferents. Amb particionat:

Ara dos treballadors que atenguin estacions de particions diferents no competeixen en absolut: amb 16 particions i estacions ben repartides, la probabilitat de col·lisió cau a 1/16. I el farciment fins a 64 bytes no és decoratiu: sense ell, diversos mutexos caurien a la mateixa línia de memòria cau i els nuclis se la invalidarien mútuament en bloquejar forrellats diferents. És el false sharing de 03-01, i pot anul·lar per complet l'avantatge del particionat.

Mesura sobre meteo-01 amb 8 fils i 4 milions d'operacions:

Tres conclusions: el particionat funciona (7,25× amb 8 fils és gairebé el màxim possible), hi ha rendiments decreixents (de 16 a 64 particions amb prou feines es guanya res, perquè amb 8 fils ja gairebé no hi ha col·lisions) i oblidar el farciment arruïna el disseny (2,97 s davant de 0,53 s: un factor de 5,6 perdut per no alinear a la línia de memòria cau).

Les regles d'enginyeria que se'n deriven: comença amb granularitat grossa, perquè un forrellat simple i correcte val més que un de fi i trencat; mesura abans de refinar, ja que si el forrellat s'adquireix sense contenció el 99 % de les vegades, refinar-lo no guanyarà res; mantén la secció crítica curta, perquè treure'n un printf o un malloc sol donar més que qualsevol redisseny del forrellat; no facis mai E/S amb un forrellat pres, ja que un write() a disc pot tenir els altres esperant mil·lisegons, quatre ordres de magnitud més del previst; alinea els forrellats a la línia de memòria cau quan en tinguis diversos; i pren sempre els forrellats en el mateix ordre, que és la regla que evita els interbloqueigs i a la qual dedicarem Interbloquejos sencera.

Fer servir if en lloc de while amb pthread_cond_wait. L'error més comú i més car: els despertars espuris existeixen, i amb broadcast diversos fils es desperten encara que només hi hagi feina per a un, així que amb if tots continuen endavant sobre una condició falsa. Sempre while.

Creure que volatile serveix per sincronitzar. Impedeix la reordenació del compilador, no la del processador, i no fa atòmica cap operació: volatile int comptador; comptador++; perd increments exactament igual. Fes servir <stdatomic.h> o un mutex.

Oblidar l'unlock en un camí d'error. Un return prematur dins de la secció crítica deixa el forrellat pres per sempre i penja tots els altres. En C, un sol punt de sortida o macros de neteja; en C++, std::lock_guard; en Python, with lock:.

Fer servir un spinlock on havia d'anar un mutex, o posar diversos mutexos a la mateixa línia de memòria cau. Si la secció crítica dura més d'uns centenars de nanosegons, o hi ha més fils que nuclis, un spinlock crema nuclis sencers esperant: en espai d'usuari, la resposta per defecte és sempre el mutex. I diversos forrellats independents que comparteixen línia de memòria cau surten 5,6 vegades més lents, com hem mesurat abans; farceix fins a 64 bytes o fes servir alignas(64).

Protegir amb el forrellat equivocat, o no fer servir PTHREAD_PROCESS_SHARED en memòria compartida. Dues seccions crítiques sobre la mateixa dada amb forrellats diferents no s'exclouen entre si, i un mutex per defecte posat a /dev/shm/meteora-cache no dona error: simplement no exclou res. La convenció de guardar el forrellat dins de l'estructura que protegeix evita gairebé tots els casos del primer tipus.

Consell: l'ordre de preferència pràctic és (1) no compartir, (2) dades immutables, (3) una operació atòmica, (4) un mutex, (5) rwlock o granularitat fina si has mesurat contenció, (6) codi sense forrellats només si ets especialista. Baixa un esglaó només quan l'anterior no basti, i amb una mesura a la mà. I documenta què protegeix cada forrellat: un comentari /* protegeix: peticions_totals, n_ultimes, ultimes[] */ al costat de la declaració és el primer que buscarà qui depuri una penjada a les tres de la matinada.

Implementa un comptador compartit incrementat per N fils un milió de vegades cadascun, amb quatre estratègies: sense protecció, amb atomic_fetch_add en mode relaxed, amb pthread_mutex_t i amb pthread_spinlock_t. Mesura el temps amb N = 1, 2, 4 i 8 fils, verifica la correcció de cadascuna i construeix la taula. Explica per què l'spinlock es comporta com es comporta en passar de 4 a 8 fils en una màquina de 8 nuclis amb altres processos actius.

Escriu un programa amb una cua compartida de capacitat 1, tres consumidors que esperen amb una variable de condició i un productor que fa broadcast després d'inserir un element. Implementa l'espera primer amb if i després amb while. Executa totes dues versions i explica exactament què passa a la versió amb if, incloent-hi què imprimeix i per què.

Implementa la memòria cau de Meteora amb dues variants: protegida per pthread_mutex_t i per pthread_rwlock_t. Llança 7 fils lectors i 1 escriptor, on cada lectura recorre 100 elements de l'array i cada escriptura n'actualitza 100. Mesura el nombre total d'operacions per segon de cada variant i determina, variant la proporció d'escriptures (1 %, 10 %, 50 %), a partir de quin punt el mutex torna a ser millor.

Solució 1

Resultats a meteo-01 (8 nuclis):

(✓ = resultat correcte; ✗ = increments perduts.) Lectures de la taula. La versió sense protecció és sempre la més ràpida i sempre incorrecta a partir de 2 fils: la sincronització té un cost real i cal pagar-lo. L'atòmic és 4-9 vegades més ràpid que el mutex, perquè una sola instrucció lock xadd substitueix tot el protocol d'adquisició i alliberament.

Per què l'spinlock es dispara amb 8 fils. Fins a 4 fils l'spinlock guanya al mutex (0,381 s davant de 0,412 s): amb una secció crítica de nanosegons, girar costa menys que adormir-se. Amb 8 fils en 8 nuclis es dispara a 4,72 s, 2,5 vegades pitjor, per dues causes que se sumen. Primera: no hi ha cap nucli realment lliure, perquè el sistema (intèrpret d'ordres, systemd, els ksoftirqd) també vol CPU, així que quan el planificador expulsa el fil que té l'spinlock, els altres set continuen girant mil·lisegons sencers sense que ningú pugui avançar. Segona: cada gir és un CAS que exigeix la propietat exclusiva de la línia de memòria cau, i vuit nuclis barallant-s'hi generen una tempesta de trànsit de coherència que alenteix fins i tot el que sí que té el forrellat.

El mutex, en canvi, adorm els que no poden entrar: deixen de consumir CPU i d'invalidar la línia de memòria cau. Regla: en espai d'usuari, mutex per defecte; spinlock només amb seccions crítiques de nanosegons, menys fils que nuclis i una mesura que ho avali.

Solució 2

Què passa amb if. El broadcast desperta els tres consumidors, però només hi ha un element. Els tres eren dins de pthread_cond_wait, recuperen el mutex un darrere l'altre i tots tres continuen més enllà de l'if, perquè un if comprova la condició una sola vegada, abans de dormir. El consumidor 0 consumeix l'únic element i deixa elements = 0; l'1 i el 2, ja desperts, no tornen a comprovar res i decrementen igualment, deixant el comptador a -2.

Aquí el dany és un número negatiu. En codi real és molt pitjor: si elements fos l'índex d'un array, tindries accessos amb índex negatiu; si fos un punter tret d'una cua buida, un NULL desreferenciat; si fos un descriptor, un read sobre escombraries. I tot això de manera intermitent, perquè només passa quan diversos consumidors esperen alhora.

Amb while, els consumidors 1 i 2 reavaluen elements == 0 en despertar-se, comproven que és cert i tornen a dormir. Aquesta reavaluació és el que aporta el bucle, i és la raó que POSIX pugui permetre despertars espuris sense trencar cap programa ben escrit.

Solució 3

Resultats amb 8 fils, en milers d'operacions per segon:

Interpretació. Amb lectures dominants el rwlock guanya clarament: els 7 lectors recorren l'array en paral·lel en lloc de en sèrie, i el guany de 5,56× amb un 0,1 % d'escriptures s'acosta al màxim teòric de 7×. El punt d'equilibri és al voltant del 35-40 % d'escriptures; a partir d'aquí el rwlock és pitjor que el mutex, per dos motius que se sumen: la seva estructura interna és més complexa —porta el compte de lectors actius, cosa que exigeix operacions atòmiques addicionals a cada adquisició— i amb moltes escriptures els lectors amb prou feines se solapen, així que es paga el sobrecost sense cobrar l'avantatge.

Aplicat a Meteora: meteo-api llegeix 1.200 vegades per segon i l'agregador escriu una vegada per hora, un 0,00002 % d'escriptures, molt a l'esquerra de la primera fila. El rwlock és l'elecció correcta, i amb una proporció tan extrema val la pena anar un pas més enllà: un esquema de doble memòria intermèdia en què l'agregador prepara una còpia nova i publica el seu punter amb un atomic_store en mode release faria que els lectors no prenguessin cap forrellat en absolut, ni tan sols el de lectura.

El problema de la secció crítica no es pot resoldre bé amb variables normals, i hem vist per què fallant tres vegades: la bandera única trenca l'exclusió mútua perquè comprovar i actuar són dues operacions; el torn estricte la garanteix però viola el progrés, deixant que un fil inactiu en bloquegi un altre per sempre; i les dues banderes produeixen un interbloqueig en cinc línies. La solució de Peterson les combina i és correcta sobre el paper, amb espera limitada òptima, però només serveix per a dos fils, és espera activa pura i —el que és definitiu— falla en maquinari real per la reordenació de memòria llevat que hi afegeixis una barrera explícita.

La sortida és el maquinari: test-and-set i sobretot compare-and-swap, que comparen i escriuen de manera indivisible en una sola instrucció (lock cmpxchg). Costen uns 20 ns, vint vegades més que una escriptura normal, perquè negocien la propietat exclusiva de la línia de memòria cau. Sobre CAS hem arreglat el primer asterisc del mòdul: atomic_fetch_add sobre peticions_totals dona el resultat exacte sempre, és 3,6 vegades més ràpid que un mutex, i funciona igual entre processos a /dev/shm/meteora-cache mentre sigui lliure de bloqueigs.

D'aquí surten les dues famílies d'espera. Els spinlocks giren: correctes per a seccions de nanosegons i obligatoris en context d'interrupció, catastròfics amb més fils que nuclis —ho hem mesurat: 4,72 s davant d'1,89 s del mutex amb 8 fils—. El bloqueig amb suspensió adorm el fil, costa 2-5 µs i consumeix zero CPU. Els mutexos POSIX protegeixen regions de codi arbitràries i no només una variable, per la qual cosa són la resposta quan cal escriure una struct Lectura de 24 bytes de manera indivisible; entre processos exigeixen PTHREAD_PROCESS_SHARED, i PTHREAD_MUTEX_ROBUST evita que la mort d'un treballador pengi el servei sencer. Els semàfors compten recursos i no tenen propietari, cosa que els fa l'eina de senyalització entre fluxos diferents i l'única segura dins d'un gestor de senyal. Les variables de condició resolen «esperar que es compleixi alguna cosa», amb l'atomicitat de wait protegint contra la senyal perduda i la regla més important de la lliçó: sempre while, mai if. Els rwlock permeten lectors simultanis —5,56× amb un 0,1 % d'escriptures, però pitjor que un mutex a partir del 40 %— i les barreres sincronitzen fases de càlcul al ritme del fil més lent.

Per sota, Linux ho implementa tot amb futex: el cas sense contenció es resol sencer en espai d'usuari amb un CAS de 20 ns, i només es crida el nucli per dormir o despertar. Els números ho confirmen: 841 crides al sistema per a 2.000.000 d'adquisicions, el 99,96 % sense tocar el nucli. Hem tancat també el compte de volatile: impedeix la reordenació del compilador però no la del processador i no fa atòmic res, així que no serveix per sincronitzar; el seu lloc són els registres de maquinari i la bandera d'un gestor de senyal. I la granularitat decideix el rendiment: particionar la memòria cau en 16 forrellats alineats a la línia de memòria cau dona 7,25× davant del forrellat global, mentre que oblidar el farciment de 64 bytes ho enfonsa a 1,29× per false sharing.

Ja tens totes les peces, i ara ve el que és interessant: combinar-les. Un mutex protegeix una dada, però com es coordina un productor que omple una memòria intermèdia amb un consumidor que la buida, sense que el productor escrigui en una memòria intermèdia plena ni el consumidor llegeixi d'una de buida? Com es reparteix l'accés entre molts lectors i un escriptor sense que ningú passi gana? I per què cinc filòsofs amb cinc forquilles es queden tots bloquejats? Aquests patrons tenen nom propi des de fa seixanta anys, són el vocabulari comú de la concurrència, i tot problema real que et trobis serà una variant d'algun d'ells. Els veiem a Problemes Clàssics de Concurrència.