Semaforos

De Departamento de Informatica
Saltar a: navegación, buscar

Los semáforos son una herramienta de sincronización que ofrece una solución al problema de la sección crítica (porción de código de un programa de computador en la cual se accede a un recurso compartido que no debe ser accedido por mas de un proceso o hilo en ejecución). Un semáforo provee una simple pero útil abstracción para controlar el acceso de múltiples procesos a un recurso común en programación paralela, o entornos multi-usuarios. El concepto de semáforo fue inventando por el holandés Esdger W. Dijkstra.


Contenido

Descripción

En palabras simples, un semáforo es un entero con tres diferencias:

  • Cuando se crea un semáforo, se pueden inicializar su valor con cualquier entero, pero después de eso las únicas que pueden hacerlo son los incrementos y decrementos en una unidad.
  • No puede leerse el valor actual del semáforo
  • Cuando un thread intenta decrementar el semáforo, si su valor es negativo, el subproceso se bloquea a sí mismo y no puede continuar hasta que otro subproceso incremente el semáforo
  • Cuando un thread incrementa el semáforo, si hay otros threads esperando, uno de ellos se desbloquea.

Semáforo como TDA

Un semáforo es un Tipo Abstracto de datos que permite el uso de un recurso de forma exclusiva, en el caso de que existan múltiples procesos que requieran acceso a éste.

Este TDA cumple con:

  • El valor del semáforo cuenta cuántos procesos pueden usar el recurso.
  • Existen 3 operaciones en un semáforo: init(), wait() y signal().

Descripción de las operaciones init(), wait() y signal()

init(): inicia el semáforo antes de que los procesos hayan ejecutado una operación wait() o signal() con el número máximo de procesos que tiene derecho a acceder al recurso. Si este semáforo se inicializa con 1, se convierte en un semáforo binario.

wait(): Si el valor del semáforo es mayor a cero, indica que un proceso más puede acceder al recurso, el contador del semáforo se disminuye en uno, y el proceso continúa con éxito. Si el semáforo es cero, el proceso queda esperando hasta que es despertado por otro proceso Cabe destacar que la prueba del valor entero de S (s<=0) y su posible modificación se debe realizar sin interrupción.

signal(): Cuando el proceso ha terminado de utilizar el recurso, éste lo indica al semáforo mediante signal(), el que aumenta el valor del semáforo en 1. Si existe algún proceso esperando su turno para utilizar el recurso, el proceso que finaliza puede despertarlo, o, de lo contrario, se incrementa el contador. Para despertar un proceso existen varias formas de implementación: por ejemplo, un sistema tipo FIFO.

Cuando un proceso modifica el valor del semáforo S, ningún otro proceso puede modificar el valor de tal semáforo simultáneamente.

Observaciones

  • Si los procesos no indican al semáforo el término del uso del recurso protegido, puede provocarse un bloqueo.
  • No hace falta que un proceso libere su propio recurso, sino que la operación signal() puede ser ejecutada por otro proceso.
  • Un semáforo simple no es suficiente para imponer un orden de acceso a los recursos.

Diferencias entre Semáforo y Mutex

Un mutex es esencialmente lo mismo que un semáforo binario, y a veces usan la misma implementación básica, pero el término mutex (exclusión mutua) se utiliza para describir una construcción que impide que dos procesos usen un recurso compartido al mismo tiempo. El semáforo binario se usa para describir una construcción que limita el acceso a un solo recurso.

Además, en la exclusión mutua existe el concepto de “propietario”: el proceso que bloquea el mutex es el único que está permitido para desbloquearlo. En contraste, los semáforos no tienen esta restricción.

Implementación

Previamente a dar detalles de su Implementación, hace falta hacer un par de definiciones:

  • Cambio de contexto: Un cambio de contexto consiste en la ejecución de una rutina perteneciente al núcleo del sistema operativo multitarea de una computadora, cuyo propósito es parar la ejecución de un hilo (o proceso o Threads) para dar paso a la ejecución de otro distinto.
  • Spinlocks: La principal desventaja de un semáforo es que requiere de una espera activa, es decir, mientras un proceso se encuentre en su región crítica cualquier otro proceso que intente entrar a su sección crítica debe ejecutar continuamente un bucle en el código de entrada siendo este un grave problema en un sistema de multi-programación con una sola CPU(ya que múltiples procesos comparten una sola CPU) desperdiciando ciclos del reloj. Estos tipos de semáforos se denominan Spinlocks. Resultan útiles cuando se espera que el Spinlock dure una corta cantidad de tiempo.

Para superar de cierto modo la necesidad de una espera activa, se pueden modificar las definiciones de las operaciones wait() y signal() del siguiente modo:

  • Cuando un proceso ejecute la función wait(), en lugar de entrar en una espera activa, el proceso se bloqueará a si mismo.
  • La operación de bloqueo coloca al proceso en una cola de espera asociada al semáforo y el estado de proceso queda en "espera".
  • Luego, el control se transfiere al planificador de la CPU, que selecciona otro proceso para su ejecución.
  • Un proceso bloqueado que está esperando en un semáforo S, debe reiniciarse cuando algún otro proceso realiza la operación signal() mediante la operación wakeup() que cambia el estado del proceso de "espera" a "preparado" entrando en la cola de procesos preparados.


typedef struct{
  int valor;
  struct proceso *nodo;
}semaforo;
wait(semaforo s){
  s-> valor--;
  if( s->valor < 0){
     //[añadir proceso a s-list]
     block;
  }
signal(semaforo s){
  s->valor++;
  if( s->valor >= 0){
     //[eliminar un proceso "P" de s-list]
     wakeup(p);
  }
  • Si el valor del semáforo en esta implementación es negativo, su módulo es la cantidad de procesos en espera de dicho semáforo.

Ventajas y desventajas del Uso de Semáforos

Ventajas

En cuanto a la definición de semáforos, no es obvio por qué son útiles. Es cierto que no se necesitan para solucionar problemas de sincronización, pero sus ventajas de uso son:

  • Los semáforos pueden imponer restricciones que ayuden a los programadores a evitar errores
  • Las soluciones que usan semáforos suelen ser limpias y organizadas, haciendo fácil demostrar su correctitud.
  • Los semáforos pueden implementarse de manera eficiente en muchos sistemas, por lo que las soluciones que los usan son portables y usualmente eficientes

Desventajas

  • El uso correcto de wait() y signal() es sólo una buena práctica de programación: es decir, su uso correcto no es obligatorio.
  • No existe una asociación directa entre el semáforo y el recurso que regula
  • Entre wait() y signal() el usuario puede realizar cualquier operación con el recurso.

Ejemplo: Problema del Productor-Consumidor

En el problema del productor-consumidor, un proceso (el productor) genera datos, y otro proceso (el consumidor) los recibe y usa. se comunican usando una cola de tamaño maximo N y estan sujetos a las siguientes condiciones:

  • El consumidor debe esperar que el productor produzca algo si la cola esta vacia.
  • El productor debe esperar que el consumidor consuma algo si la cola esta llena.

Ejemplo:

producir:
    P(Vacia)
    P(usarCola)
    encolarDato(dato)
    V(usarCola)
    V(Llena)

El consumidor hace lo mismo repetidamente:

consumir:
    P(Llena)
    P(usarCola)
    item ← desencolarDato()
    V(usarCola)
    V(Vacia)

En el ejemplo anterior se verifica el estado de la cola con 2 semaforos: Vacia, numero de lugares de la cola vacios. Llena, numero de elementos de la cola.

Ejemplo: Memoria Compartida

Al crear un proceso nuevo con fork() se crea una copia exacta de la imagen del proceso, es decir, de su bloque de control, del texto, de los datos y de la pila. En concreto al copiarse la zona de datos y de pila se copian tanto las variables locales o automáticas como las externas. Sin embargo dichas variables, aún teniendo el mismo nombre, son locales a cada proceso y no se pueden compartir. Para compartir memoria entre procesos hay que solicitarlo al sistema operativo. Para utilizar la memoria compartida se siguen 3 pasos:

Obtención de un fragmento de memoria compartida con su identificador en el sistema (entero). Se hace con la función shmget(). Localizar dicha zona a través de un puntero a un determinado tipo de datos. Se usa la función shmat(). Eliminación de la memoria compartida. Se usan las funciones shmdt() y shmctl().

La obtención y eliminación de la memoria se hará una sola vez. Apuntar a esa zona tienen que hacerlo todos los procesos que vayan a acceder a ella. Para conseguir esto, hay varios modos: pasar el identificador del fragmento de memoria obtenido, o bien pasar directamente el puntero (dirección de memoria donde comienza el fragmento compartido).

Código:

#include <stdio.h> 
#include <sys/time.h> 
#include <unistd.h> 
#include <sys/types.h> 
#include <sys/ipc.h> 
#include <sys/shm.h> 
#include <sys/sem.h> 
#include <errno.h>
#define ESPERA 1000 // Son los microsegundos de espera usados para asegurar 
                   // la finalización del quantum. 
#define NINCR  400 // Es el número de veces que cada proceso incrementa 
                   // la variable compartida.

/********************************************************************** 
* 
* PROBAR ESTE PROGRAMA CON Y SIN LAS OPERACIONES P Y V 
* 
**********************************************************************/  
 

main() 
{ 
int pid; 
int memoria; 
int *dato;  /*para acceder*/ 
int mutex;

 // Inicialización del semáforo binario 
 mutex = inicia(1);

 // Solicitamos memoria al sistema operativo 
 if ((memoria=shmget(IPC_PRIVATE, sizeof(int) * 1, 0660)) ==-1) { 
  perror ("Error en acceso a memoria compartida de sistema."); 
  exit(-1); 
 } 
 // Obtenemos el puntero a dicha memoria 
 dato = (int*) shmat(memoria, (char*) 0, 0);

 // Inicializamos la posición compartida 
 *dato = 0;  
 printf("memoria:%d   &dato:%x dato:%d\n",memoria,dato,*dato);

 // Creación de procesos concurrentes 
 if (0 == (pid=fork())) 
   proceso_hijo(dato,mutex); 
 else 
   proceso_padre(dato,mutex); 
 

 // A este punto se llega después de que hijo y padre hayan acabado 
 shmdt((char *)dato); 
 shmctl(memoria, IPC_RMID, 0); /* destruye la memoria */ 
 borra_s(mutex); /* destruye el semaforo */ 
} 
 

proceso_hijo(dato,mutex) 
int *dato; 
int mutex; 
{ 
int i, copia;

 // Impresión de algunos datos antes de empezar 
 printf("HIJO:&dato:%x dato:%d\n",dato,*dato);

 // Bucle de acceso a la variable compartida 
 for (i=0; i< NINCR; i++) { 
   P(mutex);  
// Comienzo sección crítica

   copia = *dato; 
   copia +=1; 
   // Esperamos un tiempo para forzar la finalización del quantum 
   retardo(); 
   // Actualizamos la memoria compartida 
   *dato = copia; 

// Fin sección crítica 
   V(mutex);  
 }

exit(); 
}

proceso_padre(dato, mutex) 
int *dato; 
int mutex; 
{ 
int i, copia;

 // Impresión de algunos datos antes de empezar 
 printf("PADRE:&dato:%x dato:%d\n",dato,*dato);   

 // Bucle de acceso a la variable compartida 
 for (i=0; i< NINCR; i++) { 
   P(mutex);  
   // Comienzo sección crítica

   copia = *dato; 
   copia +=1; 
   // Esperamos un tiempo para forzar la finalización del quantum 
   retardo(); 
   // Actualizamos la memoria compartida 
   *dato = copia; 
 
   // Fin sección crítica 
   V(mutex);  
 }

 wait(0); /* espera finalizacion de hijo */

 printf("Proceso padre. El hijo ya terminó. Valor final %d.\n", *dato); 
 printf("Debería valer %d.\n", 2*NINCR);

} 
 

/********************************************************************** 
* * 
* * Provocamos la espera durante ESPERA microsegundos 
* * 
***********************************************************************/ 
retardo() 
{

struct timeval tiempo; 
struct timezone tz; 
unsigned long inicio, ahora;

 gettimeofday(&tiempo, &tz); 
 ahora = inicio = tiempo.tv_sec * 1000000 + tiempo.tv_usec;

//  ESPERA microsegs 
 while (ahora < inicio + ESPERA) { 
   gettimeofday(&tiempo, &tz); 
   ahora = tiempo.tv_sec * 1000000 + tiempo.tv_usec; 
 }

}

Ejemplo obtenido de: Página Personal de Quiliano Isaac Moro Sancho

Referencias

Semáforos, Dr. Arno Formella, Universidad de Vigo, Departamento de Informática, 2006

The Little Book of Semaphores,second edition, Allen B. Downey

  • Silberschatz, Galvin, Gagne - “Fundamentos de Sistemas Operativos”, Séptima Edición. Sección 6.5 págs. 178 - 186
Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas