Azul Systems 的设备支持数千个缓存一致的 CPU。我很想深入了解操作系统需要发生哪些更改才能安排数千个同时运行的线程。
问问题
1494 次
8 回答
15
调度数千个线程并不是什么大问题，但在数百个 CPU 上调度它们却是。您首先需要的是非常细粒度的锁定，或者更好的是无锁数据结构和算法。你不能让 200 个 CPU 在一个 CPU 执行临界区时等待。
于 2009-04-10T20:55:19.757 回答
6
使 Linux 规模化是一个长期且持续的项目。第一个支持多处理器的 Linux 内核有一个保护整个内核的锁（Big Kernel Lock，BKL），这很简单，但可扩展性有限。
随后，锁定变得更加细粒度，即有许多锁（数千？），每个只覆盖一小部分数据。但是，这可以走多远是有限制的，因为细粒度锁定往往很复杂，并且锁定开销开始消耗性能优势，特别是考虑到大多数多 CPU Linux 系统的 CPU 相对较少。
另一件事是，内核尽可能使用 per-cpu 数据结构。这非常重要，因为它避免了共享数据的缓存一致性性能问题，当然也没有锁定开销。例如，每个 CPU 都运行自己的进程调度程序，只需要偶尔进行全局同步。
此外，一些算法的选择考虑了可扩展性。例如，一些以读取为主的数据受 Read-Copy-Update (RCU) 保护，而不是传统的互斥锁；这允许读者在并发更新期间继续。
至于内存，Linux 会努力从进程运行所在的同一个 NUMA 节点分配内存。这为应用程序提供了更好的内存带宽和延迟。
于 2009-04-15T19:02:49.297 回答
6
您要求对操作系统进行可能的更改，因此我认为这项工作背后有一个重要的工程团队。
还有一些有助于定义问题参数的澄清信息：
你需要多少 IPC（进程间通信）？
它们真的必须是线程，还是可以是进程？
如果它们是进程，是否必须通过套接字而不是使用共享内存相互通信？
什么是内存架构？您是具有 1024 个内核的直接 SMP，还是这里有其他一些 NUMA（非统一内存架构）或 MMP？你的页表是什么样的？
仅了解有关 Azul 系统的最少量信息，我猜想您的 IPC 很少，而且简单的“每个内核运行一个内核”模型实际上可能效果很好。如果进程需要相互通信，那么它们可以创建套接字并以这种方式传输数据。你的硬件支持这个模型吗？（您可能最终每个内核也需要一个 IP 地址，并且在 1024 个 IP 地址处，这可能会很麻烦，尽管它们都可以进行 NAT，也许这没什么大不了的）。当然，如果这种模型会导致一些效率低下，例如额外的页表和相当多的 RAM 开销，甚至可能不被您的硬件系统支持。
即使“每个内核 1 个内核”不起作用，您也可能会运行 1024/8 个内核，并且很好，让每个内核控制 8 个物理 CPU。
也就是说，如果您想在具有 1024 个内核（并且只有几个物理 CPU）的传统 SMP 机器中每个内核运行 1 个线程，那么我希望老式的 O(1) 调度程序是您想要的。您的 CPU[0] 很可能会在内核中接近 100% 并进行中断处理，但这对于这个用例来说很好，除非您需要超过 1 个内核来处理您的工作负载。
于 2009-04-18T03:43:32.567 回答
5
我未受过教育的猜测是，每个处理器都有一个运行队列，并且当处理器空闲时有一个工作窃取算法。我可以看到这在 M:N 模型中工作，其中每个 cpu 有一个进程，轻量级进程作为工作项。这会让人感觉类似于窃取工作的线程池，例如 Java-7 的 fork-join 库中的线程池。
如果您真的想知道，请去学习 Solaris Internals 或深入研究 Solaris 内核代码。我仍在阅读 FreeBSD 的 Design & Impl，其中 Solaris Internals 是我列表中的下一个，所以我所能做的就是对 atm 进行疯狂的猜测。
于 2009-04-11T02:29:50.950 回答
1
我很确定我们工作中的 SGI Altix（它执行 ccNUMA）使用特殊硬件来实现缓存一致性。
有一个巨大的开销连接到每个核心保持 4mb 的缓存一致。仅在软件中不太可能发生。
在 256 cpu 的数组中，您需要 768mb 内存来保存缓存无效位。12mb 高速缓存 / 每个高速缓存行 128 字节 * 256² 个内核。
于 2009-04-14T11:20:19.887 回答
1
修改操作系统是一回事，但使用未更改的应用程序代码是对硬件的浪费。当超过一些限制（取决于硬件）时，为了执行通用代码而保持一致性和同步的努力实在是太多了。你可以这样做，但它会非常昂贵。从操作系统方面，您将需要复杂的关联模型，即不要仅仅因为您的 CPU 很忙而跳过 CPU。基于硬件拓扑调度线程——在“关闭”的 CPU 上协作线程以最大程度地减少惩罚。简单的工作窃取不是一个好的解决方案，您必须考虑拓扑。一种解决方案是分层工作窃取 - 按距离窃取工作，将拓扑划分为扇区并尝试从最近的位置首先窃取。稍微接触一下锁的问题；您仍然会使用自旋锁，但使用完全不同的实现。这可能是当今 CS 中获得专利最多的领域。但是，同样，您需要专门针对如此大规模的程序进行编程。或者你会简单地使用它。没有自动“并行器”会为你做这件事。
于 2009-04-14T12:10:31.467 回答
1
最简单的方法是将每个进程/线程绑定到几个 CPU，然后只有这些 CPU 必须竞争该线程上的锁。显然，需要某种方式来移动线程以平衡负载，但在 NUMA 架构上，您必须尽可能减少这种情况。
于 2009-04-16T14:01:35.510 回答
0
即使在双核英特尔系统上，我很确定 Linux 已经可以使用本地 posix 线程处理“数千个”线程。
（但是，Glibc 和内核都需要配置为支持这一点，但我相信现在大多数系统现在都默认支持）。
于 2009-06-03T04:46:37.400 回答