Semáforo (programación)

En informática , un semáforo es una variable o un tipo de datos abstracto que se utiliza para controlar el acceso a un recurso común por parte de varios 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 modifica (por ejemplo, se incrementa o decrementa, o se alterna) según 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 particular están disponibles, junto con operaciones para ajustar ese registro de manera segura (es decir, para evitar condiciones de carrera ) a medida que se adquieren unidades o se liberan y, si es necesario, esperar hasta que una unidad del recurso esté disponible.

Aunque los semáforos son útiles para evitar condiciones de carrera, no garantizan su ausencia. 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, ^[1] cuando Dijkstra y su equipo estaban desarrollando un sistema operativo para Electrologica X8 . Ese sistema finalmente se conocería como el sistema multiprogramación THE .

Supongamos que una biblioteca física tiene diez salas de estudio idénticas, que pueden ser utilizadas por un solo estudiante a la vez. Los estudiantes deben solicitar una sala en la recepción. Si no hay salas libres, los estudiantes esperan en la recepción hasta que alguien ceda una sala. Cuando un estudiante termina de usar una sala, debe regresar a la recepción e indicar que la sala está libre.

En la implementación más simple, el empleado de recepción solo conoce la cantidad de habitaciones libres disponibles. Esto requiere que todos los estudiantes utilicen su habitación mientras la hayan reservado y la devuelvan cuando hayan terminado. Cuando un estudiante solicita una habitación, el empleado disminuye este número. Cuando un estudiante libera una habitación, el empleado 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 anticipación.

En este escenario, el contador de 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 salas vacías. Cuando un estudiante solicita una sala, se le concede el acceso y el valor del semáforo cambia a 9. Después de que llega el siguiente estudiante, baja a 8, luego a 7, y así sucesivamente. Si alguien solicita una sala y el valor actual del semáforo es 0, ^[2] se ve obligado a esperar hasta que se libere una sala (cuando el conteo aumenta desde 0). Si una de las salas se liberó, pero hay varios estudiantes esperando, entonces se puede usar cualquier método para seleccionar al que ocupará la sala (como FIFO o elegir uno al azar). Y, por supuesto, un estudiante debe informar al empleado sobre la liberación de su sala solo después de realmente abandonarla.

Cuando se utiliza para controlar el acceso a un conjunto de recursos, un semáforo solo registra cuántos recursos están libres. No registra cuáles de ellos están libres. Es posible que se requiera algún otro mecanismo (que posiblemente implique más semáforos) para seleccionar un recurso libre en particular.

El paradigma es especialmente poderoso porque el recuento del semáforo puede servir como un disparador útil para una serie de acciones diferentes. El bibliotecario mencionado anteriormente puede apagar las luces en la sala de estudio cuando no quedan estudiantes, o puede colocar un cartel 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 imparcialidad y la seguridad se vean comprometidas (lo que prácticamente significa que un programa puede comportarse con lentitud, actuar de forma errática, bloquearse o bloquearse ) si un solo proceso actúa de forma incorrecta. Esto incluye:

• solicitar un recurso y olvidarse de liberarlo;
• liberar un recurso que nunca fue solicitado;
• mantener un recurso durante mucho tiempo sin necesitarlo;
• utilizando un recurso sin solicitarlo primero (o después de liberarlo).

Incluso si todos los procesos siguen estas reglas, aún puede producirse un bloqueo 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 comedores .

Los semáforos de conteo están equipados con dos operaciones, históricamente denominadas P y V (consulte § Nombres de operaciones para conocer los nombres alternativos). La operación V incrementa el semáforo S y la operación P lo decrementa.

El valor del semáforo S es el número de unidades del recurso que están disponibles en ese momento. La operación P pierde tiempo o permanece inactiva hasta que un recurso protegido por el semáforo esté disponible, momento en el que se reclama el recurso inmediatamente. La operación V es la inversa: hace que un recurso esté disponible nuevamente después de que el proceso haya 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 entender las operaciones de espera (P) y señal (V) es:

• wait : decrementa el valor de la variable semáforo en 1. Si el nuevo valor de la variable semáforo es negativo, el proceso que está ejecutando wait se bloquea (es decir, se agrega a la cola del semáforo). De lo contrario, el proceso continúa la ejecución, habiendo utilizado una unidad del recurso.
• señal : incrementa el valor de la variable semáforo en 1. Después del incremento, si el valor previo al incremento fue negativo (lo que significa que hay procesos esperando un recurso), transfiere un proceso bloqueado de la cola de espera del semáforo a la cola de listos.

Muchos sistemas operativos proporcionan primitivas de semáforo eficientes que desbloquean un proceso en espera cuando se incrementa el semáforo. Esto significa que los procesos no pierden tiempo comprobando el valor del semáforo innecesariamente.

El concepto de semáforo de conteo 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 para otros procesos:

función V(semáforo S, entero I): [S ← S + yo]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 asociada de procesos (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 añade 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 se reanuda la ejecución. Cuando los procesos tienen diferentes prioridades, la cola puede ordenarse de esta forma, de modo que el proceso con 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 pueda leer, modificar y escribir el semáforo en una sola operación. Sin 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 preempción 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 de prueba y establecimiento de bloqueo .

Considere una variable A y una variable booleana S . Solo se accede a A cuando S está marcada como verdadera. Por lo tanto, S es un semáforo para A .

Podemos imaginarnos una señal de semáforo ( S ) justo antes de una estación de tren ( A ). En este caso, si la señal es verde, se puede entrar en la estación de tren. Si es amarilla o roja (o cualquier otro color), no se puede acceder a la estación de tren.

Considere un sistema que solo puede admitir diez usuarios (S = 10). Siempre que un usuario inicia sesión, se llama a P, lo que disminuye el semáforo S en 1. Siempre que un usuario cierra sesión, se llama a V, lo que incrementa S en 1, lo que representa un espacio de inicio de sesión que se ha vuelto 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 pone en cola en una cola FIFO hasta que se libera un espacio. Se utiliza la exclusión mutua para garantizar que las solicitudes se pongan en cola en orden. Siempre que S aumenta (hay espacios de inicio de sesión disponibles), una solicitud de inicio de sesión se saca 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 sacan de la cola inmediatamente.

En el problema productor-consumidor , un proceso (el productor) genera elementos de datos y otro proceso (el consumidor) los recibe y los utiliza. Se comunican mediante una cola de tamaño máximo N y están sujetos a las siguientes condiciones:

• El consumidor debe esperar a que el productor produzca algo si la cola está vacía;
• El productor debe esperar a que el consumidor consuma algo si la cola está llena.

La solución de semáforo para el 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 vacíos y los elementos representan dos tipos de recursos, cajas vacías y cajas llenas, y los semáforos emptyCounty fullCountmantienen el control sobre estos recursos.

El semáforo binario useQueuegarantiza que la integridad del estado de la cola no se vea comprometida, por ejemplo, si dos productores intentan agregar elementos a una cola vacía simultáneamente, lo que dañaría su estado interno. Alternativamente, se podría utilizar un mutex en lugar del semáforo binario.

El emptyCountes inicialmente N , fullCountes inicialmente 0 y useQueuees inicialmente 1.

El productor hace lo siguiente repetidamente:

producir: P(número de vacíos) P(utilizarQueue) putItemIntoQueue(elemento) V(utilizarQueue) V(conteocompleto)

El consumidor hace lo siguiente repetidamente

consumir: P(conteo completo) P(utilizarQueue) elemento ← getItemFromQueue() V(utilizarQueue) V(número de vacíos)

A continuación se muestra un ejemplo sustancial:

1. Un solo consumidor entra en su sección crítica. Como fullCountes 0, el consumidor se bloquea.
2. Varios productores ingresan a la sección crítica de productores. No más de N productores pueden ingresar a su sección crítica debido a emptyCountlas restricciones de entrada.
3. Los productores, uno a la vez, obtienen acceso a la cola useQueuey depositan artículos en ella.
4. Una vez que el primer productor sale de su sección crítica, 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, donde muchos productores lo han disminuido pero están esperando su turno useQueueantes de llenar los lugares vacíos. Tenga en cuenta que esto 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 "Passing the baton" ^{[3] [4] [5]} 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 de prioridad específicos o evitar la inanición). Dado un recurso compartido, el patrón requiere un semáforo "priv" privado (inicializado a cero) para cada proceso (o clase de procesos) involucrado y un único semáforo "mutex" de exclusión mutua (inicializado a uno). El pseudocódigo para cada proceso es:

void proceso ( int proc_id , int res_id ) { adquisición_de_recursos ( proc_id , res_id ); < usar el recurso res_id > ; liberación_de_recursos ( 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 se verifica para proc_id > ) { < indica que proc_id está suspendido para res_id > ; V ( mutex ); P ( priv [ proc_id ]); < indica que proc_id ya no está suspendido para res_id > ; } < indica que proc_id está accediendo al recurso > ; pass_the_baton (); // Ver más abajo }                                  

void resource_release ( int proc_id , int res_id ) { P ( mutex ); < indica que proc_id ya no accede al recurso res_id > ; pass_the_baton ( ) ; // Ver más abajo }              

Ambos primitivos utilizan a su vez el método "pass_the_baton", cuyo pseudocódigo es:

void pass_the_baton ( int res_id ) { if < la condición para acceder a res_id es verdadera para al menos un proceso suspendido > { int p = < elige el proceso a reactivar > ; V ( priv [ p ]); } else { V ( mutex ); } }                      

Observaciones

El patrón se denomina "pasar la posta" porque un proceso que libera el recurso, así como un proceso recién reactivado, activarán como máximo un proceso suspendido, es decir, le "pasarán la posta". El mutex se libera solo cuando un proceso va a suspenderse a sí mismo (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 se explica generalmente como verhogen ("aumentar"). Se han ofrecido varias explicaciones para P, incluyendo proberen ("probar" o "intentar"), ^[6] passeren ("pasar") y pakken ("agarrar"). El primer artículo de Dijkstra sobre el tema ^[1] da passering ("pasar") como el significado de P , y vrijgave ("liberar") como el significado de V. También menciona que la terminología está tomada de la utilizada en las señales ferroviarias. Dijkstra escribió posteriormente que pretendía que P significara prolaag , ^[7] abreviatura de probeer te verlagen , literalmente "intentar reducir", o para hacer un paralelo de los términos utilizados en el otro caso, "intentar disminuir". ^{[8] [9] [10]}

En ALGOL 68 , el núcleo de Linux , ^[11] y en algunos libros de texto en inglés, las operaciones V y P se denominan, respectivamente, up y down . En la práctica de la ingeniería de software, a menudo se las denomina signal y wait , ^[12] release y acquire ^[12] ( biblioteca estándar de Java ), ^[13] o post y pend . Algunos textos las denominan vacate y procure para que coincidan con las iniciales holandesas originales. ^{[14] [15]}

Un mutex es un mecanismo de bloqueo que a veces utiliza la misma implementación básica que el semáforo binario. Sin embargo, difieren en cómo se utilizan. Si bien un semáforo binario puede denominarse coloquialmente mutex, un mutex verdadero 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 abordar algunos problemas potenciales del uso de semáforos:

1. Inversión de prioridad : si el mutex sabe quién lo bloqueó y se supone que debe desbloquearlo, es posible promover la prioridad de esa tarea siempre que una tarea de mayor prioridad comience a esperar en el mutex.
2. Terminación prematura de tareas: los mutex también pueden brindar seguridad de eliminación, donde la tarea que contiene el mutex no puede eliminarse accidentalmente. ^{[ cita requerida ]}
3. Bloqueo de terminación: si una tarea que mantiene un mutex finaliza por cualquier motivo, el sistema operativo puede liberar el mutex y las tareas de espera de señal de esta condición.
4. Bloqueo de recursión: a una tarea se le permite bloquear un mutex reentrante varias veces mientras lo desbloquea una cantidad igual de veces.
5. Liberación accidental: se genera un error al liberar el mutex si la tarea que lo libera no es su propietario.

• Asíncrono/espera
• Bandera (programación)
• Sincronización (informática)
• El problema de los fumadores de cigarrillos
• Problema de los filósofos de la cena
• Problema de lectores-escritores
• Problema del barbero dormido
• Monitor
• Despertar espurio

• Hilsheimer, Volker (2004). "Implementación de un mutex de lectura/escritura" (página web). Qt Quarterly , número 11, tercer trimestre de 2004
• Zelenski, Julie; Parlante, Nick. "Ejemplos de hilos y semáforos" (PDF) . Folleto . CS107 Paradigmas de programación. Primavera de 2008 (23). Stanford Engineering Everwhere (SEE).

• Dijkstra, Edsger W. Procesos secuenciales cooperativos (EWD-123) (PDF) . Archivo EW Dijkstra. Centro de Historia Estadounidense, Universidad de Texas en Austin .(transcripción) (septiembre de 1965)
• "semaphore.h - semáforos (TIEMPO REAL)". Especificaciones básicas de Open Group, edición 6, IEEE Std 1003.1, edición 2004. Open Group. 2004.
• Downey, Allen B. (2016) [2005]. "El pequeño libro de los semáforos" (2.ª ed.). Green Tea Press.
• Leppäjärvi, Jouni (11 de mayo de 2008). "Un estudio pragmático y de orientación histórica sobre la universalidad de las primitivas de sincronización" (PDF) . Universidad de Oulu, Finlandia.