Semaforos

50 %
50 %
Information about Semaforos

Published on June 24, 2007

Author: stefanosalvatori

Source: slideshare.net

Description

semaforos

Semáforos Cecilia Hernández 2007-1

Semáforos Primitiva de Sincronización propuesta por Dijkstra en 1968 Como parte de sistema THE Usados para exclusión mutua y planificación De nivel más alto que locks Variable atómica manipulada por dos operaciones Wait(semaforo) Decrementa semáforo Bloquea hebra/proceso si el semáforo es menor que cero, sino entonces permite a hebra/proceso continuar Operacion tambien llamada P(semaforo) o down(semaforo) Signal(semáforo) Incrementa semáforo en uno y si hay algún proceso/hebra esperando lo despierta También llamada V(semaforo) o up(semaforo) Valor de semáforo puede ser mayor que 1 Inicializado en 1 es como lock. Usado para exclusión mutua Inicializado en N Usado como contador atómico

Primitiva de Sincronización propuesta por Dijkstra en 1968

Como parte de sistema THE

Usados para exclusión mutua y planificación

De nivel más alto que locks

Variable atómica manipulada por dos operaciones

Wait(semaforo)

Decrementa semáforo

Bloquea hebra/proceso si el semáforo es menor que cero, sino entonces permite a hebra/proceso continuar

Operacion tambien llamada P(semaforo) o down(semaforo)

Signal(semáforo)

Incrementa semáforo en uno y si hay algún proceso/hebra esperando lo despierta

También llamada V(semaforo) o up(semaforo)

Valor de semáforo puede ser mayor que 1

Inicializado en 1 es como lock.

Usado para exclusión mutua

Inicializado en N

Usado como contador atómico

Implementación de Semáforos typedef struct { int value; struct hebra *L; } semaphore; void wait(semaphore S) { S.value--; if (S.value < 0){ agregar hebra a S.L; block(); } } void signal(semaphore S){ S.value++; if (S.value <= 0){ remover hebra T de S.L; wakeup(T); } }

Exclusión mutua vs planificación Sección crítica lock unlock Exclusión mutua Sólo una hebra a la vez en SC - Puede ser cualquier hebra Planificación Requerimiento de orden en ejecución de hebras. tiempo

Exclusión mutua

Sólo una hebra a

la vez en SC

- Puede ser cualquier hebra

Planificación

Requerimiento de

orden en ejecución de hebras.

Ejemplo planificación sem S1 = 0, S2 = 0 H1: H2: H3: print A; wait(S1); wait(S2); signal(S1); print B; print C; signal(S2); tiempo H1. imprime A H2. imprime B H3. imprime C

sem S1 = 0, S2 = 0

H1: H2: H3:

print A; wait(S1); wait(S2);

signal(S1); print B; print C;

signal(S2);

Tipos de Semáforos Binarios (mutex) Garantizan exclusión mutua a recurso Sólo una hebra/proceso puede accesar sección crítica a la vez Contador de semáforo inicializado en 1 Contadores Representan recursos con más de una unidad disponible Permiten accesar recursos de acuerdo al número de recursos disponibles Contador es inicializado en N, donde N es la cantidad de unidades disponibles del recurso

Binarios (mutex)

Garantizan exclusión mutua a recurso

Sólo una hebra/proceso puede accesar sección crítica a la vez

Contador de semáforo inicializado en 1

Contadores

Representan recursos con más de una unidad disponible

Permiten accesar recursos de acuerdo al número de recursos disponibles

Contador es inicializado en N, donde N es la cantidad de unidades disponibles del recurso

Ejemplos Clásicos de Sincronización Problema Productor/Consumidor Un buffer en memoria con N slots disponibles Necesita llevar cuenta de ítemes en buffer Productor produce ítemes a ingresar al buffer Consumidor consume ítemes del buffer P C out in Productor Agrega item usando puntero in Consumidor Remueve item usando puntero out

Problema Productor/Consumidor

Un buffer en memoria con N slots disponibles

Necesita llevar cuenta de ítemes en buffer

Productor produce ítemes a ingresar al buffer

Consumidor consume ítemes del buffer

Algoritmo Productor/Consumidor int contador = 0; //indica número de items en buffer Tipo buffer[N]; int in = 0; int out = 0; Productor while (true) { /* produce un item en proxProd */ while (contador == N); //espera buffer[in] = proxProd; in = (in + 1) % N; contador++; } Consumidor while (true) { while (contador == 0); //espera proxCons = buffer[out]; out = (out + 1) % N; contador--; /* consume prodCons */ }

Cómo resolver problema? Identificar restricciones inherentes al problema Estado compartido? contador (consumidores y productores) Buffer in ( productores) . Productores no pueden insertar en buffer lleno out ( consumidores). Consumidores no pueden extraer de buffer vacío Posible resolver con locks? Si Posible resolver con semáforos? Si

Identificar restricciones inherentes al problema

Estado compartido?

contador (consumidores y productores)

Buffer

in ( productores) . Productores no pueden insertar en buffer lleno

out ( consumidores). Consumidores no pueden extraer de buffer vacío

Posible resolver con locks? Si

Posible resolver con semáforos? Si

Cómo resolver problema? Identificar estado compartido y restricciones de problema Buffer de tamaño limitado compartido entre productores y consumidores Productor escribe en buffer[in], in indica posición de escritura en buffer Consumidor extrae de buffer[out], out indica posición de extracción de buffer Contador indica el número de elementos actuales en el buffer Múltiples productores deben manipular in, buffer[in] y contador atómicamente. Múltiples consumidores deben manipular out, buffer[out] y contador atómicamente Múltiples consumidores y productores deben manejar contador atómicamente

Identificar estado compartido y restricciones de problema

Buffer de tamaño limitado compartido entre productores y consumidores

Productor escribe en buffer[in], in indica posición de escritura en buffer

Consumidor extrae de buffer[out], out indica posición de extracción de buffer

Contador indica el número de elementos actuales en el buffer

Múltiples productores deben manipular in, buffer[in] y contador atómicamente.

Múltiples consumidores deben manipular out, buffer[out] y contador atómicamente

Múltiples consumidores y productores deben manejar contador atómicamente

Solución Productor/Consumidor usando locks Productor while (true) { /* produce un item en proxProd */ lock(mutex); while(contador == N){ unlock(mutex); yield(); } buffer[in] = proxProd; in = (in + 1) % N; contador++; unlock(lock); } Consumidor While(true){ lock(mutex); while(contador == 0){ unlock(mutex); yield(); } proxCons = buffer[out]; out = (out + 1) % N; contador--; unlock(mutex); /* consume proxCons */ } int contador = 0; //indica número de items en buffer char buffer[N]; int in = 0; int out = 0; lock_t mutex;

Solución usando semáforos Identificar estado compartido y restricciones de problema Ya presentadas Especificar condiciones de espera y señalización Cuando buffer está lleno productores deben esperar a que exista una posición vacía (generada por un consumidor) Cuando buffer esta vacío consumidores deben esperar a que exista un elemento en el buffer (generado por un productor) Acceso a buffer y contador debe realizarse atómicamente Identificar semáforos para proveer sincronización Mutex (inicializado en 1): para exclusión mutua de buffer, in, out y contador. Full (inicializado en 0). Para indicar cuántas posiciones llenas hay en el buffer Empty (inicializado en N). Para indicar cuantas posiciones vacías hay en el buffer Proporcionar algoritmos

Identificar estado compartido y restricciones de problema

Ya presentadas

Especificar condiciones de espera y señalización

Cuando buffer está lleno productores deben esperar a que exista una posición vacía (generada por un consumidor)

Cuando buffer esta vacío consumidores deben esperar a que exista un elemento en el buffer (generado por un productor)

Acceso a buffer y contador debe realizarse atómicamente

Identificar semáforos para proveer sincronización

Mutex (inicializado en 1): para exclusión mutua de buffer, in, out y contador.

Full (inicializado en 0). Para indicar cuántas posiciones llenas hay en el buffer

Empty (inicializado en N). Para indicar cuantas posiciones vacías hay en el buffer

Proporcionar algoritmos

Solución usando semáforos Productor while (true) { /* produce un item en proxProd */ wait(vacio); wait(mutex); buffer[in] = proxProd; in = (in + 1) % N; contador++; signal(mutex); signal(lleno); } Consumidor While(true){ wait(lleno); wait(mutex); proxCons = buffer[out]; out = (out + 1) % N; contador--; signal(mutex); signal(vacio); /* consume proxCons */ } int contador = 0; //indica número de items en buffer char buffer[N]; int in = 0; int out = 0; sem mutex=1; sem vacio = N; sem lleno = 0;

Ejemplos Productor/consumidor usando pthreads y locks http://www.inf.udec.cl/~chernand/sc/ejemplos/prodconsLocks.C Productor/consumidor usando pthreads y semáforos http://www.inf.udec.cl/~chernand/sc/ejemplos/prodconsSem.C

Productor/consumidor usando pthreads y locks

http://www.inf.udec.cl/~chernand/sc/ejemplos/prodconsLocks.C

Productor/consumidor usando pthreads y semáforos

http://www.inf.udec.cl/~chernand/sc/ejemplos/prodconsSem.C

Problema lectores/escritor Caso base de datos Varios lectores pueden accesar registro datos simultaneamente Sólo un escritor puede escribir E L L Registro BD

Caso base de datos

Varios lectores pueden accesar registro datos simultaneamente

Sólo un escritor puede escribir

Cómo resolver problema? Identificar estado compartido y restricciones de problema Base de datos compartida Mientras haya un lector un escritor no puede accesar base de datos Mientras exista un escritor en base de datos ningún otro escritor o lector puede accesarla Identificar condiciones de espera y señalización Si existe un escritor en BD otro escritor o lector debe esperar Cuando un escritor termina debe señalizar escritor o lector que espera Si podemos tener varios lectores debemos contarlos, para saber cuando existe uno Si hay uno leyendo y llegan otros, otros tambien pueden leer Si solo hay uno y sale puede haber un escritor esperando accesar BD Qué semáforos necesitamos Uno inicializado en 1 como mutex para manejar contador de lectores Uno tipo mutex para escritor y primer lector

Identificar estado compartido y restricciones de problema

Base de datos compartida

Mientras haya un lector un escritor no puede accesar base de datos

Mientras exista un escritor en base de datos ningún otro escritor o lector puede accesarla

Identificar condiciones de espera y señalización

Si existe un escritor en BD otro escritor o lector debe esperar

Cuando un escritor termina debe señalizar escritor o lector que espera

Si podemos tener varios lectores debemos contarlos, para saber cuando existe uno

Si hay uno leyendo y llegan otros, otros tambien pueden leer

Si solo hay uno y sale puede haber un escritor esperando accesar BD

Qué semáforos necesitamos

Uno inicializado en 1 como mutex para manejar contador de lectores

Uno tipo mutex para escritor y primer lector

Algoritmo usando semáforos sem mutex=1; sem escribir = 1; Int contadorLectores = 0; Escritor: wait(escribir); espera por escritor o lector Escritor_escribe; Escribe objeto signal(escribir); permite leer y/o escribir a otros, escritura completada Lector: wait(mutex); asegura acceso exclusivo a contador de lectores contadorLectores = contadorLectores++; incrementa lectores if(contadorLectores == 1) then wait(escribir); Si es el primer lector espera si hay escritor signal(mutex); Lector_lee; wait(mutex); asegura acceso exclusivo a contador de lectores contadorLectores = contadorLectores--; lector terminó de leer if(contadorLectores == 0) then signal(escribir); no mas lectores por si escritor esperaba signal(mutex)

sem mutex=1;

sem escribir = 1;

Int contadorLectores = 0;

Escritor:

wait(escribir); espera por escritor o lector

Escritor_escribe; Escribe objeto

signal(escribir); permite leer y/o escribir a otros, escritura completada

Lector:

wait(mutex); asegura acceso exclusivo a contador de lectores

contadorLectores = contadorLectores++; incrementa lectores

if(contadorLectores == 1) then wait(escribir); Si es el primer lector espera si hay escritor

signal(mutex);

Lector_lee;

wait(mutex); asegura acceso exclusivo a contador de lectores

contadorLectores = contadorLectores--; lector terminó de leer

if(contadorLectores == 0) then signal(escribir); no mas lectores por si escritor esperaba

signal(mutex)

Notas sobre Lectores/Escritores Primer lector se bloquea si hay un escritor activo cualquier otro escritor se bloquea también Si un escritor espera porque existen lectores activos, el último lector lo despierta cuando sale pueden otros lectores entrar cuando el escritor está esperando? Cuando un escritor sale, si hay un escritor y un lector esperando quien entra?

Primer lector se bloquea si hay un escritor activo

cualquier otro escritor se bloquea también

Si un escritor espera porque existen lectores activos, el último lector lo despierta cuando sale

pueden otros lectores entrar cuando el escritor está esperando?

Cuando un escritor sale, si hay un escritor y un lector esperando quien entra?

Otro ejemplo clásico Problema de Filósofos comensales Cada filósofo tiene su plato de arroz, con 5 palitos 5 filósofos se sientan a la mesa. Piensan por un rato y cuando les da hambre comen Hay sólo 5 palitos en la mesa (cada persona necesita 2 palitos para comer arroz a la manera china) Para poder comer cada filósofo tiene que obligatoriamente conseguir dos palitos Problema es importante porque introduce posibles problemas de Deadlock(bloqueo mortal) y Starvation(inanición)

Problema de Filósofos comensales

Cada filósofo tiene su plato de arroz, con 5 palitos

5 filósofos se sientan a la mesa. Piensan por un rato y cuando les da hambre comen

Hay sólo 5 palitos en la mesa (cada persona necesita 2 palitos para comer arroz a la manera china)

Para poder comer cada filósofo tiene que obligatoriamente conseguir dos palitos

Problema es importante porque introduce posibles problemas de Deadlock(bloqueo mortal) y Starvation(inanición)

Problema de Filósofos comensales

Problemas que pueden surgir con mala sincronización Deadlock Hebras/Procesos están en deadlock cuando 2 o más hebras o procesos están esperando por una condición que sólo puede ser causada por una hebra que tambien está esperando. Puede darse con 2 o más hebras en la lista de espera de un mismo semáforo? Starvation o espera indefinida Hebras/Procesos esperan indefinidamente para poder accesar un recurso. Ejemplo, una hebra en la lista de espera de un semáforo de la cual están entrando y saliendo continuamente hebras y la lista de espera de semáforo es LIFO

Deadlock

Hebras/Procesos están en deadlock cuando

2 o más hebras o procesos están esperando por una condición que sólo puede ser causada por una hebra que tambien está esperando.

Puede darse con 2 o más hebras en la lista de espera de un mismo semáforo?

Starvation o espera indefinida

Hebras/Procesos esperan indefinidamente para poder accesar un recurso.

Ejemplo, una hebra en la lista de espera de un semáforo de la cual están entrando y saliendo continuamente hebras y la lista de espera de semáforo es LIFO

Ejemplo deadlock con productor/consumidor Productor while (true) { /* produce un item en proxProd */ wait(mutex); wait(vacio); buffer[in] = proxProd; in = (in + 1) % N; contador++; signal(mutex); signal(lleno); } Consumidor While(true){ wait(lleno); wait(mutex); proxCons = buffer[out]; out = (out + 1) % N; contador--; signal(mutex); signal(vacio); /* consume proxCons */ } int contador = 0; //indica número de items en buffer char buffer[N]; int in = 0; int out = 0; sem mutex=1; sem vacio = N; sem lleno = 0; Que sucede aquí?

Problemas con Semáforos A pesar que se pueden usar para resolver cualquier problema de sincronización Son variables globales por lo tanto pueden ser accesadas de cualquier hebra directamente no es buena técnica de ingeniería de software No hay conexión entre el semáforo y el recurso para el cual se quiere controlar acceso Usados como mutex (ingreso a sección crítica) y para coordinación (planificación, elección quien tiene acceso al recurso) No se puede controlar su uso, no hay garantía que el programador los use adecuadamente (fácil de cometer errores)

A pesar que se pueden usar para resolver cualquier problema de sincronización

Son variables globales por lo tanto pueden ser accesadas de cualquier hebra directamente

no es buena técnica de ingeniería de software

No hay conexión entre el semáforo y el recurso para el cual se quiere controlar acceso

Usados como mutex (ingreso a sección crítica) y para coordinación (planificación, elección quien tiene acceso al recurso)

No se puede controlar su uso, no hay garantía que el programador los use adecuadamente (fácil de cometer errores)

Resumen Semáforos primitivas de sincronización de más alto nivel que locks No relación entre semáforo y recurso que controla Fácil de cometer errores que pueden producir deadlock y starvation Importante entender bien problema antes de utilizarlos Próxima semana Monitores

Semáforos primitivas de sincronización de más alto nivel que locks

No relación entre semáforo y recurso que controla

Fácil de cometer errores que pueden producir deadlock y starvation

Importante entender bien problema antes de utilizarlos

Próxima semana Monitores

Add a comment

Related presentations

Related pages

Semáforo - Wikipedia, la enciclopedia libre

http://www.semaforos.wikispaces.com; http://www.ceibal.edu.uy/portal/contenidos/areas_conocimiento/cs_sociales/081031semaforo/index.html;
Read more

A la luz de los semaforos - Microsoft Store

Kostenlos erhältlich + + Groove Music Pass 30 Tage kostenlos testen Mit Groove Music Pass anhören
Read more

Semáforos - Apuntes, Tareas, Ensayos, Resúmenes ...

COORDINACIÓN DE SEMAFOROS. Sistemas de coordinación: Los sistemas coordinados pueden, o no, estar sujetos a un control maestro.
Read more

Semafors — Vikipēdija

Semafors (grieķu: sēma — ‘zīme’, phoros — ‘nesējs’) ir optiska stacionāra signālierīce ar signālplāksnēm (spārniem), agrāk bieži ...
Read more

SEMAFOROSLED.NET - Reparacion de Semaforos Led

Reparacion de Semaforos. Brindamos Servicio de Reparacion de semaforos led a nivel Electronico de todas las marcas y modelos. Mantenimiento de Semaforos
Read more

Ampelmännchen - Wikipedia, la enciclopedia libre

El primer Ampelmännchen fue instalado oficialmente en Berlín el 13 de octubre de 1961, en una época en la cual el interés de público y medios se ...
Read more

Semaforos - Scribd - Read books, audiobooks, and more

Semaforos - Free download as PDF File (.pdf) or read online for free. Semaforos
Read more

Semáforos - Scribd - Read books, audiobooks, and more

Scribd is the world's largest social reading and publishing site.
Read more

semaforos - Funcionamiento

Funcionamiento Los semáforos de control de tráfico vehicular pueden funcionar de dos maneras distintas; el cambio de estado puede depende del tiempo o ...
Read more

Semaforos Inteligentes S.A.S.

Desarrollamos nuestro trabajo con el firme compromiso de generarles a nuestros clientes muchas ventajas técnicas y económicas, además de crear un ...
Read more