代码之家  ›  专栏  ›  技术社区  ›  amit kumar

这个多线程用例的最佳数据结构:入侵列表好吗?

  •  2
  • amit kumar  · 技术社区  · 15 年前

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

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

    我考虑使用列表来添加和删除中间的元素。只有有限的时间间隔,所以使用map可能是不对的。STL列表不支持这种访问(一个写入程序,多个读取器)。boost::intrusive::list似乎很合适。在侵入列表的顶部,我必须获取锁来读取/写入间隔。

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

    这个方法行吗?如果是的话,我还想了解您使用intrusive::list的经验,特别是对于多线程应用程序。

    2 回复  |  直到 15 年前
        1
  •  5
  •   Jon    15 年前

    1. 如何表示数据结构
    2. 如何使其线程安全,在一个有效的庄园

    (1). 首先,假设您的范围是一个数据结构,如下所示

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

    由于读取的数量大大超过写入的数量,所以查找需要快速,而修改则不需要。

    为数据结构使用列表意味着O(N)个查找和O(1)个修改-这完全是错误的方法。

    结构最简单的可能表示形式是向量。如果间隔按排序顺序保持,则查找为O(logN),修改为O(N)。

    要实现这一点,只需向Interval添加一个比较器:

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

    std::lower_bound

    下一个和上一个间隔是O(1)-递减或递增返回的迭代器。

    拆分间隔意味着在当前间隔之后插入一个新元素,并调整当前间隔的长度-O(N)。

    连接两个间隔意味着将下一个间隔的长度与当前间隔相加,并删除下一个间隔-O(N)。

    reserve() 向量中有足够的空间容纳最大数量的元素,以最小化调整大小的开销。

    过早的优化是万恶之源 '.

    在保存向量的结构上有一个读/写锁<间隔>这很可能就足够了。唯一可能的问题是(2a)由于读卡器垄断了锁而导致写卡器饥饿,或者(2b)由于写卡器更新时间过长而导致读卡器饥饿。

    (2a)如果(且仅当)您面临写入程序饥饿,您可以使锁定更细粒度。它的

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

    内容如下:

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

    对于写入:

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

    上述作品通过对作者线程更自私来实现,这应该可以消除饥饿。

    内容如下: 获取写锁和共享\u ptr的副本。放弃写锁。读取器现在可以在不使用任何锁(其不可变)的情况下读取集合。

    按照读卡器的要求将共享的ptr带到集合中,放弃锁。创建集合的私有副本并对其进行修改(由于集合是私有副本,因此不需要锁)。再次使用写锁,并用新集合替换现有的共享\u ptr。完成旧集合的最后一个线程将销毁它。所有将来的线程都将使用新更新的集合。

        2
  •  0
  •   Dave    15 年前

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