En informática , un semáforo es un tipo de datos variable o abstracto que se utiliza para controlar el acceso a un recurso común mediante múltiples subprocesos y evitar problemas de secciones críticas en un sistema concurrente , como un sistema operativo multitarea . Los semáforos son un tipo de primitiva de sincronización . Un semáforo trivial es una variable simple que se cambia (por ejemplo, se incrementa, se reduce o se alterna) dependiendo de las condiciones definidas por el programador.
Una forma útil de pensar en un semáforo tal como se utiliza en un sistema del mundo real es como un registro de cuántas unidades de un recurso en particular están disponibles, junto con operaciones para ajustar ese registro de manera segura ( es decir, para evitar condiciones de carrera ) a medida que las unidades se distribuyen. adquirido o liberado y, si es necesario, esperar hasta que una unidad del recurso esté disponible.
Los semáforos son una herramienta útil en la prevención de condiciones de carrera; sin embargo, su uso no es garantía de que un programa esté libre de estos problemas. Los semáforos que permiten un recuento arbitrario de recursos se denominan semáforos de conteo , mientras que los semáforos que están restringidos a los valores 0 y 1 (o bloqueados/desbloqueados, no disponibles/disponibles) se denominan semáforos binarios y se utilizan para implementar bloqueos .
El concepto de semáforo fue inventado por el informático holandés Edsger Dijkstra en 1962 o 1963, [2] cuando Dijkstra y su equipo estaban desarrollando un sistema operativo para Electrologica X8 . Ese sistema finalmente llegó a ser conocido como EL sistema de multiprogramación .
Supongamos que una biblioteca física tiene 10 salas de estudio idénticas, para ser utilizadas por un estudiante a la vez. Los estudiantes deben solicitar una habitación en la recepción si desean utilizar una sala de estudio. Si no hay habitaciones libres, los estudiantes esperan en el escritorio hasta que alguien ceda una habitación. Cuando un estudiante haya terminado de usar una habitación, deberá regresar al escritorio e indicar que una habitación ha quedado libre.
En la implementación más simple, el empleado de la recepción sólo sabe el número de habitaciones libres disponibles, lo cual sólo sabe correctamente si todos los estudiantes realmente usan su habitación mientras se han inscrito y las devuelven cuando terminan. Cuando un estudiante solicita una habitación, el secretario disminuye este número. Cuando un estudiante libera una habitación, el secretario aumenta este número. La habitación se puede utilizar durante el tiempo que se desee, por lo que no es posible reservar habitaciones con antelación.
En este escenario, el conteo de la recepción representa un semáforo de conteo, las salas son el recurso y los estudiantes representan procesos/hilos. El valor del semáforo en este escenario es inicialmente 10, con todas las habitaciones vacías. Cuando un estudiante solicita una habitación, se le concede acceso y el valor del semáforo se cambia a 9. Después de que llega el siguiente estudiante, baja a 8, luego a 7 y así sucesivamente. Si alguien solicita una habitación y el valor actual del semáforo es 0, [3] se ve obligado a esperar hasta que se libere una habitación (cuando el recuento aumenta de 0). Si una de las salas fue liberada, pero hay varios estudiantes esperando, entonces se puede usar cualquier método para seleccionar quién ocupará la sala (como FIFO o elegir uno al azar). Y, por supuesto, un estudiante debe informar al secretario que liberará su habitación solo después de haberla abandonado; de lo contrario, puede haber una situación incómoda cuando dicho estudiante esté en el proceso de salir de la habitación (está empacando sus libros de texto, etc.). y otro estudiante entra al salón antes de que ellos salgan.
Cuando se utiliza para controlar el acceso a un conjunto de recursos, un semáforo rastrea sólo cuántos recursos están libres; no realiza un seguimiento de cuáles de los recursos son gratuitos. Es posible que se requiera algún otro mecanismo (que posiblemente involucre más semáforos) para seleccionar un recurso gratuito en particular.
El paradigma es especialmente poderoso porque el recuento de semáforos puede servir como un disparador útil para una serie de acciones diferentes. El bibliotecario de arriba puede apagar las luces en la sala de estudio cuando no quedan estudiantes, o puede colocar un letrero que diga que las salas están muy ocupadas cuando la mayoría de las salas están ocupadas.
El éxito del protocolo requiere que las aplicaciones lo sigan correctamente. Es probable que la equidad y la seguridad se vean comprometidas (lo que prácticamente significa que un programa puede comportarse lentamente, actuar de manera errática, colgarse o fallar ) si incluso un solo proceso actúa incorrectamente. Esto incluye:
Incluso si todos los procesos siguen estas reglas, aún puede ocurrir un punto muerto de múltiples recursos cuando hay diferentes recursos administrados por diferentes semáforos y cuando los procesos necesitan usar más de un recurso a la vez, como lo ilustra el problema de los filósofos gastronómicos .
Los semáforos de conteo están equipados con dos operaciones, históricamente denominadas P y V (ver § Nombres de operaciones para nombres alternativos). La operación V incrementa el semáforo S y la operación P lo disminuye.
El valor del semáforo S es la cantidad de unidades del recurso que están disponibles actualmente. La operación P pierde tiempo o duerme hasta que un recurso protegido por el semáforo esté disponible, momento en el cual el recurso se reclama inmediatamente. La operación V es la inversa: hace que un recurso vuelva a estar disponible una vez que el proceso ha terminado de usarlo. Una propiedad importante del semáforo S es que su valor no se puede cambiar excepto mediante las operaciones V y P.
Una forma sencilla de comprender las operaciones de espera (P) y señal (V) es:
Muchos sistemas operativos proporcionan primitivas de semáforo eficientes que desbloquean un proceso de espera cuando se incrementa el semáforo. Esto significa que los procesos no pierden tiempo comprobando innecesariamente el valor del semáforo.
El concepto de conteo de semáforo se puede ampliar con la capacidad de reclamar o devolver más de una "unidad" del semáforo, una técnica implementada en Unix . Las operaciones V y P modificadas son las siguientes, utilizando corchetes para indicar operaciones atómicas , es decir, operaciones que parecen indivisibles desde la perspectiva de otros procesos:
función V(semáforo S, entero I): [S ← S + I]función P(semáforo S, entero I): repetir: [ si S ≥ I: S ← S − Yo romper ]
Sin embargo, el resto de esta sección se refiere a semáforos con operaciones unarias V y P, a menos que se especifique lo contrario.
Para evitar la inanición , un semáforo tiene una cola de procesos asociada (normalmente con semántica FIFO ). Si un proceso realiza una operación P en un semáforo que tiene el valor cero, el proceso se agrega a la cola del semáforo y se suspende su ejecución. Cuando otro proceso incrementa el semáforo realizando una operación V y hay procesos en la cola, uno de ellos se elimina de la cola y reanuda la ejecución. Cuando los procesos tienen diferentes prioridades, la cola se puede ordenar por prioridad, de modo que el proceso de mayor prioridad se tome primero de la cola.
Si la implementación no garantiza la atomicidad de las operaciones de incremento, decremento y comparación, existe el riesgo de que se olviden los incrementos o decrementos, o de que el valor del semáforo se vuelva negativo. La atomicidad se puede lograr mediante el uso de una instrucción de máquina que sea capaz de leer, modificar y escribir el semáforo en una sola operación. En ausencia de dicha instrucción de hardware, se puede sintetizar una operación atómica mediante el uso de un algoritmo de exclusión mutua de software . En sistemas monoprocesador , las operaciones atómicas se pueden garantizar suspendiendo temporalmente la preferencia o deshabilitando las interrupciones de hardware . Este enfoque no funciona en sistemas multiprocesador donde es posible que dos programas que comparten un semáforo se ejecuten en diferentes procesadores al mismo tiempo. Para resolver este problema en un sistema multiprocesador se puede utilizar una variable de bloqueo para controlar el acceso al semáforo. La variable de bloqueo se manipula mediante un comando test-and-set-lock .
Considere una variable A y una variable booleana S. Solo se accede a A cuando S está marcado como verdadero. Por tanto, S es un semáforo de A.
Se puede imaginar un semáforo ( S ) justo antes de una estación de tren ( A ). En este caso, si la señal está en verde, entonces se puede entrar a la estación de tren. Si es amarillo o rojo (o cualquier otro color), no se puede acceder a la estación de tren.
Considere un sistema que sólo puede admitir diez usuarios (S=10). Cada vez que un usuario inicia sesión, se llama a P, lo que disminuye el semáforo S en 1. Cada vez que un usuario cierra sesión, se llama a V, incrementando S en 1, lo que representa un espacio de inicio de sesión que está disponible. Cuando S es 0, cualquier usuario que desee iniciar sesión debe esperar hasta que S aumente; la solicitud de inicio de sesión se coloca en una cola FIFO hasta que se libera una ranura. La exclusión mutua se utiliza para garantizar que las solicitudes se pongan en cola en orden. Siempre que S aumenta (espacios de inicio de sesión disponibles), una solicitud de inicio de sesión se retira de la cola y el usuario propietario de la solicitud puede iniciar sesión. Si S ya es mayor que 0, las solicitudes de inicio de sesión se retiran inmediatamente de la cola.
En el problema productor-consumidor , un proceso (el productor) genera elementos de datos y otro proceso (el consumidor) los recibe y utiliza. Se comunican mediante una cola de tamaño máximo N y están sujetos a las siguientes condiciones:
La solución de semáforo al problema productor-consumidor rastrea el estado de la cola con dos semáforos: emptyCount, el número de lugares vacíos en la cola y fullCount, el número de elementos en la cola. Para mantener la integridad, emptyCountpuede ser menor (pero nunca mayor) que el número real de lugares vacíos en la cola y fullCountpuede ser menor (pero nunca mayor) que el número real de elementos en la cola. Los lugares y elementos vacíos representan dos tipos de recursos, cajas vacías y cajas llenas, y los semáforos emptyCountmantienen fullCountel control sobre estos recursos.
El semáforo binario useQueuegarantiza que la integridad del estado de la cola en sí no se vea comprometida, por ejemplo, si dos productores intentan agregar elementos a una cola vacía simultáneamente, corrompiendo así su estado interno. Alternativamente, se podría utilizar un mutex en lugar del semáforo binario.
emptyCountInicialmente es N , inicialmente fullCountes 0 e useQueueinicialmente es 1.
El productor hace lo siguiente repetidamente:
producir: P(cuentavacia) P (utilizar cola) ponerItemIntoQueue(elemento) V(utilizarcola) V(cuenta completa)
El consumidor hace lo siguiente repetidamente
consumir: P(cuenta completa) P (utilizar cola) artículo ← getItemFromQueue() V(utilizarcola) V(cuentavacia)
A continuación se muestra un ejemplo sustantivo:
fullCountes 0, el consumidor bloquea.emptyCountlimitan su entrada.useQueuey depositan artículos en la cola.fullCountse incrementa, permitiendo que un consumidor ingrese a su sección crítica.Tenga en cuenta que emptyCountpuede ser mucho menor que el número real de lugares vacíos en la cola, por ejemplo, en el caso de que muchos productores lo hayan disminuido pero estén esperando su turno useQueueantes de llenar los lugares vacíos. Tenga en cuenta que eso siempre se cumple, con igualdad si y solo si ningún productor o consumidor está ejecutando sus secciones críticas.emptyCount + fullCount ≤ N
El patrón "Pasar el testigo" [4] [5] [6] propuesto por Gregory R. Andrews es un esquema genérico para resolver muchos problemas complejos de programación concurrente en los que múltiples procesos compiten por el mismo recurso con condiciones de acceso complejas (como satisfacer criterios prioritarios específicos o evitar el hambre). Dado un recurso compartido, el patrón requiere un semáforo privado "priv" (inicializado en cero) para cada proceso (o clase de procesos) involucrado y un único semáforo "mutex" de exclusión mutua (inicializado en uno). El pseudocódigo para cada proceso es:
proceso nulo ( int proc_id , int res_id ) { recurso_acquire ( proc_id , res_id ); < utilizar el recurso res_id > ; liberación_recurso ( proc_id , res_id ); } El pseudocódigo de las primitivas de adquisición y liberación de recursos es:
void Resource_acquire ( int proc_id , int res_id ) { P ( mutex ); if ( < la condición para acceder a res_id no está verificada para proc_id > ) { < indica que proc_id está suspendido para res_id > ; V ( exclusión mutua ); P ( priv [ proc_id ]); < indica que proc_id ya no está suspendido para res_id > ; } < indica que proc_id está accediendo al recurso > ; pasar_el_baton (); // Vea abajo } void Resource_release ( int proc_id , int res_id ) { P ( mutex ); < indica que proc_id ya no accede al recurso res_id > ; _ pasar_el_baton (); // Vea abajo } Ambas primitivas utilizan a su vez el método "pass_the_baton", cuyo pseudocódigo es:
void pass_the_baton ( int res_id ) { si < la condición para acceder a res_id es verdadera para al menos un proceso suspendido > { int p = < elija el proceso a reactivar > ; V ( priv [ p ]); } más { V ( mutex ); } } Observaciones
El patrón se llama "pasar el testigo" porque un proceso que libera el recurso, así como un proceso recién reactivado, activará como máximo un proceso suspendido, es decir, "le pasará el testigo". El mutex se libera solo cuando un proceso se va a suspender (resource_acquire) o cuando pass_the_baton no puede reactivar otro proceso suspendido.
Los nombres canónicos V y P provienen de las iniciales de palabras holandesas . V generalmente se explica como verhogen ("aumento"). Se han ofrecido varias explicaciones para P, incluidas proberen ("probar" o "probar"), [7] passeren ("pasar") y pakken ("agarrar"). El primer artículo de Dijkstra sobre el tema [2] da passering ("pasar") como el significado de P y vrijgave ("liberar") como el significado de V. También menciona que la terminología se toma de la utilizada en las señales ferroviarias. Posteriormente, Dijkstra escribió que pretendía que P representara prolaag , [8] abreviatura de probeer te verlagen , literalmente "intentar reducir", o en paralelo a los términos utilizados en el otro caso, "intentar disminuir". [9] [10] [11]
En ALGOL 68 , el kernel de Linux , [12] y en algunos libros de texto en inglés, las operaciones V y P se denominan arriba y abajo , respectivamente . En la práctica de la ingeniería de software, a menudo se les llama señal y espera , [13] liberar y adquirir [13] ( biblioteca Java estándar), [14] o publicar y pendiente . Algunos textos los llaman desocupar y procurar para que coincidan con las iniciales holandesas originales. [15] [16]
Un mutex es un mecanismo de bloqueo que a veces utiliza la misma implementación básica que el semáforo binario. Las diferencias entre ellos están en cómo se utilizan. Si bien un semáforo binario puede denominarse coloquialmente mutex, un verdadero mutex tiene un caso de uso y una definición más específicos, ya que se supone que solo la tarea que bloqueó el mutex debe desbloquearlo. Esta restricción tiene como objetivo manejar algunos problemas potenciales del uso de semáforos:
java.util.concurrent.Semaphore