Поточно-безопасная структура данных

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Структура данных и ее методы.
2. Синхронизация потоков.

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

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

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