2

我需要设计一个支持以下操作的数据结构:

  • 基于作为间隔的键在数据结构中搜索元素。例如,区间 1-5 内的值可能是 3,区间 6-11 内的值可能是 5,依此类推。间隔是连续的,它们之间没有重叠。
  • 查找上一个和下一个间隔 - 这几乎与搜索间隔一样频繁。
  • 分割区间,加入连续区间
  • 并发性:我已将设计限制为一个编写器线程和其他读取器线程,如下所示。编写器线程可以拆分或连接区间,或修改区间中的值。任何读取器线程仅在一个时间间隔内读取值(读取器可能读取多个时间间隔,但我不必序列化所有读取 - 在两次读取之间进行写入是可以的)。每个读取器每次写入大约有 20-80 次读取。此外,我仍然需要确定读者人数,但应该是 2-8 人左右。

我考虑使用 list 在中间添加和删除元素。只有有限数量的间隔 - 所以使用 map 可能是不正确的。这种访问(一个写入器,多个读取器)不受 STL 列表的良好支持。boost::intrusive::list 似乎合适。在侵入性列表的顶部,我将不得不获取锁来读/写间隔。

此外,我了解侵入式列表可用于比 STL 列表更好的缓存位置(以及为包含的对象分配适当的内存)。

方法好吗?如果是,我也很想知道您使用 intrusive::list 的经验,特别是对于多线程应用程序。

4

2 回答 2

5

您在这里有两个不同的问题:

  1. 如何表示你的数据结构
  2. 如何以高效的方式使其线程安全

您的数据结构将为每次写入执行 (20-80) x (2-8) 次读取。

(1)。首先,假设您的范围是如下数据结构


    struct Interval
    {
        Interval(int start, int length)
          : m_start(start),
            m_length(length)
        {}
        int m_start;
        int m_length;
        int value; // Or whatever
    };

Since reads massively outnumber writes, lookup needs to be fast, while modifications don't.

Using a list for your data structure means O(N) lookups and O(1) modification - exactly the wrong way around.

The simplest possible representation of your structure is a vector. If the intervals are held in sorted order, lookups are O(logN) and modifications are O(N).

To implement this, just add a comparator to Interval:

bool operator<(const Interval& rhs) const
{
    return m_start < rhs.m_start;
}

You can then use std::lower_bound to find the first interval equal or lower to your search interval in O(logN).

Next and previous interval are O(1) - decrement or increment the returned iterator.

Splitting an interval means inserting a new element after the current one and adjusting the length of the current - O(N).

Joining two intervals means adding the length of the next one to the current one and erasing the next one - O(N).

You should reserve() enough space in the vector for the maximum number of elements to minimise resizing overhead.

(2). Following Knuth, 'premature optimisation is the root of all evil'.

A single read/write lock on the structure holding your vector<Interval>很可能就足够了。唯一可能的问题是(2a)由于读者独占锁而导致写入者饥饿,或(2b)由于写入者更新花费太长时间而导致读取者饥饿。

(2a) 如果(且仅当)您面临作家饥饿,您可以使锁定更加精细。不过,这种情况有可能不会发生。去做这个:

使您的向量通过指针而不是值保持其间隔。这样调整大小就不会在内存中移动对象。让每个间隔都包含一个读/写锁。

对于读取:获取集合的读取锁,然后获取所需的时间间隔。如果您不需要读取任何其他区间,请在获得区间锁后立即放弃集合锁,以允许其他线程继续执行。

如果您需要读取其他存储桶,您可以按任何顺序对它们进行读锁定,直到您放弃集合读锁定,此时写入器可以添加或删除您尚未锁定的任何间隔。获取这些锁时顺序无关紧要,因为当您持有集合上的读锁时,作者无法更改向量,并且读锁不会竞争。

对于写入:

获取集合的写锁,然后获取所需的时间间隔。请注意,对于将添加或删除间隔的所有更新,您必须持有集合写锁。如果您只更新一个间隔,您可以放弃收集锁。否则,您需要持有写锁并在您将要修改的任何时间间隔上获取写锁。您可以按任何顺序获取间隔锁,因为没有集合锁,没有读者可以获取新的读锁。

上述工作对作者线程更加自私,这应该消除饥饿。

(2b) 如果您面临读者饥饿(这种情况更不可能),最好的解决方案是将集合写入和读取分开。通过共享指针持有集合,并对其有一个写锁。

对于读取:获取写入锁和 shared_ptr 的副本。放弃写锁。读者现在可以在没有任何锁的情况下读取集合(它是不可变的)。

对于写入:根据读者将 shared_ptr 带到集合中,放弃锁定。制作集合的私有副本并对其进行修改(因为它是私有副本,所以不需要锁定)。再次获取写锁并将现有的 shared_ptr 替换为您的新集合。完成旧集合的最后一个线程将销毁它。所有未来的线程都将使用新更新的集合。

请注意,根据您的问题描述,此算法仅适用于一位作家。

于 2009-05-30T13:25:36.150 回答
0

并发二叉树可能是一个很好的选择,它允许对不同间隔的读取和写入并行进行。

于 2009-05-30T02:38:04.803 回答