Conceptos de la clase anterior
La sincronización por busy waiting resulta
ineficiente en multiprogramación. Además la mezcla
de variables “comunes” usadas para sincronizar
hace difícil verificar los algoritmos.
Semáforo  instancia de un tipo de datos abstracto con
solo 2 operaciones: P y V
===> Permiten proteger SC y pueden usarse para
implementar sincronización por condición.
Programación Concurrente 2004 - Clase 4
3-5-04
1
Conceptos de la clase anterior
Vimos la resolución de problemas de sincronización
con semáforos, en particular semáforos binarios y
semáforos binarios divididos.
Analizamos problemas de sincronización entre 2 o
más procesos al llegar a una “barrera”.
Vimos el problema de productores-consumidores, donde la
exclusión es total (entre productores, entre consumidores y
entre ambos tipos de procesos). Discutimos un buffer de
tamaño 1 y de tamaño K.
Programación Concurrente 2004 - Clase 4
3-5-04
2
Conceptos de la clase anterior
Analizamos una clase de problema de exclusión
entre clases de procesos (lectores-escritores) donde
tratamos dos secciones críticas simultáneas.
Discutimos el problema de los filósofos como de
exclusión mútua selectiva. Analizamos la posibilidad de
centralizar el scheduling o hacerlo distribuido.
Quedó planteada la técnica de “passing the baton”
para ser utilizada con semáforos.
Programación Concurrente 2004 - Clase 4
3-5-04
3
Ideas sobre las próximas clases y
primer evaluación teórica
3-5 Semáforos y Políticas de Schedulling.
Pthreads con semáforos. Planteo de clases de problemas.
10-5 Monitores.
17-5 Monitores e Implementaciones (kernels, JAVA).
24-5
Primer parcial teórico, abarcando básicamente
preguntas conceptuales, busy waiting, semáforos y
monitores.
Programación Concurrente 2004 - Clase 4
3-5-04
4
La técnica de “passing the baton”
passing the baton: cuando un proceso está dentro de una
SC mantiene el “baton” (testimonio, token) que significa
permiso para ejecutar.
Cuando el proceso llega a un SIGNAL, pasa el “baton”
(control) a otro proceso.
Si ningún proceso está esperando una condición que sea
true, el baton se pasa al próximo proceso que trata de
entrar a su SC por primera vez (es decir, un proceso que
ejecuta P(e) ).
3-5-04
Programación Concurrente 2004 - Clase 4
5
Lectores-Escritores, passing the
baton.
r : condición de demora del lector
nw = 0
w : condición de demora del escritor
nr = 0  nw = 0
dr y dw los contadores asociados
e el semáforo de entrada
var nr := 0, nw := 0
{ RW: ( nr = 0  nw = 0 )  nw  1 }
var e : sem := 1, r : sem := 0,
{SPLIT: 0  (e + r + w)  1}
var dr := 0, dw := 0
3-5-04
w : sem := 0
{COUNTERS: dr  0  dw  0 }
Programación Concurrente 2004 - Clase 4
6
Lectores-Escritores, passing the
baton.
Reader[i:1..m] :: do true 
P(e)
if nw > 0  dr := dr + 1; V(e); P(r) fi
nr := nr + 1
SIGNAL1
lee la BD
P(e)
nr := nr - 1
SIGNAL2
od
3-5-04
Programación Concurrente 2004 - Clase 4
7
Lectores-Escritores, passing the
baton.
Writer[j:1..n] :: do true 
P(e)
if nr > 0 or nw > 0 
dw := dw + 1;
V(e); P(w)
fi
nw := nw + 1
SIGNAL3
escribe la BD
P(e)
nw := nw - 1
SIGNAL4
Programación Concurrente 2004 - Clase 4
od
3-5-04
8
Lectores-Escritores, passing the
baton.
SIGNALi es una abreviación de:
if nw = 0 and dr > 0  dr := dr - 1; V(r)
 nr = 0 and nw = 0 and dw > 0  dw := dw - 1; V(w)
 (nw > 0 or dr = 0 and (nr >0 or nw >0 or dw =0)  V(e)
fi
nr > 0 y nw = 0 son true antes de SIGNAL1  :
if dr > 0  dr := dr -1; V(r)  dr = 0  V(e) fi
Análogamente para SIGNAL2, SIGNAL3, y SIGNAL4
3-5-04
Programación Concurrente 2004 - Clase 4
9
Lectores-Escritores, passing the
baton.
var nr := 0, nw := 0
{ RW: ( nr = 0  nw = 0 )  nw  1 }
var e : sem := 1, r : sem := 0, w : sem := 0 {SPLIT: 0  (e + r + w)  1 }
var dr := 0, dw := 0
{COUNTERS: dr  0  dw  0 }
Reader[i:1..m] :: do true 
P(e)
if nw > 0  dr := dr + 1; V(e); P(r) fi
nr := nr + 1
if dr > 0  dr := dr - 1; V(r)  nr = 0  V(e) fi
lee la BD
P(e)
nr := nr - 1
if nr = 0 and dw > 0  dw := dw - 1; V(w)
 nr > 0 or dw = 0  V(e)
fi
od
3-5-04
Programación Concurrente 2004 - Clase 4
10
Lectores-Escritores, passing the
baton.
Writer[j:1..n] :: do true 
P(e)
if nr > 0 or nw > 0  dw := dw + 1; V(e); P(w) fi
nw := nw + 1
V(e)
escribe la BD
P(e)
nw := nw - 1
if dr > 0  dr := dr - 1; V(r)
 dw > 0  dw := dw - 1; V(w)
 dr = 0 and dw = 0  V(e)
fi
od
Da a los lectores preferencia sobre los escritores. Puede modificarse
3-5-04
Programación Concurrente 2004 - Clase 4
11
Habíamos visto Lectores/Escritores con
semáforos y preferencia para los lectores.
rw semáforo:
rw = 1 - (reading + writing[1] + .... + writing[n])
var nr := 0, mutexR : sem := 1, rw : sem := 1
Reader[i:1..m] :: do true 
P(mutexR)
nr := nr + 1
if nr = 1  P(rw) fi
V(mutexR)
lee la BD
P(mutexR)
nr := nr - 1
if nr = 0  V(rw) fi
V(mutexR)
od
Writer[j:1..n] :: do true 
P(rw)
escribe en la BD
V(rw)
od
{Da preferencia a los lectores, no es fair}
3-5-04
12
Programación Concurrente 2004 - Clase 4
Ahora, Lectores-Escritores con preferencia
para los escritores.
INT nr = 0, nw=0;
SEM m1= 1, m2=1, m3=1; # semáforos para exclusión mútua
SEM read=1, write=1;
# semáforos de lectura-escritura
Procesos Lectores;
P(m3);
P(read);
P(m1);
nr = nr + 1;
IF (nr == 1) P(write);
V(m1);
V(read);
V(m3);
LEER LA BD;
P(m1);
nr= nr – 1;
IF (nr == 1) V(write);
V(m1);
3-5-04
Programación Concurrente 2004 - Clase 4
13
Lectores-Escritores con preferencia para los
escritores.
Procesos Escritores;
P(m2);
nw = nw + 1;
IF (nw == 1) P(read);
V(m2);
P(write);
ESCRIBIR LA BD;
V(write);
P(m2);
nw= nw – 1;
IF (nw == 0) V(read);
V(m2);
3-5-04
Programación Concurrente 2004 - Clase 4
14
Asignación de recursos y schedulling.
Problema===>decidir cuándo se le puede dar a un
proceso determinado acceso a un recurso.
Recurso===>cualquier objeto, elemento, componente,
dato por la que un proceso puede ser demorado
esperando adquirirlo.
Programación Concurrente 2004 - Clase 4
3-5-04
15
Asignación de recursos y schedulling.
Hasta ahora, empleamos la política más simple:
si algún proceso está esperando y el recurso está
disponible, se lo asigna (allocation).
La política de alocación más compleja fue en R/W,
aunque se daba preferencia a clases de procesos,
no a procesos individuales.
Qué es lo que viene??
Programación Concurrente 2004 - Clase 4
3-5-04
16
Planteo general del problema de
asignación (alocación)de recursos.
N procesos identificables compiten por el uso de unidades
de un recurso compartido (cada unidad está libre o en uso).
request(parámetros):
await ( request puede ser satisfecho)  tomar unidades
release(parámetros):
retornar unidades
Este patrón general puede implementarse usando la
técnica de “passing the baton”.
3-5-04
Programación Concurrente 2004 - Clase 4
17
Planteo general del problema de
asignación de recursos
request tiene la forma de un AWAIT general 
request(parámetros):
P(e);
IF(request no puede ser satisfecho)  DELAY;
tomar unidades del recurso;
SIGNAL;
release tiene la forma 
release(parámetros):
P(e);
retorna unidades del recurso;
SIGNAL;
Programación Concurrente 2004 - Clase 4
3-5-04
18
Asignación de recursos SJN
(Shortest Job Next)
N procesos compiten por el uso de un único recurso
compartido (1 unidad).
Se le dará prioridad al proceso que “prometa” usar
menos tiempo al recurso compartido.
request(time,id) = AWAIT (free == true) free = false 
time indica el tiempo solicitado.
Id indica cual es el proceso.
Si el recurso está libre, es inmediatamente asignado al
proceso; si no, el proceso se demora.
3-5-04
Programación Concurrente 2004 - Clase 4
19
Asignación de recursos SJN
(Shortest Job Next)
release( ) = free = true 
Cuando el recurso es liberado, es alocado al proceso
demorado (si lo hay) que tiene el mínimo valor de time.
Si dos o más procesos tienen el mismo valor de time, el
recurso es alocado al que ha permanecido en la cola de
espera más tiempo.
Ejemplos:
- alocación de procesador (time es el tiempo de ejecución)
- spooling de una impresora (time tiempo de impresión)
3-5-04
Programación Concurrente 2004 - Clase 4
20
Asignación de recursos: SJN
(Shortest Job Next)
SJN minimiza el tiempo promedio de uso, pero NO es fair
request(time, id):
P(e);
IF (free ==false )  DELAY;
free = false;
V(e); # SIGNAL
release( ):
P(e);
free = true;
SIGNAL;
3-5-04
Programación Concurrente 2004 - Clase 4
21
Asignacion de recursos SJN:
Comentarios Previos
En DELAY un proceso:
 inserta sus parámetros en un conjunto, cola o lista de
espera que llamaremos pairs.
 libera la SC ejecutando V(e).
 se demora en un semáforo hasta que el request puede ser
satisfecho.
3-5-04
Programación Concurrente 2004 - Clase 4
22
Asignacion de recursos SJN:
Comentarios Previos
Cuando el recurso es liberado, si el conjunto pairs no está
vacío, el recurso es asignado a un proceso de acuerdo con la
política SJN.
Cada proceso tiene una condición de demora distinta,
dependiendo de su posición en pairs.
b[1:n] arreglo
inicialmente 0.
de
semáforos,
donde
cada
entry
es
 el proceso id se demora sobre el semáforo b[id]
3-5-04
Programación Concurrente 2004 - Clase 4
23
Alocación de recursos: SJN
bool free = true;
sem e = 1, b[n] = ([n] 0); # for entry and delay
typedef Pairs = set of (int, int);
Pairs pairs =  ;
# SJN: pairs es un conjunto ordenado  free  ( pairs==  )
request(time,id):
P(e);
IF (! free) {
insert (time,id) in pairs;
V(e);
# release entry lock
P(b[id]); # El proceso espera en SU semáforo a ser despertado
}
free = false; # Se está tomando el recurso
V(e);
# Se libera el entry lock para encolar otros procesos
3-5-04
Programación Concurrente 2004 - Clase 4
24
Alocación de recursos: SJN
release( ):
P(e);
free = true;
IF (pairs   ) {
 remover el primer par (time,id) de pairs;
V(b[id]); # pasar el control (baton) al proceso id
}
ELSE V(e);
Se asume que el insert en request pone el proceso en el
lugar apropiado del conjunto pairs, para mantener el criterio
de SJN
3-5-04
Programación Concurrente 2004 - Clase 4
25
Comentarios sobre la solución del
problema de SJN
Los semáforos b[id] son ejemplos de semáforos
privados. A diferencia de los vistos anteriormente, se
asocian con un único proceso.
s es un semáforo privado si exactamente un proceso (y
sólo ese proceso) ejecuta operaciones P y V sobre s
Útiles para señalar procesos individuales.
Se puede generalizar la solución a recursos de más
de una unidad.
Programación Concurrente 2004 - Clase 4
3-5-04
26
Conceptos de Pthreads.
Un thread es un proceso que tiene su propio contador de
programa y su pila de ejecución, pero no controla el “contexto”
(todas las tablas asociadas con la aplicación por ejemplo).
Algunos sistemas operativos y lenguajes proveen mecanismos
para permitir la programación de aplicaciones “multithreading”.
En principio estos mecanismos fueron heterogéneos y poco
portables. = a mediados de los 90 POSIX desarrolló una
biblioteca en C para multithreading. (Pthreads)
Con esta biblioteca se pueden crear threads, asignarles
atributos, darlos por terminados, identificarlos, etc.
3-5-04
Programación Concurrente 2004 - Clase 4
27
Semáforos con Pthreads.
Los threads pueden sincronizar por semáforos (semaphore.h es el
archivo que contiene las definiciones y operaciones para los semáforos
con Pthreads).
Los semáforos pueden declararse globales a threads que los van a
utilizar:
sem_t mutex;
En la operación sem_init se inicializa un semáforo, indicando por
ejemplo si el semáforo es compartido por threads de diferentes
procesos, o sólo por los threads del mismo proceso:
Sem_init (&mutex, SHARED, 1);
Las operaciones sem_wait(&mutex) y sem_post(&mutex) equivalen
a las operaciones P y V sobre el semáforo.
3-5-04
Programación Concurrente 2004 - Clase 4
28
Productores-Consumidores con
Pthreads.
Las funciones de Productor y Consumidor serán
ejecutadas por threads independientes.
Acceden a un buffer compartido, data.
El productor deposita una secuencia de enteros de 1 a
numiters en el buffer.
El consumidor busca estos valores y los suma.
Los semáforos empty y full garantizan el acceso
alternativo de productor y consumidor sobre el buffer.
3-5-04
Programación Concurrente 2004 - Clase 4
29
Productores-Consumidores con
Pthreads. (Leerlo)
#include <pthread.h> /* standard lines */
#include <semaphore.h>
#define SHARED 1
#include <stdio.h>
void *Producer(void *); /* the two threads */
void *Consumer(void *);
sem_t empty, full; /* global semaphores */
int data; /* shared buffer */
int numIters;
/* main() -- read command line and create threads */
int main(int argc, char * argv[ ]) {
pthread_t pid, cid; /* thread and attributes */
pthread_attr_t attr; /* descriptors */
pthread_attr_init(&attr);
pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);
3-5-04
Programación Concurrente 2004 - Clase 4
30
Productores-Consumidores con
Pthreads. (leerlo)
sem_init(&empty, SHARED, 1); /* sem empty = 1 */
sem_init(&full, SHARED, 0);
/* sem full = 0 */
numIters = atoi(argv[1]);
pthread_create(&pid, &attr, Producer, NULL);
pthread_create(&cid, &attr, Consumer, NULL);
pthread_join(pid, NULL);
pthread_join(cid, NULL);
}
/* deposit 1, ..., numIters into the data buffer */
void *Producer(void *arg) {
int produced;
for (produced = 1; produced <= numIters; produced++) {
sem_wait(&empty);
data = produced;
sem_post(&full);
}
}
3-5-04
Programación Concurrente 2004 - Clase 4
31
Productores-Consumidores con
Pthreads. (leerlo)
/* fetch numIters items from the buffer and sum them */
void *Consumer(void *arg) {
int total = 0, consumed;
for (consumed = 1; consumed <= numIters; consumed++) {
sem_wait(&full);
total = total + data;
sem_post(&empty);
}
printf("the total is %d\n", total);
}
3-5-04
Programación Concurrente 2004 - Clase 4
32
Casos problema de interés: Grafo de
precedencia
Analizar el problema de modelizar N procesos que deben
sincronizar, de acuerdo a lo especificado por un grafo de
precedencia arbitrario. (con semáforos)
N2
N3
N1
N4
N5
N6
3-5-04
Programación Concurrente 2004 - Clase 4
33
Casos problema de interés: Grafo de
precedencia
Por ejemplo en este caso N4 hará P(N3) y V(N5), N1 hará V(N2) y
V(N6)...
N2
N3
N1
N4
N5
N6
3-5-04
Programación Concurrente 2004 - Clase 4
34
Casos problema de interés: ProductoresConsumidores con broadcast.
En el problema del buffer atómico, tenemos un proceso productor
y N procesos consumidores. El proceso Productor DEPOSITA y
debe esperar que TODOS los procesos consumidores consuman
el mismo mensaje (broadcast).
Notar la diferencia entre una solución por memoria compartida y
por mensajes.
Una versión más compleja del problema es un buffer con K
lugares, un productor y N consumidores. Ahora el productor
puede depositar hasta K mensajes, los N consumidores deben
leer cada mensaje para que el lugar se libere y el orden de
lectura de cada consumidor debe ser FIFO.
Analizar el tema con semáforos.
3-5-04
Programación Concurrente 2004 - Clase 4
35
Casos problema de interés: Variantes del
problema de los Filósofos.
Si en lugar de administrar tenedores, cada filósofo tiene un estado
(comiendo, pensando, con hambre) y debe consultar a sus dos
filósofos laterales para saber si puede comer, tendremos una
solución distribuida donde se puede utilizar la técnica de “passing
the baton”.
Otra alternativa es tener una solución de filósofos centralizada, en
la que un scheduler administra por ejemplo los tenedores y los
asigna con posiciones fijas o variables (notar la diferencia).
En la solución que vimos de filósofos, para evitar el deadlock
utilizabamos un código diferente para un filósofo (orden de
toma de los tenedores). Otra alternativa es la de la elección al
azar del primer tenedor a tratar de tomar... Cómo?
3-5-04
Programación Concurrente 2004 - Clase 4
36
Casos problema de interés: El problema de
los baños.
Un baño único para varones o mujeres (exluyente) sin límite de
consumidores.
Un baño único para varones o mujeres (excluyente) ´con un
número máximo de ocupantes simultáneos (que puede ser
diferente para varones y mujeres)
Dos baños utilizables simultáneamente por un número máximo
de varones (K1) y de mujeres (K2), con una restricción adicional
respecto que el total de consumidores (v + m) debe ser menor
que una restricción K3 < (K1 + K2).
3-5-04
Programación Concurrente 2004 - Clase 4
37
Casos problema de interés: El problema de
la molécula de agua.
Existen procesos O (oxígeno) y H (hidrógeno) que en un
determinado momento toman un estado “ready” y se buscan para
combinarse formando una molécula de agua (HH0).
Puede pensarse en un esquema cliente-servidor, donde el servidor
es el proceso que recibe los pedidos y cuando tiene 2 Hready y 1
Oready concreta la molécula de agua y libera los procesos H y O.
También puede pensarse como un esquema “passing the baton”
que puede iniciarse por cualquiera de los dos procesos H o por el
proceso O, pero tiene un orden determinado (analizar con cuidado).
Podría pensar la solución con un esquema de productoresconsumidores? Quiénes serían los productores y quienes los
consumidores? Niveles.
3-5-04
Programación Concurrente 2004 - Clase 4
38
Casos problema de interés: El puente de
una vía.
Suponga un puente de una sóla vía que es accedido por sus
extremos, digamos por procesos Norte y procesos Sur. Cómo
especificaría la exclusión mútua sobre el puente, de modo que
circulen los vehículos (procesos) en una sola dirección.
El problema anterior es un caso típico donde es difícil asegurar
fairness y no inanición. Por qué ? Cuál podría ser un método para
asegurar no inanición con un scheduler ? Qué ideas propone para
tener fairness entre Norte y Sur ?
Suponga que cruzar el puente requiere a lo sumo 3 minutos y
Ud. Quiere implementar una solución tipo “time sharing” entre
los procesos Norte y Sur, habilitando alternativamente el puente
15 minutos en una y otra dirección. Cómo lo esquematizaría?
3-5-04
Programación Concurrente 2004 - Clase 4
39
Casos problema: Search–Insert- Delete
sobre una lista c/ procesos concurrentes.
Una generalización de la exclusión mútua selectiva entre clases de
procesos que vimos con lectores-escritores es el problema de
procesos que acceden a una lista enlazada con posibilidad de
buscar (search), Insertar al final de la lista o Borrar un elemento en
cualquier posición de la lista.
Los procesos que BORRAN se excluyen entre sí y además
excluyen a los procesos que buscan e insertan. Sólo un proceso de
borrado puede acceder a la lista.
Los procesos de inserción se excluyen entre sí, pero pueden
coexistir con los procesos de búsqueda. A su vez los procesos
de búsqueda NO se excluyen entre sí
3-5-04
Programación Concurrente 2004 - Clase 4
40
Un problema para investigar: drinking
philosophers
Investigar el tema definido por Chandy y Misra en 1984.
Se trata de una generalización del problema de los dining
philosophers.
Analizar las diferencias de los dos problemas, estudiar los
mecanismos de sincronización y discutir las ventajas/dificultades de
utilizar semáforos en la sincronización.
3-5-04
Programación Concurrente 2004 - Clase 4
41
Descargar

Teoría 4