PDF de programación - Tema 4 - Herramientas avanzadas de comunicación sincronizada - Programación Avanzada

Asignatura 780014

Programación Avanzada

Tema 4 –Herramientas avanzadas de

comunicación sincronizada

Decíamos ayer…

 Java dispone de tres sentencias
para implementar un monitor:



 wait(); el proceso que la ejecuta dentro de
una RC, se queda bloqueado hasta que otro
proceso lo saque de esa situación.

 notify(); ejecutada por un proceso dentro

de una RC, saca a uno de los procesos en
wait de su estado.

 notifyAll(); igual que la anterior, pero saca

a todos los procesos en wait dentro de esa
RC.

 El igloo de los ejemplos

implementado como monitor:
(atención a la forma en que se
comprueba la condición)


// Monitor
public class Igloo {
private boolean pescando=false;

public synchronized void pidoTurno(){
while(pescando){ //El recurso está ocupado
try {
wait();
} catch(InterruptedException e){}
}
pescando=true; //El proceso adquiere el recurso
}

public synchronized void cedoTurno(){
pescando=false; //El proceso libera el recurso
notifyAll(); //Libera los procesos que estén
esperando el recurso
}
}

Monitores de estilo Hoare

 Propuesta original de Hoare y Hansen

– Llamados Monitores de estilo Hoare.
– Proponen un monitor con varias colas

• Tantas como se necesiten
• Cada una implica una condición distinta
• Todas las cosas son justas (fair)

 Comportamiento:

Monitor de estilo Hoare

– Thread A espera una condición específica

• Wait() de una cola específica

– Thread B ejecuta un signal()

• Abandona temporalmente el monitor
• Espera hasta que el thread despertado A

salga del monitor o ejecute un nuevo wait()

Sir Charles Antony Richard Hoare

(Tony Hoare)

Monitores de estilo Hoare

 Comparativa con monitores simples

– Un monitor de Hoare, garantiza que

• Si un proceso sale de su cola de condición, es porque dicha

condición se cumple y no ha dejado de cumplirse

• No es necesario comprobar la condición
• El proceso que detecta la condición y despierta a otro, sale del

monitor en ese momento.

– Un monitor simple, no garantiza

• El cumplimiento de la condición de un proceso despertado
• Cuando llega a ejecutar, puede haber cambiado, es necesario

volver a comprobar

– El proceso que despierta sigue ejecutando
– Otros procesos pueden haber entrado antes

Atomic Variables


• Las Variables Atómicas proporcionan:

– Clases para el manejo atómico (indivisible) de variables simples

• Tipos primitivos o referencias
• Aritmética de alto rendimiento y métodos ‘compare-and-set’.


– Utilidad en la creación de aplicaciones que necesitan

• Sincronización
• Comunicación sincronizada

– En concreto:

• Algoritmos concurrentes de alto rendimiento
• Contadores y generadores de secuencias de números

concurrentes



– Implementado en el paquete java.util.concurrent.atomic

Atomic Variables

 Programación ‘lock-free’ segura sobre variables

simples

 Extienden la noción de volátil sobre:
– Valores, campos y elementos de arrays

– Proporcionán una operación de actualización atómica:



boolean compareAndSet(expectedValue,updateValue);



(Este método pone atómicamente el valor updateValue si el

valor actual es expectedValue, devolviendo true si se
cumple).

Atomic Variables

 Ejemplos de clases atomic:

– AtomicBoolean, AtomicInteger, AtomicLong, y

AtomicReference

– Acceso y actualización a variables de los tipos relacionados

 Ejemplo métodos atómicos increment():

class Sequencer

{

private AtomicLong seqNum = new AtomicLong(0);

public long next()

{

return seqNum.getAndIncrement();

}

}

Semáforos

Tipo Abstracto de Datos (TAD ) concebido por
Dijkstra. Resuelve problemas de concurrencia

Estructura
 Contador
 Cola de procesos

Operaciones
 Declaración: VAR s: SEMAPHORE;
 Initial(s,v) Inicializa el contador de s
 Wait(s) (definida como P por Dijkstra)
Decrementa en uno el contador si es mayor que
cero. Si no, suspende al proceso en la cola.


PROCEDURE wait(s:SEMAPHORE);

BEGIN (* Operación Atómica *)

IF (s.contador>0) THEN

s.contador := s.contador -1;

ELSE

suspende_en(S.cola);

END;

 Signal(s) (definida como V por Dijkstra)



Incrementa en uno el contador si la cola
de procesos está vacía. Si existen procesos
en cola, activa uno.

PROCEDURE signal(s:SEMAPHORE);

BEGIN (* Operación Atómica *)

IF empty(s.cola) THEN

s.contador := s.contador +11;

ELSE

activar_desde(S.cola);

END;

Edsger W. Dijkstra

Semáforos

Atomicidad
wait y signal deben realizarse de forma atómica.

Tipos de Semáforos
Binarios: 0 ó 1
De contador: 0 .. N

Invariantes
a) S >= 0
b) S = S0 + #Signal - #Wait

#signals es la cantidad de signal ejecutados en S

#waits es la cantidad de waits completados en S


Usos de los semáforos
Exclusión Mutua
Sincronización


La clase Java Semaphore

public class Semaphore

•Un semáforo contiene un número de permits.

•Un semáforo puede crearse como ‘justo’ (fair)

– Libera a los procesos bloqueados en el orden de llegada.


– Operaciones disponibles

• acquire() bloquea el thread si es necesario, hasta que haya un permiso y lo

toma.

• release() añade un permiso, liberando potencialmente a un proceso

bloqueado en acquire()

• Antes de bloquearse, un thread puede comprobar si el semáforo tiene permisos

con tryAcquire()

La clase Java Semaphore

 Se utilizan para controlar el número de threads que pueden

acceder a un recurso.

– Un semáforo inicializado a 1 se comporta como semáforo binario.

– Difiere de un lock en que un proceso bloqueado en un semáforo

puede ser liberado por otro, mientras que un lock pertenece al
proceso que lo tiene.

– Pueden tomarse y poner varios permisos de una vez sobre un

semáforo con los métodos acquire(n) y release(n).



Colas y Colecciones

Conceptos:

•JSR166 introdujo dos contenedores de objetos que
grantizan su acceso en exclusión mutua y pueden usarse
para implementar la concurrencia.

• Colas
• Colecciones

Colas concurrentes

 La clase ConcurrentLinkedQueue proporciona

una cola FIFO escalable, concurrente, segura y no
bloqueante.

– Es apropiada cuando muchos threads comparten una

colección.

– Métodos:

• offer(E e) Añade el elemento e al final de la cola

• contains(E e) Dice si el elemento e está en la cola

• poll() Devuelve el primer elemento y lo borra (o null si vacía)

• peek() Devuelve el primer elemento sin borrarlo (o null si vacía)



Colas concurrentes

public class ThreadedQueueExample

{

public static void main(String[] args)

{

Queue<Message> queue = new ConcurrentLinkedQueue<Message>();

Producer p = new Producer(queue);

Consumer c = new Consumer(queue);



Thread t1 = new Thread(p);

Thread t2 = new Thread(c);



t1.start();

t2.start();

}

}

El problema de Productor
y Consumidor resuelto
con una cola concurrente.

Colas Concurrentes

public class Productor implements Runnable {

private static int ctr;

private final Queue<String> colaMensajes;

private final Random r;



public Productor(Queue<Message> colaMensajes) {

this.colaMensajes = colaMensajes;

r = new Random(); }



public void run() {

while (true) {

produce();

try {

Thread.sleep(r.nextInt(5000));

} catch (InterruptedException ex) {}

}

}

private void produce() {

String m = "Mensaje numero: " + (ctr++);

colaMensajes.offer(m);

synchronized (colaMensajes) colaMensajes.notifyAll();

System.out.println("Productor: " + m);

}

}

public class Consumidor implements Runnable {
private final Queue<Message> cola;
public Consumer(Queue<Message> cola) {
this.cola = cola;
}

public void run() {
while (true) {
consume();
try {
synchronized (cola) cola.wait();
} catch (InterruptedException ex) { }
}
}

private void consume() {
while (!cola.isEmpty()) {
String m = cola.poll();
if (m != null) {
System.out.println("Consumidor: " + m);
}
}
}
}

Colas concurrentes

Interface BlockingQueue

– Define 5 versiones de colas bloqueantes donde meter y sacar

elementos:

• LinkedBlockingQueue

• ArrayBlockingQueue

• SynchronousQueue

• PriorityBlockingQueue

• DelayQueue

– Tienen un tamaño máximo definido y permiten esperas por

cola vacía y cola llena.

– Sirven para resolver muchos problemas de concurrencia de

intercambios de mensajes.

Colas concurrentes

 LinkedBlockingQueue

 Basadas en nodos enlazados.

 ArrayBlockingQueue

 Están construidas sobre arrays

 SynchronousQueue

 Cada put espera por un take y viceversa

 PriorityBlockingQueue

 No tiene límite de elementos y los libera en su orden natural

 DelayQueue

 Cada elemento es un objeto Delayed, que solo puede ser extraído después de

transcurrido su tiempo de retardo.



Productores/Consumidores con BockingQueue

class Producer implements Runnable

{

private final BlockingQueue queue;

Producer(BlockingQueue q) { queue = q; }



public void run()

{

try { while(true) { queue.put(produce()); } }

catch (InterruptedException ex) { ... handle ...}

}

Object produce() { ... }

}

Productores/Consumidores con Bock