1

描述：

我有多个线程（4-32）。这些线程都可以访问一个数组：int resources[1024]。资源数组包含不同的值 (0-1023)。单个资源（int）只能有一个实例。每个线程需要不同数量的资源，这些资源有时会返回到数组中。线程可以多次请求资源，并且一次只返回部分获取的资源。每个线程都通过 2 种方法访问该数组：GetElement()、ReturnElement(int element)

GetElement()：此方法锁定部分，从资源数组中删除最后一个元素并将其返回给调用线程。每个线程都在循环调用 n 个资源的方法。

ReturnElement(int element)：此方法锁定部分，将参数中的资源元素附加到数组中的最后一个元素之后。每个线程都在循环调用 n 个资源的方法。

当前的实现存在缺陷，即当多个线程同时获取资源时，它们可能都没有获得所需的数量。我正在考虑在单个线程获取或返回资源时锁定对数组的访问，然后解锁它。这种方法阻塞了所有其他可能成为问题的线程。

有没有更有效的方法？

4

1 回答 1

2

这个问题是哲学家进餐问题的一个变体，这是一个活跃的研究领域。有一些解决方案，但没有一个是完美的，通常在这种情况下，以通用和恒定时间的方式避免死锁是有问题的。

一些通用的解决方案方向：

  • 使用仲裁员。这可以像全局或每个节点（在 NUMA 的情况下）锁定整个资源分配过程一样简单，但也可以以无锁方式完成，例如优先考虑 ID 较低的工作人员。

  • 实施工作窃取：从另一个等待的工作人员那里回收部分分配的资源，但有一些内置的不公平性（例如，从不从工作人员 0 获取）。这需要跟踪部分分配的资源和一些线程间（进程间）通信。

  • Try-and-release：尝试获取资源，如果失败，释放部分获取的资源并让执行（等待一小段时间）。Howard Hinnant 对此做了一些研究，可以在这里找到。

鉴于您的问题描述，我建议使用中央锁定的简单解决方案，或者更好的是，首先尝试避免该问题。鉴于您正在开发一个虚拟内存分配器，有一些专门针对它的研究，例如来自jemalloc的这个。

于 2021-04-18T10:16:22.967 回答