Semaforos (concurrencia)

Semáforos

Sistemas Operativos 1 Universidad de San Carlos de Guatemala

Guatemala, Marzo de 2009

Conceptos (I) • Los semáforos son una solución, del tipo soporte al sistema operativo para garantizar la exclusión mutua • Un semáforo es una estructura diseñada para sincronizar dos o más threads o procesos, de modo que su ejecución se realice de forma ordenada y sin conflictos entre ellos.

Conceptos (II) • Un semáforo nos sirve para poder permitir o restringir a los procesos o hilos el acceso a algún recurso compartido • Un semáforo básico es una estructura formada por una posición de memoria y dos instrucciones, una para reservarlo y otra para liberarlo. A esto se le puede añadir una cola de threads para recordar el orden en que se hicieron las peticiones.

Operaciones Básicas • Los semáforos cuentan con operaciones básicas, una de ellas es para reservarlo y la otra para liberarlo, wait (espera) y signal (señal) respectivamente, equivalente down y up. • Existe una tercera operación que consiste en inicializar el semáforo. • Existen algunos semáforos que manejan una cola de espera.

Wait, Down ó Espera • Decrementa en una unidad el semáforo

• Bloquea hilo/proceso si el semáforo es menor que cero, sino entonces permite a hilo/proceso continuar • Llamada W(semaforo) o down(semaforo)

Signal, Up ó Señal • Incrementa semáforo en uno y si hay algún proceso/hebra esperando lo despierta • Existe un valor máximo para incrementar el semáforo, este no se va a infinito • Llamada S(semáforo) o up(semáforo)

Inicializador • Los semáforos pueden ser de 2 tipos: Binarios o Generales (Contadores). • La operación de inicializador definirá si el semáforo será binario o no, es decir, si se inicializa con 1, el semáforo será binario ya que solo podrá manejar un recurso compartido, en caso de tener “N” recursos compartidos se inicializara con “N”. • Si tenemos “N” procesos inicializamos un semáforo para que solo “N” procesos acceda a un recurso compartido.

Semáforos con manejo de cola • Existen semáforos que tienen la operación de manejar una cola del tipo FIFO (PEPS) para llevar el control de los procesos que están solicitando los recursos, así cuando se liberen los recursos estos puedan asignarle dicho recurso al primer proceso que lo solicito.

Desventajas • No se puede imponer el uso correcto de los “Down” y “Up”

• No existe una asociación entre el semáforo y el recurso • Entre “Down” y “Up” el usuario puede realizar cualquier operación con el recurso.

Algoritmo semáforo //Para bloquear Down (semaforo){ if semaforo > 0 then semaforo=semaforo -1 else bloquear_el_proceso(); }

//constructor Init (semaforo, num) semaforo = num; end

//Para liberar Up (semaforo){ if hay_proceso_bloqueado then despertar_el_proceso() else semáforo = semáforo + 1 }

Implementación de Semáforo en Java public class Semaforo { private int valor; /** Creates a new instance of Semaforo */ public Semaforo(int v) { valor = v; }

public synchronized void up(){ valor++; notify(); } }

public synchronized void down(){ while(valor <= 0){ try{ wait(); }catch(InterruptedException e){ ; } } valor--; }

Problema Productor-Consumidor • • • •

Un buffer en memoria con N slots disponibles Necesita llevar cuenta de ítems en buffer Productor produce ítems a ingresar al buffer Consumidor consume ítems del buffer

Algoritmo Productor-Consumidor //IS: Inicializa Semáforo Productor(){ IS(lleno, 0) IS(vacio, 7) IS(EM, 1)

Consumidor(){ repeat Hace_algo() Down(lleno) Down(EM)

repeat hace_cosas() x = produce() Down(vacio) Down(EM)

y = Pop() Up(EM) Up(vacio) consume(); Until Fin

Push(x) Up(EM) Up(lleno) Hace_mas_cosas() until FIN }

}

Problema Lectores-Escritores • Caso base de datos • Varios lectores pueden accesar registro datos simultáneamente • Sólo un escritor puede escribir

Algoritmo Lector-Escritor(I) • Hay un objeto de datos(fichero de texto) que es utilizado por varios procesos, unos leen y otro que escribe. • Solo puede utilizar el recurso un proceso y solo uno, es decir, o bien un proceso estará escribiendo o bien leyendo, pero nunca ocurrirá simultáneamente (teniendo en cuenta que si no lo esta utilizando nadie, tendrá preferencia el escritor ante el lector). • Existe el algoritmo de lector/escritor sin prioridad y con prioridad al lector y otro con prioridad al escritor.

Algoritmo Lector-Escritor(II) Algoritmo Lector/Escritor (Prioridad lector) //IS: Inicializa Semáforo IS(EM, 1) IS(DB, 0) NL = 0

Escritor(){ Hace_Algo() Down(DB) Escribe() Up(DB) Hace_mas() }

Lector(){ Hace_Cosas() Down(EM) NL = NL +1 if(NL = 1) then Down(DB) Up(EM) Leer() Down(EM) NL = NL - 1 if(NL = 0) then Up(DB) Up(EM) Hace_Mas_Cosas() }

Referencias •

Conceptos concretos, y un ejemplo interesante de cómo hacer un semáforo general por medio de 2 semáforos binarios y un contador. http://trevinca.ei.uvigo.es/~formella/doc/cd05/node77.html

•

Conceptos generales de Semáforos, su funcionamiento, y ejemplos de llamadas por medio de semáforos http://www.rastersoft.com/OS2/CURSO/SEMAFORO.HTM

•

Ejemplo de Productor/Consumidor usando semáforos http://wwwdi.ujaen.es/~lina/TemasSO/CONCURRENCIA/ProductorConsumidor/proble ma_del_productor_consumidor_resuelto_con_semaforos.html

•

Lector/Escritor http://www.infor.uva.es/~cllamas/concurr/pract98/sisos30/index.html

•

Productor/Consumidor, Lector/Escritor sin prioridad, con prioridad lector y prioridad escritor http://www.dc.fi.udc.es/ai/~soto/sist_oper/Sol_prob_clas_sem.htm

Acerca del autor y la licencia • Pedro Domingo – http://elcopypaste.wordpress.com – [email protected]

• Licencia