Concurrència

Concurrència i paral·lelisme

La computació concurrent permet que diverses tasques dins d'una aplicació puguin executar-se sense un ordre concret, fora d'una seqüència. O sigui: no cal que una tasca es completi perquè comenci la següent. Aquesta és una propietat de l'algorisme. És a dir, cal que dissenyem la nostra aplicació perquè ho permeti.

La computació concurrent no implica que l'execució es produeix en el mateix instant de temps. La computació paral·lela sí que fa referència a l'execució en el mateix instant de temps, i treu profit de sistemes amb múltiples cores per a accelerar la computació. És una propietat de la màquina.

Per una banda, hi ha situacions on les aplicacions són inherentment concurrents. Per una altra, si no dissenyem concurrentment, les nostres aplicacions no poden aprofitar les arquitectures hardware multi-core de les CPU dels ordinadors, i estarem limitats a la capacitat i rendiment d'un sol core.

Processos i fils

El planificador o scheduler d'un sistema és el mecanisme que permet assignar tasques a treballadors. A una aplicació, una tasca sol traduir-se en un fil o thread i un treballador en un core de CPU. L'assignació fa que el planificador substitueixi una tasca per un altra. D'això se'n diu canvi de context (context switching). És un procés pesat per als processos, amb un context més gran, i lleuger per als fils, amb un context més petit.

La unitat bàsica d'execució d'un sistema operatiu és el procés, que són col·leccions de codi, memòria, dades i altres recursos. Un procés té un entorn independent d'execució, simulant un ordinador. Per exemple, té el seu espai independent de memòria. Solen ser sinònim de programa, o aplicació, encara que pugui ser un conjunt de processos.

Un fil és una seqüència de codi que s'executa dins de l'àmbit del procés, i que pot compartir dades amb altres fils. Un fil és la seqüència mínima d'instruccions que gestiona un scheduler. Un procés pot tenir diversos fils executant-se simultàniament a dins.

Quan desenvolupem una aplicació, les seves dades es troben en dos espais de memòria diferents: el heap i la pila de crides (call stack):

  • Pila de crides (call stack): estructura de dades que guarda les rutines actives d'un fil apilades en frames. El frame es crea quan es fa una crida, i s'esborra quan s'acaba la rutina. Cada frame conté:

    • L'adreça de retorn
    • Els paràmetres de la rutina
    • Les variables locals

  • Heap: espai dinàmic de memòria que s'assignen quan es creen dades i es desassignen quan s'esborren. Habitualment aquí trobem els objectes.

El processos són totalment independents, no comparteixen res a la pila o el heap. Els fils poden compartir dades del heap.

Aplicacions de la concurrència

La programació ens permet implementar concurrència de diverses formes segons el llenguatge i el context del desenvolupament. Aquests són possibles casos d'ús:

  • A una UI, fer operacions en un treballador independent que no bloquegi la interfície.
  • Implementar alarmes i temporitzadors.
  • Implementació d'algorismes paral·lels.
  • Implementar tasques de múltiples clients concurrents, accedint a recursos compartits.

Models de concurrència

Una tasca pot caracteritzar-se, segons el seu tipus d'activitat, com:

  • Limitada per la CPU: és una tasca que necessita la CPU per fer càlculs intensius.
  • Limitada per l'E/S (Entrada/Sortida): és una tasca que habitualment està esperant per una operació d'entrada/sortida, com pot ser llegir o escriure a disc o a la xarxa.

L'assignació de tasques del scheduler pot ser de dos tipus: cooperativa o apropiativa.

  • Cooperativa: les tasques gestionen el seu cicle de vida, i decideixen quan abandonen el treballador.
  • Apropiativa: el scheduler assigna un time slice per a la tasca, i la treu del treballador quan es compleix.

El principal repte per implementar la concurrència és la correcta coordinació entre tasques i l'accés als recursos compartits de manera segura. Aquests són alguns dels enfocaments disponibles:

  • Un sol fil: només tenim un fil que es comparteix entre les tasques.
  • Estat compartit (o memòria compartida): dues o més tasques comparteixen un estat que totes poden llegir i escriure, i diversos mecanismes permeten fer-ho de manera segura.
  • Pas de missatges: no es comparteix res. En el seu lloc, s'intercanvien missatges.

El següent diagrama mostra el model d'un sol fil, el de memòria compartida i el de pas de missatges.

Un sol fil

Aquesta opció simplifica el disseny de la concurrència, ja que no cal utilitzar mecanismes per a gestionar l'accés simultani a recursos compartits. Té el desavantatge que no es poden paral·lelitzar les tasques, però això només és un problema si estan limitades per CPU.

Un exemple habitual és el del bucle d'esdeveniments de les UI. S'implementa amb una cua que rep els esdeveniments i els gestiona ràpidament, ja que només realitzen operacions asíncrones.

Estat compartit

Les tasques concurrents interaccionen llegint i escrivint objectes compartits i mutables en memòria. És complex, ja que cal implementar mecanismes de bloqueig per coordinar els fils.

Imaginem que els fils A i B utilitzen un mateix codi per a compartir els objectes mutables. Aquest codi, que permet que diversos fils l'accedeixin simultàniament de forma segura, s'anomena "thread-safe".

Hi ha quatre estratègies que veurem: confinament, immutabilitat, tipus thread-safe i sincronització.

Pas de missatges

Les tasques concurrents interaccionen enviant-se missatges entre ells (1:1 o N:1) a través d'un canal de comunicació. Les tasques envien missatges amb objectes immutables, i els missatges entrants de cada tasca es col·loquen en cola per a la seva gestió. Ho poden fer de forma síncrona o asíncrona, en funció de si s'espera o no la resposta.

El pass de missatges es pot implementar en dos contextos: entre fils d'un procés (p.ex. cues i productor/consumidor) o entre processos d'una xarxa (p. ex. amb sòcols).