🪴 Quartz 4.0

RCU

5 min read

RCU（Read-Copy-Update）是一种用于多线程环境中的同步机制，特别适用于读多写少的场景。RCU 的设计目的是为了提高读操作的性能，同时保证数据的一致性和完整性。下面是关于 RCU 的详细介绍：

基本概念

  1. 读多写少：RCU 最适合应用于读操作远多于写操作的场景。例如，文件系统的目录结构、网络路由表等。
  2. 非阻塞性读：在 RCU 中，读操作是非阻塞的，这意味着读操作不会因为写操作而被阻塞。读操作可以随时进行，而不会影响其他读操作的性能。
  3. 延迟更新：写操作（更新）不会立即修改数据结构，而是先创建一个新的副本，然后更新指针指向新的副本。旧的数据结构会在所有活跃的读操作完成后才被回收。

工作原理

  1. 读路径：

    • 读操作直接访问数据结构，无需获取任何锁。
    • 读操作假设数据结构在整个读操作期间不会发生变化。

  2. 写路径：

    • 写操作首先创建一个新的数据结构副本。
    • 更新指针，使新的数据结构生效。
    • 等待所有活跃的读操作完成，确保没有读操作还在使用旧的数据结构。
    • 回收旧的数据结构。

关键技术

  1. 版本号：

    • 每个读操作都会记录一个版本号。
    • 写操作完成后，会增加版本号。
    • 读操作在完成时会检查版本号，确保没有错过任何更新。

  2. 栅栏（Fence）：

    • 栅栏机制用于确保所有活跃的读操作都已完成。
    • 写操作完成后，会插入一个栅栏，等待所有活跃的读操作通过栅栏。

  3. 回调机制：

    • 写操作完成后，可以注册一个回调函数，该函数在所有活跃的读操作完成后被调用。
    • 回调函数通常用于回收旧的数据结构。

示例

假设有一个简单的链表结构，我们使用 RCU 来管理这个链表：

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <urcu.h>
 
struct Node {
    int value;
    struct Node *next;
};
 
struct Node *head = NULL;
 
void insert_node(int value) {
    struct Node *new_node = malloc(sizeof(struct Node));
    new_node->value = value;
    new_node->next = head;
 
    // 使用 RCU 保护写操作
    rcu_read_lock();
    head = new_node;
    rcu_read_unlock();
 
    // 注册回调函数，用于回收旧的头节点
    call_rcu(&old_head->rcu_head, free_node);
}
 
void free_node(struct rcu_head *head) {
    struct Node *node = container_of(head, struct Node, rcu_head);
    free(node);
}
 
void read_list() {
    struct Node *node;
 
    // 使用 RCU 保护读操作
    rcu_read_lock();
    for (node = head; node != NULL; node = node->next) {
        printf("%d ", node->value);
    }
    rcu_read_unlock();
}

优点

  1. 高性能读操作：读操作完全无锁，不会因为写操作而被阻塞。
  2. 低延迟：由于读操作不受写操作的影响，系统的整体延迟较低。
  3. 可扩展性：RCU 适用于大规模并发系统，可以有效提升系统的吞吐量。

缺点

  1. 内存开销：需要额外的内存来存储旧的数据结构副本。
  2. 复杂性：实现和调试 RCU 比较复杂，需要仔细管理版本号和回调函数。
  3. 延迟回收：旧的数据结构需要等待所有活跃的读操作完成后才能被回收，可能会导致内存暂时占用较高。

应用场景

RCU 广泛应用于操作系统内核、文件系统、网络协议栈等领域，特别是在读多写少的场景中表现出色。例如，Linux 内核中大量使用 RCU 来管理数据结构。

Graph View