Els fils es poden comunicar intercanviant informació a través dels objectes
emmagatzemats a la memòria principal. Com que els fils pertanyen a un procés,
poden accedir tots als objectes d'aquest procés que hi haja en memòria.
Aquest mètode de comunicació és molt eficient, ja que aquesta operació és molt ràpida.
No obstant això, aquesta manera d'intercanviar informació entre fils
pot produir resultats erronis si els fils hi accedeixen alhora.
Per solucionar aquests problemes s'utilitza necessitem establir mecanismes
per sincronitzar i controlar l'accés als recursos.
Condició de carrera: es defineix així quan el resultat de l'execució
d'un programa depèn de l'ordre concret en què es realitzen els accessos a memòria.
Exemple
Suposem que tenim dos fils que realitzen una operació
sobre la mateixa variable comptador, que inicialment té el valor 10.
Fil1: comptador++;
Fil2: comptador--;
En una execució correcta, primer el Fil1 sumaria i despés el Fil2 restaria
o viceversa, però el resultat sempre seria el mateix.
Info
Una operació atòmica és aquella que en codi màquina només es tradueix
en una única instrucció.
En aquest cas, el problema és que ++ i --no són operacions
atòmiques i es tradueixen en codi màquina de la manera següent:
La inconsistència de memòria es produeix quan diferents fils tenen una
visió diferent del que hauria de ser la mateixa dada. Pot passar des del
no alliberament de dades obsoletes fins al desbordament d'un buffer («buffer overflow»).
Exemple
Suposem que tenim dos fils i la variable comptador que inicialment té
el valor 0.
Fil1: comptador++;
Fil2: System.out.print(comptador);
Si les dues sentències s'executaren al mateix fil, primer la sumaria i
després s'imprimiria amb el valor 1.
Si aquestes instruccions s'executen en fils diferents no hi ha garantia
que primer es sume i que després s'imprimisca, de manera que el valor
imprès podria ser 0, cosa que és un resultat no desitjat.
La inanició és el fenomen que passa quan a un procés o fil se li
denega l'accés a un recurs compartit pel fet que altres processos o fils
sempre prenen en control d'aquest recurs abans per diferents motius.
Això es pot produir si un fil té una prioritat inferior a la resta de fils.
Exemple
Imagina que estàs en la cua d'un mercat per comprar,
on es dona prioritat a la gent més major per poder comprar abans.
En el moment que tu arribes, comencen a arribar molta gent més major
que tu tota la estona, sense parar.
Si no pots comprar menjar mai, en un temps estaràs famolenc.
En aquest exemple, tu eres un fil amb prioritat baixa i la gent major
son fils amb prioritat alta.
L'interbloqueig es produeix quan dos o més processos o fils es troben esperant
indefinidament per un esdeveniment que ha de generar un altre procés o fil que està
bloquejat o que es troba esperant un recurs que té assignat un altre procés o fil
que està bloquejat.
Exemple
Suposem que tenim 2 fils F1 i F2, i tenim dos
recursos R1 i R2. Els dos fils necessiten tindre la propietat
dels dos recursos per poder treballar. La seqüencia d'instruccions de
cada fils és:
Si els fils s'executen de manera paral·lela i executen la primera instrucció alhora
es bloquejarien entre ells, ja que cada fil està esperant a obtindre el recurs
que té en propietat l'altre fil, que no alliberarà fins que acabe.
El bloqueig actiu és molt similar a un interbloqueig, però aquest cas,
el bloqueig es dona perquè els fils involucrats van canviant el seu estat
per desbloquejar-se a la vegada, tornant a bloquejar-se mútuament.
Imagineu-se que aneu per la vorera d'un carrer, i vegeu algú que
s'apropa en sentit contrari a tu. Els dos aneu pegats a la pared de les cases,
pensant que l'altra persona s'apartarà.
En el moment que esteu molt a prop, els dos s'aparteu cap al carrer,
per deixar que l'altra persona passe.
Com els dos s'heu apartat, s'heu tornat a bloquejar entre vosaltres
i decidiu a la vegada tornar al lloc original.
Si cap dels dos trenca el bucle, entreu en el que es coneix
com bloqueig actiu.
Els problemes anteriorment esmentats ocorren pel fet que diversos fils
s'executen concurrentment i no es té control sobre el seu ordre,
cosa que pot desembocar en una ordenació i uns resultats no desitjats.
Per solucionar-ho, s'ha de controlar que els accessos a dades compartits
es realitzin de manera ordenada o síncrona. Quan estiguen executant codi
independent, que s'executin en paral·lel lliurement, s'anomena execució asíncrona.
Les condicions de Berstein defineixen les condicions que permeten
esbrinar si dos segments de codi (\(S_1\) i \(S_2\)) es poden executar en
paral·lel de manera asíncrona en diferents fils.
Aquestes condicions permeten fer una anàlisi de dependència. Si les
dues instruccions són independents, es poden executar en paral·lel.
Dependència de flux: Les variables d'entrada de \(S_2\) han de ser
diferents de les variables d'eixida de \(S_1\). En cas contrari, \(S_2\) depén
de \(S_1\).
\[
S_1: \textcolor{red}{C} = A + B \\
S_2: D = \textcolor{red}{C} + E
\]
Anti-dependència: Les variables d'entrada de \(S_1\) han de ser
diferents de les variables d'eixida de \(S_2\). En cas contrari, \(S_1\) depén
de \(S_2\). És el cas contrari al punt anterior.
\[
S_1: D = \textcolor{red}{C} + E \\
S_2: \textcolor{red}{C} = A + B
\]
Dependència d'eixida: Totes les variables d'eixida de \(S_1\) han de ser
diferents de les variables d'eixida de \(S_2\). En cas contrari els dos segments
podrien escriure al mateix lloc provocant resultats inesperats.
\[
S_1: \textcolor{red}{C} = A + B \\
S_2: \textcolor{red}{C} = D + E
\]
El codi que complisca alguna d'aquestes condicions
s'ha d'executar de manera síncrona.
Com s'ha exposat anteriorment, una operació atòmica és aquella que es
tradueix com una única instrucció i s'executarà completament sense ser
interrompuda.
Exemple
Imagina que fas un Bizum de 10€ a un conegut.
Aquesta és una operació no atòmica, ja que ha de restar 10€ del teu compte i transferir-los al compte de l'altra persona.
Aquesta operació s'ha de realitzar com una única instrucció o podrien
haver problemes de consistència en les dades.
Una secció crítica és aquella en què s'accedeix a variables i recursos
compartits, per la qual cosa les instruccions han d'executar-se de manera síncrona.
Aquest concepte es pot aplicar tant
a processos com a fils si accedeixen dades o recursos compartits.
Si ja hi ha un procés o fil executant la secció crítica i un altre vol
executar-la, aquest últim es bloquejarà fins que el primer acabe
amb la secció crítica.
D'aquesta manera s'estableix un abans-després en l'ordre d'execució
de seccions crítiques, de manera que els canvis es realitzen en un entorn
controlat i eviten que diferents fils puguen modificar les dades alhora.
Exemple
Una secció crítica podria englobar les instruccions
per realitzar canvis en un compte bancari.
Un fil ha d'esperar a que acabe una transacció
en un compte per poder fer canvis en el mateix.
Les seccions crítiques s'han de dissenyar de manera que es complisquen
les següents condicions:
Exclusió mútua. Si un procés o fil està executant la secció crítica,
cap altre pot passar a executar-la.
Progrés. Si no hi ha cap procés o fil executant la secció crítica
i n'hi ha diversos esperant a executar-la, algun ha de començar.
Espera limitada. Hi ha d'haver un nombre limitat de processos o
fils que entren a la secció crítica quan un procés o fil demana executar-la.
En cas contrari, es podria produir inanició.
Resumint, el codi corresponent a la secció crítica ha d'acabar en un temps
determinat i cal evitar la inanició.
Per implementar la secció crítica hi ha diferents mecanismes,
la implementació dels quals depèn de cada sistema operatiu.
Java proveeix aquests mecanismes, però ocultant al programador aquestes
diferències que hi ha a nivell de SO.
Els mecanismes són objectes sincronitzats, semàfors i els monitors.
Els semàfors són mecanismes que permeten que un nombre limitat
de processos accedisquen de manera ordenada a un recurs. Es representa
amb una variable sencera, el valor de la qual és el nombre de llocs
disponibles al recurs compartit i una cua on emmagatzemar els processos
bloquejats que esperen l'accés.
A Java, s'utilitza la classe Semaphore.
A la inicialització es proporciona un valor que serà el nombre de llocs
disponibles.
Hi ha dues operacions atòmiques per accedir i modificar el
valor del semàfor:
adquire():
Mitjançant aquesta operació es disminueix el nombre de buits en un,
si el valor és menor que zero és que no hi ha lloc i el procés s'hauria
de bloquejar fins que hi haja lloc. En cas que el valor siga negatiu, indica
quants fils hi han en espera.
release():
S'utilitza per avisar que un procés ha acabat d'utilitzar
el recurs. Amb aquesta operació s'augmenta un el nombre de llocs disponibles.
Si el valor és menor o igual a zero és que hi ha algun procés bloquejat
esperant i caldrà despertar-lo. El procés que es desperta és aleatori i
depèn de la implementació del semàfor i del SO on s'execute.
Els MUTEX (MUTual EXclusion) són semàfors binaris que sols
permeten que un fil tinga accés a un recurs. Podem crear un semàfor binari
amb new Semaphore(1).
Un monitor és un objecte o mòdul que es pot utilitzar d'una manera
segura per diversos fils i proporciona un mecanisme de exclusió mútua:
sols un fil pot accedir a aquest recurs.
Es podria dir que els monitors són com un forrellat (lock) que permet l'accés o no al recurs.
El seu funcionament és molt similar al dels semàfors binaris,
però amb més simplicitat, ja que el programador no cal que faça
explicita l'adquisició i alliberament del monitor.
Els semàfors depenen que el programador introdueixi les
sentències a l'ordre correcte per no bloquejar el sistema.
A Java, tots els objectes derivats de la classe Object(pràcticament tots),
tenen associats dos monitors:
Un afecta la pròpia classe, que permet que el mateix objecte s'utilitze com un monitor.
L'altre afecta els mètodes definits com synchronized.
Un mètode declarat synchronized garanteix que no es puga executar de
manera concurrent a un altre mètode declarat sinchronized del mateix objecte.
Quan un fil invoca un mètode synchronized intenta prendre el «lock»
de l'objecte a què pertanya el mètode.:
Si està lliure l'adquireix i executa el mètode.
Si el «lock» està ocupat, el fil se suspendrà fins que s'allibere el «lock».
En cas que el mètode siga static synchronized, el «lock» serà de la classe
i afectarà tots els mètodes static synchronized d'aquesta classe.
Per crear un mètode sincronitzat cal afegir la paraula synchronized
a la seua declaració. És important saber que els constructors per defecte
són síncrons, de manera que no es poden marcar amb synchronized.
Quan un fil pren el «lock» d'un objecte pot accedir a un altre mètode
synchronized d'aquest objecte sense necessitat d'alliberar el «lock».
Hi ha un «lock» per cada instància de l'objecte.
Quan s'herete (extends) una classe i se sobreescriga un mètode
synchronized, no és obligatori que el mètode nou siga synchronized.
Si es vol que el mètode de la subclasse siga sincronitzat, cal especificar-ho.
Les eines de sincronització anteriors utilitzen els mètodes wait() i notify() internament
per realitzar la sincronització de fils.
Quan un fil executa el mètode wait(), quedarà en estat suspés i pararà la seua execució
fins que siga notificat.
Quan un fil executa el mètode notify(), notificarà a un fil (el qual no es pot triar) que
pot continuar la seua execució. També existeix el mètode notifyAll(), que notificarà tots
els fils que estiguen esperant.
Tots aquests mètodes estan vinculats a un monitor en concret.
Aquests mètodes són útils si es vol esperar fins que una condició es complisca per poder
continuar amb l'execució del fil.
packageud2.examples.copyshop;importjava.util.ArrayList;importjava.util.List;importjava.util.concurrent.Semaphore;publicclassCopyShop{privateList<Printer>freePrinters;privateList<Printer>usedPrinters;privateSemaphoresemaphore;publicCopyShop(){freePrinters=newArrayList<>();usedPrinters=newArrayList<>();freePrinters.add(newPrinter("HP DeskJet 2755e",100));// freePrinters.add(new Printer("Brother MFC-J1010DW", 120));freePrinters.add(newPrinter("Epson Workforce Pro WF-3820",50));// Semàfor que permet tants clients com impresores en la tendasemaphore=newSemaphore(freePrinters.size());}publicSemaphoregetSemaphore(){returnsemaphore;}publicsynchronizedPrintergetFreePrinter(){Printerp=freePrinters.remove(0);usedPrinters.add(p);returnp;}publicsynchronizedvoidreleasePrinter(Printerp){freePrinters.add(p);usedPrinters.remove(p);}publicstaticvoidmain(String[]args){CopyShopshop=newCopyShop();List<CustomerThread>customers=newArrayList<>();CustomerThreadbob=newCustomerThread("Bob",shop);bob.addDocument("PSP Work",10);bob.addDocument("TFG",70);customers.add(bob);CustomerThreadalice=newCustomerThread("Alice",shop);alice.addDocument("Chopin - Nocturnes, Op. 9: No. 2 in E-Flat Major",5);alice.addDocument("Chopin - Nocturne in C-sharp minor, Op. posth.",4);alice.addDocument("Beethoven - Für Elise",3);alice.addDocument("The Real Book - Volume I",247);customers.add(alice);CustomerThreadpatrick=newCustomerThread("Patrick",shop);patrick.addDocument("Don Quijote de la Mancha",145);customers.add(patrick);CustomerThreadpere=newCustomerThread("Pere",shop);pere.addDocument("Tirant lo Blanc",276);customers.add(pere);CustomerThreadmar=newCustomerThread("Mar",shop);mar.addDocument("Joshua Bloch - Effective Java",50);customers.add(mar);for(CustomerThreadcustomer:customers){customer.start();}for(CustomerThreadcustomer:customers){try{customer.join();}catch(InterruptedExceptione){thrownewRuntimeException(e);}}}}
packageud2.examples.copyshop;publicclassPrinter{privateStringmodel;privateintdelay;publicPrinter(Stringmodel,intdelay){this.model=model;this.delay=delay;}publicStringgetModel(){returnmodel;}publicvoidprintDocument(Documentd){try{intmilis=d.getPages()*delay;Thread.sleep(milis);System.out.printf("Printer %s: Printed document %s with %d pages (%.2f seconds).\n",model,d.getTitle(),d.getPages(),milis/1000.0);}catch(InterruptedExceptione){thrownewRuntimeException(e);}}}
CustomerThread.java
packageud2.examples.copyshop;importjava.util.ArrayList;importjava.util.List;publicclassCustomerThreadextendsThread{privateList<Document>documents;privateStringname;privateCopyShopshop;publicCustomerThread(Stringname,CopyShopshop){this.name=name;this.documents=newArrayList<>();this.shop=shop;}publicList<Document>getDocuments(){returndocuments;}publicvoidaddDocument(Stringtitle,intpages){documents.add(newDocument(title,pages));}@Overridepublicvoidrun(){try{shop.getSemaphore().acquire();Printerprinter=shop.getFreePrinter();System.out.printf("%s ha obtingut l'impresora: %s\n",this.name,printer.getModel());for(Documentd:documents){printer.printDocument(d);}System.out.printf("%s ha alliberat l'impresora: %s\n",this.name,printer.getModel());shop.releasePrinter(printer);shop.getSemaphore().release();}catch(InterruptedExceptione){thrownewRuntimeException(e);}}}
Aquest programa simula una copisteria, que disposa de 3 impressores
que es poden utilitzar al mateix temps.
S'han creat 5 clients, cadascun en un fil distint.
Cada client realitza les següents accions:
Mira si hi ha alguna impressora lliure.
Si hi ha alguna, l'adquireix.
Si no hi ha cap, espera.
Quan aconsegueix accedir a una impressora lliure, imprimeix tots els documents.
Quan acaba d'imprimir, allibera la impressora que estava utilitzant.
Mètode run() de CustomerThread
shop.getSemaphore().acquire();Printerprinter=shop.getFreePrinter();System.out.printf("%s ha obtingut l'impressora: %s\n",this.name,printer.getModel());for(Documentd:documents){printer.printDocument(d);}System.out.printf("%s ha alliberat l'impressora: %s\n",this.name,printer.getModel());shop.releasePrinter(printer);shop.getSemaphore().release();
El mecanisme per gestionar les impressores lliures o ocupades
es realitza mitjançant un semàfor en la classe CopyShop,
que s'ha creat amb el número de impressores que disposa:
Constructor de CopyShop
publicCopyShop(){freePrinters=newArrayList<>();usedPrinters=newArrayList<>();freePrinters.add(newPrinter("HP DeskJet 2755e",100));freePrinters.add(newPrinter("Brother MFC-J1010DW",120));freePrinters.add(newPrinter("Epson Workforce Pro WF-3820",50));// Semàfor que permet tants clients com impressores en la tendasemaphore=newSemaphore(freePrinters.size());}
A més, podem observar que els mètodes getFreePrinter() i releasePrinter()
s'han definit com synchronized.
Aquests mètodes modifiquen els recursos freePrinters i usedPrinters i,
per evitar problemes derivats de la concurrència, s'ha de garantir que
només un fil puga accedir a aquests recursos al mateix temps.
Aquest exemple simula una parada en bòxers d'un cotxe de Formula 1.
Quan un cotxe para, hi ha una persona encarregada de elevar el cotxe per poder canviar
les rodes del cotxe. Cada roda del cotxe és canviada per una persona diferent.
Una vegada s'han canviat totes les rodes, es pot tornar a baixar el cotxe i continuar la carrera.
En el següent codi, creem un mecànic que s'encarrega de pujar i baixar el cotxe, i altres
quatre mecànics que s'encarreguen de canviar les rodes.
L'ordre de les acciona hauria de ser:
El mecànic alça el cotxe.
Els mecànics de les rodes esperen a que el cotxe estiga alçat.
Els mecànics de les rodes canvien les rodes.
El mecànic espera a que totes les rodes hagen segut canviades.
El mecànic baixa el cotxe.
Per realitzar aquestes esperes, s'han definit els següents mètodes en la classe `Car``:
Si un fil intenta canviar una roda (replaceTire), haurà d'esperar fins que el cotxe estiga en alt (raised).
Això es possible gràcies al mètode wait().
Si un altre fil alça el cotxe amb el mètode raise(), notificarà a tots els possibles fils que estiguen esperant
que continuen la seua execució. Com el valor de la variable raised ha canviat, els fils poden continuar la seua execució.
El mateix passa quan un fil intenta baixar el cotxe amb release(). Fins que no s'hagen canviat totes les rodes
no es podrà baixar el cotxe.