Read-copy-update

In computer science, read-copy-update (RCU) is a synchronization mechanism that avoids the use of lock primitives while multiple threads concurrently read and update elements that are linked through pointers and that belong to shared data structures (e.g., linked lists, trees, hash tables). Whenever a thread is inserting or deleting elements of data structures in shared memory, all readers are guaranteed to see and traverse either the older or the new structure, therefore avoiding inconsistencies (e.g., dereferencing null pointers). It is used when performance of reads is crucial and is an example of space–time tradeoff, enabling fast operations at the cost of more space. This makes all readers proceed as if there were no synchronization involved, hence they will be fast, but also making updates more difficult. The name comes from the way that RCU is used to update a linked structure in place. A thread wishing to do this uses the following steps: create a new structure, copy the data from the old structure into the new one, and save a pointer to the old structure, modify the new, copied, structure, update the global pointer to refer to the new structure, sleep until the operating system kernel determines that there are no readers left using the old structure, for example, in the Linux kernel, by using , once awakened by the kernel, deallocate the old structure. So the structure is read concurrently with a thread copying in order to do an update, hence the name "read-copy update". The abbreviation "RCU" was one of many contributions by the Linux community. Other names for similar techniques include passive serialization and MP defer by VM/XA programmers and generations by K42 and Tornado programmers. A key property of RCU is that readers can access a data structure even when it is in the process of being updated: RCU updaters cannot block readers or force them to retry their accesses. This overview starts by showing how data can be safely inserted into and deleted from linked structures despite concurrent readers.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (5)

Cours associés (2)

Séances de cours associées (32)

CS-307: Introduction to multiprocessor architecture

Multiprocessors are a core component in all types of computing infrastructure, from phones to datacenters. This course will build on the prerequisites of processor design and concurrency to introduce

CS-453: Concurrent computing

With the advent of modern architectures, it becomes crucial to master the underlying algorithmics of concurrency. The objective of this course is to study the foundations of concurrent algorithms and

Read-copy-update

Concurrency control

In information technology and computer science, especially in the fields of computer programming, operating systems, multiprocessors, and databases, concurrency control ensures that correct results for concurrent operations are generated, while getting those results as quickly as possible. Computer systems, both software and hardware, consist of modules, or components. Each component is designed to operate correctly, i.e., to obey or to meet certain consistency rules.

Verrou (informatique)

Un verrou informatique permet de s'assurer qu'une seule personne, ou un seul processus accède à une ressource à un instant donné. Ceci est souvent utilisé dans le domaine des accès à des fichiers sur des systèmes d'exploitation multi-utilisateur, car si deux programmes modifient un même fichier au même moment, le risque est de : provoquer des erreurs dans un des deux programmes, voire dans les deux ; laisser le fichier en fin de traitement dans une complète incohérence ; endommager le fichier manipulé.

Verrouillage du lecteur CS-206: Parallelism and concurrency

Introduit le verrou lecteur-auteur pour gérer la concordance dans les scénarios avec des lectures fréquentes et des mises à jour occasionnelles.

Registres et linéarisabilité CS-453: Concurrent computing

Explore la puissance des registres en linéarisabilité et introduit l'algorithme SCAN.

Synchronisation : Serrures et barrières CS-307: Introduction to multiprocessor architecture

Explore les principes de synchronisation à l'aide de verrous et de barrières, en mettant l'accent sur des implémentations matérielles efficaces et des mécanismes de coordination tels qu'OpenMP.