Sincronització de baix nivell

// test-and-set
while (test_and_set(&lock) == 1) ;

// test-and-test-and-set
do {
  while (lock == 1) ;            // espera llegint la còpia de la cache
} while (test_and_set(&lock) == 1);

Per implementar primitives com locks i barreres, el software necessita instruccions atòmiques que el hardware garanteixi indivisibles.

Implementació de locks: Test-and-Set

La instrucció Test-and-Set (t&s) llegeix el valor d’una adreça i, en un sol pas indivisible, hi escriu un 1. Un spinlock bàsic s’implementa:

lock:   t&s  r1, flag   // r1 = flag; flag = 1 (atomicament)
        bnez r1, lock   // si el lock estava pres, torna-ho a intentar
        // ... (Seccio critica) ...
unlock: st   flag, #0   // allibera el lock

Problema: com que t&s inclou una escriptura, cada intent fallit genera una petició d’exclusivitat (BusRdX/WrReq) i invalida les còpies de la resta. Amb molts threads en espera, el bus o el directori queden saturats de tràfic inútil.

Optimització: Test-and-Test-and-Set

lock:   ld   r1, flag   // 1r TEST: lectura normal
        bnez r1, lock   // spin mentre el lock esta ocupat
        t&s  r1, flag   // 2n TEST: intenta agafar-lo
        bnez r1, lock   // si algu se l'ha avancat, comenca de nou

Mentre el lock és ocupat, els threads fan ld: hit local a la caché (línia en estat S), sense cap tràfic de bus. Quan el propietari allibera el lock, les cachés s’invaliden i tots els threads intenten el t&s una vegada.

Load-Linked / Store-Conditional (LL/SC)

Alternativa preferida en arquitectures modernes (ARM, RISC-V) que evita bloquejar el bus:

• LL (Load-Linked): llegeix una adreça i marca la línia com a vigilada.
• SC (Store-Conditional): escriu a la mateixa adreça només si cap altre core l’ha modificada des del LL; retorna 1 si èxit, 0 si falla.

Si el SC falla, es torna a executar el LL. Delega el control de l’exclusió mútua al seguiment local de la caché, sense operacions pesades al bus.

Barreres de sincronització

Una barrera fa que $P$ threads esperin fins que tots hi han arribat. S’implementa amb un lock que protegeix un comptador d’arribades i un flag d’alliberament: quan l’últim thread porta el comptador a $P$, activa el flag i desperta la resta. Mentre esperen, els threads fan spin sobre el flag en lectura (hits locals en S, sense tràfic de bus), aprofitant el mateix principi que el TT&S.