Leer-copiar-actualizar

En informática , lectura-copia-actualización ( RCU ) es un mecanismo de sincronización que evita el uso de primitivas de bloqueo mientras varios subprocesos leen y actualizan simultáneamente elementos que están vinculados a través de punteros y que pertenecen a estructuras de datos compartidas (por ejemplo, listas vinculadas , árboles , tablas hash ). ^[1]

Siempre que un hilo inserta o elimina elementos de estructuras de datos en la memoria compartida , se garantiza que todos los lectores verán y atravesarán la estructura anterior o la nueva, evitando así inconsistencias (por ejemplo, desreferenciar punteros nulos). ^[1]

Se utiliza cuando el rendimiento de las lecturas es crucial y es un ejemplo de compensación espacio-tiempo , lo que permite operaciones rápidas a costa de más espacio. Esto hace que todos los lectores procedan como si no hubiera una sincronización involucrada, por lo tanto, serán rápidos, pero también dificultan las actualizaciones.

Nombre y descripción general

El nombre proviene de la forma en que se usa RCU para actualizar una estructura vinculada en su lugar. Un hilo que desee hacer esto utiliza los siguientes pasos:

• crear una nueva estructura,
• copie los datos de la estructura anterior en la nueva y guarde un puntero a la estructura anterior,
• modificar la estructura nueva copiada
• actualice el puntero global para hacer referencia a la nueva estructura, y luego
• sleep hasta que el kernel del sistema operativo determine que no quedan lectores usando la estructura anterior, por ejemplo, en el kernel de Linux, usando synchronize_rcu () .

Cuando el hilo que hizo la copia es despertado por el kernel, puede desasignar de forma segura la estructura anterior.

Entonces, la estructura se lee al mismo tiempo que se copia un hilo para realizar una actualización , de ahí el nombre "actualización de lectura-copia". La abreviatura "RCU" fue una de las muchas contribuciones de la comunidad Linux. Otros nombres para técnicas similares incluyen serialización pasiva y diferimiento de MP por programadores VM / XA y generaciones por programadores K42 y Tornado .

Descripción detallada

Procedimiento de inserción de lectura-copia-actualización. Un hilo asigna una estructura con tres campos, luego establece el puntero global gptr para que apunte a esta estructura.

Una propiedad clave de RCU es que los lectores pueden acceder a una estructura de datos incluso cuando está en proceso de actualización: los actualizadores de RCU no pueden bloquear a los lectores ni obligarlos a reintentar sus accesos. Esta descripción general comienza mostrando cómo se pueden insertar y eliminar datos de forma segura en estructuras vinculadas a pesar de los lectores simultáneos. El primer diagrama de la derecha muestra un procedimiento de inserción de cuatro estados, con el tiempo avanzando de izquierda a derecha.

El primer estado muestra un puntero global llamado gptr que inicialmente es NULL , de color rojo para indicar que un lector podría acceder a él en cualquier momento, por lo que es necesario que los actualizadores tengan cuidado. La asignación de memoria para una nueva estructura pasa al segundo estado. Esta estructura tiene un estado indeterminado (indicado por los signos de interrogación) pero es inaccesible para los lectores (indicado por el color verde). Debido a que la estructura es inaccesible para los lectores, el actualizador puede realizar cualquier operación deseada sin temor a interrumpir a los lectores concurrentes. La inicialización de esta nueva estructura pasa al tercer estado, que muestra los valores inicializados de los campos de la estructura. Asignar una referencia a esta nueva estructura a gptrtransiciones al cuarto y último estado. En este estado, la estructura es accesible para los lectores y, por lo tanto, está coloreada en rojo. La primitiva rcu_assign_pointer se utiliza para realizar esta asignación y asegura que la asignación sea atómica en el sentido de que los lectores concurrentes verán un puntero NULL o un puntero válido a la nueva estructura, pero no una combinación de los dos valores. Las propiedades adicionales de rcu_assign_pointer se describen más adelante en este artículo.

Procedimiento de eliminación de lectura-copia-actualización

Este procedimiento demuestra cómo se pueden insertar nuevos datos en una estructura de datos vinculada aunque los lectores estén atravesando simultáneamente la estructura de datos antes, durante y después de la inserción. El segundo diagrama de la derecha muestra un procedimiento de eliminación de cuatro estados, nuevamente con el tiempo avanzando de izquierda a derecha.

La primera muestra de estado una lista enlazada que contiene elementos A , B , y C . Los tres elementos están coloreados en rojo para indicar que un lector de RCU puede hacer referencia a cualquiera de ellos en cualquier momento. El uso de list_del_rcu para eliminar el elemento B de esta lista pasa al segundo estado. Tenga en cuenta que el enlace del elemento B al C se deja intacto para permitir que los lectores que actualmente hacen referencia al elemento B recorran el resto de la lista. Los lectores que accedan al enlace desde el elemento A obtendrán una referencia al elemento B o al elemento C , pero de cualquier manera, cada lector verá una lista enlazada válida y correctamente formateada. ElementoB ahora está coloreado de amarillo para indicar que, si bien los lectores preexistentes aún pueden tener una referencia al elemento B , los nuevos lectores no tienen forma de obtener una referencia. Una operación de espera de lectores pasa al tercer estado. Tenga en cuenta que esta operación de esperar lectores solo necesita esperar a los lectores preexistentes, pero no a los nuevos. El elemento B ahora está coloreado en verde para indicar que los lectores ya no pueden hacer referencia a él. Por lo tanto, ahora es seguro para el actualizador liberar el elemento B , pasando así al cuarto y último estado.

Es importante reiterar que en el segundo estado diferentes lectores pueden ver dos versiones diferentes de la lista, ya sea con o sin elemento de B . En otras palabras, RCU proporciona coordinación en el espacio (diferentes versiones de la lista) así como en el tiempo (diferentes estados en los procedimientos de eliminación). Esto está en marcado contraste con las primitivas de sincronización más tradicionales, como el bloqueo o las transacciones que se coordinan en el tiempo, pero no en el espacio.

Este procedimiento demuestra cómo se pueden eliminar los datos antiguos de una estructura de datos vinculada aunque los lectores estén atravesando simultáneamente la estructura de datos antes, durante y después de la eliminación. Dada la inserción y eliminación, se puede implementar una amplia variedad de estructuras de datos utilizando RCU.

Los lectores de RCU se ejecutan dentro de las secciones críticas del lado de lectura , que normalmente están delimitadas por rcu_read_lock y rcu_read_unlock . Cualquier declaración que no esté dentro de una sección crítica del lado de lectura de RCU se dice que está en un estado inactivo , y no se permite que dichas declaraciones contengan referencias a estructuras de datos protegidas por RCU, ni se requiere que la operación de espera de lectores espere. para hilos en estados inactivos. Cualquier período de tiempo durante el cual cada subproceso reside al menos una vez en un estado inactivo se denomina período de gracia.. Por definición, cualquier sección crítica del lado de lectura de RCU que exista al comienzo de un período de gracia determinado debe completarse antes del final de ese período de gracia, que constituye la garantía fundamental proporcionada por RCU. Además, la operación de espera de lectores debe esperar a que transcurra al menos un período de gracia. Resulta que esta garantía se puede proporcionar con una sobrecarga del lado de lectura extremadamente pequeña, de hecho, en el caso límite que realmente se da en las compilaciones del kernel de Linux de clase de servidor, la sobrecarga del lado de lectura es exactamente cero. ^[2]

La garantía fundamental de RCU se puede utilizar dividiendo las actualizaciones en fases de eliminación y recuperación . La fase de eliminación elimina las referencias a elementos de datos dentro de una estructura de datos (posiblemente reemplazándolos con referencias a nuevas versiones de estos elementos de datos) y puede ejecutarse simultáneamente con las secciones críticas del lado de lectura de RCU. La razón por la que es seguro ejecutar la fase de eliminación al mismo tiempo que los lectores RCU es que la semántica de las CPU modernas garantiza que los lectores verán la versión antigua o la nueva de la estructura de datos en lugar de una referencia parcialmente actualizada. Una vez que ha transcurrido un período de gracia, ya no puede haber lectores que hagan referencia a la versión anterior, por lo que es seguro que la fase de recuperación libere ( recupere ) los elementos de datos que componían esa versión anterior.^[3]

Dividir una actualización en fases de eliminación y recuperación permite al actualizador realizar la fase de eliminación inmediatamente y aplazar la fase de recuperación hasta que todos los lectores activos durante la fase de eliminación hayan finalizado, en otras palabras, hasta que haya transcurrido un período de gracia. ^{[nota 1]}

Entonces, la secuencia típica de actualización de RCU es algo como lo siguiente: ^[4]

1. Asegúrese de que todos los lectores que acceden a estructuras de datos protegidas por RCU realicen sus referencias desde una sección crítica del lado de lectura de RCU.
2. Elimine los punteros a una estructura de datos, de modo que los lectores posteriores no puedan obtener una referencia a ella.
3. Espere a que transcurra un período de gracia, de modo que todos los lectores anteriores (que aún podrían tener punteros a la estructura de datos eliminados en el paso anterior) hayan completado sus secciones críticas del lado de lectura de RCU.
4. En este punto, no puede haber ningún lector que todavía tenga referencias a la estructura de datos, por lo que ahora se puede reclamar de manera segura (por ejemplo, liberar). ^{[nota 2]}

En el procedimiento anterior (que coincide con el diagrama anterior), el actualizador está realizando tanto la eliminación como el paso de recuperación, pero a menudo es útil que un subproceso completamente diferente realice la recuperación. El recuento de referencias se puede usar para permitir que el lector realice la eliminación, por lo que, incluso si el mismo hilo realiza tanto el paso de actualización (paso (2) anterior) como el paso de recuperación (paso (4) anterior), a menudo es útil pensar en ellos por separado.

Usos

A principios de 2008, había casi 2.000 usos de la API RCU dentro del kernel de Linux ^[5], incluidas las pilas de protocolos de red ^[6] y el sistema de gestión de memoria. ^[7] En marzo de 2014 ^[actualizar], había más de 9.000 usos. ^[8] Desde 2006, los investigadores han aplicado RCU y técnicas similares a una serie de problemas, incluida la gestión de metadatos utilizados en el análisis dinámico, ^{[9] la} gestión de la vida útil de los objetos agrupados, ^{[10] la} gestión de la vida útil de los objetos en el sistema operativo de investigación K42 , ^{[11] [12]} y optimización de implementaciones de memoria transaccional de software . ^{[13] [14]} Dragonfly BSD utiliza una técnica similar a RCU que se parece más a la implementación de Sleepable RCU (SRCU) de Linux.

Ventajas y desventajas

La capacidad de esperar hasta que todos los lectores hayan terminado permite que los lectores de RCU utilicen una sincronización mucho más liviana; en algunos casos, absolutamente ninguna sincronización. Por el contrario, en los esquemas basados ​​en bloqueos más convencionales, los lectores deben usar una sincronización de gran peso para evitar que un actualizador elimine la estructura de datos debajo de ellos. La razón es que los actualizadores basados ​​en bloqueos normalmente actualizan los datos en su lugar y, por lo tanto, deben excluir a los lectores. Por el contrario, los actualizadores basados ​​en RCU suelen aprovechar el hecho de que las escrituras en punteros alineados simples son atómicas en las CPU modernas, lo que permite la inserción, eliminación y reemplazo atómicos de datos en una estructura vinculada sin interrumpir a los lectores. Los lectores simultáneos de RCU pueden continuar accediendo a las versiones anteriores y pueden prescindir de las instrucciones atómicas de lectura-modificación-escritura, barreras de memoria,y errores de caché que son tan costosos en losSistemas informáticos SMP , incluso en ausencia de contención de bloqueo. ^{[15] [16]} La naturaleza liviana de las primitivas del lado de lectura de RCU proporciona ventajas adicionales más allá de un excelente rendimiento, escalabilidad y respuesta en tiempo real. Por ejemplo, brindan inmunidad a la mayoría de las condiciones de interbloqueo y bloqueo activo. ^{[nota 3]}

Por supuesto, RCU también tiene desventajas. Por ejemplo, RCU es una técnica especializada que funciona mejor en situaciones con mayor cantidad de lecturas y pocas actualizaciones, pero a menudo es menos aplicable a cargas de trabajo de solo actualización. Para otro ejemplo, aunque el hecho de que los lectores y actualizadores de RCU puedan ejecutarse al mismo tiempo es lo que habilita la naturaleza liviana de las primitivas del lado de lectura de RCU, algunos algoritmos pueden no ser aptos para la concurrencia de lectura / actualización.

A pesar de más de una década de experiencia con RCU, el alcance exacto de su aplicabilidad sigue siendo un tema de investigación.

Patentes

La técnica está cubierto por los Estados Unidos de patentes de software 5.442.758, expedida el 15 de agosto de, 1995 y asignada a Sequent Computer Systems , así como por 5.608.893 (expiró 2009-03-30), 5.727.209 (expiró 2010-04-05), 6.219.690 (2009 expiró -05-18) y 6,886,162 (vencido el 25 de mayo de 2009). La patente de EE.UU. 4.809.168, ahora vencida, cubre una técnica estrechamente relacionada. UCR es también el tema de una reclamación en el SCO v. IBM demanda .

Ejemplo de interfaz RCU

RCU está disponible en varios sistemas operativos y se agregó al kernel de Linux en octubre de 2002. También están disponibles implementaciones a nivel de usuario como liburcu . ^[17]

La implementación de RCU en la versión 2.6 del kernel de Linux se encuentra entre las implementaciones de RCU más conocidas y se utilizará como inspiración para la API de RCU en el resto de este artículo. La API central ( interfaz de programación de aplicaciones ) es bastante pequeña: ^[18]

• rcu_read_lock (): Marca una estructura de datos protegida por RCU para que no sea reclamada durante toda la duración de esa sección crítica.
• rcu_read_unlock (): utilizado por un lector para informar al recuperador de que el lector está saliendo de una sección crítica del lado de lectura de RCU. Tenga en cuenta que las secciones críticas del lado de lectura de RCU pueden estar anidadas y / o superpuestas.
• Synchronize_rcu (): se bloquea hasta que se hayan completado todas las secciones críticas del lado de lectura de RCU preexistentes en todas las CPU. Tenga en cuenta que synchronize_rcuse no necesariamente esperar a que cualquier RCU posterior lectura por el lado de las secciones críticas para completar. Por ejemplo, considere la siguiente secuencia de eventos:

 CPU 0 CPU 1 CPU 2 ----------------- ------------------------- -------- ------- 1. rcu_read_lock () 2. ingresa sincronizar_rcu () 3. rcu_read_lock () 4. rcu_read_unlock () 5. sale de synchronize_rcu () 6. rcu_read_unlock ()

Dado que synchronize_rcues la API la que debe averiguar cuándo terminan los lectores, su implementación es clave para RCU. Para que RCU sea útil en todas las situaciones, excepto en las más intensivas en lectura, synchronize_rcula sobrecarga también debe ser bastante pequeña.

Alternativamente, en lugar de bloquear, synchronize_rcu puede registrar una devolución de llamada para ser invocada después de que se hayan completado todas las secciones críticas del lado de lectura de RCU en curso. Esta variante de devolución de llamada se llama call_rcuen el kernel de Linux.

• rcu_assign_pointer (): El actualizador utiliza esta función para asignar un nuevo valor a un puntero protegido por RCU, con el fin de comunicar de forma segura el cambio de valor del actualizador al lector. Esta función devuelve el nuevo valor y también ejecuta las instrucciones de barrera de memoria necesarias para una arquitectura de CPU determinada. Quizás lo más importante es que sirve para documentar qué punteros están protegidos por RCU.
• rcu_dereference (): el lector usa rcu_dereferencepara buscar un puntero protegido por RCU, que devuelve un valor que luego puede desreferenciarse de manera segura. También ejecuta cualquier directiva requerida por el compilador o la CPU, por ejemplo, una conversión volátil para gcc, una carga memory_order_consume para C / C ++ 11 o la instrucción de barrera de memoria requerida por la antigua CPU DEC Alpha. El valor devuelto por rcu_dereferencees válido solo dentro de la sección crítica del lado de lectura de la RCU adjunta. Al igual que con rcu_assign_pointer, una función importante de rcu_dereferencees documentar qué punteros están protegidos por RCU.

Comunicaciones de la API de RCU entre el lector, el actualizador y el recuperador

El diagrama de la derecha muestra cómo se comunica cada API entre el lector, el actualizador y el recuperador.

La infraestructura RCU observa la secuencia de tiempo de rcu_read_lock, rcu_read_unlock, synchronize_rcu, y call_rcuinvocaciones a fin de determinar cuando (1) synchronize_rcuinvocaciones pueden volver a sus llamantes y (2) call_rculas devoluciones de llamada pueden ser invocado. Las implementaciones eficientes de la infraestructura RCU hacen un uso intensivo del procesamiento por lotes para amortizar su sobrecarga en muchos usos de las API correspondientes.

Implementación simple

RCU tiene implementaciones de "juguete" extremadamente simples que pueden ayudar a comprender RCU. Esta sección presenta una implementación de "juguete" de este tipo que funciona en un entorno no preventivo . ^[19]

void  rcu_read_lock ( void )  {  }void  rcu_read_unlock ( void )  {  }void  call_rcu ( void  ( * callback )  ( void  * ),  void  * arg ) {  // agregar par callback / arg a una lista }vacío  sincronizar_rcu ( vacío ) {  int  CPU ,  ncpus  =  0 ; para  cada_cpu ( cpu )  schedule_current_task_to ( cpu ); para  cada  entrada  en  la  lista call_rcu  entrada -> devolución de llamada ( entrada -> arg ); }  

En el ejemplo de código, rcu_assign_pointery rcu_dereferencese puede ignorar sin perder mucho. Sin embargo, son necesarios para suprimir la optimización dañina del compilador y evitar que las CPU reordenen los accesos.

#define rcu_assign_pointer (p, v) ({\  smp_wmb (); / * Ordenar escrituras anteriores. * / \  ACCESS_ONCE (p) = (v); \ })#define rcu_dereference (p) ({\  typeof (p) _value = ACCESS_ONCE (p); \  smp_read_barrier_depends (); / * nop en la mayoría de las arquitecturas * / \  (_value); \ })

Tenga en cuenta eso rcu_read_locky rcu_read_unlockno haga nada. Ésta es la gran fortaleza de la RCU clásica en un kernel no preventivo: la sobrecarga del lado de lectura es precisamente cero, al igual smp_read_barrier_depends()que una macro vacía en todas las CPUs excepto DEC Alpha ; ^{[20] [ verificación fallida ]} tales barreras de memoria no son necesarias en las CPU modernas. La ACCESS_ONCE()macro es una conversión volátil que no genera código adicional en la mayoría de los casos. Y no hay forma de que rcu_read_lockpueda participar en un ciclo de interbloqueo , hacer que un proceso en tiempo real no cumpla con su fecha límite de programación, precipitar la inversión de prioridad o dar como resultado una alta contención de bloqueo.. Sin embargo, en esta implementación de RCU de juguete, el bloqueo dentro de una sección crítica del lado de lectura de RCU es ilegal, al igual que bloquear mientras se mantiene un spinlock puro.

La implementación de synchronize_rcumueve el llamador de synchronize_cpu a cada CPU, bloqueando así hasta que todas las CPU hayan podido realizar el cambio de contexto. Recuerde que este es un entorno no preventivo y que el bloqueo dentro de una sección crítica del lado de lectura de RCU es ilegal, lo que implica que no puede haber puntos de preferencia dentro de una sección crítica del lado de lectura de RCU. Por lo tanto, si una CPU determinada ejecuta un cambio de contexto (para programar otro proceso), sabemos que esta CPU debe haber completado todas las secciones críticas anteriores del lado de lectura de la RCU. Una vez que todas las CPU hayan ejecutado un cambio de contexto, se habrán completado todas las secciones críticas anteriores del lado de lectura de la RCU.

Analogía con bloqueo de lector-escritor

Aunque RCU se puede usar de muchas formas diferentes, un uso muy común de RCU es análogo al bloqueo de lector-escritor. La siguiente pantalla de código lado a lado muestra cuán estrechamente relacionados pueden estar el bloqueo de lector-escritor y RCU. ^[21]

 / * bloqueo de lector-escritor * /  / * RCU * / 1  estructura  el  {  1  estructura  el  {  2  estructura  list_head  lp ;  2  struct  list_head  lp ;  3  teclas largas  ; 3 teclas largas ; 4 spinlock_t mutex ; 4 spinlock_t mutex ; 5 datos int ; 5 datos int ; 6 / * Otros campos de datos * / 6 / * Otros campos de datos * / 7 }; 7 }; 8                         DEFINE_RWLOCK ( listmutex );  8  DEFINE_SPINLOCK ( listmutex );  9  LIST_HEAD ( cabeza );  9  LIST_HEAD ( cabeza ); 1  búsqueda int  ( tecla larga , int * resultado ) 1 búsqueda int ( tecla larga , int * resultado ) 2 { 2 { 3 struct el * p ; 3 estructura el * p ; 4 4 5 read_lock ( & listmutex ); 5 rcu_read_lock (); 6 list_for_each_entry ( p ,                              & head ,  lp )  {  6  list_for_each_entry_rcu ( p ,  & head ,  lp )  {  7  if  ( p -> key  ==  key )  {  7  if  ( p -> key  ==  key )  {  8  * result  =  p -> data ;  8  * resultado  =  p -> datos ; 9 read_unlock (  & listmutex );  9  rcu_read_unlock (); 10  devuelve  1 ;  10  devuelve  1 ; 11  }  11  } 12  }  12  } 13  read_unlock ( & listmutex );  13  rcu_read_unlock (); 14  return  0 ;  14  return  0 ; 15  }  15  } 1  int  borrar ( tecla larga  ) 1 int borrar ( tecla larga ) 2 { 2 { 3 struct el * p ; 3 estructura el * p ; 4 4 5 write_lock ( & listmutex ); 5 spin_lock ( & listmutex ); 6 list_for_each_entry ( p , & head , lp )                           {  6  list_for_each_entry ( p ,  & head ,  lp )  {  7  if  ( p -> key  ==  key )  {  7  if  ( p -> key  ==  key )  { 8 list_del ( & p -> lp ); 8 list_del_rcu ( & p -> lp ); 9 write_unlock ( & listmutex ); 9        spin_unlock ( & listmutex ); 10 sincronizar_rcu (); 10 k libre ( p ); 11 k libre ( p ); 11 retorno 1 ; 12 retorno 1 ; 12 } 13 } 13 } 14 } 14 write_unlock ( & listmutex ); 15 spin_unlock ( & listmutex ); 15 return 0 ; 16 volver 0                        ; 16  }  17  }

Las diferencias entre los dos enfoques son bastante pequeñas. El bloqueo del lado de lectura se mueve hacia rcu_read_locky rcu_read_unlock, el bloqueo del lado de actualización se mueve de un bloqueo de lector-escritor a un bloqueo de giro simple, y a synchronize_rcuprecede al kfree.

Sin embargo, hay un problema potencial: las secciones críticas del lado de la lectura y del lado de la actualización ahora pueden ejecutarse al mismo tiempo. En muchos casos, esto no será un problema, pero es necesario verificarlo con cuidado independientemente. Por ejemplo, si varias actualizaciones de listas independientes deben verse como una única actualización atómica, la conversión a RCU requerirá un cuidado especial.

Además, la presencia de synchronize_rcusignifica que la versión RCU de deleteahora puede bloquear. Si esto es un problema, call_rcupodría usarse como call_rcu (kfree, p)en lugar de synchronize_rcu. Esto es especialmente útil en combinación con el recuento de referencias.

Historia

Esta sección está en formato de lista , pero puede leerse mejor en prosa . Puede ayudar convirtiendo esta sección , si corresponde. La ayuda de edición está disponible. ( Mayo de 2014 )

Varias veces se han inventado de forma independiente técnicas y mecanismos que se asemejan a RCU: ^[22]

1. HT Kung y Q. Lehman describieron el uso de recolectores de basura para implementar un acceso similar a RCU a un árbol de búsqueda binario. ^[23]
2. Udi Manber y Richard Ladner ampliaron el trabajo de Kung y Lehman a entornos sin recolección de basura al aplazar la recuperación hasta que todos los subprocesos que se ejecutan en el momento de la eliminación hayan terminado, lo que funciona en entornos que no tienen subprocesos de larga duración. ^[24]
3. Richard Rashid y col. describió una implementación de búfer de búsqueda lenta de traducción (TLB) que aplazó la recuperación del espacio de direcciones virtuales hasta que todas las CPU vaciaron su TLB, que es similar en espíritu a algunas implementaciones de RCU. ^[25]
4. A James P. Hennessy, Damian L. Osisek y Joseph W. Seigh, II se les concedió la patente de EE.UU. 4.809.168 en 1989 (ya que caducó). Esta patente describe un mecanismo similar a RCU que aparentemente se usó en VM / XA en mainframes IBM . ^[26]
5. William Pugh describió un mecanismo similar a RCU que se basaba en el establecimiento explícito de banderas por parte de los lectores. ^[27]
6. Aju John propuso una implementación similar a RCU donde los actualizadores simplemente esperan un período de tiempo fijo, bajo el supuesto de que todos los lectores completarían dentro de ese tiempo fijo, como podría ser apropiado en un sistema de tiempo real duro. ^[28] Van Jacobson propuso un esquema similar en 1993 (comunicación verbal).
7. J. Slingwine y PE McKenney recibieron la patente de EE.UU. 5.442.758 en agosto de 1995, que describe RCU como implementado en DYNIX / ptx y posteriormente en el kernel de Linux. ^[29]
8. B. Gamsa, O. Krieger, J. Appavoo y M. Stumm describieron un mecanismo similar a RCU utilizado en el sistema operativo de investigación Tornado de la Universidad de Toronto y los sistemas operativos de investigación IBM Research K42 estrechamente relacionados . ^[30]
9. Rusty Russell y Phil Rumpf describieron técnicas similares a RCU para manejar la descarga de módulos del kernel de Linux. ^{[31] [32]}
10. D. Sarma agregó RCU a la versión 2.5.43 del kernel de Linux en octubre de 2002.
11. Robert Colvin y col. verificado formalmente un algoritmo de conjunto basado en listas concurrentes perezosas que se asemeja a RCU. ^[33]
12. M. Desnoyers y col. publicó una descripción de la RCU del espacio de usuario. ^{[34] [35]}
13. A. Gotsman y col. semántica formal derivada para RCU basada en la lógica de separación. ^[36]
14. Ilan Frenkel, Roman Geller, Yoram Ramberg y Yoram Snir obtuvieron la patente estadounidense 7.099.932 en 2006. Esta patente describe un mecanismo similar a RCU para recuperar y almacenar información de gestión de políticas de calidad de servicio utilizando un servicio de directorio de una manera que refuerza la lectura / escritura. consistencia y habilita la concurrencia de lectura / escritura. ^[37]

Ver también

• Control de concurrencia
• Copiar en escrito
• Lock (ingeniería de software)
• Algoritmos sin bloqueo y sin espera
• Control de concurrencia multiversion
• Multi tareas preventivo
• Computación en tiempo real
• Contención de recursos
• Hambre de recursos
• Sincronización

Notas

1. Solo se deben considerar los lectores que están activos durante la fase de eliminación, ya que cualquier lector que comience después de la fase de eliminación no podrá obtener una referencia a los elementos de datos eliminados y, por lo tanto, la fase de recuperación no podrá interrumpirlos.
2. Se pueden utilizar recolectores de basura , cuando estén disponibles, para realizar este paso.
3. Los puntos muertos basados ​​en RCU todavía son posibles, por ejemplo, ejecutando una instrucción que se bloquea hasta que se completa un período de gracia dentro de una sección crítica del lado de lectura de RCU.

Referencias

1. Tanenbaum, Andrew (2015). Sistemas operativos modernos (4ª ed.). Estados Unidos: Pearson. pag. 148. ISBN 9781292061429.
2. Guniguntala, Dinakar; McKenney, Paul E .; Triplett, Joshua; Walpole, Jonathan (abril-junio de 2008). "El mecanismo de lectura-copia-actualización para soportar aplicaciones en tiempo real en sistemas multiprocesador de memoria compartida con Linux". Revista de sistemas de IBM . 47 (2): 221-236. doi : 10.1147 / sj.472.0221 .
3. McKenney, Paul E .; Walpole, Jonathan (17 de diciembre de 2007). "¿Qué es RCU, fundamentalmente?" . Noticias semanales de Linux . Consultado el 24 de septiembre de 2010 .
4. McKenney, Paul E .; Slingwine, John D. (octubre de 1998). Actualización de lectura y copia: uso del historial de ejecución para resolver problemas de simultaneidad (PDF) . Computación y sistemas paralelos y distribuidos . págs. 509–518.
5. McKenney, Paul E .; Walpole, Jonathan (julio de 2008). "Introducción de tecnología en el kernel de Linux: un caso de estudio". SIGOPS Oper. Syst. Rev . 42 (5): 4–17. doi : 10.1145 / 1400097.1400099 .
6. Olsson, Robert; Nilsson, Stefan (mayo de 2007). BASURA: Una estructura dinámica de tabla hash y LC-trie . Taller de Conmutación y Enrutamiento de Alto Rendimiento (HPSR'07) . doi : 10.1109 / HPSR.2007.4281239 .
7. Piggin, Nick (julio de 2006). Un Pagecache sin bloqueo en Linux --- Introducción, progreso, rendimiento . Simposio de Ottawa Linux .
8. "Paul E. McKenney: uso de RCU Linux" .
9. Kannan, Hari (2009). "Ordenar accesos a metadatos desacoplados en multiprocesadores". Actas del 42º Simposio Internacional Anual IEEE / ACM sobre Microarquitectura - Micro-42 . pag. 381. doi : 10.1145 / 1669112.1669161 . ISBN 978-1-60558-798-1.
10. Matthews, Chris; Coady, Yvonne; Appavoo, Jonathan (2009). Eventos de portabilidad: un modelo de programación para infraestructuras de sistemas escalables . PLOS '06: Actas del III Taller de Lenguajes de Programación y Sistemas Operativos . San José, CA, Estados Unidos. doi : 10.1145 / 1215995.1216006 . ISBN 978-1-59593-577-9.
11. Da Silva, Dilma ; Krieger, Orran; Wisniewski, Robert W .; Waterland, Amos; Tam, David; Baumann, Andrew (abril de 2006). "K42: una infraestructura para la investigación de sistemas operativos". SIGOPS Oper. Syst. Rev . 40 (2): 34–42. doi : 10.1145 / 1131322.1131333 .
12. Appavoo, Jonathan; Da Silva, Dilma; Krieger, Orran; Auslander, Mark; Ostrowski, Michal; Rosenburg, Bryan; Waterland, Amos; Wisniewski, Robert W .; Xenidis, Jimi (agosto de 2007). "Experiencia distribuyendo objetos en un SO SMMP". Transacciones ACM en sistemas informáticos . 25 (3): 6 / 1–6 / 52. doi : 10.1145 / 1275517.1275518 .
13. Fraser, Keir; Harris, Tim (2007). "Programación concurrente sin cerraduras". Transacciones ACM en sistemas informáticos . 25 (2): 34–42. CiteSeerX 10.1.1.532.5050 . doi : 10.1145 / 1233307.1233309 . 
14. Porter, Donald E .; Hofmann, Owen S .; Rossbach, Christopher J .; Benn, Alexander; Witchel, Emmett (2009). "Transacciones de sistemas operativos". Actas del 22º simposio de ACM SIGOPS sobre principios de sistemas operativos - SOSP '09 . pag. 161. doi : 10.1145 / 1629575.1629591 . ISBN 978-1-60558-752-3.
15. Hart, Thomas E .; McKenney, Paul E .; Demke Brown, Angela; Walpole, Jonathan (diciembre de 2007). "Rendimiento de recuperación de memoria para sincronización sin bloqueo". J. Parallel Distrib. Computación . 67 (12): 1270-1285. doi : 10.1016 / j.jpdc.2007.04.010 .
16. McKenney, Paul E. (4 de enero de 2008). "RCU parte 2: uso" . Noticias semanales de Linux . Consultado el 24 de septiembre de 2010 .
17. Desnoyers, Mathieu (diciembre de 2009). Seguimiento del sistema operativo de bajo impacto (PDF) . École Polytechnique de Montreal (Tesis).
18. McKenney, Paul E. (17 de enero de 2008). "RCU parte 3: la API de RCU" . Noticias semanales de Linux . Consultado el 24 de septiembre de 2010 .
19. McKenney, Paul E .; Appavoo, Jonathan; Kleen, Andi; Krieger, Orran; Russell, oxidado; Sarma, Dipankar; Soni, Maneesh (julio de 2001). Actualización de lectura y copia (PDF) . Simposio de Ottawa Linux .
20. Asistente, el (agosto de 2001). "Memoria compartida, subprocesos, comunicación entre procesos" . Hewlett-Packard . Consultado el 26 de diciembre de 2010 .
21. McKenney, Paul E. (octubre de 2003). "Usando {RCU} en el kernel de {Linux} 2.5" . Diario de Linux . Consultado el 24 de septiembre de 2010 .
22. McKenney, Paul E. (julio de 2004). Explotación de la destrucción diferida: un análisis de las técnicas de lectura, copia y actualización (PDF) . Escuela de Ciencias e Ingeniería OGI de la Universidad de Ciencias y Salud de Oregon (Tesis).
23. Kung, HT; Lehman, Q. (septiembre de 1980). "Mantenimiento concurrente de árboles de búsqueda binaria". Transacciones ACM en sistemas de bases de datos . 5 (3): 354. CiteSeerX 10.1.1.639.8357 . doi : 10.1145 / 320613.320619 . 
24. Manber, Udi; Ladner, Richard E. (septiembre de 1984). "Control de concurrencia en una estructura de búsqueda dinámica". Transacciones ACM en sistemas de bases de datos . 9 (3).
25. Rashid, Richard; Tevanian, Avadis; Joven, Michael; Golub, David; Baron, Robert; Bolosky, William; Chew, Jonathan (octubre de 1987). Administración de memoria virtual independiente de la máquina para arquitecturas de multiprocesador y monoprocesador paginado (PDF) . Segundo Simposio de Soporte Arquitectónico para Lenguajes de Programación y Sistemas Operativos . Asociación para Maquinaria de Computación.
26. US 4809168 , "Serialización pasiva en un entorno multitarea" 
27. Pugh, William (junio de 1990). Mantenimiento concurrente de listas de omisión (informe técnico). Instituto de Estudios Avanzados de Ciencias de la Computación, Departamento de Ciencias de la Computación, Universidad de Maryland. CS-TR-2222.1.
28. John, Aju (enero de 1995). Vnodes dinámicos: diseño e implementación . USENIX Invierno de 1995 .
29. US 5442758 , "Aparato y método para lograr la exclusión mutua de gastos indirectos reducidos y mantener la coherencia en un sistema multiprocesador" 
30. Gamsa, Ben; Krieger, Orran; Appavoo, Jonathan; Stumm, Michael (febrero de 1999). Tornado: maximización de la ubicación y la simultaneidad en un sistema operativo multiprocesador de memoria compartida (PDF) . Actas del Tercer Simposio sobre Diseño e Implementación de Sistemas Operativos .
31. Russell, Rusty (junio de 2000). "Re: controladores de red modular" .
32. Russell, Rusty (junio de 2000). "Re: controladores de red modular" .
33. Colvin, Robert; Groves, Lindsay; Luchangco, Victor; Moir, Mark (agosto de 2006). Verificación formal de un algoritmo de conjunto basado en listas concurrentes perezosas (PDF) . Verificación asistida por computadora . Archivado desde el original (PDF) el 17 de julio de 2009.
34. Desnoyers, Mathieu; McKenney, Paul E .; Stern, Alan; Dagenais, Michel R .; Walpole, Jonathan (febrero de 2012). Implementaciones a nivel de usuario de la actualización de lectura y copia (PDF) . Transacciones IEEE en sistemas paralelos y distribuidos . doi : 10.1109 / TPDS.2011.159 .
35. McKenney, Paul E .; Desnoyers, Mathieu; Jiangshan, Lai (13 de noviembre de 2013). "Espacio de usuario RCU" . Noticias semanales de Linux . Consultado el 17 de noviembre de 2013 .
36. Gotsman, Alexey; Rinetzky, Noam; Yang, Hongseok (16 al 24 de marzo de 2013). Verificación de algoritmos de recuperación de memoria concurrente con gracia (PDF) . ESOP'13: Simposio Europeo de Programación .
37. US 7099932 , Frenkel, Ilan; Geller, Roman & Ramberg, Yoram et al., "Método y aparato para recuperar información de política de calidad de servicio de red de un directorio en un sistema de gestión de política de calidad de servicio", publicado el 29 de agosto de 2006, asignado a Cisco Tech Inc.  

Bauer, RT, (junio de 2009), "Verificación operativa de un programa relativista" Informe técnico de la PSU TR-09-04 ( http://www.pdx.edu/sites/www.pdx.edu.computer-science/files/ tr0904.pdf )

enlaces externos

• Paul E. McKenney, Mathieu Desnoyers y Lai Jiangshan: UCR del espacio de usuario . Noticias semanales de Linux .
• Paul E. McKenney y Jonathan Walpole: ¿Qué es RCU, fundamentalmente? , ¿Qué es RCU? Parte 2: uso y RCU parte 3: la API de RCU . Noticias semanales de Linux .
• Página web de la RCU de Paul E. McKenney
• Hart, McKenney y Demke Brown (2006). Cómo acelerar la sincronización sin bloqueo: Implicaciones de rendimiento de la recuperación de memoria Un mejor artículo de IPDPS 2006 que compara el rendimiento de RCU con el de otros mecanismos de sincronización sin bloqueo. Versión de la revista (incluido Walpole como autor).
• Patente de Estados Unidos 5.442.758 (1995) "Aparato y método para lograr una exclusión mutua de gastos indirectos reducidos y mantener la coherencia en un sistema multiprocesador que utiliza el historial de ejecución y la supervisión de subprocesos"
• Paul McKenney: RCU para dormir . Noticias semanales de Linux .