Date post: | 01-Jul-2015 |
Category: |
Documents |
Upload: | oriol-torres |
View: | 89 times |
Download: | 1 times |
PROGRAMACIÓ CONCURRENT
Semàfors 3
PROCESSOS CONCURRENTS I MEMÒRIA COMPARTIDA
El mètode més senzill de comunicació entre els processos d’un programa concurrent és l’ús comú d’unes variables de dades.
PROBLEMA D’AQUESTA METODOLOGIA: L’acció d’un procés pot interferir en les accions d’un altre.
COM EVITEM AQUEST TIPUS D’ERRORS? Identificant aquelles regions dels processos que accedeixen a variables compartides i dotant-les de la possibilitat d’execució com si fossin una única instrucció.
PROCESSOS CONCURRENTS I MEMÒRIA COMPARTIDA
Seccions crítiques
La programació concurrent pot donar lloc a molts errors donada la utilització de recursos compartits que poden ser alterats.
Les seccions de codi potencialment perilloses de provocar aquests errors es coneixen com seccions crítiques.
PROCESSOS CONCURRENTS I MEMÒRIA COMPARTIDA
Què és una secció crítica?
public class Taula { int quantitat; public Taula() { quantitat=0; } public void posarCaixa(){ quantitat=quantitat+1; } public void prendreCaixa(){ while (quantitat≤2) quantitat=quantitat-2; } }
El procés Repartidor intenta prendre 2 encàrrecs. Si, solament, n’hi ha 1 o 0 esperar fins que, com a mínim, n’hi hagin 2.
PROCESSOS CONCURRENTS I MEMÒRIA COMPARTIDA
Què és una secció crítica?
public class Taula { int quantitat; public Taula() { quantitat=0; } public void posarCaixa(){ quantitat=quantitat+1; } public void prendreCaixa(){ while (quantitat≤2) quantitat=quantitat-2; } }
El cuiner i el
repartidor
accedeixen a DADES
COMPARTIDES
MODIFICABLES?
Cuiner i repartidor
comparteixen la
variable quantitat.
PROCESSOS CONCURRENTS I MEMÒRIA COMPARTIDA
Què és una secció crítica?
La variable quantitat
acabarà presentant un
valor incorrecte perquè
es permet que ambdós
fils manipulin la variable
de manera concurrent.
PROCESSOS CONCURRENTS I MEMÒRIA COMPARTIDA
Què és una secció crítica?
Quina serà la secció
crítica del cuiner? I la
del repartidor?
public void posarCaixa(){
quantitat=quantitat+1; }
public void prendreCaixa(){ while (quantitat ≤ 2)
quantitat=quantitat-2; } }
Localitzar la secció crítica
en un exemple donat
MECANISMES BASATS EN LA MEMÒRIA COMPARTIDA
Idealment, desitjarem que únicament un fil pugui accedir/executar simultàniament a determinades regions de programari (secció crítica) Haurem de definir, doncs, una zona d’exclusió mútua.
Haurem de instal·lar un mecanisme de control • Que permeti l’entrada d’un procés si el recurs està
disponible (i) • Que prohibeixi l’entrada d’un procés si el recurs es
troba ocupat.
MECANISMES BASATS EN LA MEMÒRIA COMPARTIDA
Idealment, desitjarem que únicament un fil pugui accedir/executar simultàniament a determinades regions de programari (secció crítica) Zona d’exclusió mútua. Exemple:
Per controlar el pas a un túnel d’un sol
carril, en ambdós costats del túnel es
col·loquen semàfors.
Quan un automòbil troba el semàfor en
verd, té permís d’entrada, entra i,
immediatament, el semàfor es posa en
vermell fins que surt del túnel.
MECANISMES BASATS EN LA MEMÒRIA COMPARTIDA
Idealment, desitjarem que únicament un fil pugui accedir/executar simultàniament a determinades regions de programari (secció crítica) Zona d’exclusió mútua. Exemple:
Per controlar el pas a un túnel d’un sol
carril, en ambdós costats del túnel es
col·loquen semàfors.
Quan un automòbil troba el semàfor en
verd, té permís d’entrada, entra i,
immediatament, el semàfor es posa en
vermell fins que surt del túnel.
.......
if (Semafor.equals(“Verd”)) {
PermisPerPassar();
Semafor=“Vermell”;
}
.............
MEMÒRIA COMPARTIDA Arquitectures
No estructurades Locks (candaus)
Semàfors
Estructurades Blocs synchronized
Mètodes synchronized
Monitors
MEMÒRIA COMPARTIDA Lock
package java.util.concurrent.locks
interfície Lock
class ReentrantLock implements Lock
lock.lock()
int valor = cc.getN(id);
valor++;
sleep(1000);
cc.setN(id, valor);
lock.unlock();
Important: Cal assegurar-se que
s’allibera el forrellat; per
exemple, si hi ha excepcions
MEMÒRIA COMPARTIDA Semàfors
Una de les múltiples formes d’establir zones d’exclusió mútua són els semàfors.
Definits l’any 1968 per Dijkstra.
Els semàfors són components passius de baix nivell d’abstracció que serveixen per arbitrar/gestionar l’accés a un recurs compartit.
MEMÒRIA COMPARTIDA Semàfors
Estructura formada per una posició de memòria i 2 instruccions, una per reservar-la i una altra per alliberar-la.
A això se li pot afegir una cua de fils per recordar l’ordre en que es van realitzar les peticions.
MEMÒRIA COMPARTIDA Semàfors
Un semàfor sincronitzarà 2 o més fils perquè la seva execució es realitzi de forma ordenada i sense conflictes donant permís o restringint l’accés a algun recurs compartit.
MEMÒRIA COMPARTIDA Semàfors binaris
Els semàfors s’implementen amb una cua de tasques (o de condició) a la que s’afegeixen els processos que es troben a l’espera del recurs.
Únicament, es permeten 3 operacions sobre un semàfor:
o Inicialitzar
o Esperar (wait) Anomenada P per Dijkstra (de l’holandès passeren)
o Avisar/Senyal (signal) Anomenada V per Dijkstra (de l’holandès vrygeren)
MEMÒRIA COMPARTIDA Semàfors binaris
En pseudocodi no existeixen els semàfors binaris, per tant, ens haurem d’assegurar que mai assumeixi valors més grans que 1.
Els mètodes que defineix la classe semàfor són: o Wait (). Decrementa el valor del semàfor si aquest és major que 0. Si és
igual a 0, bloquejarà el procés.
o Signal(). Desbloquejarà a un procés bloquejat i si no n’hi ha cap, incrementarà el valor del semàfor.
o Semàfor(int ValorInicial). Constructor de la classe que crea un nou semàfor amb ValorInicial. Aquesta construcció no es pot executar concurrentment – ni definir dins del bloc concurrent -.
MEMÒRIA COMPARTIDA Semàfor
A partir de la Java v.1.5., va sorgir una alternativa a wait/notify Java.util.concurrent.Semaphore accquire() funciona de forma similar a wait(). release() funciona de manera similar a notify(). El semàfor pot permetre més d’un accés (permits).
MEMÒRIA COMPARTIDA Semàfor
package java.util.concurrent class semaphore
Semaphore (int permissos)
Semàfor binari: gestiona 1 permís d’accés void acquire()
void release()
Semàfor general: gestiona N permisos void acquire(int n)
Sol·licita n permisos del semàfor.
o Si no n’hi ha suficients, espero.
o Quan els tingui, continuo.
void release() o Retorno n permisos al semàfor.
o Si hi ha algú esperant, es prova de satisfer-lo.
MEMÒRIA COMPARTIDA Semàfor binari: Ús
semafor.acquire ();
int valor = cc.getN(id);
valor++;
sleep(1000);
cc.setN(id, valor);
semafor.release();
Important: Cal assegurar-se que
s’allibera el forrellat; per
exemple, si hi ha excepcions
MEMÒRIA COMPARTIDA Exemple: Semàfor amb N permissos
public class Tasca extends Thread {
private Semaphore comptador;
public Tasca(Semaphore comptador){
this.comptador=comptador;
}
public void run() {
// fa la seva tasca
comptador.release();
}
}
MEMÒRIA COMPARTIDA Exemple: Semàfor amb N permisos
public class EsperaNtasques {
public static void main(String[] args)
throws comptador = new Semaphore(0);
List<Tasca>tasques = new ArrayList<Tasca>();
tasques.add(new Tasca(comptador));
// .. N vegades
for (Tasca tasca:tasques)
tasca.start();
// espera a que totes acabin
comptador.acquire(tasques.size());
}
}
MEMÒRIA COMPARTIDA Semàfors: Exemple
Els processos P1 i P3 precedeixen als processos 2 i 4. És a dir, P2 i P4 no podran arrencar fins que P1 i P3 hagin finalitzat la seva secció crítica.
Primera opció: Treballa sense semàfors. Definim 4 classes que llençarem com a processos, executaran un sleep() simulant un processament i, a continuació imprimir el número de procés.
Amb l’execució obtindrem diferents resultats donat que cada procés
tardarà més o menys en executar-se.
Segona opció: Sincronització dels processos.
Ara les possibles sortides són {P3, P1, P2, P4}, {P1, P3, P4, P2}, ..
Es compleix perfectament la sincronització requerida.
MEMÒRIA COMPARTIDA Classe java.util.concurrentSemaphore
En alguns sistemes corporatius, pot ser interessant regular el número de sol·licituds obertes (fils/accions) envers un recurs en particular – de vegades, la regulació pot millorar el rendiment d’un sistema en reduir la quantitat de contenció davant d’aquest recurs en particular -. Qui s’encarrega d’aquesta regulació? Els semàfors. Seguint l’exemple [Ex1], tot i que els 10 fils s’estiguin executant, únicament 3 es troben actives. Els 7 restants es troben continguts en el compartiment fins que un dels comptadors semàfors l’alliberi.
Exemple 1:
SemaforTestCinc
MEMÒRIA COMPARTIDA Classe java.util.concurrentSemaphore
La classe java.util.concurrent.Semaphore és un semàfor comptador que resulta d’utilitat per la implementació de la regulació sobre un recurs compartit. Per tant, com podríem forçar a 5 perquè s’executin simultàniament, fins i tot quan tenim 10 fils d’execució? new Semaphore(5); En el cas de l’exemple [EX2], 5 fils correran de forma concurrent, dormiran durant 5 segons i, després, uns altres 5 fils correran de forma concurrent altre cop i dormiran durant 5 segons i, etc. I si canviem el número dels permisos dels semàfors a, per exemple, 2 permisos (new Semaphore (2);)? Únicament 2 fils correran de forma concurrent, .. El semàfor és l’encarregat de controlar la regulació. Exemple 2:
SemaforTestCinc
MEMÒRIA COMPARTIDA Classe java.util.concurrentSemaphore
Ja hem vist que podem regular el número de sol·licituds obertes (fils/accions) envers un recurs en particular utilitzant un semàfor. Per altra banda, podem millorar el rendiment d’un sistema gestionant/regulant varis semàfors i, en conseqüència, les sol·licituds obertes en cadascun d’ells. En l’exemple [Ex3], utilitzarem diferents semàfors definint la grandària de la cua en funció dels nens/fils/accions que volem permetre que estigui en cada estació.
Exemple 3:
Hot dogs