"非阻塞"数据结构如何可能？

Question

我无法理解任何数据结构如何"无阻塞".

假设您正在制作"非阻塞"哈希表.在某些时候,您的散列表变得太满,所以您必须重新散列到更大的表中.

这意味着您需要分配内存,这是一个全局资源.因此,您似乎必须获得某种锁以防止堆的全局损坏......无论您的数据结构本身可能出现什么问题!
但那意味着在分配内存时,每个其他线程都必须阻塞...

我在这里错过了什么？
(如何)你可以分配内存而不阻塞另一个正在做同样的线程吗？

Answer 1

非阻塞设计的两个例子是乐观设计和事务内存。

这样做的想法是——在大多数情况下，阻塞是多余的——因为两个 OP 可以同时发生而不会互相中断。但是，有时当 2 个 OP 同时发生并且数据因此而损坏时 - 您可以回滚到之前的状态，然后重试。

这些设计中可能仍然存在锁，但数据被锁定的时间明显更短，并且仅限于发生 OP 影响的关键时间。