Hispanopedia Wiki
Articulo de referencia

Semáforo (programación)

En informática , un semáforo es una variable o un tipo de dato abstracto que se utiliza para controlar el acceso a un recurso común al que acceden múltiples hilos y evitar probl...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , un semáforo es una variable o un tipo de dato abstracto que se utiliza para controlar el acceso a un recurso común al que acceden múltiples hilos y evitar problemas de sección crítica 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, se decrementa o se alterna) según condiciones definidas por el programador.

Una forma útil de entender un semáforo, tal como se usa 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 forma segura (es decir, para evitar condiciones de carrera ) a medida que se adquieren o se liberan unidades y, si es necesario, esperar hasta que una unidad del recurso esté disponible.

Si bien los semáforos son útiles para prevenir 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 restringidos a los valores 0 y 1 (o bloqueado/desbloqueado, no disponible/disponible) se denominan semáforos binarios y se utilizan para implementar bloqueos .

El concepto de semáforo fue inventado por el científico informático holandés Edsger Dijkstra en 1962 o 1963, [ 1 ] cuando Dijkstra y su equipo estaban desarrollando un sistema operativo para la Electrologica X8 . Ese sistema finalmente se conoció como el sistema de multiprogramación THE .

Analogía de la biblioteca

Supongamos que una biblioteca física cuenta con diez salas de estudio idénticas, que un estudiante puede usar a la vez. Los estudiantes deben solicitar una sala en la recepción. Si no hay salas libres, esperan en la recepción hasta que alguien desocupe una. Cuando un estudiante termina de usar una sala, debe regresar a la recepción e indicar que la sala está libre.

En su implementación más sencilla, el recepcionista solo conoce el número de habitaciones libres disponibles. Esto requiere que todos los estudiantes utilicen la habitación que tienen reservada y la devuelvan al terminar. Cuando un estudiante solicita una habitación, el recepcionista disminuye este número. Cuando un estudiante libera una habitación, el recepcionista aumenta este número. La habitación puede utilizarse durante el tiempo que se desee y no se pueden reservar con antelación.

En este escenario, el encargado del conteo en la recepción representa un semáforo de conteo, las habitaciones 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 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, [ 2 ] se ve obligado a esperar hasta que una habitación se libere (cuando el conteo aumenta desde 0). Si una de las habitaciones se liberó, pero hay varios estudiantes esperando, se puede utilizar cualquier método para seleccionar al que ocupará la habitación (como FIFO o selección aleatoria). Y, por supuesto, un estudiante debe informar al recepcionista sobre la liberación de su habitación solo después de abandonarla.

Observaciones importantes

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 los recursos están libres. Es posible que se requiera algún otro mecanismo (que podría involucrar más semáforos) para seleccionar un recurso libre en particular.

Este paradigma resulta especialmente eficaz porque el conteo de señales puede servir como un útil desencadenante para diversas acciones. El bibliotecario mencionado anteriormente podría apagar las luces de la sala de estudio cuando no queden estudiantes, o colocar un cartel que indique que las salas están muy concurridas cuando la mayoría estén ocupadas.

El éxito del protocolo requiere que las aplicaciones lo sigan correctamente. La equidad y la seguridad pueden verse comprometidas (lo que en la práctica significa que un programa puede comportarse lentamente, actuar de forma errática, bloquearse o fallar ) si incluso un solo proceso actúa incorrectamente. Esto incluye:

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

Aunque todos los procesos sigan estas reglas, puede producirse un interbloqueo de múltiples recursos cuando hay diferentes recursos gestionados por diferentes semáforos y cuando los procesos necesitan utilizar más de un recurso a la vez, como ilustra el problema de los filósofos comensales .

Semántica e implementación

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

El valor del semáforo S representa la cantidad de unidades de recursos disponibles cuando es no negativo. En algunas implementaciones, los valores negativos indican la cantidad de procesos que esperan el recurso. La operación P consume tiempo o espera hasta que un recurso protegido por el semáforo esté disponible, momento en el que se reclama inmediatamente. La operación V es la inversa: vuelve a poner un recurso a disposición 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 del semáforo en 1. Si el nuevo valor de la variable del semáforo es negativo, el proceso que ejecuta wait se bloquea (es decir, se agrega a la cola del semáforo). De lo contrario, el proceso continúa su ejecución, habiendo utilizado una unidad del recurso.
  • señal : Incrementa el valor de la variable del semáforo en 1. Después del incremento, si el valor previo al incremento era 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 valor del semáforo. Esto significa que los procesos no pierden tiempo comprobando innecesariamente el valor del semáforo.

El concepto de semáforo de conteo se puede extender 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 + I] función P(sémaforo S, entero I): repetir: [ si S ≥ I: S ← S − I 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 (generalmente con semántica FIFO ). Si un proceso realiza una operación P sobre un semáforo con valor cero, se añade a la cola del semáforo y se suspende su ejecución. Cuando otro proceso incrementa el semáforo mediante una operación V, y hay procesos en la cola, uno de ellos se elimina y reanuda su ejecución. Si los procesos tienen diferentes prioridades, la cola puede ordenarse de forma que el proceso de mayor prioridad se extraiga primero.

Si la implementación no garantiza la atomicidad de las operaciones de incremento, decremento y comparación, existe el riesgo de que se olviden incrementos o decrementos, o de que el valor del semáforo se vuelva negativo. La atomicidad se puede lograr mediante una instrucción de máquina que permita 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 un algoritmo de exclusión mutua por 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 simultáneamente. 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 .

Ejemplos

Ejemplo trivial

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

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

Cola de inicio de sesión

Consideremos un sistema que solo admite diez usuarios (S=10). Cada vez que un usuario inicia sesión, se llama a P, decrementando 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 una ranura de inicio de sesión disponible. Cuando S es 0, los usuarios que deseen iniciar sesión deben esperar hasta que S aumente. La solicitud de inicio de sesión se encola en una cola FIFO hasta que se libera una ranura. Se utiliza la exclusión mutua para garantizar que las solicitudes se encolan en orden. Cada vez que S aumenta (ranuras de inicio de sesión disponibles), se extrae una solicitud de inicio de sesión 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 extraen inmediatamente.

Problema productor-consumidor

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:

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

La solución de semáforos para el problema productor-consumidor rastrea el estado de la cola con dos semáforos: emptyCount, que representa el número de espacios vacíos en la cola, y fullCount, que representa el número de elementos en la cola. Para mantener la integridad, emptyCountpuede ser menor (pero nunca mayor) que el número real de espacios vacíos en la cola, y fullCountpuede ser menor (pero nunca mayor) que el número real de elementos en la cola. Los espacios 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 añadir elementos a una cola vacía simultáneamente, corrompiendo así su estado interno. Como alternativa, 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 realiza lo siguiente repetidamente:

producir: P(conteo de vacíos) P(usarCola) ponerElementoEnLaCola(elemento) V(usarCola) V(conteo completo)

El consumidor realiza lo siguiente repetidamente

consumir: P(recuento completo) P(usarCola) elemento ← obtenerElementoDeLaCola() V(usarCola) V(conteo de vacíos)

A continuación se presenta un ejemplo sustancial:

  1. Un único 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 por uno, acceden a la cola useQueuey depositan los artículos en ella.
  4. Una vez que el primer productor sale de su sección crítica, fullCountse incrementa, lo que permite que un consumidor entre en su sección crítica.

Tenga en cuenta que emptyCountpuede ser mucho menor que el número real de espacios vacíos en la cola, por ejemplo, cuando muchos productores la han disminuido pero esperan su turno useQueueantes de llenar los espacios vacíos. Tenga en cuenta que siempre se cumple, con igualdad si y solo si ningún productor o consumidor está ejecutando sus secciones críticas.emptyCount + fullCount ≤ N

Patrón de traspaso de testigo

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 privado "priv" (inicializado a cero) para cada proceso (o clase de procesos) involucrado y un único semáforo de exclusión mutua "mutex" (inicializado a uno). El pseudocódigo para cada proceso es:

void process ( int proc_id , int res_id ) { resource_acquire ( proc_id , res_id ); < usar el recurso res_id > ; resource_release ( proc_id , res_id ); }

El pseudocódigo de las primitivas de adquisición y liberación de recursos es el siguiente:

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 }

Ambas primitivas, a su vez, utilizan 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 = < elegir el proceso a despertar > ; V ( priv [ p ]); } else { V ( mutex ); } }

Observaciones

Este patrón se denomina "pasar el testigo" porque un proceso que libera el recurso, al igual que un proceso recién reactivado, activará como máximo un proceso suspendido; es decir, le "pasará el testigo". El mutex se libera únicamente cuando un proceso se va a suspender (adquirir recurso) o cuando el patrón "pasar el testigo" no logra reactivar otro proceso suspendido.

Nombres de operaciones

Los nombres canónicos V y P provienen de las iniciales de palabras neerlandesas . 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 significado para P , y vrijgave ("soltar") como significado para 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 significara prolaag , [ 7 ] abreviatura de probeer te verlagen , literalmente "intentar reducir", o para ser paralelo a 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 llama signal y wait , [ 12 ] release y acquire [ 12 ] ( biblioteca estándar de Java ), [ 13 ] o post y pend . Algunos textos las llaman vacate y procure para que coincidan con las iniciales originales en neerlandés. [ 14 ] [ 15 ]

Semáforos frente a mutexes

Un mutex es un mecanismo de bloqueo que a veces utiliza la misma implementación básica que un semáforo binario. Sin embargo, difieren en su uso. Si bien un semáforo binario puede denominarse coloquialmente mutex, un mutex propiamente dicho tiene un caso de uso y una definición más específicos, ya que solo la tarea que lo bloqueó puede desbloquearlo. Esta restricción busca solucionar algunos problemas potenciales del uso de semáforos.

  1. Inversión de prioridad : Si el mutex sabe quién lo bloqueó y 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 proporcionar seguridad contra la eliminación, impidiendo que la tarea que los contiene sea eliminada accidentalmente. (Esto también tiene un coste: si el mutex impide que una tarea sea recuperada, el recolector de basura debe supervisarlo).
  3. Interbloqueo de terminación: Si una tarea que mantiene un mutex finaliza por cualquier motivo, el sistema operativo puede liberar el mutex y notificar a las tareas en espera sobre esta condición.
  4. Interbloqueo recursivo: una tarea puede bloquear un mutex reentrante varias veces, al igual que lo desbloquea un número igual de veces.
  5. Liberación accidental: Se produce un error al liberar el mutex si la tarea que lo libera no es su propietaria.

Véase también

Referencias

  1. ^ Dijkstra , Edsger W. Over de sequentialiteit van procesbeschrijvingen (EWD-35) (PDF) . Archivo EW Dijkstra. Centro de Historia Estadounidense, Universidad de Texas en Austin .( transcripción ) (sin fecha, 1962 o 1963)
  2. ↑ El pequeño libro de las señales de Allen B. Downey
  3. ↑ Andrews, Gregory R. (1999). Fundamentos de la programación multihilo, paralela y distribuida . Addison-Wesley.
  4. ↑ Carver, Richard H.; Thai, Kuo-Chung (2005). Multihilo moderno: implementación, prueba y depuración de programas multihilo en Java y C++/Pthreads/Win32 . Wiley.
  5. ↑ Maurer, Christian (2021). Programación no secuencial y distribuida con Go . Springer.
  6. ↑ Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008), Conceptos de sistemas operativos (8.ª ed.), John Wiley & Sons. Inc, pág. 234, ISBN   978-0-470-12872-5
  7. ↑ Dijkstra, Edsger W. EWD-74 (PDF) . Archivo EW Dijkstra. Centro de Historia Americana, Universidad de Texas en Austin .( transcripción )
  8. ↑ Dijkstra, Edsger W. MULTIPROGAMMERING EN DE X8 (EWD-51) (PDF) . Archivo EW Dijkstra. Centro de Historia Americana, Universidad de Texas en Austin .( transcripción ) (en neerlandés )
  9. ↑ La propia traducción de Dijkstra dice "intentar y disminuir", aunque esa frase podría resultar confusa para quienes desconocen la expresión coloquial "intentar y...".
  10. ↑ (PARCHE 1/19) MUTEX: Introducir una implementación simple de mutex Lista de correo del kernel de Linux, 19 de diciembre de 2005
  11. ↑ Guía práctica para hackear el kernel de Linux. Archivado el 28/05/2010 en Wayback Machine LinuxGrill.com
  12. 1 2 Mullender, Sape; Cox, Russ (2008). Semáforos en Plan 9 (PDF) . 3er Taller Internacional sobre Plan 9 .
  13. ↑java.util.concurrent.Semaphore
  14. ↑ "exec.library/Procure" . amigadev.elowar.com . Consultado el 19 de septiembre de 2016 .
  15. ↑ "exec.library/Vacate" . amigadev.elowar.com . Consultado el 19 de septiembre de 2016 .

Presentaciones

  • 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) . Material complementario . CS107 Paradigmas de programación. Primavera de 2008 (23). Stanford Engineering Everywhere (SEE).

Referencias

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