En la informática distribuida , un objeto de instantánea compartido es un tipo de estructura de datos , que se comparte entre varios subprocesos o procesos. Para muchas tareas, es importante tener una estructura de datos que pueda proporcionar una vista coherente del estado de la memoria. En la práctica, resulta que no es posible obtener un estado tan consistente de la memoria simplemente accediendo a un registro compartido tras otro, ya que los valores almacenados en registros individuales se pueden cambiar en cualquier momento durante este proceso. Para resolver este problema, los objetos instantáneos almacenan un vector de n componentes y proporcionan las siguientes dos operaciones atómicas :update (i, v) cambia el valor del i- ésimo componente av , y scan () devuelve los valores almacenados en todos los n componentes. [1] [2] Los objetos de instantánea se pueden construir utilizando registros compartidos atómicos de un solo escritor y de múltiples lectores .
En general, se distingue entre objetos de instantánea de un solo escritor y de múltiples lectores (swmr) y objetos de instantáneas de múltiples lectores y múltiples lectores (mwmr). En un objeto swmr instantánea, el número de componentes coincide con el número de procesos y sólo un proceso P i se deja de escritura a la posición de memoria i y todos los demás procesos se les permite leer la memoria. Por el contrario, en un objeto de instantánea mwmr, todos los procesos pueden escribir en todas las posiciones de la memoria y también pueden leer la memoria.
General
Una memoria compartida se divide en varias partes. Cada una de estas partes tiene un valor de datos único. En el caso de múltiples lector de un solo escritor de cada proceso P i tiene una posición de memoria i asignado y sólo este proceso se permite escribir en la posición de memoria. Sin embargo, cada proceso puede leer cualquier posición en la memoria. En el caso de múltiples escritores y lectores múltiples, la restricción cambia y cualquier proceso puede cambiar cualquier posición de la memoria. Cualquier proceso P i {1, ..., n } en un sistema de n procesos es capaz de realizar dos operaciones en el objeto de instantánea: escanear () y actualizar (i, v) . La operación de exploración no tiene argumentos y devuelve una vista coherente de la memoria. La operación de actualización (i, v) actualiza la memoria en la posición i con el valor v .
Se considera que ambos tipos de operaciones ocurren atómicamente entre la llamada del proceso y el retorno de la memoria. Hablando de manera más general, en el vector de datoscada entrada d k corresponde al argumento de la última operación de actualización linealizada , que actualiza la parte k de la memoria. [1]
Para obtener el máximo beneficio de los objetos instantáneos compartidos, en términos de simplificaciones para validaciones y construcciones, se agregan otras dos restricciones a la construcción de objetos instantáneos. [1] La primera restricción es arquitectónica, lo que significa que cualquier objeto de instantánea se construye solo con registros de lector múltiple de un solo escritor como elemento básico. Esto es posible para instantáneas de varios lectores de un solo escritor. Para objetos instantáneos de múltiples lectores, múltiples lectores, es posible utilizar registros de múltiples lectores y múltiples escritores , que a su vez pueden construirse a partir de registros de múltiples lectores de un solo escritor. [1] [3] [4]
En la computación distribuida, la construcción de un sistema está impulsada por el objetivo de que todo el sistema progrese durante la ejecución. Por lo tanto, el comportamiento de un proceso no debería detener todo el sistema ( Lock-freedom ). La versión más fuerte de esto es la propiedad de la libertad de espera , lo que significa que ningún proceso puede evitar que otro proceso termine su operación. De manera más general, esto significa que cada operación debe terminar después de un número finito de pasos, independientemente del comportamiento de otros procesos. Un algoritmo de instantáneas muy básico garantiza el progreso de todo el sistema, pero solo está libre de bloqueos. Es fácil ampliar este algoritmo para que no tenga que esperar. El algoritmo de Afek et al., [1] que se presenta en la sección Implementación tiene esta propiedad.
Implementación
Existen varios métodos para implementar objetos instantáneos compartidos. El primer algoritmo presentado proporciona una implementación principal de objetos instantáneos. Sin embargo, esta implementación solo proporciona la propiedad de libertad de bloqueo . El segundo presentó la implementación propuesta por Afek et al. [1] tiene una propiedad más fuerte llamada libertad de espera . Fich ofrece una descripción general de otras implementaciones. [2]
Algoritmo básico de instantánea swmr
La idea básica de este algoritmo es que cada proceso que ejecuta las scan()
operaciones lee todos los valores de la memoria dos veces. Si el algoritmo lee exactamente el mismo contenido de memoria dos veces, ningún otro proceso cambió un valor intermedio y puede devolver el resultado. Un proceso, que ejecuta una update(i,v)
operación, simplemente actualiza su valor en la memoria.
función scan () mientras es verdadera a [1..n]: = recolectar; b [1..n]: = recolectar; si (∀i∈ {1, .., n} ubicación i no se cambió entre las lecturas durante las dos recolecciones)) entonces volver b; // doble recolección exitosa final del bucle
actualización de función (i, v) M [i]: = v;final
Este algoritmo proporciona una implementación muy básica de objetos instantáneos. Garantiza que el sistema avanza, mientras que los subprocesos individuales pueden morir de hambre debido al comportamiento de los procesos individuales. Un proceso P i puede evitar que otro proceso P j termine una scan()
operación cambiando siempre su valor, entre las dos recopilaciones de memoria. Por lo tanto, el algoritmo está libre de bloqueos , pero no de espera . Para mantener esta propiedad más fuerte, no se permite que ningún proceso muera de hambre debido al comportamiento de otros procesos. La figura 1 ilustra el problema. Mientras P 1 intenta ejecutar la scan()
operación, un segundo proceso P 2 siempre perturba el "doble cobro". Por lo tanto, el proceso de escaneo siempre tiene que reiniciar la operación y nunca puede terminar y morir de hambre.
Implementación de lector múltiple de un solo escritor por Afek et al.
La idea básica del algoritmo de instantáneas swmr de Afek et al. es que un proceso puede detectar si otro proceso cambió su ubicación de memoria y que los procesos se ayudan entre sí. Para detectar si otro proceso cambió su valor, se adjunta un contador a cada registro y un proceso aumenta el contador en cada actualización. La segunda idea es que, cada proceso que actualiza su posición de memoria también realiza una scan()
operación y proporciona su "vista de la memoria" en su registro a otros procesos. Un proceso de escaneo puede tomar prestado este scan
resultado y devolverlo.
Basado en memoria ilimitada
Usando esta idea, se puede construir un algoritmo sin esperas que use registros de tamaño ilimitado. Un proceso que realiza una operación de actualización puede ayudar a un proceso a completar el análisis. La idea básica es que si un proceso ve que otro proceso actualiza una ubicación de memoria dos veces, ese proceso debe haber ejecutado una operación de actualización completa y linealizada en el medio. Para implementar esto, cada operación de actualización primero realiza un escaneo de la memoria y luego escribe el valor de la instantánea de forma atómica junto con el nuevo valor vy un número de secuencia. Si un proceso está realizando un escaneo de la memoria y detecta que un proceso actualizó la parte de la memoria dos veces, puede "tomar prestado" el escaneo "integrado" de la actualización para completar la operación de escaneo . [1]
función de exploración () // devuelve una visión consistente de la memoria para j = 1 a n do trasladó [j]: = 0 extremo mientras que la verdadera do a [1..n]: = recolectar; // recopila (datos, secuencia, vista) triples b [1..n]: = recolectar; // recopila (datos, secuencia, vista) triples si (∀j∈ {1, ..., n}) (a [j] .seq = b [j] .seq) entonces devuelve (b [1] .data, ..., b [n] .data ) // no proceso de la memoria cambiado más para j = 1 a n hacer si un [j] .seq ≠ b [j] .seq entonces // proceso movido si movido [j] = 1 entonces // proceso ya se trasladaron antes retorno b [j] .vista; más movido [j]: = movido [j] + 1; función final final final
actualización del procedimiento ( i , v ) // actualiza los registros con los valores de datos, actualiza el número de secuencia, escaneo integrado s [1..n]: = escanear; // escaneo incrustado r i : = (v, r i .seq = r i .seq + 1, s [1..n]);procedimiento final
Cada registro consta de un campo para el valor de los datos, el número de secuencia y un campo para el resultado del último escaneo integrado, recopilado antes de la última actualización. En cada operación de exploración del proceso P i puede decidir si un proceso cambió su memoria usando el número de secuencia. Si no hay ningún cambio en la memoria durante el doble cobro revertido, P i puede devolver el resultado de la segunda exploración. Una vez que el proceso observa que otro proceso actualizó la memoria en el medio, guarda esta información en el campo movido. Si un proceso P j cambió su memoria dos veces durante la ejecución del escaneo (), el proceso de escaneo P i puede devolver el escaneo incrustado del proceso de actualización, que guardó en su propio registro durante su operación de actualización.
Estas operaciones se pueden linealizar linealizando cada operación update () en su escritura en el registro. La operación de escaneo es más complicada de linealizar. Si la recopilación doble de la operación de escaneo tiene éxito, la operación de escaneo se puede linealizar al final del segundo escaneo. En el otro caso, un proceso actualizó su registro dos veces, la operación se puede linealizar en el momento en que el proceso de actualización recopiló su escaneo integrado antes de escribir su valor en el registro. [1]
Basado en memoria limitada
Una de las limitaciones del algoritmo presentado es que se basa en una memoria ilimitada ya que el número de secuencia aumentará constantemente. Para superar esta limitación, es necesario introducir una forma diferente de detectar si un proceso ha cambiado su posición de memoria dos veces en el medio. Cada par de procesosse comunica mediante dos registros de un solo escritor y un solo lector (swsr), que contienen dos bits atómicos. Antes de que un proceso comience a realizar una "recopilación doble", copia el valor de su proceso asociado a su propio registro. Si el proceso de escáner P i observa después de ejecutar el "doble cobro" que el valor del proceso socio P j ha cambiado en el medio indica que el proceso se ha realizado una operación de actualización de la memoria. [1]
función de exploración () // devuelve una visión consistente de la memoria para j = 1 a n do trasladó [j]: = 0 extremo mientras que la verdadera do para j = 1 a n hacer q i, j : = r j .p j, i termino un [1..n]: = cobro revertido; // recopila (datos, vector de bits, alternar, ver) triples b [1..n]: = recopilar; // recopila (datos, vector de bits, alternar, ver) triplica si (∀j∈ {1, ..., n}) (a [j] .p j, i = b [j] .p j, i = q i, j ) y a [j] .toggle = b [j] .toggle then return (b [1] .data, ..., b [n] .data) // ningún proceso cambió la memoria más para j = 1 a n hacer si (a [j] .p j, i ≠ q i, j ) o (b [j] .p j, i ≠ q i, j ) o (b a [j] .toggle ≠ [ j] .toggle) luego // el proceso j realizó una actualización si se movió [j] = 2 luego // el proceso ya se movió antes de return b [j] .view; else movido [j]: = movido [j] + 1; función final final final
procedimiento de actualización ( i , v ) // actualiza los registros con los datos de valor, "escritura estado" de todos los registros, invertir el bit de conmutación y el embebido de exploración para j = 1 a n do f [j]: = ¬Q j, i final s [1..n]: = exploración; // escaneo incrustado r i : = (v, f [1..n], ¬r i .toggle, s [1..n]);procedimiento final
El número de secuencia ilimitado se reemplaza por dos bits de protocolo de enlace para cada par de procesos. Estos bits de apretón de manos se basan en registros RSOL y se pueden expresar por una matriz M , donde proceso P i se permite escribir en la fila i y se le permite leer los bits de apretón de manos en una columna i . Antes de que el proceso de escaneo realice la recopilación doble, recopila todos los bits de protocolo de enlace de todos los registros, leyendo su columna. Posteriormente, puede decidir si un proceso cambió su valor durante el valor doble o no. Por lo tanto, el proceso solo tiene que comparar la columna nuevamente con los bits de protocolo de enlace leídos inicialmente. Si sólo hay un proceso P j ha escrito dos veces, durante la recogida de P i es posible que los bits de apretón de manos no cambian durante la exploración. Por tanto, es necesario introducir otro bit llamado "bit toggle", este bit se cambia en cada escritura. Esto permite distinguir dos escrituras consecutivas, aunque ningún otro proceso actualizó su registro. Este enfoque permite sustituir los números de secuencia ilimitados con los bits de protocolo de enlace, sin cambiar nada más en el procedimiento de exploración.
Mientras que el proceso de exploración P i utiliza un bit de diálogo para detectar si se puede utilizar su doble cobro revertido o no, otros procesos pueden también realizar operaciones de actualización. Como primer paso, vuelven a leer los bits de protocolo de enlace proporcionados por los otros procesos y generan el complemento de ellos. Posteriormente, estos procesos vuelven a generar el escaneo integrado y guardan el valor de datos actualizado, los bits de protocolo de enlace recopilados (complementados), el bit de alternancia complementado y el escaneo integrado en el registro.
Dado que los bits de protocolo de enlace reemplazan de manera equivalente a los números de secuencia, la linealización es la misma que en el caso de memoria ilimitada.
Implementación de Multi-Writer Multi-Reader por Afek et al.
La construcción de un objeto de instantánea de múltiples lectores y múltiples escritores asume que n procesos pueden escribir en cualquier ubicación de la memoria, que consta de m registros. Por lo tanto, ya no hay correlación entre la identificación del proceso y la ubicación de la memoria. Por lo tanto, ya no es posible acoplar los bits de protocolo de enlace o el escaneo integrado con los campos de datos. Por lo tanto, los bits de protocolo de enlace, la memoria de datos y el escaneo integrado no se pueden almacenar en el mismo registro y la escritura en la memoria ya no es una operación atómica.
Por lo tanto, el update()
proceso tiene que actualizar tres registros diferentes de forma independiente. Primero tiene que guardar los bits de protocolo de enlace que lee, luego hacer el escaneo integrado y finalmente guarda su valor en la posición de memoria designada. Cada escritura de forma independiente parece hacerse de forma atómica, pero juntas no lo son. El nuevo update()
procedimiento conduce a algunos cambios en la scan()
función. Ya no es suficiente leer los bits del protocolo de enlace y recopilar el contenido de la memoria dos veces. Para detectar un update
proceso de inicio , un proceso tiene que recopilar los bits de reconocimiento por segunda vez, después de recopilar el contenido de la memoria.
Si falla una recopilación doble, ahora es necesario que un proceso vea que otro proceso se mueve tres veces antes de tomar prestado el escaneo integrado. La figura 3 ilustra el problema. La primera recopilación doble falla porque un update
proceso se inició antes de que la operación de escaneo finalice su escritura en memoria durante la primera recopilación doble. Sin embargo, el escaneo incrustado de esta escritura se realiza y se guarda, antes de que P 1 comience a escanear la memoria y, por lo tanto, no hay un punto de linealización válido. La segunda recopilación doble falla, porque el proceso P 2 inicia una segunda escritura y actualiza sus bits de reconocimiento. En el escenario swmr, ahora tomaríamos prestado el escaneo incrustado y lo devolveríamos. En el escenario mwmr, esto no es posible porque el escaneo incrustado del segundo write
aún no está linealizado dentro del intervalo de escaneo (inicio y finalización de la operación). Por lo tanto, el proceso tiene que ver un tercer cambio con respecto al otro proceso para estar completamente seguro de que al menos un escaneo incrustado se ha linealizado durante el intervalo de escaneo. Después del tercer cambio por un proceso, el proceso de escaneo puede tomar prestado el valor de la memoria anterior sin violar el criterio de linealización.
Complejidad
La implementación básica presentada de objetos instantáneos compartidos por Afek et al. necesidadesoperaciones de memoria. [1] Otra implementación de Anderson, que se desarrolló de forma independiente, necesita un número exponencial de operaciones. [5] También hay implementaciones aleatorias de objetos instantáneos basados en registros swmr usandooperaciones. [6] Otra implementación de Israel y Shirazi, que usa memoria ilimitada, requiereoperaciones en la memoria. [7] [8] Israelí y col. mostrar en un trabajo diferente el límite inferior de las operaciones de bajo nivel para cualquier operación de actualización. El límite inferior es, donde w es el número de actualizadores y r es el número de escáneres. Attiya y Rachman presentan un algoritmo de instantánea determinista basado en registros swmr, que utilizaoperaciones por actualización y escaneo. [8] Aplicando un método general de Israel, Shaham y Shirazi [9], esto se puede mejorar a un algoritmo de instantánea ilimitado, que solo necesita operaciones por escaneo y operaciones por actualización. Hay más mejoras introducidas por Inoue et al., [10] utilizando solo un número lineal de operaciones de lectura y escritura. A diferencia de los otros métodos presentados, este enfoque utiliza registros mwmr y no registros swmr.
Aplicaciones
Hay varios algoritmos en la computación distribuida que pueden simplificarse en el diseño y / o verificación utilizando objetos instantáneos compartidos. [1] Ejemplos de esto son problemas de exclusión, [11] [12] [13] sistemas concurrentes de sellos de tiempo, [14] acuerdo aproximado, [15] consenso aleatorio [16] [17] e implementaciones sin espera de otros datos estructuras. [18] Con los objetos instantáneos mwmr también es posible crear registros atómicos de múltiples escritores y múltiples lectores .
Ver también
- Registro compartido
- Memoria compartida (comunicación entre procesos)
- Arquitectura de memoria compartida
- Memoria compartida distribuida
- Linealizabilidad
Referencias
- ^ a b c d e f g h i j k Afek, Yehuda; Attiya, Hagit; Dolev, Danny; Gafni, Eli; Merritt, Michael; Shavit, Nir (septiembre de 1993). "Instantáneas atómicas de memoria compartida". J. ACM . 40 (4): 873–890. doi : 10.1145 / 153724.153741 .
- ^ a b Fich, Faith Ellen (2005). "¿Qué tan difícil es tomar una instantánea?". SOFSEM 2005: Teoría y práctica de la informática . Apuntes de conferencias en informática. 3381 (SOFSEM 2005: Teoría y práctica de la informática ed.). Springer Berlín Heidelberg. págs. 28–37. doi : 10.1007 / 978-3-540-30577-4_3 . ISBN 978-3-540-24302-1.
- ^ Li, Ming; Tromp, John; Vitanyi, Paul MB (julio de 1996). "Cómo compartir variables simultáneas sin espera". J. ACM . 43 (4): 723–746. CiteSeerX 10.1.1.56.3236 . doi : 10.1145 / 234533.234556 .
- ^ Peterson, Gary L; Burns, James E. (1987). "Lectura concurrente mientras se escribe ii: el caso de varios escritores". Fundamentos de las Ciencias de la Computación, 1987., 28º Simposio Anual de . págs. 383–392.
- ^ Anderson, James H. (1993). "Registros compuestos". Computación distribuida . 6 (3): 141-154. doi : 10.1007 / BF02242703 .
- ^ Attiya, Hagit; Helihy, Maurice; Rachman, Ophir (1995). "Instantáneas atómicas mediante acuerdo de celosía". Computación distribuida . 8 (3): 121-132. doi : 10.1007 / BF02242714 .
- ^ Israelí, Amos; Shirazi, Asaf (1992). "Protocolo de instantánea eficiente mediante acuerdo de 2 celosías". Manuscrito .
- ^ a b Attiya, Hagit; Rachman, Ophir (abril de 1998). "Instantáneas atómicas en operaciones O (n log n)". Revista SIAM de Computación . 27 (2): 319–340. doi : 10.1145 / 164051.164055 .
- ^ Israelí, Amos; Shaham, Amnon; Shirazi, Asaf (1993). "Protocolos de instantáneas en tiempo lineal para sistemas no balanceados" . Algoritmos distribuidos . Saltador. págs. 26–38. doi : 10.1007 / 3-540-57271-6_25 . ISBN 978-3-540-57271-8.
- ^ Inoue, Michiko; Masuzawa, Toshimitsu; Chen, Wei; Tokura, Nobuki (1994). Instantánea en tiempo lineal mediante registros de varios lectores y varios escritores . Algoritmos distribuidos . 857 . Saltador. págs. 130-140. doi : 10.1007 / BFb0020429 . ISBN 978-3-540-58449-0.
- ^ Dolev, Danny; Gafni, Eli; Shavit, Nir (1988). "Hacia una era no atómica: l-exclusión como caso de prueba". Actas del vigésimo simposio anual de ACM sobre teoría de la computación . págs. 78–92.
- ^ Katseff, Howard P (1978). "Una nueva solución al problema de la sección crítica". Actas del décimo simposio anual ACM sobre teoría de la computación . págs. 86–88.
- ^ Lamport, Leslie (1988). "El problema de la exclusión mutua: parte II: declaración y soluciones". Revista de la ACM . 33 (2): 327–348. CiteSeerX 10.1.1.32.9808 . doi : 10.1145 / 5383.5385 .
- ^ Dolev, Danny; Shavit, Nir (1989). "Los sistemas de sellos de tiempo concurrentes delimitados son construibles". Actas del vigésimo primer simposio anual ACM sobre teoría de la computación . ACM. págs. 454–466.
- ^ Attiya, Hagit; Lynch, Nancy; Shavit, Nir (1990). "¿Son rápidos los algoritmos sin espera?". Fundamentos de las Ciencias de la Computación, 1990. Actas., 31º Simposio Anual de . págs. 55–64.
- ^ Abrahamson, Karl (1988). "Sobre la consecución de consensos utilizando una memoria compartida". Actas del séptimo simposio anual de ACM sobre principios de computación distribuida . págs. 291-302.
- ^ Attiya, Hagit; Dolev, Danny; Shavit, Nir (1989). Consenso aleatorizado de polinomio acotado . Actas del octavo simposio anual ACM sobre principios de computación distribuida . págs. 281-293.
- ^ Aspnes, James; Herlihy, Maurice (1990). "Estructuras de datos sin espera en el modelo PRAM asincrónico". Actas del segundo simposio anual de ACM sobre algoritmos y arquitecturas paralelas . ACM. págs. 340–349.