通过更改基地址快速同步访问共享数组（在 C11 中）
Fast synchronized access to shared array with changing base address (in C11)
我目前正在为 Linux 下的自定义协处理器（用户 space，因为协处理器不 运行 它自己的 OS，但由主机 CPU 上的软件 运行ning 控制）。它使用数组跟踪所有任务的状态。在这种情况下，任务状态是常规整数。该数组是动态分配的，每次提交状态不再适合该数组的新任务时，该数组将重新分配为当前大小的两倍。调度程序使用多个线程，因此需要同步其数据结构。
现在，问题是我经常需要读取该数组中的条目，因为我需要知道任务的状态以进行调度决策和资源管理。如果保证每次重新分配后基地址始终相同，我会简单地使用 C11 原子来访问它。不幸的是，realloc 显然不能给出这样的保证。所以我目前的方法是用一个 pthread 互斥体形式的大锁来包装每次访问（读取和写入）。显然，这真的很慢，因为每次读取都有锁定开销，而且读取非常小，因为它只包含一个整数。
为了澄清问题，我在这里给出一些显示相关段落的代码：
写作：
// pthread_mutex_t mut;
// size_t len_arr;
// int *array, idx, x;
pthread_mutex_lock(&mut);
if (idx >= len_arr) {
len_arr *= 2;
array = realloc(array, len_arr*sizeof(int));
if (array == NULL)
abort();
}
array[idx] = x;
pthread_mutex_unlock(&mut);
阅读中：
// pthread_mutex_t mut;
// int *array, idx;
pthread_mutex_lock(&mut);
int x = array[idx];
pthread_mutex_unlock(&mut);
我已经在实现的其他地方使用 C11 原子进行高效同步，也很想用它们来解决这个问题，但我找不到有效的方法。在一个完美的世界中，将有一个用于数组的原子访问器，它在单个原子操作中执行地址计算和内存 read/write。不幸的是，我找不到这样的操作。但在这种情况下，也许有一种同样快速甚至更快的方法来实现同步？
编辑：
我忘了指定当任务终止时我不能重用数组中的槽。因为我保证可以访问自调度程序启动以来提交的每个任务的状态，所以我需要存储每个任务的最终状态，直到应用程序终止。因此，静态分配并不是一个真正的选择。
虚拟地址space需要这么省钱吗？你不能只 设置一个非常大的上限并为其分配足够的地址 space （甚至可以是静态数组，或者动态如果你想设置上限从 command-line 选项启动时）。
Linux 进行惰性内存分配，因此您从未接触过的虚拟页面实际上并未使用 任何 物理内存。请参阅 ，它通过示例显示第一次读取或写入匿名页面会导致页面错误。如果是读访问，它将内核获取 CoW (copy-on-write) 将其映射到共享的物理零页。只有初始写入或写入 CoW 页面才会触发物理页面的实际分配。
让虚拟页面完全保持不变甚至可以避免将它们连接到硬件页表的开销。
如果你的目标是像 x86-64 这样的 64 位 ISA，你有大量的虚拟地址 space。使用更多的虚拟地址space（只要你不浪费物理页面）基本上没问题。
分配比您可以使用的地址更多的虚拟地址 space 的实际示例：
如果你分配的内存比你实际使用的多（触摸它肯定会出现段错误或调用内核的 OOM 杀手），那将和你一样大或更大可以通过 realloc.
增长
要分配这么多，您可能需要将 /proc/sys/vm/overcommit_memory 全局设置为 1（不检查）而不是默认的 0（启发式方法，这会使非常大的分配失败）。或者 使用 mmap(MAP_NORESERVE) 分配它 ，使那个映射只是 best-effort 在 page-faults.
上的增长
文档说您可能会在触摸分配有 MAP_NORESERVE 的内存时得到 SIGSEGV，这与调用 OOM 杀手不同。但我认为一旦你已经成功触及记忆，它就是你的，不会被丢弃。我认为它也不会虚假地失败，除非你实际上 运行 内存不足 + 交换 space。 IDK 你打算如何在你当前的设计中检测到它（如果你没有办法解除分配，这听起来很粗略）。
测试程序：
#include <stdlib.h>
#include <stdio.h>
#include <sys/mman.h>
int main(void) {
size_t sz = 1ULL << 46; // 2**46 = 64 TiB = max power of 2 for x86-64 with 48-bit virtual addresses
// in practice 1ULL << 40 (1TiB) should be more than enough.
// the smaller you pick, the less impact if multiple things use this trick in the same program
//int *p = aligned_alloc(64, sz); // doesn't use NORESERVE so it will be limited by overcommit settings
int *p = mmap(NULL, sz, PROT_WRITE|PROT_READ, MAP_PRIVATE|MAP_ANONYMOUS|MAP_NORESERVE, -1, 0);
madvise(p, sz, MADV_HUGEPAGE); // for good measure to reduce page-faults and TLB misses, since you're using large contiguous chunks of this array
p[1000000000] = 1234; // or sz/sizeof(int) - 1 will also work; this is only touching 1 page somewhere in the array.
printf("%p\n", p);
}
$ gcc -Og -g -Wall alloc.c
$ strace ./a.out
... process startup
mmap(NULL, 70368744177664, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_NORESERVE, -1, 0) = 0x15c71ef7c000
madvise(0x15c71ef7c000, 70368744177664, MADV_HUGEPAGE) = 0
... stdio stuff
write(1, "0x15c71ef7c000\n", 15) = 15
0x15c71ef7c000
exit_group(0) = ?
+++ exited with 0 +++
我的桌面有 16GiB 的 RAM（Chromium 和 /tmp 中的一些大文件使用了很多内存）+ 2GiB 的交换空间。然而，这个程序分配了 64 TiB 的虚拟地址 space 并几乎立即触及了其中的 1 int。并不比只分配 1MiB 慢多少。 （实际使用该内存的未来性能也应该不受影响。）
您可以预期在当前 x86-64 硬件上工作的最大 power-of-2 是 1ULL << 46。 48 位虚拟地址 space 的总低规范范围是 47 位（user-space 虚拟地址 space 在 Linux 上），其中一些已经分配给 stack/code/data。分配一个连续的 64 TiB 块仍然为其他分配留下足够的空间。
（如果你 实际上有那么多 RAM + swap，你可能正在等待一个新的 CPU with 5-level page tables 所以你甚至可以使用更多虚拟地址 space.)
说到页表，数组越大，将一些 other 未来分配放置在离现有块非常非常远的地方的可能性就越大。如果您的实际 in-use 页面最终更分散在您的地址 space 周围，这可能会在 TLB-miss（页面遍历）时间内产生 minor 成本更多 。这是更多 page-table 内存保存在缓存中（包括缓存在 page-walk 硬件中）。
分配大小不必是 2 的幂，但也可以。也没有理由让它变得 那么 大。 1ULL << 40 (1TiB) 在大多数系统上应该 很好 。 IDK 如果分配的进程的可用地址 space 超过一半可能会减慢未来的分配；我认为簿记是基于范围（ptr + 长度）而不是位图。
请记住，如果每个人都开始对库中的随机数组执行此操作，那可能会占用大量地址 space。这对于花费大量时间使用它的程序中的 the 主数组非常有用。保持它尽可能小，同时仍然足够大，总是比你需要的多。 （如果您想避免“640kiB 对每个人都足够”的情况，可选择将其作为配置参数）。用完虚拟地址space很low-cost，但还是少用点可能更好
将其视为保留space以备将来使用，但在您触摸它之前不要实际使用它。尽管从某种角度来看，内存已经是 "allocated"。但在 Linux 中确实不是。 Linux 默认允许 "overcommit"：进程映射的匿名内存总量可以超过系统的物理 RAM + 交换空间。如果太多进程试图通过实际接触所有分配的内存来使用太多，OOM 杀手必须kill something（因为像 mmap 这样的 "allocate" 系统调用已经 return 成功了）。参见 https://www.kernel.org/doc/Documentation/vm/overcommit-accounting
（使用 MAP_NORESERVE，它只保留线程之间共享的地址 space，但不保留任何物理页面，直到您触摸它们。）
你可能希望你的数组是 page-aligned: #include <stdalign.h> 这样你就可以使用类似
alignas(4096) struct entry process_array[MAX_LEN];
或者对于 non-static，用 C11 aligned_alloc().
分配它
当您确定所有线程都已完成处理时，返回数组的早期部分
如果您的数组的逻辑大小足够小，页面对齐可以轻松计算 "give back" 内存页面（x86 上为 4kiB）。 madvise(addr, 4096*n, MADV_FREE);（Linux 4.5 及更高版本）。这有点像 mmap(MAP_FIXED) 用新的未触及的匿名页面（将读取为零）替换一些页面，除了它不会拆分逻辑映射范围并为内核创建更多簿记。
除非您 return 正在处理多个页面，否则请不要为此烦恼，并且在当前顶部上方至少保留一个未释放的页面，以避免在您很快再次增长时出现页面错误。就像维护一个你曾经接触过（不回馈）的 high-water 标记和当前的逻辑大小。如果 high_water - logical_size > 16 pages 返回超过逻辑大小的第 4 页到高水位线。
如果您通常实际上 using/touching 数组的至少 2MiB，请在分配它时使用 madvise(MADV_HUGEPAGE) 让内核更喜欢使用透明大页面。这将减少 TLB 未命中。
（使用 strace 查看来自 madvise 系统调用的 return 值，并查看 /proc/PID/smaps 以查看您的调用是否产生了预期的效果。 )
如果 up-front 分配不可接受，RCU (read-copy-update) 如果是 read-mostly 可能是可行的。 https://en.wikipedia.org/wiki/Read-copy-update。但是每次元素更改时都复制一个巨大的数组是行不通的。
您会想要一个完全不同的 data-structure，只需要复制一小部分。或者 RCU 以外的东西；就像您的回答一样，您可能不需要阅读方 always wait-free。选择将取决于可接受的 worst-case 延迟 and/or 平均吞吐量，以及必须在所有线程之间反弹的任何类型的引用计数器的争用程度。
太糟糕了，没有一个 realloc 变体会在不复制的情况下尝试增长，因此您可以在打扰其他线程之前尝试这样做。 （例如，在 len 上有 idx>len spin-wait 的线程，以防它在 array 地址没有改变的情况下增加。）
所以，我想出了一个解决办法：
阅读：
while(true) {
cnt++;
if (wait) {
cnt--;
yield();
} else {
break;
}
}
int x = array[idx];
cnt--;
写作：
if (idx == len) {
wait = true;
while (cnt > 0); // busy wait to minimize latency of reallocation
array = realloc(array, 2*len*sizeof(int));
if (!array) abort(); // shit happens
len *= 2; // must not be updated before reallocation completed
wait = false;
}
// this is why len must be updated after realloc,
// it serves for synchronization with other writers
// exceeding the current length limit
while (idx > len) {yield();}
while(true) {
cnt++;
if (wait) {
cnt--;
yield();
} else {
break;
}
}
array[idx] = x;
cnt--;
wait 是一个初始化为 false 的原子 bool，cnt 是一个初始化为零的原子 int。
这只有效，因为我知道任务 ID 是按升序选择的，没有间隙，并且在写入操作初始化之前没有读取任务状态。所以我总是可以依靠一个线程来拉取只超过当前数组长度 1 的 ID。并发创建的新任务将阻塞它们的线程，直到负责的线程执行重新分配。因此需要等待，因为重新分配应该很快发生，这样其他线程就不必等待太久。
这样，我消除了瓶颈大锁。可以以两次原子加法为代价同时进行数组访问。由于很少发生重新分配（由于指数增长），数组访问实际上是无块的。
编辑：
再看一眼后，我注意到在长度更新前后对商店的重新排序必须小心。此外，只有当并发写入始终使用不同的索引时，整个事情才有效。我的实施就是这种情况，但通常情况下可能并非如此。因此，这并不像我想象的那么优雅，应该首选接受的答案中提供的解决方案。
我目前正在为 Linux 下的自定义协处理器（用户 space，因为协处理器不 运行 它自己的 OS，但由主机 CPU 上的软件 运行ning 控制）。它使用数组跟踪所有任务的状态。在这种情况下，任务状态是常规整数。该数组是动态分配的，每次提交状态不再适合该数组的新任务时，该数组将重新分配为当前大小的两倍。调度程序使用多个线程，因此需要同步其数据结构。
现在，问题是我经常需要读取该数组中的条目，因为我需要知道任务的状态以进行调度决策和资源管理。如果保证每次重新分配后基地址始终相同，我会简单地使用 C11 原子来访问它。不幸的是，realloc 显然不能给出这样的保证。所以我目前的方法是用一个 pthread 互斥体形式的大锁来包装每次访问（读取和写入）。显然，这真的很慢，因为每次读取都有锁定开销，而且读取非常小，因为它只包含一个整数。
为了澄清问题，我在这里给出一些显示相关段落的代码：
写作：
// pthread_mutex_t mut;
// size_t len_arr;
// int *array, idx, x;
pthread_mutex_lock(&mut);
if (idx >= len_arr) {
len_arr *= 2;
array = realloc(array, len_arr*sizeof(int));
if (array == NULL)
abort();
}
array[idx] = x;
pthread_mutex_unlock(&mut);
阅读中：
// pthread_mutex_t mut;
// int *array, idx;
pthread_mutex_lock(&mut);
int x = array[idx];
pthread_mutex_unlock(&mut);
我已经在实现的其他地方使用 C11 原子进行高效同步，也很想用它们来解决这个问题，但我找不到有效的方法。在一个完美的世界中，将有一个用于数组的原子访问器，它在单个原子操作中执行地址计算和内存 read/write。不幸的是，我找不到这样的操作。但在这种情况下，也许有一种同样快速甚至更快的方法来实现同步？
编辑： 我忘了指定当任务终止时我不能重用数组中的槽。因为我保证可以访问自调度程序启动以来提交的每个任务的状态，所以我需要存储每个任务的最终状态，直到应用程序终止。因此，静态分配并不是一个真正的选择。
虚拟地址space需要这么省钱吗？你不能只 设置一个非常大的上限并为其分配足够的地址 space （甚至可以是静态数组，或者动态如果你想设置上限从 command-line 选项启动时）。
Linux 进行惰性内存分配，因此您从未接触过的虚拟页面实际上并未使用 任何 物理内存。请参阅
让虚拟页面完全保持不变甚至可以避免将它们连接到硬件页表的开销。
如果你的目标是像 x86-64 这样的 64 位 ISA，你有大量的虚拟地址 space。使用更多的虚拟地址space（只要你不浪费物理页面）基本上没问题。
分配比您可以使用的地址更多的虚拟地址 space 的实际示例：
如果你分配的内存比你实际使用的多（触摸它肯定会出现段错误或调用内核的 OOM 杀手），那将和你一样大或更大可以通过 realloc.
要分配这么多，您可能需要将 /proc/sys/vm/overcommit_memory 全局设置为 1（不检查）而不是默认的 0（启发式方法，这会使非常大的分配失败）。或者 使用 mmap(MAP_NORESERVE) 分配它 ，使那个映射只是 best-effort 在 page-faults.
文档说您可能会在触摸分配有 MAP_NORESERVE 的内存时得到 SIGSEGV，这与调用 OOM 杀手不同。但我认为一旦你已经成功触及记忆，它就是你的，不会被丢弃。我认为它也不会虚假地失败，除非你实际上 运行 内存不足 + 交换 space。 IDK 你打算如何在你当前的设计中检测到它（如果你没有办法解除分配，这听起来很粗略）。
测试程序：
#include <stdlib.h>
#include <stdio.h>
#include <sys/mman.h>
int main(void) {
size_t sz = 1ULL << 46; // 2**46 = 64 TiB = max power of 2 for x86-64 with 48-bit virtual addresses
// in practice 1ULL << 40 (1TiB) should be more than enough.
// the smaller you pick, the less impact if multiple things use this trick in the same program
//int *p = aligned_alloc(64, sz); // doesn't use NORESERVE so it will be limited by overcommit settings
int *p = mmap(NULL, sz, PROT_WRITE|PROT_READ, MAP_PRIVATE|MAP_ANONYMOUS|MAP_NORESERVE, -1, 0);
madvise(p, sz, MADV_HUGEPAGE); // for good measure to reduce page-faults and TLB misses, since you're using large contiguous chunks of this array
p[1000000000] = 1234; // or sz/sizeof(int) - 1 will also work; this is only touching 1 page somewhere in the array.
printf("%p\n", p);
}
$ gcc -Og -g -Wall alloc.c
$ strace ./a.out
... process startup
mmap(NULL, 70368744177664, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_NORESERVE, -1, 0) = 0x15c71ef7c000
madvise(0x15c71ef7c000, 70368744177664, MADV_HUGEPAGE) = 0
... stdio stuff
write(1, "0x15c71ef7c000\n", 15) = 15
0x15c71ef7c000
exit_group(0) = ?
+++ exited with 0 +++
我的桌面有 16GiB 的 RAM（Chromium 和 /tmp 中的一些大文件使用了很多内存）+ 2GiB 的交换空间。然而，这个程序分配了 64 TiB 的虚拟地址 space 并几乎立即触及了其中的 1 int。并不比只分配 1MiB 慢多少。 （实际使用该内存的未来性能也应该不受影响。）
您可以预期在当前 x86-64 硬件上工作的最大 power-of-2 是 1ULL << 46。 48 位虚拟地址 space 的总低规范范围是 47 位（user-space 虚拟地址 space 在 Linux 上），其中一些已经分配给 stack/code/data。分配一个连续的 64 TiB 块仍然为其他分配留下足够的空间。
（如果你 实际上有那么多 RAM + swap，你可能正在等待一个新的 CPU with 5-level page tables 所以你甚至可以使用更多虚拟地址 space.)
说到页表，数组越大，将一些 other 未来分配放置在离现有块非常非常远的地方的可能性就越大。如果您的实际 in-use 页面最终更分散在您的地址 space 周围，这可能会在 TLB-miss（页面遍历）时间内产生 minor 成本更多
分配大小不必是 2 的幂，但也可以。也没有理由让它变得 那么 大。 1ULL << 40 (1TiB) 在大多数系统上应该 很好 。 IDK 如果分配的进程的可用地址 space 超过一半可能会减慢未来的分配；我认为簿记是基于范围（ptr + 长度）而不是位图。
请记住，如果每个人都开始对库中的随机数组执行此操作，那可能会占用大量地址 space。这对于花费大量时间使用它的程序中的 the 主数组非常有用。保持它尽可能小，同时仍然足够大，总是比你需要的多。 （如果您想避免“640kiB 对每个人都足够”的情况，可选择将其作为配置参数）。用完虚拟地址space很low-cost，但还是少用点可能更好
将其视为保留space以备将来使用，但在您触摸它之前不要实际使用它。尽管从某种角度来看，内存已经是 "allocated"。但在 Linux 中确实不是。 Linux 默认允许 "overcommit"：进程映射的匿名内存总量可以超过系统的物理 RAM + 交换空间。如果太多进程试图通过实际接触所有分配的内存来使用太多，OOM 杀手必须kill something（因为像 mmap 这样的 "allocate" 系统调用已经 return 成功了）。参见 https://www.kernel.org/doc/Documentation/vm/overcommit-accounting
（使用 MAP_NORESERVE，它只保留线程之间共享的地址 space，但不保留任何物理页面，直到您触摸它们。）
你可能希望你的数组是 page-aligned: #include <stdalign.h> 这样你就可以使用类似
alignas(4096) struct entry process_array[MAX_LEN];
或者对于 non-static，用 C11 aligned_alloc().
当您确定所有线程都已完成处理时，返回数组的早期部分
如果您的数组的逻辑大小足够小，页面对齐可以轻松计算 "give back" 内存页面（x86 上为 4kiB）。 madvise(addr, 4096*n, MADV_FREE);（Linux 4.5 及更高版本）。这有点像 mmap(MAP_FIXED) 用新的未触及的匿名页面（将读取为零）替换一些页面，除了它不会拆分逻辑映射范围并为内核创建更多簿记。
除非您 return 正在处理多个页面，否则请不要为此烦恼，并且在当前顶部上方至少保留一个未释放的页面，以避免在您很快再次增长时出现页面错误。就像维护一个你曾经接触过（不回馈）的 high-water 标记和当前的逻辑大小。如果 high_water - logical_size > 16 pages 返回超过逻辑大小的第 4 页到高水位线。
如果您通常实际上 using/touching 数组的至少 2MiB，请在分配它时使用 madvise(MADV_HUGEPAGE) 让内核更喜欢使用透明大页面。这将减少 TLB 未命中。
（使用 strace 查看来自 madvise 系统调用的 return 值，并查看 /proc/PID/smaps 以查看您的调用是否产生了预期的效果。 )
如果 up-front 分配不可接受，RCU (read-copy-update) 如果是 read-mostly 可能是可行的。 https://en.wikipedia.org/wiki/Read-copy-update。但是每次元素更改时都复制一个巨大的数组是行不通的。
您会想要一个完全不同的 data-structure，只需要复制一小部分。或者 RCU 以外的东西；就像您的回答一样，您可能不需要阅读方 always wait-free。选择将取决于可接受的 worst-case 延迟 and/or 平均吞吐量，以及必须在所有线程之间反弹的任何类型的引用计数器的争用程度。
太糟糕了，没有一个 realloc 变体会在不复制的情况下尝试增长，因此您可以在打扰其他线程之前尝试这样做。 （例如，在 len 上有 idx>len spin-wait 的线程，以防它在 array 地址没有改变的情况下增加。）
所以，我想出了一个解决办法：
阅读：
while(true) {
cnt++;
if (wait) {
cnt--;
yield();
} else {
break;
}
}
int x = array[idx];
cnt--;
写作：
if (idx == len) {
wait = true;
while (cnt > 0); // busy wait to minimize latency of reallocation
array = realloc(array, 2*len*sizeof(int));
if (!array) abort(); // shit happens
len *= 2; // must not be updated before reallocation completed
wait = false;
}
// this is why len must be updated after realloc,
// it serves for synchronization with other writers
// exceeding the current length limit
while (idx > len) {yield();}
while(true) {
cnt++;
if (wait) {
cnt--;
yield();
} else {
break;
}
}
array[idx] = x;
cnt--;
wait 是一个初始化为 false 的原子 bool，cnt 是一个初始化为零的原子 int。
这只有效，因为我知道任务 ID 是按升序选择的，没有间隙，并且在写入操作初始化之前没有读取任务状态。所以我总是可以依靠一个线程来拉取只超过当前数组长度 1 的 ID。并发创建的新任务将阻塞它们的线程，直到负责的线程执行重新分配。因此需要等待，因为重新分配应该很快发生，这样其他线程就不必等待太久。
这样，我消除了瓶颈大锁。可以以两次原子加法为代价同时进行数组访问。由于很少发生重新分配（由于指数增长），数组访问实际上是无块的。
编辑： 再看一眼后，我注意到在长度更新前后对商店的重新排序必须小心。此外，只有当并发写入始终使用不同的索引时，整个事情才有效。我的实施就是这种情况，但通常情况下可能并非如此。因此，这并不像我想象的那么优雅，应该首选接受的答案中提供的解决方案。