设计报告资源冲突的数据结构

Question

我有一个有1024个地址的内存地址池。程序内部运行着 16 个线程，它们访问这些内存位置，执行读或写操作。该程序的输出采用一系列四元组的形式，其定义如下

四元组 q1 : (线程号、内存地址、读/写、时间)

例如 q1 = (12,578,r,2t), q2= (16,578 ,w,6t)

我想设计一个程序，它将四元组流作为输入，并报告如果两个以上线程尝试在 5t 秒的时间间隔内至少进行一次写入操作访问同一内存资源时发生的所有冲突。

我心里有几个解决方案，但我不确定它们是否是解决这个问题的最佳方案。我正在从设计和数据结构的角度寻找解决方案。

Answer 1

所以这里的基本问题是碰撞检测。我通常会寻找一种将元素添加到某种关联集合中的解决方案。当即将添加新元素时，您需要能够判断集合中是否已经包含相似的元素，这表明发生了冲突。在这里，您似乎需要一个允许重复元素的集合类型，例如 STL 多重映射。四元组（四元组？）显然是关联集合中的值类型，而键类型将包含确定两个元素是否表示冲突所需的数据，即内存地址和时间。为了使用像STL multimap这样的标准关联集合，您需要通过定义operator<来定义键上的一些排序。对于密钥类型（我假设这里是 C++，你没有指定）。您将碰撞定义为内存位置相同且时间值相差小于某个阈值量的两个元素。键类型的排序必须使得表示冲突的两个键在该排序下是等效的。 < 下的等价性运算符表示为 < b 为假且 b < a 也是 false，因此顺序可能由该运算符定义：

bool operator<( Key const& a, Key const& b ) {
    if ( a.address == b.address ) {
        if ( abs(a.time - b.time) < threshold ) {
            return false;
        }
        return a.time < b.time;
    }
    return a.address < b.address;
}

此设计存在问题，因为在 << 下两个键可能是等效的。没有平等。这意味着两个不同但相似的四元组（即两个相互冲突的值）将存储在集合中的相同键下。您可以使用更简单的排序定义

bool operator<( Key const& a, Key const& b ) {
    if ( a.address == b.address ) {
        return a.time < b.time;
    }
    return a.address < b.address;
}

在此排序定义下，碰撞元素最终在有序关联容器中相邻（但在不同的键下），因此您可以在它们具有后处理步骤中轻松找到它们全部已添加到集合中。