View
47
Download
0
Category
Preview:
DESCRIPTION
Ejercicio para la promoción. P= 4 n=16 Cuántas asignaciones, sumas y productos hace c/Procesador? Si P1=P2=P3 y los tiempos de asignación con 1, de suma 2 y de producto 3, si P4 es 4 veces más lento, Cuánto tarda el proceso total? Qué haría Ud. en bien del speed-up??. - PowerPoint PPT Presentation
Citation preview
26-4-2004 1
Ejercicio para la promoción
P= 4 n=16 Cuántas asignaciones, sumas y productos hace c/Procesador?Si P1=P2=P3 y los tiempos de asignación con 1, de suma 2 y de producto 3, si P4 es 4 veces más lento, Cuánto tarda el proceso total? Qué haría Ud. en bien del speed-up??
process worker[w = 1 to P] { # strips en paraleloint first = (w-1) * n/P; # Primer fila del stripint last = first + n/P - 1; # Ultima fila del strip for [i = first to last] { for [j = 0 to n-1] { c[i,j] = 0.0; for [k = 0 to n-1] c[i,j] = c[i,j] + a[i,k]*b[k,j]; } }} Programación Concurrente 2004 - Clase 1
26-4-2004 2
Ejercicio para la promoción
process worker[w = 1 to 4] { # 4 strips en paraleloint first = (w-1) * 4; # n/p = 4 Primer fila del stripint last = first + 3; # Ultima fila del strip#P1 = 1 a 4, P2= 5 a 8, P3= 9 a 12, P4=13 a 16
for [i = first to last] {
for [j = 0 to 15] { c[i,j] = 0.0; # 16 asignaciones
for [k = 0 to 15] c[i,j] = c[i,j] + a[i,k]*b[k,j]; # 16 productos, 16 sumas, 16 asign. } }} Total = 256x4+64 = 1088 as. 16x16x4= 1024 sum 16x16x4= 1024 p Además hay 32x4 incrementos que no consideramos.
Programación Concurrente 2004 - Clase 1
26-4-2004 3
Ejercicio para la promoción
P1, P2, P3 y P4 tienen igual número de operaciones.
Total = 1088 asign. 1024 sumas 1024 productos
Para P1 = P2 = P3 = 1088 + 2048 + 3072 = 6208 unid. de tiempo
Para P4 = 6208 x 4 = 24832 unid. de tiempoHay que esperar a P4
Si todo fuera secuencial:Total = 512x16=8192 as. 256x16=4096 su 256x16= 4096 prod
Para P1 = P2 = P3 = 8192 + 8192 + 12288 = 28672 unid. de tiempoSpeed Up ????? = 28672/24832 = 1.15
Programación Concurrente 2004 - Clase 1
26-4-2004 4
Ejercicio para la promoción
Speed Up ????? = 28672/24832 = 1.15
Si le damos a P4 solo 1 fila y a P1, P2,P3 5 filas, podemos corregir los tiempos:
P1=P2=P3= 1344 as. 16x16x5= 1280 sum 16x16x5= 1280 pP1=P2=P3= 1344 +2560 +3840 = 7744 unid. de tiempo
P4 con una sóla fila = 6204 unid. de tiempo
Speed Up ? = 28672/7744 = 3.70
Mejor balance carga/capacidad Mejor Speed UpPOR QUE NO el Speed-Up = 4 ??
Programación Concurrente 2004 - Clase 1
26-4-2004 5
8-Queens / N-Queens
Estudiar el problema de las 8 reinas en un tablero de ajedrez.Analizar un algoritmo secuencial posible para establecer todas las soluciones.Demostrar que existen 92 soluciones.Analizar una posible solución recursiva.
Programación Concurrente 2004 - Clase 3
Estudiar la paralelización de la solución anterior. Expresar conceptualmente la paralelización. Cuántos procesos concurrentes definiría Ud. ??
26-4-2004 6
Defectos de la sincronización por busy waiting
No hay clara separación entre las variables de sincronización y las usadas para computar resultados.
Es difícil diseñar para probar corrección. Incluso la verificación es compleja cuando se incrementa el número de procesos.
Si implementamos los procesos en un esquema de multiprogramación, es una técnica muy ineficiente.
Programación Concurrente 2004 - Clase 3
26-4-2004 7
Herramientas de mayor nivel---> Semáforos
Semáforo instancia de un tipo de datos abstracto con solo 2 operaciones: P y V
V señala la ocurrencia de un evento.P se usa para demorar un proceso hasta que ocurra un evento.
===> Permiten proteger SC y pueden usarse para implementar sincronización por condición.
Programación Concurrente 2004 - Clase 3
26-4-2004 8
Semáforos
Invariante de Semáforo: En todos los estados de programa visibles,
nP nV + init.
Si s = init + nV - nP semáforo general
=el invariante se convierte en: SEM: s 0
P(s): await s > 0 s := s - 1 V(s): s := s + 1
Programación Concurrente 2004 - Clase 3
26-4-2004 9
Semáforos Binarios. Tipo Semáforo.
BSEM: semáforo binario 0 <= b <= 1
P(b): await b > 0 b := b - 1 V(b): await b < 1 b := b + 1
En un programa, declararemos el tipo semáforo:
VAR mutex: sem:= 1
VAR fork[1:5] : sem:= ([5] 1)
Programación Concurrente 2004 - Clase 3
26-4-2004 10
Semáforos. Usos básicos en sincronización---> cambio de variable.
n procesos P[1:n] ejecutan repetidamente SC y luego SNCSea in[i] = 1 cuando P[i] está en su SC, y 0 en otro caso
var in[1:n] : int := ( [n] 0 ){ CS: in[1] + ..... + in[n] 1 }P[i: 1..n] :: do true
await in[1] + ... + in[n] = 0 in[i] := 1 SECCION CRITICAin[i] := 0SECCION NO CRITICA
odPodemos hacer cambio de variables para que cada sentencia atómica se convierta en una operación de semáforo:Sea mutex un semáforo cuyo valor es:mutex = 1 - (in[1] + ... + in[n])
Programación Concurrente 2004 - Clase 3
26-4-2004 11
Semáforos. Usos básicos en sincronización---> cambio de variable.
El protocolo de entrada a la SC en la solución de grano grueso sería:
await mutex > 0 mutex := mutex - 1; in[i] := 1
El protocolo de salida: mutex := mutex + 1; in[i] := 0
in se convierte en variable auxiliar y se puede borrar.
var mutex : sem := 1P[i: 1..n] :: do true P(mutex) SECCION CRITICA V(mutex) SECCION NO CRITICA od
Es mucho más simple que las soluciones busy-waitingProgramación Concurrente 2004 - Clase 3
26-4-2004 12
Sincronización por barreras (“barrier”)
Hay muchos casos de algoritmos iterativos que computan sucesivas aproximaciones a una respuesta hasta converger. Generalmente manipulan un arreglo, y cada iteración realiza la misma computación sobre todos los elementos del arreglo = Se pueden usar múltiples procesos para computar partes disjuntas de la solución en paralelo
Ignorando terminación, y asumiendo n tareas paralelas en cada iteración, se tiene la forma general:
do true co i := 1 to n código para implementar tarea i ocod
Programación Concurrente 2004 - Clase 3
26-4-2004 13
Sincronización por barreras
más eficiente: crear los procesos una vez al comienzo de la computación, y sincronizarlos al final de cada iteración:
Worker[i: 1..n] :: do true código para implementar la tarea i esperar a que se completen las n tareas od
barrier synchronization: el punto de demora al final de cada iteración representa una barrera a la que todos los procesos deben llegar antes de que se les permita pasar.
Programación Concurrente 2004 - Clase 3
26-4-2004 14
Sincronización por barrera. Contador compartido.
n workers que necesitan encontrarse en una barrera
Se puede usar un entero compartido, count, que es incrementado por cada proceso que llega a la barrera
Si el siguiente es un invariante global, se asegura que ninguno pase la barrera hasta que todos hayan llegado:
COUNT :: ( i : 1 i n : passed[i]=TRUE count = n ) var count := 0, passed[1:n] : bool := ( [n] false ) Worker[i: 1..n] :: do true código para implementar la tarea i count := count + 1 await count = n passed[i] := true od
Programación Concurrente 2004 - Clase 3
26-4-2004 15
Sincronización por barrera. Contador compartido.
Se puede implementar con:
FA(count,1)do count n skip od
Pero count necesita ser reseteada a 0 en cada iteración y antes de que cualquier proceso intente incrementarla
Puede haber memory contention.
Programación Concurrente 2004 - Clase 3
26-4-2004 16
Sincronización por barreras. Flags y coordinadores.
Podemos usar un conjunto adicional de valores compartidos y un proceso adicional. Cada Worker espera por un único valor.
Worker[i] haría:arrive[i] := 1 await continue[i] = 1
Coordinator haría:fa i := 1 to n await arrive[i] = 1 affa i := 1 to n continue[i] := 1 af
arrive y continue son llamadas flags
Programación Concurrente 2004 - Clase 3
26-4-2004 17
Sincronización por barrera. Flags y coordinadores.
var arrive[1:n] : int := ( [n] 0 ), continue[1:n] : int := ( [n] 0 )
Worker[i: 1..n] :: do true código para implementar la tarea i arrive[i] := 1 await continue[i] = 1 continue[i] := 0 odCoordinator :: var i : int do true fa i := 1 to n await arrive[i] = 1 ; arrive[i] := 0 af fa i := 1 to n continue[i] := 1 af od
* requiere un proceso extra y un procesador donde ejecute* el tiempo de ejecución de Coordinator es proporcional a Worker
Programación Concurrente 2004 - Clase 3
26-4-2004 18
Sincronización por barrera. Barreras simétricas.
Una barrera simétrica para n procesos se construye a partir de pares de barreras simples para dos procesos:
P[i] :: await arrive[i] = 0 P[j] :: await arrive[j] = 0 arrive[i] := 1 arrive[j] := 1
await arrive[j] = 1 await arrive[i] = 1 arrive[j] := 0 arrive[i] := 0
Programación Concurrente 2004 - Clase 3
26-4-2004 19
Semáforos en sincronización por barreras.
Idea: usar un semáforo para cada flag de sincronizaciónUn proceso setea un flag ejecutando VUn proceso espera que se setee un flag y lo limpia usando un P
Implementamos una barrera para dos procesos Necesitamos saber cada vez que un proceso llega o parte de la barrera hay que relacionar los estados de los dos procesos
La sincronización barrier es especificada por el predicado:{BARRIER: depart1 arrive2 depart2 arrive1}
var arrive1 := 0, depart1 := 0, arrive2 := 0, depart2 := 0P1:: do true arrive1 := arrive1 + 1 await depart1 < arrive2 depart1 := depart1 + 1 odP2:: do true arrive2 := arrive2 + 1 await depart2 < arrive1 depart2 := depart2 + 1 od
Programación Concurrente 2004 - Clase 3
26-4-2004 20
Semáforos en sincronización por barreras.
Sean:
barrier1 = arrive1 - depart2barrier2 = arrive2 - depart1
var barrier1 : sem := 0, barrier2 : sem := 0P1 :: do true V(barrier1) P(barrier2) odP2 :: do true V(barrier2) P(barrier1) od
Los semáforos se usan como señales que indican cuando ocurren eventos
Programación Concurrente 2004 - Clase 3
26-4-2004 21
Productores y Consumidores: Semáforos binarios divididos (split)
Múltiples productores y consumidores
Los productores envían mensajes que reciben los consumidores
Buffer simple compartido manipulado por deposit y fetch, que deben alternarse
inD y afterD cuentan el número de veces que los productores han comenzado y terminado de ejecutar deposit
inF y afterF cuentan el número de veces que los consumidores han comenzado y terminado de ejecutar fetch
Programación Concurrente 2004 - Clase 3
26-4-2004 22
Productores y Consumidores: Semáforos binarios divididos (split)
var buf : T # para algún tipo T
var inD := 0, afterD := 0, inF := 0, afterF := 0{ PC: inD afterF + 1 inF afterD }Producer[i: 1..M]::do true producir mensaje m deposit: await inD < afterF inD := inD + 1 buf := m afterD := afterD + 1 odConsumer[i: 1..N]:: do true fetch: await inF < afterD inF := inF + 1 m := buf afterF := afterF + 1 consumir mensaje m od
Programación Concurrente 2004 - Clase 3
26-4-2004 23
Productores y Consumidores: Semáforos binarios divididos (split)
Sean empty y full semáforos: empty = afterF - inD + 1; full = afterD - inFvar buf : T # para algún tipo T
var empty : sem := 1, full : sem := 0{ PC’ : 0 empty + full 1 }Producer[i: 1..M]:: do true producir mensaje m deposit: P(empty) buf := m V(full) odConsumer[i: 1..N]:: do true fetch: P(full) m := buf V(empty) consumir mensaje m od
Programación Concurrente 2004 - Clase 3
26-4-2004 24
Semáforos binarios divididos.
empty y full son semáforos binariosJuntos forman lo que se llama “split binary semaphore”: a lo sumo uno de ellos es 1 a la vez, como especifica PC’.
Split Binary Semaphore. Los semáforos binarios b1, ...., bn forman un SBS en un programa si el siguiente es un invariante global:
SPLIT: 0 b1, + ... + bn 1.
Los bi pueden verse como un único semáforo binario b que fue dividido en n semáforos binariosSon importantes por la forma en que pueden usarse para implementar exclusión mutua.
Programación Concurrente 2004 - Clase 3
26-4-2004 25
Buffer limitado. Los semáforos como contadores de recursos
Un productor y un consumidor. El buffer es una cola de mensajes depositados y aún no buscados.
var buf[1:n] : T # para algún tipo Tvar front := 0, rear := 0var empty : sem := n, full : sem := 0 # n - 2 empty + full n{ BUFFER: inD afterF + n inF afterD }Producer:: do true producir mensaje m deposit: P(empty) buf[rear] := m; rear := rear mod n + 1 V(full) odConsumer:: do true fetch: P(full) m := buf[front]; front := front mod n + 1 V(empty) consumir mensaje m
od
Programación Concurrente 2004 - Clase 3
26-4-2004 26
Buffer limitado.
Aquí, los semáforos sirven como contadores de recursos.empty cuenta los slots vacíos, y full cuenta los slots llenos.
Son útiles cuando los procesos compiten por el acceso a recursos de múltiple unidad.
deposit y fetch se asumen atómicas pues hay un productor y un consumidor.Si hay varios productores y varios consumidores, deposit y fetch se convierten en secciones críticas.
Programación Concurrente 2004 - Clase 3
26-4-2004 27
Buffer limitado con múltiples productores y consumidores
var buf[1:n] : T # para algún tipo Tvar front := 0, rear := 0var empty : sem := n, full : sem := 0 # n - 2 empty + full nvar mutexD : sem := 1, mutexF : sem := 1
Producer[1:M]:: do true producir mensaje m deposit: P(empty) P(mutexD) buf[rear] := m; rear := rear mod n + 1 V(mutexD) V(full) od
Programación Concurrente 2004 - Clase 3
26-4-2004 28
Exclusión mútua selectiva. El problema de los filósofos.
Planteo del problema:
Philosopher[i:1..5] :: do true piensa adquiere tenedores come libera tenedores od
Cómo se especifica el adquirir y liberar los tenedores?
Programación Concurrente 2004 - Clase 3
26-4-2004 29
Exclusión mútua selectiva. El problema de los filósofos
Cómo se especifica el adquirir y liberar los tenedores?
Usando contadores incrementales:up[i] cuenta el número de veces que el tenedor i fue levantadodown[i] cuenta el número de veces que fue bajado.
Un tenedor no puede bajarse más veces de las que se levantó, y un tenedor puede se levantado por a lo sumo un filósofo a la vez.
Programación Concurrente 2004 - Clase 3
26-4-2004 30
Exclusión mútua selectiva. El problema de los filósofos.
Solución coarse-grained (usamos i 1 en lugar de (i mod 5) + 1 ):var up[1:5] : int := ( [5] 0 ), down[1:5] int := ( [5] 0 ){ FORKS: ( i: 1 i 5: down[i] up[i] down[i] + 1 ) }
Philosopher[i:1..5]:: do true await up[i] = down[i] up[i] := up[i] + 1 await up[i 1] = down[i 1] up[i 1] := up[i 1] + 1 come down[i] := down[i] + 1 down[i 1] := down[i 1] + 1 piensa od
Programación Concurrente 2004 - Clase 3
26-4-2004 31
Exclusión mútua selectiva. El problema de los filósofos
Cambiando variables:
fork[i] = 1 - ( up[i] - down[i] )fork se convierte en un arreglo de semáforos
Philosopher[i] levanta ambos tenedores ejecutando:P(fork[i]); P(fork[i 1])
Baja los tenedores ejecutando:V(fork[i]); V(fork[i 1])
Asegura que filósofos vecinos no coman al mismo tiempo, pero puede resultar en deadlock.Una condición necesaria para deadlock es que haya waiting circular para evitarlo es suficiente asegurar que no habrá waiting circular.
Programación Concurrente 2004 - Clase 3
26-4-2004 32
Exclusión mútua selectiva. El problema de los filósofos
Para este problema, una posibilidad es hacer que un proceso levante los tenedores en orden inverso:
var forks[1:5] : sem := ( [5] 1 )Philosopher[i:1..4]:: do true P(fork[i]); P(fork[i 1]) come V(fork[i]); V(fork[i 1]) piensa odPhilosopher[5]:: do true P(fork[1]); P(fork[5]) come V(fork[1]); V(fork[5]) piensa od
Programación Concurrente 2004 - Clase 3
26-4-2004 33
Lectores/Escritores resuelto con semáforos
Dos clases de procesos (lectores y escritores) comparten una base de datos.Ambos tipos de procesos son asimétricos y pueden tener diferente prioridad, según el scheduler.
Es un problema de exclusión mutua selectiva: clases de procesos compiten por el acceso a la BD.
writing[j] = 1 cuando un escritor está accediendo la BD
reading =1 cuando cualquier lector está leyendo la BD (sólo se requiere una variable porque no importa cuantos lectores haya)
Programación Concurrente 2004 - Clase 3
26-4-2004 34
Lectores/Escritores resuelto con semáforos
var reading := 0, nr := 0, writing[1:n] := ( [n] 0 )
{ RW: reading + writing[1] + .... + writing[n] 1 }{SUM es reading + writing[1] + .... + writing[n] }
Reader[i:1..m] :: do true nr := nr + 1 if nr = 1 await SUM 0 reading := reading + 1 fi
lee la BD nr := nr - 1 if nr = 0 reading := reading - 1 fi od
Writer[j:1..n] :: do true await SUM 0 writing[j] := writing[j] + 1 escribe la BD writing[j] := writing[j] - 1
odProgramación Concurrente 2004 - Clase 3
26-4-2004 35
Lectores/Escritores con semáforos.
mutexR semáforo para implementar SC entre lectores el protocolo de entrada de los lectores se convierte en:
P(mutexR) nr := nr + 1 if nr = 1 await SUM 0 reading := reading + 1 fiV(mutexR)
Protocolo de salida para el lector:P(mutexR) nr := nr - 1 if nr = 0 reading := reading - 1 fiV(mutexR)
Programación Concurrente 2004 - Clase 3
26-4-2004 36
Lectores/Escritores con semáforos.
rw semáforo: rw = 1 - (reading + writing[1] + .... + writing[n])
var nr := 0, mutexR : sem := 1, rw : sem := 1Reader[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) odWriter[j:1..n] :: do true P(rw) escribe en la BD V(rw) od{Da preferencia a los lectores, no es fair}
Programación Concurrente 2004 - Clase 3
26-4-2004 37
Comentarios sobre las soluciones vistas con semáforos
En la solución entonces se superponen la resolución de dos secciones críticas: una para los escritores y otra para los lectores.
Ahora veremos una técnica más general: “passing the baton”. De este modo usaremos semáforos binarios divididos para producir exclusión y decidir que proceso se “despierta” en un dado momento. De este modo podremos implementar cualquier AWAIT y decidir el orden en que procesos demorados se “despiertan”.
Programación Concurrente 2004 - Clase 5
La solución anterior trata el problema de lectores-escritores como de exclusión mútua. El foco está en que los escritores se excluyen entre sí y los lectores como clase excluyen a los escritores.
26-4-2004 38
Lectores-Escritores con semáforos, revisado.
Contaremos el número de cada clase de proceso que trata de acceder a la BD, y luego se restringen los valores de los contadores
nr y nw enteros no negativos que registran el número de lectores y escritores que están accediendo la BD
El estado malo a evitar es uno en el cual nr AND nw > 0, OR nw > 1
El conjunto de estados buenos es caracterizado por:
RW: ( nr = 0 nw = 0 ) nw 1
Programación Concurrente 2004 - Clase 5
26-4-2004 39
Lectores-Escritores con semáforos, revisado.
var nr := 0, nw := 0{ RW: ( nr = 0 nw = 0 ) nw 1 }
Reader[i:1..m] :: do true await nw = 0 nr := nr + 1 lee la BD nr := nr - 1 od
Writer[j:1..n] :: do true await nr = 0 and nw = 0 nw := nw + 1 escribe la BD nw := nw - 1 od
Programación Concurrente 2004 - Clase 5
26-4-2004 40
La técnica de “passing the baton”
La sincronización con sentencias atómicas de la forma:F1 : Si o F2 : await Bj Sj
Puede hacerse con semáforos binarios divididos (SBS)
Sea e semáforo binario inicialmente 1 (controla la entrada a sentencias atómicas).Además utilizaremos un semáforo bj y un contador dj cada uno con guarda diferente Bj; estos son todos inicialmente 0.
bj se usa para demorar procesos esperando que Bj sea truedj es un contador del número de procesos demorados sobre bj
e y los bj se usa para formar un SBS:
Programación Concurrente 2004 - Clase 5
26-4-2004 41
Lectores-Escritores con semáforos, revisado. Passing the baton.
F1: P(e) Si
SIGNALF2: P(e) if not Bj dj := dj + 1; V(e); P(bj) fi Si
SIGNAL
SIGNAL: if B1 and d1 > 0 d1 := d1 - 1; V(b1) ... Bn and dn > 0 dn := dn - 1; V(bn) else V(e) fi Programación Concurrente 2004 - Clase 5
26-4-2004 42
La técnica de “passing the baton”
La sincronización con sentencias atómicas de la forma:F1 : Si o F2 : await Bj Sj
Puede hacerse con semáforos binarios divididos (SBS)
Sea e semáforo binario inicialmente 1 (controla la entrada a sentencias atómicas).Además utilizaremos un semáforo bj y un contador dj cada uno con guarda diferente Bj; estos son todos inicialmente 0.
bj se usa para demorar procesos esperando que Bj sea truedj es un contador del número de procesos demorados sobre bj
e y los bj se usa para formar un SBS:
Programación Concurrente 2004 - Clase 5
26-4-2004 43
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) ).
Programación Concurrente 2004 - Clase 5
26-4-2004 44
Lectores-Escritores, passing the baton.
r : condición de demora del lector nw = 0w : condición de demora del escritor nr = 0 nw = 0dr y dw los contadores asociados e el semáforo de entradavar 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 SIGNAL1
lee la BD P(e) nr := nr - 1 SIGNAL2
odProgramación Concurrente 2004 - Clase 5
26-4-2004 45
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
od
Programación Concurrente 2004 - Clase 5
26-4-2004 46
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 od 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
Algo similar puede verse para SIGNAL2, SIGNAL3, y SIGNAL4
Programación Concurrente 2004 - Clase 5
26-4-2004 47
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
Programación Concurrente 2004 - Clase 5
26-4-2004 48
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 Programación Concurrente 2004 - Clase 5
Recommended