AtomicData или механизм атомарной операции записи данных

[m_ax]

Вечер добрый)

Хочу спросить у бывалых в многопоточном программировании совета)
Ситуация следующая:
Имеется один поток, который пишет данные (в некотурую структуру) и есть несколько потоков, которые эти данные читают.
Сами данные представляются в виде класса и ссылка на объект этого класса передаётся пишущему и читающим потокам.
Ясно, что операция записи в общем случае не атомарна и могут возникнуть неприятности если один или более читающих потоков будут считывать даные, одновременно с записью их пишущим потоком.
Использовать mutex тоже не очень рационально, поскольку доступ к данным для чтения будет доступен только одному потоку.

Написать класс, который должен эту проблему решить, но есть сомнения...
Вот сам класс:

Код

C++ (Qt)
#ifndef ATOMICDATA_H
#define ATOMICDATA_H
 
template <class T>
class AtomicData
{
public:
    AtomicData() : m_flag(0) {}
    AtomicData(const T &data) : m_flag(0), m_data(data) {}
    AtomicData(const AtomicData<T> &other) : m_flag(0), m_data(other.get()) {}
    void set(const T &data) {
        while (m_flag) {}
        m_flag = 1;
        m_data = data;
        m_flag = 0;
    }
    T get() const {
        while (m_flag & 1) {}
        m_flag = 2;
        T data = m_data;
        m_flag = 0;
        return data;
    }
private:
    mutable volatile char m_flag;
    T m_data;
    AtomicData<T> &operator=(const AtomicData<T> &);
};
 
#endif // ATOMICDATA_H
 

 
Суть в том, что операция с char - атомарны (на сколько мне известно) и перед тем как считать или записать данные мы взводим соответствующий флаг m_flag.
Значения:
m_flag = 0 - никто не пишет, никто не читает;
m_flag = 1 - кто-то пишет (читать запрещено).
m_flag = 2 - кто-то читает (запись запрещена, читать можно).

примечание: mutable - нужно чтоб метод get() можно было сделать const;
volatile - чтоб компилятор не оптимизировал m_flag.

Собственно вопрос: По фен-шую ли такое решение или есть грабли?

Спасибо за внимание)

P.S. пишу ядро и не хотелось бы завязывать его на сторонних библиотеках, Qt использую для ГУЯ только. 

[SimpleSunny]

Сомнения оправданы (:
Посмотрите в сторону QReadWriteLock или погуглите lock-free алгоритмы (http://www.1024cores.net/ http://www.rsdn.ru/forum/cpp/1800649.flat.aspx).

Сценарий.
Один поток исполняет инструкцию while (m_flag) {}, другой поток исполняет инструкцию while (m_flag & 1) {}, только потом оба потока устанавливают флаг, дальше непредвиденные последствия.

[Igors]

Код

C++ (Qt)
        while (m_flag) {}
                      <- Здесь пробой
        m_flag = 1;
 

На эти грабли будут наступать все и всегда, так что не расстраивайтесь  
Дело в том что когда управление вернулось из while - все вроде Ок, m_flag равен нулю. Но беда в том что др. нитка может установить m_flag ПОСЛЕ while но ДО следующей команды (здесь m_flag = 1). Набор подобных ситуаций обсуждался http://www.prog.org.ru/index.php?topic=14448.msg94325#msg94325

Варианты

1) Сделать все самому. В нативных вызовах ничего особо страшного нет (OSSpinLockLock и InterlockedExchange для моих платформ, неплохо и QAtomicInt), но пройдя примерно половину пути приходишь к выводу - нерационально. Вот напр. у Вас пустое тело while. Эта, на первый взгляд несущественная мелочь, начинает доставлять неприятности - одно из ядер "загружено до упора" холостым ходом. Попытки решить это "сходу" (yield и.т.п) вызывают новые проблемы.

2) Использовать Qt QReadWriteLock. Здесь все прекрасно в том смысле что все решается очень быстро после чтения Assistant. Только одно маленькое "но" - Qt честно усыпляет нитки, поэтому при достаточно интенсивных блокировках скорость будет убита в ноль (N ядер медленнее одного).

3) После долгого обдумывания я выбрал Intel TBB и весьма доволен - шикарный выбор локов, atomic и scoped_lock.

[m_ax]

Сомнения оправданы (:
Посмотрите в сторону QReadWriteLock или погуглите lock-free алгоритмы (http://www.1024cores.net/ http://www.rsdn.ru/forum/cpp/1800649.flat.aspx).

Сценарий.
Один поток исполняет инструкцию while (m_flag) {}, другой поток исполняет инструкцию while (m_flag & 1) {}, только потом оба потока устанавливают флаг, дальше непредвиденные последствия.

Да, Вы правы, так и есть.

На эти грабли будут наступать все и всегда, так что не расстраивайтесь  Улыбающийся
Дело в том что когда управление вернулось из while - все вроде Ок, m_flag равен нулю. Но беда в том что др. нитка может установить m_flag ПОСЛЕ while но ДО следующей команды (здесь m_flag = 1). Набор подобных ситуаций обсуждался http://www.prog.org.ru/index.php?topic=14448.msg94325#msg94325

Вот вот, я уже понял как наступить на эти грабли)

Вобщем сейчас пытаюсь разобраться с устройством lock-free механизма)
Спасибо за обсуждение, я ещё отпишусь, как возникнут вопросы)

[m_ax]

Варианты

1) Сделать все самому. В нативных вызовах ничего особо страшного нет (OSSpinLockLock и InterlockedExchange для моих платформ, неплохо и QAtomicInt), но пройдя примерно половину пути приходишь к выводу - нерационально. Вот напр. у Вас пустое тело while. Эта, на первый взгляд несущественная мелочь, начинает доставлять неприятности - одно из ядер "загружено до упора" холостым ходом. Попытки решить это "сходу" (yield и.т.п) вызывают новые проблемы.

2) Использовать Qt QReadWriteLock. Здесь все прекрасно в том смысле что все решается очень быстро после чтения Assistant. Только одно маленькое "но" - Qt честно усыпляет нитки, поэтому при достаточно интенсивных блокировках скорость будет убита в ноль (N ядер медленнее одного).

3) После долгого обдумывания я выбрал Intel TBB и весьма доволен - шикарный выбор локов, atomic и scoped_lock.

А что Вы можете сказать о библиотеки ZThread?
Судя по отзывам она неплоха)

[Igors]

А что Вы можете сказать о библиотеки ZThread?
Судя по отзывам она неплоха)

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

- выглядит старой (неск лет не обновлялась)
- масса template, вникнуть трудно
- с локами бедненько (как и с ожиданием)

[m_ax]

У меня ещё такой вопрос возник:
Является ли следующая операция атомарна? (m_flag - это char):

Код

C++ (Qt)
while (m_flag++);  // <<-- Атомарна ли оно?
critical_section();
m_flag = 0; 
 

[brankovic]

У меня ещё такой вопрос возник:
Является ли следующая операция атомарна? (m_flag - это char):

Код

C++ (Qt)
while (m_flag++);  // <<-- &#1040;&#1090;&#1086;&#1084;&#1072;&#1088;&#1085;&#1072; &#1083;&#1080; &#1086;&#1085;&#1086;?
critical_section();
m_flag = 0; 
 

Из обычных операций атомарны только запись и чтение, и только того, что не больше size_t. Операция m_flag++ это по сути:

R = m_flag;
R = R + 1;
m_flag = R;

где R это регистр процессора. Между строкой 1 и 3 может вклиниться другой тред и всё испортить. Атомарные операции это специальные инструкции процессора (не портабильные), самая главная атомарная операция это atomic CAS, ещё можно почитать про load linked/store conditional.

В gcc есть набор встроенных операций типа на __sync*. Например __sync_fetch_and_add (&m_flag, 1). Но эти же операции спрятаны в мьютексах. pthread_mutex, вообще не выходит в режим ядра, если тред успел залочиться, разлочиться, и в середине никто этот мьютекс не захватывал. Поэтому rw_lock часто быстрее любых lockfree (по сути он распадается на atomic++ и atomic--). В данной задаче рекомендация однозначно rwlock.

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

По сути локфри: на локфри операциях можно сделать всё (есть теорема даже ), но на практике это нечитабельно, плюс бывает, что от локфри тормозов больше, чем скорости, по конкретной задаче надо мерить. Например: как-то наблюдал написание локфри аллокатора, из-за проблем с фрагментацией обычного маллока. Так вот, фрагментировался он меньше, а работал чуть медленнее, хотя в гцц-шном маллоке есть мьютексы.

[Igors]

Код

C++ (Qt)
while (m_flag++);  // <<-- Атомарна ли оно?
critical_section();
m_flag = 0; 
 

Нет, и замена ++ на атомарный инкремент здесь ничего не даст (ввиду тех же граблей).

[vregess]

Сомнения оправданы (:
Посмотрите в сторону QReadWriteLock или погуглите lock-free алгоритмы (http://www.1024cores.net/ http://www.rsdn.ru/forum/cpp/1800649.flat.aspx).

Отдельное спасибо хотел бы сказать за ссылки на lock-free.
Кто-нибудь использовал приведенную по ссылке (rsdn) реализацию? Имею ввиду fire::store.

Извините за оффтоп.

[Igors]

lock-free конечно дело заводное, поражает красота/неожиданность решений и все такое. Но времени оно съедает безумно и "обобщить" ничего не удается, новая задача/потребность - и начинай сначала. А тот локер/мутекс воткнул - и все дела.

[vregess]

Я почему обратил внимание.
Раньше я просто делал сласс Data потокобезопасным при помощи мьютексов.
Сейчас думаю использовать такой подход (псевдокод):

Код:

class Data {}

class DataManager
{
public:
    ...
    SharedPointer<Data> data() const
    {
         ReadLocker lock;
         return m_data;
    }

    void setData(SharedPointer<Data> d)
    {
         WriteLocker lock;
         m_data = d;
    }
private:
    SharedPointer<Data> m_data;
}

Как я понял lock-free storage делает то же самое - атомарный обмен указателей, только меньше оверхед + решение ряда других проблем.
Вот я и думаю стоит ли заморачиваться с технологией lock-free ради оверхэда использования мьютексов.
Но да, идея lock-free достаточно интересная.

[brankovic]

Код:

class Data {}

class DataManager
{
public:
    ...
    SharedPointer<Data> data() const
    {
         ReadLocker lock;
         return m_data;
    }

    void setData(SharedPointer<Data> d)
    {
         WriteLocker lock;
         m_data = d;
    }
private:
    SharedPointer<Data> m_data;
}

Именно так все и делают, за счёт shared_ptr оверхеда здесь мизер. Собственно 2 атомарных операции на захват/отдачу мьютекса + 1 атомарная операция на копирование shared_ptr. В лучшем lockfree решении будет 2 атомарных операции. Только для этого lockfree не оправдано.

lockfree незаменимо, если очень хочется сделать код reentarable, например для доступа из юникс-сигналов. Но  задачу, где это необходимо, ещё придумать надо.

[Igors]

Код:

class Data {}
...
    SharedPointer<Data> data() const
    {
         ReadLocker lock;
         return m_data;
    }

    void setData(SharedPointer<Data> d)
    {
         WriteLocker lock;
         m_data = d;
    }

Не понял Вашей задумки: m_data "улетела" (из метода data) и тот кто ее подхватит будет использовать указатель на ее данные. Этот "улетевший" указатель не будет обновлен после setData, в чем тогда смысл?

[m_ax]

Именно так все и делают, за счёт shared_ptr оверхеда здесь мизер. Собственно 2 атомарных операции на захват/отдачу мьютекса + 1 атомарная операция на копирование shared_ptr. В лучшем lockfree решении будет 2 атомарных операции. Только для этого lockfree не оправдано.

А за счёт чего достигается атомарность копирования shared_ptr? Вот например:

Код

C++ (Qt)
shared_ptr<Data> ptr;
DataManager dataManager;
...
ptr = dataManager.data();
 

При копировании, на сколько я понял должно произойти как минимум следующее:
ptr - должен уменьшить свой счётчик ссылок и если он окажется 0 удалить сам объект, скопировать указатель на новые данные и опять увеличить счётчик ссылок.
Наверное я чегото не допонимаю в этом, почему оно атомарно? 
увеличение числа ссылок, копирование указателя на объект