Конструкция структуры данных, защищенной потоком

Question

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

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

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

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

EDIT: У меня есть лучший пример. Предположим, что поиск элемента возвращает либо ссылку, либо указатель на сохраненный элемент, а не копию. Как можно защитить вызывающего абонента, чтобы безопасно использовать этот указатель \ reference после возврата вызова? Если вы считаете, что не возвращать копии, это проблема, а затем подумайте о глубоких копиях, то есть о объектах, которые также должны копировать другие объекты, которые они указывают внутри.

спасибо.

Answer 1

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

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

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

Один, может быть, важный, подсказка о производительности находится в Will's answer ниже. [/ edit]

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

Answer 2

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

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

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

Answer 3

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

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

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

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

Answer 4

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

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

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

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

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

Answer 5

В стиле стиля 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) 
} 

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