Разработка структуры данных для отчетности о конфликтах ресурсов

Question

У меня есть пул адресов памяти с 1024 адресами. В программе запущено 16 потоков, которые обращаются к этим ячейкам памяти, выполняя операции чтения или записи. Выходные данные этой программы представлены в виде серии четверок, defn которых выглядит так:

Четырехместный q1: (№ потока, Адрес памяти, чтение / запись, время)

например, q1 = (12 578, r, 2t), q2 = (16 578, w, 6t)

Я хочу разработать программу, которая принимает поток четырехкратных данных как входные данные и сообщает обо всех конфликтах, которые возникают, если более 2 потоков пытаются получить доступ к одному и тому же ресурсу памяти в интервале 5 тс с хотя бы одной операцией записи.

У меня есть несколько решений, но я не уверен, что они являются лучшими для решения этой проблемы. Я ищу решение с точки зрения дизайна и структуры данных.

Answer 1

Итак, основная проблема здесь - обнаружение столкновений. Я бы обычно искал решение, в котором элементы добавляются в какую-то ассоциативную коллекцию. Как только новый элемент будет добавлен, вы должны быть в состоянии определить, содержит ли коллекция подобный элемент, что указывает на коллизию. Здесь вам может показаться, что вам нужен тип коллекции, который допускает дублирование элементов, таких как мультикарта STL. Quadraple (quadruple?), Очевидно, будет типом значения в ассоциативной коллекции, а тип ключа будет содержать данные, необходимые для определения того, представляют ли два элемента коллизию, то есть адрес и время памяти. Чтобы использовать стандартную ассоциативную коллекцию, такую ​​как STL multimap, вам нужно определить некоторый порядок на ключах, определив operator <для типа ключа (я предполагаю, что C ++ здесь, вы не указали). Вы определяете столкновение как два элемента, в которых место в памяти идентично, а значения времени отличаются менее чем на некоторое пороговое значение. Упорядочение типа ключа должно быть таким, чтобы два ключа, представляющих коллизию, выглядели эквивалентно при упорядочении. Эквивалентность под оператором <выражается как a <b ложно и b <a также ложно, поэтому порядок может быть определен этим оператором: </p>

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;
}

Существует проблема с этим дизайном из-за того, что два ключа могут быть эквивалентны в <без равенства. Это означает, что два разных, но похожих Quadraples, то есть два значения, которые сталкиваются друг с другом, будут храниться под ключом <em>, равным в коллекции. Вы можете использовать более простое определение порядка

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

Согласно этому определению порядка, сталкивающиеся элементы оказываются смежными в упорядоченном ассоциативном контейнере (но под разными ключами), так что вы сможете легко найти их на этапе постобработки после того, как все они будут добавлены в коллекцию. .