Concurrència
Concurrència i paral·lelisme
La concurrència és una propietat de l’algorisme; el paral·lelisme, una propietat de la màquina.
Una aplicació és concurrent quan diverses tasques poden avançar sense un ordre concret: no cal que una acabi perquè comenci la següent. Per tant, l’hem de dissenyar nosaltres.
Una execució és paral·lela quan diverses tasques avancen en el mateix instant de temps, aprofitant sistemes amb múltiples cores per accelerar la computació.
La conseqüència pràctica és que són coses independents. Podem tenir concurrència sense paral·lelisme, amb moltes tasques alternant-se en un sol core. I si no dissenyem concurrentment, no podem aprofitar les arquitectures multi-core encara que les tinguem: quedem limitats a la capacitat d’un sol core.
Hi ha aplicacions inherentment concurrents, com un servidor que ha d’atendre molts clients alhora. A la resta, la concurrència és una decisió que prenem per guanyar rendiment o capacitat de resposta.
Processos i fils
Els processos no comparteixen memòria; els fils del mateix procés sí, i d’aquí surten tots els problemes de la concurrència.
La unitat bàsica d’execució d’un sistema operatiu és el procés: una col·lecció de codi, memòria, dades i altres recursos. Un procés té un entorn d’execució independent, com si simulés un ordinador propi, amb el seu espai de memòria separat. Sol ser sinònim de programa o aplicació, encara que una aplicació pugui ser un conjunt de processos.
Un fil (thread) és una seqüència de codi que s’executa dins de l’àmbit d’un procés i que pot compartir dades amb els altres fils. És la seqüència mínima d’instruccions que gestiona un planificador. Un procés pot tenir diversos fils executant-se simultàniament a dins.
La diferència es veu millor mirant on viuen les dades. Quan desenvolupem una aplicació, les dades es reparteixen en dos espais de memòria:
- Pila de crides (call stack): estructura que guarda les rutines actives d’un fil apilades en frames. Cada fil té la seva.
- Heap: espai dinàmic de memòria que s’assigna quan es creen dades i es desassigna quan s’esborren. Habitualment aquí hi trobem els objectes.
Els processos no comparteixen ni pila ni heap. Els fils tenen una pila cadascun, però comparteixen el heap: per això dos fils poden veure i modificar el mateix objecte, i per això necessitarem mecanismes de coordinació.
Contingut d'un frame de la pila
El frame es crea quan es fa una crida i s’esborra quan la rutina acaba. Conté:
- L’adreça de retorn
- Els paràmetres de la rutina
- Les variables locals
El planificador o scheduler és el mecanisme que assigna tasques a treballadors. En una aplicació, una tasca sol traduir-se en un fil, i un treballador en un core de CPU. Quan el planificador substitueix una tasca per una altra fa un canvi de context (context switching): és una operació pesada per als processos, que tenen un context gran, i lleugera per als fils, que en tenen un de petit.
Els fils dels quals parlem aquí són els del sistema operatiu, i per tant són un recurs limitat: en tenim centenars, no milions. Alguns entorns d’execució hi afegeixen un tercer nivell, amb fils que gestiona la mateixa plataforma i que no es corresponen amb cap fil del sistema. Quan un d’aquests es bloqueja esperant una resposta, la plataforma el retira i aprofita el fil real per a una altra feina, sense que el sistema operatiu hi intervingui. Són molt més barats, i canvien quantes tasques concurrents ens podem permetre. A Java se’n diuen fils virtuals i els veurem a Fils a Java.
Aplicacions de la concurrència
La concurrència apareix sempre que una part del programa no pot quedar-se esperant que una altra acabi.
Aquests són els casos d’ús habituals:
- A una UI, fer operacions en un treballador independent que no bloquegi la interfície.
- Implementar alarmes i temporitzadors.
- Implementar algorismes paral·lels.
- Atendre múltiples clients concurrents que accedeixen a recursos compartits.
Models de concurrència
Hi ha tres models de concurrència, i la tria depèn de la mena de tasques que tenim i de com han de compartir informació.
Abans de triar, cal caracteritzar la tasca segons el tipus d’activitat que fa:
- Limitada per la CPU: necessita la CPU per fer càlculs intensius.
- Limitada per l’E/S (Entrada/Sortida): habitualment està esperant una operació d’entrada/sortida, com llegir o escriure a disc o a la xarxa.
La distinció importa perquè només les tasques limitades per la CPU guanyen alguna cosa amb el paral·lelisme real.
L’assignació de tasques que fa el planificador també pot ser de dos tipus:
- Cooperativa: les tasques gestionen el seu cicle de vida i decideixen quan abandonen el treballador.
- Apropiativa: el planificador assigna un time slice a la tasca i la treu del treballador quan s’acaba.
El repte principal en implementar concurrència és coordinar les tasques i accedir de manera segura als recursos compartits. Els tres enfocaments disponibles són un sol fil, estat compartit i pas de missatges. El diagrama següent els mostra:
Un sol fil
Amb un sol fil no hi ha res a coordinar, i per això és el model més senzill sempre que puguem permetre’ns-ho.
Com que les tasques no s’executen mai alhora, no calen mecanismes de bloqueig. El desavantatge és que no es poden paral·lelitzar, cosa que només és un problema si estan limitades per la CPU.
L’exemple habitual és el bucle d’esdeveniments de les interfícies d’usuari: una cua rep els esdeveniments i els gestiona ràpidament, perquè les operacions llargues es fan de forma asíncrona.
Estat compartit
Amb estat compartit les tasques es comuniquen a través de la memòria, i el codi ha de garantir que això és segur.
Interaccionen llegint i escrivint objectes compartits i mutables. És el model més complex, perquè cal implementar mecanismes de bloqueig per coordinar els fils.
Imaginem que els fils A i B fan servir el mateix codi per accedir a objectes mutables compartits. El codi que permet que diversos fils l’executin simultàniament sense corrompre res s’anomena thread-safe.
Hi ha quatre estratègies per aconseguir-ho, que veurem més endavant: confinament, immutabilitat, tipus thread-safe i sincronització.
Pas de missatges
Amb pas de missatges no es comparteix res, i per tant no hi ha res a bloquejar.
Les tasques concurrents interaccionen enviant-se missatges (1:1 o N:1) a través d’un canal de comunicació. Els missatges porten objectes immutables, i els que arriben a cada tasca es posen a la cua per anar-los gestionant. L’enviament pot ser síncron o asíncron, segons si s’espera la resposta o no.
El pas de missatges es pot implementar en dos contextos: entre fils d’un mateix procés, per exemple amb cues i el patró productor/consumidor, o entre processos d’una xarxa, per exemple amb sòcols.