Потокобезопасный дизайн структуры данных

Question

Мне нужно спроектировать структуру данных, которая будет использоваться в многопоточной среде. Основной API прост: вставить элемент, удалить элемент, получить элемент, проверить, существует ли этот элемент. Реализация структуры использует неявную блокировку, чтобы гарантировать атомарность одного вызова API. После того, как я это реализовал, стало очевидно, что мне действительно нужна атомарность в нескольких вызовах API. Например, если вызывающий должен проверить существование элемента, прежде чем пытаться вставить его, он не может сделать это атомарно, даже если каждый отдельный вызов API равен atomic:

if(!data_structure.exists(element)) {
   data_structure.insert(element);
}

Пример несколько неуклюжий, но суть в том, что мы больше не можем доверять результату вызова «существует» после того, как мы вернемся из атомарного контекста (сгенерированная сборка явно показывает незначительный шанс переключения контекста между двумя вызовами ).

То, что я сейчас имею в виду, чтобы решить эту проблему, это выставить блокировку через открытый API структуры данных. Таким образом, клиентам придется явно блокировать вещи, но, по крайней мере, им не придется создавать свои собственные блокировки. Есть ли лучшее общеизвестное решение таких проблем? И пока мы занимаемся этим, не могли бы вы посоветовать хорошую литературу по многопоточному проектированию?

РЕДАКТИРОВАТЬ: у меня есть лучший пример. Предположим, что извлечение элемента возвращает либо ссылку, либо указатель на сохраненный элемент, а не его копию. Как можно защитить вызывающего абонента, чтобы безопасно использовать этот указатель \ ссылку после возврата вызова? Если вы считаете, что возврат не является проблемой, подумайте о глубоких копиях, то есть объектах, которые также должны копировать другие объекты, на которые они указывают.

Спасибо.

Answer 1

Вы либо предоставляете механизм для внешней блокировки (плохо), либо перепроектируете API, например, putIfAbsent. Последний подход, например, используется для параллельных структур данных Java .

И, когда дело доходит до таких базовых типов коллекций, вы должны проверить, предлагает ли ваш язык выбора их в своей стандартной библиотеке.

[править] Чтобы уточнить: внешняя блокировка вредна для пользователя класса, так как она представляет другой источник потенциальных ошибок. Да, бывают моменты, когда соображения производительности действительно ухудшают параллельные структуры данных по сравнению с внешне синхронизированными структурами, но такие случаи редки, и тогда их, как правило, могут решить / оптимизировать только люди, обладающие гораздо большими знаниями / опытом, чем я.

Один, возможно, важный совет по производительности можно найти в Ответе Уилла ниже. [/ Править]

[edit2] Учитывая ваш новый пример: в основном вы должны стараться максимально синхронизировать коллекцию и элементы. Если время жизни элемента связано с его присутствием в одной коллекции, вы столкнетесь с проблемами; при использовании GC такая проблема становится проще. В противном случае вам придется использовать своего рода прокси вместо необработанных элементов в коллекции; в простейшем случае для C ++ вы должны использовать boost::shared_ptr, в котором используется атомный реф-счет. Вставьте обычный отказ от ответственности здесь. Когда вы используете C ++ (как я подозреваю, когда вы говорите об указателях и ссылках), комбинации boost::shared_ptr и boost::make_shared должно быть достаточно на некоторое время. [/ Edit2]

Answer 2

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

Один из подходов состоит в том, чтобы метод insertIfAbsent() возвращал заблокированный «курсор» - он вставляет заполнитель во внутреннюю структуру, так что никакой другой поток не может поверить в его отсутствие, но не вставляет новый объект , Заполнитель может содержать блокировку, так что другие потоки, которые хотят получить доступ к этому конкретному элементу, должны ждать его вставки.

В языке RAII, таком как C ++, вы можете использовать класс интеллектуального стека для инкапсуляции возвращаемого курсора, чтобы он автоматически откатывался, если вызывающий код не фиксируется. В Java это немного больше откладывается с помощью метода finalize(), но все еще может работать.

Другой подход заключается в том, чтобы вызывающая сторона создала объект, которого нет, но который иногда терпит неудачу при фактической вставке, если другой поток «выиграл гонку». Так, например, обновляются memcache. Это может работать очень хорошо.

Answer 3

В стиле RAII вы можете создавать объекты accessor / handle (не знаю, как он вызывается, возможно, существует такой шаблон), например, Список:

template <typename T>
class List {
    friend class ListHandle<T>;
    // private methods use NO locking
    bool _exists( const T& e ) { ... }
    void _insert( const T& e ) { ... }
    void _lock();
    void _unlock();
public:
    // public methods use internal locking and just wrap the private methods
    bool exists( const T& e ) {
        raii_lock l;
        return _exists( e );
    }
    void insert( const T& e ) {
        raii_lock l;
        _insert( e );
    }
    ...
};

template <typename T>
class ListHandle {
    List<T>& list;
public:
    ListHandle( List<T>& l ) : list(l) {
        list._lock();
    }
    ~ListHandle() {
        list._unlock();
    }
    bool exists( const T& e ) { return list._exists(e); }
    void insert( const T& e ) { list._insert(e); }
};


List<int> list;

void foo() {
    ListHandle<int> hndl( list ); // locks the list as long as it exists
    if( hndl.exists(element) ) {
        hndl.insert(element);
    }
    // list is unlocked here (ListHandle destructor)
}

Вы дублируете (или даже дублируете) общедоступный интерфейс, но вы предоставляете пользователям выбор между внутренней и безопасной и удобной внешней блокировкой, где это необходимо.

Answer 4

Прежде всего, вы должны действительно отделить свои проблемы. У вас есть две вещи для беспокойства:

1. Структура данных и ее методы.
2. Поток синхронизации.

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

Похоже, вы реализуете какой-то словарь. Одна вещь, которую вы можете сделать, это предоставить методы, которые имеют семантику, эквивалентную комбинированному выражению. Например, setdefault - это разумная функция, которая устанавливает значение только в том случае, если соответствующий ключ еще не существует в словаре.

Другими словами, я бы рекомендовал выяснить, какие комбинации методов часто используются вместе, и просто создать методы API, которые выполняют эту комбинацию атомарно.

Answer 5

А как насчет перевода проверки на существование в метод .insert()? Клиент вызывает его, и если он возвращает false, вы знаете, что что-то пошло не так. Очень похоже на то, что malloc() делает в старом старом C - возвращает NULL, если не удалось, установите ERRNO.

Очевидно, что вы также можете вернуть исключение или экземпляр объекта и усложнить свою жизнь оттуда ..

Но, пожалуйста, не полагайтесь на то, что пользователь устанавливает свои собственные блокировки.