En informática , lectura-copia-actualización ( RCU ) es un mecanismo de sincronización que evita el uso de primitivas de bloqueo mientras múltiples subprocesos leen y actualizan simultáneamente elementos que están vinculados a través de punteros y que pertenecen a estructuras de datos compartidas (p. ej., 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, desreferenciación de punteros nulos ). [1]
Se utiliza cuando el rendimiento de las lecturas es crucial y es un ejemplo de compensación espacio-tiempo , que permite operaciones rápidas a costa de más espacio. Esto hace que todos los lectores procedan como si no hubiera sincronización involucrada, por lo que serán rápidos, pero también dificultarán las actualizaciones.
El nombre proviene de la forma en que se utiliza RCU para actualizar una estructura vinculada en su lugar. Un hilo que desee hacer esto utiliza los siguientes pasos:
Por lo tanto, la estructura se lee simultáneamente con la copia de un hilo para realizar una actualización , de ahí el nombre "actualización de lectura y 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 aplazamiento de MP por parte de programadores VM/XA y generaciones de programadores K42 y Tornado.
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 estructuras vinculadas de forma segura 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 puede acceder a él en cualquier momento, lo que requiere 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 las transiciones de gptr al cuarto y último estado. En este estado, la estructura es accesible para los lectores y, por tanto, está coloreada en rojo. La primitiva rcu_assign_pointer se utiliza para llevar a cabo esta asignación y garantiza que la asignación sea atómica en el sentido de que los lectores simultáneos 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.
Este procedimiento demuestra cómo se pueden insertar nuevos datos en una estructura de datos vinculada incluso aunque los lectores estén recorriendo 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.
El primer estado muestra una lista vinculada que contiene los 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 vínculo del elemento B al C se deja intacto para permitir a los lectores que actualmente hacen referencia al elemento B recorrer 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 con el formato correcto. El elemento B ahora está coloreado en 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 espera de lectores solo necesita esperar a los lectores preexistentes, pero no a los lectores 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 el elemento B. En otras palabras, RCU proporciona coordinación tanto en el espacio (diferentes versiones de la lista) como en el tiempo (diferentes estados en los procedimientos de eliminación). Esto contrasta marcadamente 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 datos antiguos de una estructura de datos vinculada incluso aunque los lectores estén recorriendo 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 de reposo. Cualquier período de tiempo durante el cual cada subproceso reside al menos una vez en estado inactivo se denomina período de gracia . Por definición, cualquier sección crítica 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, lo 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 gastos generales del lado de lectura extremadamente pequeños; de hecho, en el caso límite que realmente se logra mediante compilaciones del kernel de Linux de clase servidor, el costo adicional 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 referencias a elementos de datos dentro de una estructura de datos (posiblemente reemplazándolas 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 nueva de la estructura de datos en lugar de una referencia parcialmente actualizada. Una vez transcurrido el 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 posponer la fase de recuperación hasta que todos los lectores activos durante la fase de eliminación hayan completado, 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]
En el procedimiento anterior (que coincide con el diagrama anterior), el actualizador realiza tanto el paso de eliminación como el de recuperación, pero a menudo es útil que un subproceso completamente diferente realice la recuperación. El recuento de referencias se puede utilizar para permitir que el lector realice la eliminación, de modo 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.
RCU es quizás el algoritmo sin bloqueo más común para una estructura de datos compartida. RCU no requiere ninguna espera para cualquier número de lectores. Las implementaciones de RCU de un solo escritor también están libres de bloqueos para el escritor. [5] Algunas implementaciones de RCU con múltiples escritores no tienen bloqueos. [6] Otras implementaciones de múltiples escritores de RCU serializan escritores con un bloqueo. [7]
A principios de 2008, había casi 2.000 usos de la API RCU dentro del kernel de Linux [8], incluidas las pilas de protocolos de red [9] y el sistema de gestión de memoria. [10] En marzo de 2014 [actualizar], había más de 9.000 usos. [11] 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, [12] la gestión de la vida útil de los objetos agrupados, [13] la gestión de la vida útil de los objetos en el sistema operativo de investigación K42 , [14] [15] y optimización de implementaciones de memoria transaccional de software . [16] [17] Dragonfly BSD utiliza una técnica similar a RCU que se parece más a la implementación Sleepable RCU (SRCU) de Linux.
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, ninguna sincronización en absoluto. Por el contrario, en esquemas basados en bloqueos más convencionales, los lectores deben utilizar una sincronización intensa para evitar que un actualizador borre la estructura de datos que se encuentra debajo de ellos. La razón es que los actualizadores basados en bloqueos generalmente actualizan los datos en el lugar y, por lo tanto, deben excluir a los lectores. Por el contrario, los actualizadores basados en RCU generalmente aprovechan el hecho de que las escrituras en punteros alineados únicos 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 RCU simultáneos pueden continuar accediendo a las versiones antiguas y prescindir de las instrucciones atómicas de lectura, modificación y escritura, barreras de memoria y errores de caché que son tan costosos en los sistemas informáticos SMP modernos, incluso en ausencia de contención de bloqueo. [18] [19] La naturaleza liviana de las primitivas del lado de lectura de RCU proporciona ventajas adicionales más allá del excelente rendimiento, escalabilidad y respuesta en tiempo real. Por ejemplo, brindan inmunidad a la mayoría de las condiciones de bloqueo 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 mayoritariamente lecturas y pocas actualizaciones, pero suele ser 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 simultáneamente es lo que permite la naturaleza liviana de las primitivas del lado de lectura de RCU, algunos algoritmos pueden no ser compatibles con 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.
La técnica está cubierta por la patente de software estadounidense 5.442.758 , expedida el 15 de agosto de 1995 y asignada a Sequent Computer Systems , así como por la patente estadounidense 5.608.893 (expirada el 30 de marzo de 2009), la patente estadounidense 5.727.209 (expirada el 30 de marzo de 2010) 05), la patente de EE. UU. 6.219.690 (expirada el 18 de mayo de 2009) y la patente de EE. UU. 6.886.162 (expirada el 25 de mayo de 2009). La patente estadounidense 4.809.168, ahora vencida, cubre una técnica estrechamente relacionada. RCU es también el tema de un reclamo en la demanda SCO v. IBM .
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. [20]
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 principal ( interfaz de programación de aplicaciones ) es bastante pequeña: [21]
synchronize_rcuno necesariamente esperará a que se completen las secciones críticas posteriores del lado de lectura de la RCU. 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 sincronizar_rcu() 6.rcu_read_unlock()
synchronize_rcues la API la que debe determinar cuándo terminan los lectores, su implementación es clave para RCU. Para que RCU sea útil en todas las situaciones, excepto en las de lectura más intensiva, la synchronize_rcusobrecarga de 's también debe ser bastante pequeña.call_rcuen el kernel de Linux.rcu_dereferencepara recuperar un puntero protegido por RCU, que devuelve un valor que luego se puede desreferenciar de forma segura. También ejecuta cualquier directiva requerida por el compilador o la CPU, por ejemplo, una conversión volátil para gcc, una carga de memoria_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.
El diagrama de la derecha muestra cómo se comunica cada API entre el lector, el actualizador y el recuperador.
La infraestructura de RCU observa la secuencia de tiempo de rcu_read_lock, rcu_read_unlock, synchronize_rcuy call_rculas invocaciones para determinar cuándo (1) synchronize_rculas invocaciones pueden regresar a sus llamantes y (2) call_rcuse pueden invocar las devoluciones de llamada. Las implementaciones eficientes de la infraestructura RCU hacen un uso intensivo del procesamiento por lotes para amortizar sus gastos generales en muchos usos de las API correspondientes.
RCU tiene implementaciones de "juguete" extremadamente simples que pueden ayudar a comprender RCU. Esta sección presenta una de esas implementaciones de "juguete" que funciona en un entorno no preventivo . [22]
vacío rcu_read_lock ( vacío ) { } vacío rcu_read_unlock ( vacío ) { } void call_rcu ( void ( * devolución de llamada ) ( void * ), void * arg ) { // agregar par de devolución de llamada/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_pointerse rcu_dereferencepuede 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. Esta 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 CPU excepto en DEC Alpha ; [23] [ 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 resultar en 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 la RCU es ilegal, al igual que el bloqueo mientras se mantiene un bloqueo de giro puro.
La implementación de synchronize_rcumueve la persona que llama de sincronizar_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 la 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 la 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 del lado de lectura de la RCU anteriores. Una vez que todas las CPU hayan ejecutado un cambio de contexto, se habrán completado todas las secciones críticas del lado de lectura de la RCU anteriores.
Aunque RCU se puede utilizar de muchas maneras diferentes, un uso muy común de RCU es análogo al bloqueo de lector-escritor. La siguiente visualización de códigos en paralelo muestra cuán estrechamente relacionados pueden estar el bloqueo del lector-escritor y la RCU. [24]
/* bloqueo lector-escritor */ /* RCU */ 1 estructura el { 1 estructura el { 2 estructura list_head lp ; 2 estructura list_head lp ; 3 teclas largas ; 3 teclas largas ; 4 exclusión mutua spinlock_t ; 4 exclusión mutua spinlock_t ; 5 datos enteros ; 5 datos enteros ; 6 /* Otros campos de datos */ 6 /* Otros campos de datos */ 7 }; 7 }; 8 DEFINE_RWLOCK ( listamutex ); 8 DEFINE_SPINLOCK ( listamutex ); 9 LIST_HEAD ( cabeza ); 9 LIST_HEAD ( cabeza ); 1 búsqueda int ( clave larga , int * resultado ) 1 búsqueda int ( clave larga , int * resultado ) 2 { 2 { 3 struct el * p ; 3 estructura el * p ; 4 4 5 lectura_bloqueo ( & 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 -> clave == clave ) { 7 if ( p -> clave == clave ) { 8 * resultado = p -> datos ; 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 devuelve 0 ; 14 devuelve 0 ; 15 } 15 } 1 int eliminar ( tecla larga ) 1 int eliminar ( 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 -> clave == clave ) { 7 if ( p -> clave == clave ) { 8 list_del ( & p- > lp ); 8 list_del_rcu ( & p- > lp ); 9 write_unlock ( & listmutex ); 9 spin_unlock ( & listmutex ); 10 sincronizar_rcu (); 10 k gratis ( p ); 11 k gratis ( p ); 11 devolver 1 ; 12 retorno 1 ; 12 } 13 } 13 } 14 } 14 write_unlock ( & listmutex ); 15 spin_unlock ( & listmutex ); 15 devuelve 0 ; 16 devuelve 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, existe un problema potencial: las secciones críticas del lado de lectura y del lado de actualización ahora pueden ejecutarse simultáneamente. En muchos casos, esto no será un problema, pero de todos modos es necesario comprobarlo cuidadosamente. Por ejemplo, si varias actualizaciones de listas independientes deben verse como una única actualización atómica, la conversión a RCU requerirá especial cuidado.
Además, la presencia de synchronize_rcusignifica que la versión RCU 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.
Las técnicas y mecanismos que se asemejan a la RCU se han inventado de forma independiente varias veces: [25]
{{cite conference}}: Enlace externo en |journal=Bauer, RT, (junio de 2009), "Verificación operativa de un programa relativista" PSU Tech Report TR-09-04 (http://www.pdx.edu/sites/www.pdx.edu.computer-science/files/ tr0904.pdf)