En informática , el problema productor-consumidor [1] [2] (también conocido como el problema del búfer limitado ) es un ejemplo clásico de un problema de sincronización de múltiples procesos , cuya primera versión fue propuesta por Edsger W. Dijkstra en 1965 en su manuscrito inédito, [3] en el que el búfer era ilimitado, y posteriormente publicado con un búfer limitado en 1972. [4] En la primera versión del problema, hay dos procesos cíclicos, un productor y un consumidor, que comparten un búfer común de tamaño fijo que se utiliza como cola. El productor genera datos repetidamente y los escribe en el búfer. El consumidor lee repetidamente los datos en el búfer, eliminándolos en el transcurso de la lectura y usando esos datos de alguna manera. En la primera versión del problema, con un búfer ilimitado, el problema es cómo diseñar el código de productor y consumidor para que, en su intercambio de datos, no se pierdan ni se dupliquen datos, los datos sean leídos por el consumidor en el orden en que se encuentran. está escrito por el productor, y ambos procesos progresan tanto como sea posible. En la formulación posterior del problema, Dijkstra propuso que varios productores y consumidores compartieran una colección finita de amortiguadores. Esto agregó el problema adicional de evitar que los productores intentaran escribir en búferes cuando todos estaban llenos y tratar de evitar que los consumidores lean un búfer cuando todos estaban vacíos.
El primer caso a considerar es aquel en el que hay un solo productor y un solo consumidor, y hay un búfer de tamaño finito. La solución para el productor es irse a dormir o descartar datos si el búfer está lleno. La próxima vez que el consumidor quita un artículo del búfer, notifica al productor, quien comienza a llenar el búfer nuevamente. De la misma manera, el consumidor puede irse a dormir si encuentra el búfer vacío. La próxima vez que el productor coloca datos en el búfer, despierta al consumidor dormido. La solución se puede alcanzar mediante la comunicación entre procesos , normalmente mediante semáforos . Una solución inadecuada podría resultar en un punto muerto en el que ambos procesos esperan ser despertados.
Implementación inadecuada
Para resolver el problema, es tentador proponer la "solución" que se muestra a continuación. En la solución se utilizan dos rutinas de biblioteca sleep
y wakeup
. Cuando se llama a dormir, la persona que llama se bloquea hasta que otro proceso la despierta mediante la rutina de activación. La variable global itemCount
contiene el número de elementos en el búfer.
int itemCount = 0 ; productor de procedimiento () { while ( verdadero ) { item = produceItem (); if ( itemCount == BUFFER_SIZE ) { dormir (); } putItemIntoBuffer ( elemento ); itemCount = itemCount + 1 ; if ( itemCount == 1 ) { wakeup ( consumidor ); } } } consumidor de procedimiento () { mientras ( verdadero ) { if ( itemCount == 0 ) { dormir (); } item = removeItemFromBuffer (); itemCount = itemCount - 1 ; if ( itemCount == BUFFER_SIZE - 1 ) { despertar ( productor ); } consumItem ( artículo ); } }
El problema con esta solución es que contiene una condición de carrera que puede conducir a un punto muerto . Considere el siguiente escenario:
- El
consumer
acaba de leer la variableitemCount
, se dio cuenta que es cero y está a punto de moverse dentro delif
bloque. - Justo antes de llamar a dormir, se interrumpe al consumidor y se reanuda el productor.
- El productor crea un artículo, lo coloca en el búfer y lo aumenta
itemCount
. - Debido a que el búfer estaba vacío antes de la última adición, el productor intenta despertar al consumidor.
- Desafortunadamente, el consumidor aún no estaba durmiendo y la llamada de atención se perdió. Cuando el consumidor reanuda, se duerme y nunca más se volverá a despertar. Esto se debe a que el productor solo despierta al consumidor cuando
itemCount
es igual a 1. - El productor ejecutará un ciclo hasta que el búfer esté lleno, después de lo cual también se suspenderá.
Dado que ambos procesos permanecerán inactivos para siempre, nos hemos topado con un punto muerto. Por tanto, esta solución no es satisfactoria.
Un análisis alternativo es que si el lenguaje de programación no define la semántica de accesos concurrentes a variables compartidas (en este caso itemCount
) con uso de sincronización, entonces la solución es insatisfactoria por esa razón, sin necesidad de demostrar explícitamente una condición de carrera.
Usando semáforos
Los semáforos resuelven el problema de las llamadas de atención perdidas. En la siguiente solución, usamos dos semáforos fillCount
y emptyCount
, para resolver el problema. fillCount
es el número de elementos que ya están en el búfer y están disponibles para leer, mientras que emptyCount
es el número de espacios disponibles en el búfer donde se pueden escribir los elementos. fillCount
se incrementa y emptyCount
decrementa cuando se coloca un nuevo elemento en el búfer. Si el productor intenta disminuir emptyCount
cuando su valor es cero, el productor se pone a dormir. La próxima vez que se consume un artículo, emptyCount
se incrementa y el productor se despierta. El consumidor trabaja de forma análoga.
semáforo fillCount = 0 ; // artículos producidos semáforo emptyCount = BUFFER_SIZE ; // espacio restante productor de procedimiento () { while ( verdadero ) { item = produceItem (); abajo ( emptyCount ); putItemIntoBuffer ( elemento ); arriba ( fillCount ); } } consumidor de procedimiento () { while ( verdadero ) { abajo ( fillCount ); item = removeItemFromBuffer (); up ( emptyCount ); consumItem ( artículo ); } }
La solución anterior funciona bien cuando solo hay un productor y un consumidor. Con varios productores compartiendo el mismo espacio de memoria para el búfer de elementos, o varios consumidores compartiendo el mismo espacio de memoria, esta solución contiene una condición de carrera grave que podría resultar en dos o más procesos leyendo o escribiendo en la misma ranura al mismo tiempo. Para entender cómo es posible esto, imagine cómo putItemIntoBuffer()
se puede implementar el procedimiento . Podría contener dos acciones, una que determina la siguiente ranura disponible y la otra que escribe en ella. Si el procedimiento puede ser ejecutado simultáneamente por varios productores, entonces es posible el siguiente escenario:
- Decremento de dos productores
emptyCount
- Uno de los productores determina la siguiente ranura vacía en el búfer
- El segundo productor determina el siguiente espacio vacío y obtiene el mismo resultado que el primer productor
- Ambos productores escriben en la misma ranura
Para superar este problema, necesitamos una forma de asegurarnos de que solo se esté ejecutando un productor putItemIntoBuffer()
a la vez. En otras palabras, necesitamos una forma de ejecutar una sección crítica con exclusión mutua . La solución para múltiples productores y consumidores se muestra a continuación.
mutex buffer_mutex ; // similar a "semaphore buffer_mutex = 1", pero diferente (ver notas a continuación) semaphore fillCount = 0 ; semáforo emptyCount = BUFFER_SIZE ; productor de procedimiento () { while ( verdadero ) { item = produceItem (); abajo ( emptyCount ); abajo ( buffer_mutex ); putItemIntoBuffer ( elemento ); arriba ( buffer_mutex ); arriba ( fillCount ); } } consumidor de procedimiento () { while ( verdadero ) { abajo ( fillCount ); abajo ( buffer_mutex ); item = removeItemFromBuffer (); arriba ( buffer_mutex ); up ( emptyCount ); consumItem ( artículo ); } }
Tenga en cuenta que el orden en el que se incrementan o disminuyen los diferentes semáforos es esencial: cambiar el orden puede resultar en un punto muerto. Es importante señalar aquí que, aunque mutex parece funcionar como un semáforo con valor de 1 (semáforo binario), hay una diferencia en el hecho de que mutex tiene el concepto de propiedad. La propiedad significa que el mutex solo se puede "incrementar" (establecido en 1) mediante el mismo proceso que lo "disminuyó" (establecido en 0), y todas las demás tareas esperan hasta que el mutex esté disponible para su disminución (lo que significa efectivamente que el recurso está disponible) , que asegura la exclusividad mutua y evita el estancamiento. Por lo tanto, el uso indebido de mutex puede paralizar muchos procesos cuando no se requiere acceso exclusivo, pero se usa mutex en lugar de semáforo.
Usando monitores
El siguiente pseudocódigo muestra una solución al problema productor-consumidor usando monitores . Dado que la exclusión mutua está implícita en los monitores, no es necesario ningún esfuerzo adicional para proteger la sección crítica. En otras palabras, la solución que se muestra a continuación funciona con cualquier número de productores y consumidores sin ninguna modificación. También es digno de mención que es menos probable que un programador escriba código que sufra condiciones de carrera cuando usa monitores que cuando usa semáforos. [ cita requerida ]
supervisar ProducerConsumer { int itemCount = 0 ; condición completa ; condición vacía ; procedimiento agregar ( elemento ) { if ( itemCount == BUFFER_SIZE ) { esperar ( completo ); } putItemIntoBuffer ( elemento ); itemCount = itemCount + 1 ; if ( itemCount == 1 ) { notificar ( vacío ); } } procedimiento remove () { if ( itemCount == 0 ) { esperar ( vacío ); } item = removeItemFromBuffer (); itemCount = itemCount - 1 ; if ( itemCount == BUFFER_SIZE - 1 ) { notificar ( completo ); } artículo devuelto ; } } productor de procedimiento () { while ( verdadero ) { item = produceItem (); ProducerConsumer . agregar ( elemento ); } }procedimiento consumidor () { mientras ( verdadero ) { artículo = ProducerConsumer . eliminar (); consumItem ( artículo ); } }
Sin semáforos ni monitores
El problema productor-consumidor, particularmente en el caso de un solo productor y un solo consumidor, se relaciona fuertemente con la implementación de un FIFO o un canal . El patrón productor-consumidor puede proporcionar una comunicación de datos altamente eficiente sin depender de semáforos, mutex o monitores para la transferencia de datos . El uso de esas primitivas puede resultar caro en términos de rendimiento, en comparación con la operación atómica básica de lectura / escritura. Los canales y FIFO son populares simplemente porque evitan la necesidad de una sincronización atómica de un extremo a otro. A continuación se muestra un ejemplo básico codificado en C. Tenga en cuenta que:
- Se evita el acceso atómico de lectura, modificación y escritura a las variables compartidas, ya que cada una de las dos
Count
variables se actualiza solo mediante un único hilo. Además, estas variables admiten un número ilimitado de operaciones de incremento; la relación permanece correcta cuando sus valores se envuelven en un desbordamiento de enteros. - Este ejemplo no pone los subprocesos en suspensión, lo que puede ser aceptable según el contexto del sistema. Se
schedulerYield()
inserta como un intento de mejorar el rendimiento y puede omitirse. Las bibliotecas de subprocesos normalmente requieren semáforos o variables de condición para controlar la suspensión / activación de los subprocesos. En un entorno multiprocesador, la suspensión / activación de subprocesos se produciría con mucha menos frecuencia que el paso de tokens de datos, por lo que evitar las operaciones atómicas en el paso de datos es beneficioso. - Este ejemplo no funciona para varios productores y / o consumidores porque existe una condición de carrera al verificar el estado. Por ejemplo, si solo hay un token en el búfer de almacenamiento y dos consumidores encuentran que el búfer no está vacío, ambos consumirán el mismo token y posiblemente aumentarán el contador de los tokens consumidos por encima del contador de los tokens producidos.
- Este ejemplo, tal como está escrito, requiere que
UINT_MAX + 1
sea divisible porBUFFER_SIZE
; si no es divisible uniformemente,[Count % BUFFER_SIZE]
produce el índice de búfer incorrecto después de queCount
pasa deUINT_MAX
nuevo a cero. Una solución alternativa que evita esta limitación emplea dosIdx
variables adicionales para rastrear el índice de búfer actual para la cabeza (productor) y la cola (consumidor). EstasIdx
variables serían utilizado en lugar de[Count % BUFFER_SIZE]
, y cada uno de ellos tendrían que ser incrementado al mismo tiempo que el respectivoCount
se incrementa la variable, como sigue:Idx = (Idx + 1) % BUFFER_SIZE
. - Las dos
Count
variables deben ser lo suficientemente pequeñas para admitir acciones de lectura y escritura atómicas. De lo contrario, existe una condición de carrera en la que el otro hilo lee un valor parcialmente actualizado y, por lo tanto, incorrecto.
volatile unsigned int produceCount = 0 , consumeCount = 0 ; TokenType sharedBuffer [ BUFFER_SIZE ]; productor vacío ( vacío ) { while ( 1 ) { while ( produceCount - consumeCount == BUFFER_SIZE ) { planificadorYield (); / * sharedBuffer está lleno * / } / * Escribe en sharedBuffer _antes_ incrementando produceCount * / sharedBuffer [ produceCount % BUFFER_SIZE ] = produceToken (); / * Barrera de memoria requerida aquí para asegurar que la actualización de sharedBuffer sea visible para otros hilos antes de la actualización de produceCount * / ++ produceCount ; } }nulo consumidor ( nulo ) { while ( 1 ) { while ( produceCount - consumeCount == 0 ) { planificadorYield (); / * sharedBuffer está vacío * / } consumeToken ( & sharedBuffer [ consumeCount % BUFFER_SIZE ]); ++ consumeCount ; } }
La solución anterior emplea contadores que, cuando se usan con frecuencia, pueden sobrecargarse y alcanzar su valor máximo UINT_MAX
. La idea delineada en la cuarta viñeta, originalmente sugerida por Leslie Lamport , [5] explica cómo los contadores pueden ser reemplazados por contadores de rango finito. Específicamente, se pueden reemplazar con contadores de rango finito con el valor máximo N, la capacidad del búfer.
Cuatro décadas después de la presentación del problema productor-consumidor, Aguilera, Gafni y Lamport demostraron que el problema se puede resolver para que los procesos accedan solo a contadores de rango fijo (es decir, un rango que es independiente del tamaño del búfer) mientras determina si el búfer está vacío o lleno. [6] La motivación de esta medida de eficiencia es acelerar las interacciones entre un procesador y los dispositivos que interactúan a través de canales FIFO. Propusieron una solución en la que contadores de valor máximose leen para determinar si es seguro acceder al búfer. Sin embargo, su solución aún emplea contadores ilimitados que crecen infinitamente, solo que no se accede a esos contadores durante la fase de verificación descrita.
Más tarde, Abraham y Amram [7] propusieron una solución más simple, presentada a continuación en pseudocódigo, que posee la propiedad de rango fijo discutida. La solución emplea contadores de valor máximo N. Sin embargo, para determinar si el búfer está vacío o lleno, los procesos acceden solo a registros de escritor único de rango finito . Cada uno de los procesos posee un solo escritor de 12 valores. El proceso productor escribe Flag_p
y el proceso consumidor escribe Flag_c
, ambos son matrices de 3 campos. Flag_p[2]
y Flag_c[2]
puede almacenar "lleno", "vacío" o "seguro", lo que indica correspondientemente si el búfer está lleno, vacío o ni lleno ni vacío.
La idea detrás del algoritmo es la siguiente. Los procesos cuentan el número de artículos entregados y retirados módulo N + 1 a través de registros CountDelivered
y CountRemoved
. Cuando un proceso entrega o elimina un artículo, compara esos contadores y, por lo tanto, determina con éxito el estado del búfer y almacena estos datos en Flag_p[2]
o Flag_c[2]
. En una fase de verificación, el proceso de ejecución lee Flag_p
y Flag_c
, e intenta estimar qué valor entre Flag_p[2]
y Flag_c[2]
refleja el estado actual del búfer. Dos técnicas de sincronización ayudan a lograr este objetivo.
- Después de la entrega de un artículo, el productor escribe en
Flag_p[0]
el valor que lee deFlag_c[0]
, y después de la eliminación de un elemento, las escrituras de consumo hastaFlag_c[1]
el valor:1-Flag_p[0]
. Por lo tanto, la condiciónFlag_p[0] == Flag_c[0]
sugiere que el productor verificó recientemente el estado del búfer, mientras queFlag_p[0] != Flag_c[0]
sugiere lo contrario. - Una operación de entrega (eliminación) finaliza escribiendo en
Flag_p[1]
(Flag_c[1]
) el valor almacenado enFlag_p[0]
(Flag_c[0]
). Por lo tanto, la condiciónFlag_p[0] == Flag_p[1]
sugiere que el productor terminó su última operación de entrega. Asimismo, ConditionFlag_c[0] == Flag_c[1]
sugiere que la última eliminación del consumidor ya fue cancelada.
Por lo tanto, en la fase de verificación, si el productor lo encuentra Flag_c[0] != Flag_p[0] & Flag_c[0] == Flag_c[1]
, actúa de acuerdo con el valor de Flag_c[2]
, y en caso contrario, de acuerdo con el valor almacenado en Flag_p[2]
. De manera análoga, si el consumidor lo encuentra Flag_p[0] == Flag_c[0] & Flag_p[0] == Flag_p[1]
, actúa de acuerdo con el valor de Flag_p[2]
, y en caso contrario, de acuerdo con el valor almacenado en Flag_c[2]
. En el código siguiente, las variables en mayúsculas indican registros compartidos, escritos por uno de los procesos y leídos por ambos procesos. Las variables no capitalizadas son variables locales en las que los procesos copian los valores leídos de los registros compartidos.
countDelivered = 0 ; countRemoved = 0 ; Flag_p [ 0 ] = 0 ; Flag_p [ 1 ] = 0 ; Flag_p [ 2 ] = "vacío" ; Flag_c [ 0 ] = 0 ; Flag_c [ 1 ] = 0 ; Flag_c [ 2 ] = "vacío" ; productor de procedimiento () { while ( verdadero ) { item = produceItem (); / * fase de verificación: espera ocupada hasta que el búfer no esté lleno * / repetir { flag_c = Flag_c ; if ( flag_c [ 0 ] ! = Flag_p [ 0 ] & flag_c [ 0 ] == flag_c [ 1 ]) ans = flag_c [ 2 ]; else ans = Flag_p [ 2 ]; } hasta ( ans ! = "completo" ) / * fase de entrega del artículo * / putItemIntoBuffer ( artículo ); CountDeliverd = countDelivered + 1 % N + 1 ; flag_c = Flag_c ; Flag_p [ 0 ] = flag_c [ 0 ]; eliminado = CountRemoved ; if ( CountDelivered - eliminado == N ) { Flag_p [ 1 ] = flag_c [ 0 ]; Flag_p [ 2 ] = "completo" ; } if ( CountDelivered - eliminado == 0 ) { Flag_p [ 1 ] = flag_c [ 0 ]; Flag_p [ 2 ] = "vacío" ; } if ( 0 < CountDelivered - eliminado < N ) { Flag_p [ 1 ] = flag_c [ 0 ]; Flag_p [ 2 ] = "seguro" ; } } }procedimiento consumidor () { while ( verdadero ) { / * fase de verificación: ocupado esperar hasta que el búfer no esté vacío * / repetir { flag_p = Flag_p ; if ( flag_p [ 0 ] == Flag_c [ 0 ] & flag_p [ 1 ] == flag_p [ 0 ]) ans = flag_p [ 2 ]); else ans = Flag_c [ 2 ]; } hasta ( ans ! = "vacío" ) / * fase de eliminación del elemento * / Item = removeItemFromBuffer (); countRemoved = countRemoved + 1 % N + 1 ; flag_p = Flag_p ; Flag_c [ 0 ] = 1 - flag_p [ 0 ]; entregado = CountDelivered ; if ( entregado - CountRemoved == N ) { Flag_c [ 1 ] = 1 - flag_p [ 0 ]; Flag_c [ 2 ] = "completo" ; } if ( entregado - CountRemoved == 0 ) { Flag_c [ 1 ] = 1 - flag_p [ 0 ]; Flag_c [ 2 ] = "vacío" ; } si ( 0 < entregado - CountRemoved < N ) { Flag_c [ 1 ] = 1 - flag_p [ 0 ]; Flag_c [ 2 ] = "seguro" ; } } }
La exactitud del código se basa en la suposición de que los procesos pueden leer una matriz completa o escribir en varios campos de una matriz en una sola acción atómica. Dado que esta suposición no es realista, en la práctica, uno debe reemplazar Flag_p
y Flag_c
con (log (12) -bit) enteros que codifican los valores de esas matrices. Flag_p
y Flag_c
se presentan aquí como matrices solo para la legibilidad del código.
Ver también
- Operación atómica
- Patrón de diseño
- FIFO
- Tubería
- Implementación en Java: Java Message Service
Referencias
- ^ Arpaci-Dusseau, Remzi H .; Arpaci-Dusseau, Andrea C. (2014), Sistemas operativos: tres piezas fáciles [Capítulo: Variables de condición] (PDF) , Libros de Arpaci-Dusseau
- ^ Arpaci-Dusseau, Remzi H .; Arpaci-Dusseau, Andrea C. (2014), Sistemas operativos: tres piezas fáciles [Capítulo: Semáforos] (PDF) , Libros de Arpaci-Dusseau
- ^ Dijkstra, EW "Cooperating Sequential Processes", manuscrito inédito EWD123 (1965), http://www.cs.utexas.edu/users/EWD/ewd01xx/EWD123.PDF .
- ^ Dijkstra, EW "Flujos de información que comparten un búfer finito". Cartas de procesamiento de información 1.5 (1972): 179-180.
- ^ Lamport, Leslie. "Demostrar la corrección de los programas multiproceso". Transacciones IEEE sobre ingeniería de software 2 (1977): 125-143.
- ^ Aguilera, Marcos K., Eli Gafni y Leslie Lamport. "El problema del buzón". Computación distribuida 23.2 (2010): 113-134.
- ^ Abraham, Uri y Gal Amram. "Sincronización de dos procesos". Ciencias de la computación teóricas 688 (2017): 2-23.
Otras lecturas
- Mark Grand Patterns in Java, Volumen 1, Catálogo de patrones de diseño reutilizables ilustrados con UML
- C / C ++ Users Journal (Dr. Dobb's) Enero de 2004, "Una biblioteca de plantillas de simultaneidad entre productores y consumidores de C ++" , de Ted Yuan, es una biblioteca de plantillas de C ++ lista para usar. El código fuente y los ejemplos de la biblioteca de plantillas pequeñas se pueden encontrar aquí