Problemes del paral·lelisme

La majoria de programes estan pensats per executar-se de forma seqüencial. Per tant, quan els paral·lelitzem ens hem d’assegurar que el resultat es mantingui igual!

Dependències

Quan executem vàries parts d’un mateix programa alhora no podem conèixer al 100% quin serà l’ordre d’execució de les seves parts. Això ens pot causar problemes si una part del codi necessita el resultat d’una altra.

Per exemple, si una instrucció llegeix X abans que una altra l’hagi inicialitzat o actualitzat, podem obtenir un valor incorrecte.

// CPU 1
X = 10;

// CPU 2
X = X + 2;
print(X);

Si no imposem cap ordre, X = X + 2 podria executar-se abans de X = 10, o el print(X) podria passar abans de l’increment, i per tant el nostre programa al paral·lelitzar-lo no tindria el funcionament esperat i seria incorrecte.

Per evitar-ho, caldrà establir dependències i obligar que certes instruccions s’executin abans que d’altres, segons les dades que accedeixin o modifiquin.

Concurrència

Data race condition: dos threads comparteixen una mateixa adreça de memòria (per exemple una variable) i la intenten modificar/utilitzar alhora. Això pot fer que el resultat variï entre execucions.

// CPU 1
tmp = x;
tmp = tmp + 1;
x = tmp;

// CPU 2
tmp = x;
tmp = tmp + 1;
x = tmp;

Si x comença valent 0, l’esperat seria acabar amb x = 2. Però si tots dos threads llegeixen x = 0 abans que cap escrigui, tots dos acabaran escrivint 1 i el resultat final serà x = 1.

• Bloquejar la dada mentre l’estiguem utilitzant (semàfor).

Starvation: un thread no pot accedir a un recurs compartit, perquè un altre thread el té reservat molta estona, perdent paral·lelisme potencial.

// CPU 1
for (...) {
  lock(m);
  feina_llarga();
  unlock(m);
}

// CPU 2
for (...) {
  lock(m);
  // sovint queda esperant
  feina_curta();
  unlock(m);
}

• Repartir millor la càrrega de treball entre threads (no hi ha una «solució» única i general).

Deadlock: dues tasques esperen mútuament que l’altra alliberi l’element que ella té i es crea un bloqueig cíclic; el programa queda en espera infinita.

// CPU 1
lock(A);
lock(B);   // espera B
// NO avança

// CPU 2
lock(B);
lock(A);   // espera A
// NO avança

• Imposar un ordre en l’adquisició de bloquejos per evitar esperes circulars.

Livelock: variant del deadlock: les tasques no queden «aturades» esperant, sinó que intenten evitar el bloqueig canviant d’estat, però continuen bloquejant-se mútuament.

// CPU 1
lock(A);
trylock(B); // falla
unlock(A);  // cedeix
lock(A);    // reintenta
...

// CPU 2
lock(B);
trylock(A); // falla
unlock(B);  // cedeix
lock(B);    // reintenta
...

• Imposar ordre també als desbloquejos i/o aplicar backoff per evitar que en reintentar-ho es repeteixi el patró.