Data Ownership

FIXME 总体来说，这章原文写的也比较简单，引用的内容都是之前的内容。

1. 章节核心思想

Data Ownership 是避免同步开销的最简单方式之一：将数据划分给各个线程（或 CPU），使得某一块数据只被一个线程访问和修改。它同时覆盖了并行设计的”三大支柱”：

正因为其简单直观，数据所有权被广泛使用，甚至新手都会本能地使用它。本章没有引入全新示例，而是回顾前面章节的代码，从不同视角阐释数据所有权的各种形式。

2. 各节详细分析

2.1 Multiple Processes（多进程）

这是数据所有权的逻辑极端：每个线程拥有自己独立的地址空间。通过 shell 的 & 和 wait，或者 C 的 fork()/wait()，可以创建完全独立的进程。

compute_it 1 > compute_it.1.out &
compute_it 2 > compute_it.2.out &
wait
cat compute_it.1.out
cat compute_it.2.out

由于进程之间不共享内存（除非显式使用 shmget() 或 mmap()），进程内的所有数据都被该进程”所有”。这种方式几乎完全消除了同步开销，兼具极端的简单性和最优的性能。

同步残留：仅剩的同步是 shell 的 &（创建线程）和 wait（等待线程结束）。如果进程显式共享内存，则需要额外的同步机制（System V 信号量、消息队列、UNIX domain socket、文件锁等）。

代码实现：见本目录 process_ownership.c，使用 fork() 创建两个子进程，各自累加私有计数器，父进程通过 waitpid() 等待完成，无需任何锁或原子操作。

make process_ownership.out
./process_ownership.out
# 输出：
# process 1: counter = 10000000
# process 2: counter = 10000000
# parent: both children completed, no shared data needed sync

这种朴素形式的并行绝非”作弊”或”逃避责任”，而是快速、可扩展、易于编程和维护的优雅方案。开发者可以把节省下来的时间用于单线程优化，或者将复杂并行模式应用于代码中不适用此方案的部分。

2.2 Partial Data Ownership and pthreads（部分数据所有权）

在共享内存并行程序中，数据所有权可以更加细腻：线程可以读取其他线程拥有的数据，但不允许修改。第 5 章的并发计数器就大量使用了这种模式。

典型的例子是 per-thread 统计计数器：

这种模式在内核中极为常见。例如，某个 CPU 可能被允许在禁用中断时读取自己的 per-CPU 变量；另一个 CPU 只有在持有对应的 per-CPU 锁时才能读取第一个 CPU 的 per-CPU 变量；而该 CPU 自己只有在同时禁用中断并持有 per-CPU 锁时才能更新这些变量。这种安排可以看作一种 reader-writer 锁的变体，允许每个 CPU 以极低开销访问自己的变量集。

纯数据所有权同样常见且有用，例如 per-thread 内存分配器缓存（见第 5 章资源分配器缓存），每个线程的缓存完全私有。

代码实现：见 partial_ownership.c。每个线程只写自己的 counters[tid]，而 read_count() 遍历所有线程的计数器进行读取。注意这里没有使用任何锁，因为：

make partial_ownership.out
./partial_ownership.out
# 输出：
# expected total: 4000000
# read_count:     4000000

2.3 Function Shipping（函数托运）

前面一节描述的是一种弱形式的数据所有权：线程”伸出手”去访问其他线程的数据。这可以看作把数据带到需要它的函数。另一种替代方案是把函数发送到数据所在的地方。

第 5 章的信号盗窃限制计数器（Signal-Theft Limit Counter）就是一个典型例子：

这种托运函数需要与并发的 add_count()/sub_count() 交互，增加了实现复杂度，但避免了直接跨线程访问数据。

代码实现：见 function_shipping.c。主线程创建一个工作线程，该线程累加自己的私有计数器。当工作完成后，主线程通过 pthread_kill(tid, SIGUSR1) 向工作线程发送信号。信号处理函数 flush_sig_handler 在工作线程的上下文中执行，读取该线程的 thread_counter 并写回全局变量 signal_result。主线程等待 signal_received 标志后，将结果累加到 global_count。

make function_shipping.out
./function_shipping.out
# 输出：
# global_count after collection: 5000000
# function shipping demo completed

这种模式的本质是：不直接触碰别人的数据，而是请数据所有者在自己的上下文中执行操作。除了 POSIX 信号，还可以使用 System V 消息队列、共享内存邮箱、UNIX domain socket、TCP/IP、RPC 等机制实现函数托运。

2.4 Designated Thread（指定线程）

前面各节描述的是让每个线程保留自己的数据副本或数据分片。本节描述的是功能分解方法：指定一个特殊线程拥有执行某项工作所需数据的权利。

第 5 章的”最终一致性计数器”提供了例子。该实现有一个指定线程运行 eventual() 函数，它周期性地将 per-thread 计数拉取到全局计数器中，使得对全局计数器的访问最终会收敛到实际值。

关键点：eventual() 线程并非”拥有” per-thread 的 counter 变量（那是各工作线程的私有数据），而是拥有访问这些数据的权利。这类似于部分数据所有权的概念。而 eventual() 线程确实拥有自己的数据：它内部定义的局部变量 t 和 sum。

Linux 内核中的 kernel thread（通过 kthread_create() 和 kthread_run() 创建）也是指定线程的典型例子。例如：

这些内核线程通常负责某个特定的子系统功能，拥有该功能相关的数据结构访问权。

代码实现：见 designated_thread.c。主线程创建一个”eventual”线程，它每隔 1ms 扫描所有工作线程的 per-thread 计数器并累加到 global_count。工作线程只管累加自己的计数器，完全不参与全局同步。由于 stopflag 被主线程和工作线程并发访问，代码使用 C11 的 <stdatomic.h> 中的 atomic_int 和 atomic_load/atomic_store/atomic_fetch_add 保证正确的同步语义。

make designated_thread.out
./designated_thread.out
# 输出：
# expected total: 2000000
# global_count:   2000000

2.5 Privatization（私有化）

私有化是将共享数据转换为被特定线程私有的数据，从而提升性能和可扩展性。

哲学家就餐问题是最直观的例子：

本目录 privatization.c 实现了这个对比测试：

make privatization.out
./privatization.out
# 输出示例：
# classic:     166.970 ms (with 5 mutexes)
# privatized:  0.144 ms (zero synchronization)
# speedup:     1159.51x

私有化也有代价。例如第 5 章的简单限制计数器中，线程可以读取彼此的数据，但只能更新自己的数据。read_count() 中的跨线程求和循环如果去掉，就得到了更高效的纯数据所有权，但 read_count() 的精度会下降。

部分私有化也是可能的，只需要比完全共享更少的同步。第 15 章（Deferred Processing）将通过 RCU 等机制引入时间维度上的数据所有权，提供安全地将公共数据结构私有化的方法。

2.6 Other Uses of Data Ownership（其他应用场景）

数据所有权在以下环境中作为一等公民存在：

  1. MPI 和 BOINC：所有消息传递环境天然就是数据所有权模型
  2. Map-Reduce：map 阶段数据分片，reduce 阶段聚合
  3. 客户端-服务器系统：RPC、Web 服务、后端数据库
  4. Shared-nothing 数据库系统
  5. Fork-join 系统：独立的 per-process 地址空间
  6. 基于进程的并行：如 Erlang 语言
  7. 私有变量：C 语言栈上的 auto 变量在线程环境中默认私有
  8. GPGPU 并行线性代数：许多算法天然适合数据划分
  9. 操作系统网络栈：如 IX 操作系统，每个网络连接（flow）分配给特定线程

3. Linux 内核源码分析

3.1 Per-CPU 变量：内核数据所有权的基石

Linux 内核通过 DEFINE_PER_CPU(type, name) 和 DECLARE_PER_CPU(type, name) 宏定义 per-CPU 变量。这些变量被放置在特殊的 per-CPU 段中，每个 CPU 拥有独立的副本。

在 include/linux/percpu-defs.h 中：

#define DECLARE_PER_CPU(type, name) \
    DECLARE_PER_CPU_SECTION(type, name, "")

#define DEFINE_PER_CPU(type, name) \
    DEFINE_PER_CPU_SECTION(type, name, "")

在 x86 架构上，arch/x86/include/asm/percpu.h 使用段寄存器（gs/fs）实现高效的 per-CPU 访问：

#define PER_CPU_VAR(var)    %__percpu_seg:(var)__percpu_rel

访问接口包括：

这些宏在 include/linux/percpu-defs.h 中定义：

#define this_cpu_read(pcp)     __pcpu_size_call_return(this_cpu_read_, pcp)
#define this_cpu_write(pcp, val) __pcpu_size_call(this_cpu_write_, pcp, val)

为什么 per-CPU 变量访问不需要锁？ 因为每个 CPU 只访问自己的副本，天然满足数据所有权。其他 CPU 如果需要读取，通常需要持有 cpus_read_lock() 或使用 READ_ONCE() 等机制。

3.2 vmstat：部分数据所有权的典型例子

在 mm/vmstat.c 中，内核定义了 per-CPU 的 vm 事件计数器：

DEFINE_PER_CPU(struct vm_event_state, vm_event_states) = { { 0 } };
EXPORT_PER_CPU_SYMBOL(vm_event_states);

更新时（include/linux/vmstat.h）：

static inline void count_vm_event(enum vm_event_item item)
{
    this_cpu_inc(vm_event_states.event[item]);
}

这里 this_cpu_inc 直接对当前 CPU 的 vm_event_states 进行自增，无需任何锁。这是典型的部分数据所有权：每个 CPU 拥有写权限，而读取（如 all_vm_events()）需要遍历所有 CPU：

void all_vm_events(unsigned long *ret)
{
    cpus_read_lock();
    sum_vm_events(ret);
    cpus_read_unlock();
}

sum_vm_events 内部使用 per_cpu(vm_event_states, cpu) 访问其他 CPU 的数据，此时需要 cpus_read_lock 保护，防止 CPU 热插拔导致 per-CPU 数组变化。

3.3 SLUB 分配器：per-CPU cache 的纯数据所有权

mm/slub.c 中的 SLUB 分配器使用 slub_percpu_sheaves 结构实现 per-CPU 快速路径：

struct slub_percpu_sheaves {
    ...
};

pcs = per_cpu_ptr(s->cpu_sheaves, cpu);

每个 CPU 有自己的 sheaf（捆），分配和释放时优先操作本地 sheaf，使用 spin_trylock 保护（快速路径失败时才走全局慢路径）。这是纯数据所有权在内存分配中的经典应用，避免了全局锁竞争。

3.4 内核线程：Designated Thread 的实现

kernel/kthread.c 提供了 kthread_create() 和 kthread_run()：

struct kthread_create_info {
    int (*threadfn)(void *data);
    void *data;
    ...
    struct task_struct *result;
    struct completion *done;
};

内核中的 designated thread 实例：

这些线程各自负责特定的内核子系统功能，拥有相关的数据结构和处理逻辑，其他内核代码通过工作队列、信号量或 completion 等机制与它们交互，而不是直接操作它们的数据。

4. 用户笔记中的疑问分析

在 ~/data/vn/docs/concurrent/ 目录下的笔记中，用户提出了几个与数据所有权密切相关的问题。本章内容对这些问题的解答如下：

4.1 “per_cpu 读取为什么不需要 READ_ONCE？”

用户笔记中提到了 all_vm_events 中的读取：

struct vm_event_state *this = &per_cpu(vm_event_states, cpu);

用户问：”这里为什么不需要 READ_ONCE？”

解答：

本章的”部分数据所有权”一节明确说明：线程可以读取其他线程的数据，但不修改它。这种读取通常不需要与写入方同步，除非对数据新鲜度有严格要求。

4.2 “global_node_page_state 为什么用 atomic？”

unsigned long global_node_page_state_pages(enum node_stat_item item)
{
    long x = atomic_long_read(&vm_node_stat[item]);
    ...
}

解答：

4.3 “READ_ONCE 只是保证 read 不会消失，还需要保证指令重排吗？”

用户笔记中追问 READ_ONCE 的语义：是否还需要保证指令重排？

解答：

4.4 “什么叫 weakly ordered atomic operations？”

用户笔记中提到对 weakly ordered atomic operations 的困惑。

解答：

5. 总结

数据所有权或许是现存最被低估的同步机制。当使用得当时，它提供了无与伦比的简单性、性能和可扩展性。也许正是因为它的简单，才让它没有得到应有的尊重。

本章通过六种视角展示了数据所有权：

  1. 多进程：完全独立的地址空间，零共享零同步
  2. 部分数据所有权：写私有，读共享，适用于统计计数器等场景
  3. 函数托运：不直接触碰他人数据，而是请数据所有者在自己的上下文中执行操作
  4. 指定线程：将特定功能和数据所有权赋予特定线程
  5. 私有化：将共享资源复制为私有资源，消除竞争
  6. 应用场景：MPI、Map-Reduce、客户端-服务器、Erlang、GPGPU、网络操作系统等

Linux 内核是数据所有权的集大成者：per-CPU 变量、vmstat 统计、SLUB per-CPU cache、内核线程等处处体现了这一思想。理解数据所有权，是理解高性能并发编程和内核设计的关键一步。

本站所有文章转发 CSDN 将按侵权追究法律责任，其它情况随意。