4

我对人们用来发布信息和更改跨多个线程共享的数据结构而不会丢失太多并发性的技术感兴趣。以我个人的经验,我经常遇到单个编写器/多个读取器,其中单个线程正在更新一个对象,但多个线程正在从对象中读取并且需要通知更改。

作为一个简单的例子,考虑一个哈希表(假设它是线程安全的,无论是通过粗粒度锁定、细粒度锁定还是低锁定技术等)。线程 1 负责从哈希表中放入和删除信息,但它是唯一的写入者。当任何键被更改、某个键被更改或任何变体时,其他线程可能希望得到通知。他们希望订阅什么并不是特别重要。

你会使用什么技术(我喜欢论文的建议)来确保线程接收及时和正确的更改信息?

4

2 回答 2

1

您实际上已经询问了 2 个不同的问题

MultipleReader/SingleWriter 排除

更新通知(通常称为观察者模式)

MultipleReader/SingleWriter 锁是一个有大量文献的经典问题。真正的问题是,许多经典解决方案涉及多个互斥锁和/或信号量,并且可能非常重量级,经常涉及每个简单写锁的 6 个读修改写 (RMW) 周期和第一个读锁的 6 个 RMW

这两个问题有很多解决方案,效率和实用性取决于读取到达率,写入到达率,写入持续时间,读取持续时间,是否可以批量更新,是否需要升级读锁,降级写锁(在你的情况下听起来像没有)

对于哈希表的示例,您可以使用“中等粒度的锁定,即 O(n 个访问线程)并且只是将锁任意分配给哈希表的块(请注意单独的链接。使用开放寻址,锁不一定会锁定探测到插槽)。或者您也可以使用 hop-scotch 散列并发散列表算法

就通知而言,一些典型的问题是:

每个读取线程都必须看到(并处理)每个通知吗?观察者的集合是静态的还是动态的?即通知“网络”可以是静态的(编译时间定义)

于 2009-07-27T20:40:22.793 回答
1

执行此操作的经典方法是使用等待条件,但它们会阻塞线程,直到事件到达。

现在,我会为每个工作线程使用一个消息队列,对中央数据结构的更新将是发布到工作线程队列中的消息。这也在内部使用了一个等待条件,但它是一个比裸等待条件更高级别的接口,并且几乎所有编程语言都为这种编程提供了良好的库支持。

一个更骇人听闻的解决方案是在select()调用套接字时阻塞线程,通知线程将字节写入该套接字以唤醒睡眠线程。Usingselect()的优点是您可以将这种事件与几乎所有其他事件处理进行多路复用,因此当目标线程是例如 GUI 线程时也适用。

于 2009-07-26T10:57:43.820 回答