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

[Igors]

Интересно было бы напр. такое

Типовая задача: одна нитка кладет элементы (напр задания) в контейнер, N др. ниток их оттуда изымают. Понятно это легко решается через ReadWriteLock, но только до тех пор пока интенсивность записи/чтения относительно невысока, дальше тормоза. (Q)ReadWriteLock - решение прямолинейное (захват всего контейнера). А как сделать по-умному, напр. захватывая лишь "необходимые" элементы?

[m_ax]

Подправил изначальный вариант AtomicData. Теперь по идеи должно работать коррестно (пока правда только под linux).

Код

C++ (Qt)
#ifndef ATOMICDATA_H
#define ATOMICDATA_H
 
#include <asm/atomic.h>
 
template <class T>
class AtomicData
{
private:
    AtomicData() {
        m_key1 = ATOMIC_INIT(-1);
        m_key2 = ATOMIC_INIT(-1);
    }
    void setData(const T &data) {
        while (!test_for_write(&m_key1, &m_key2));
        // critical section
        m_data = data;
 
        atomic_set(&m_key1, -1);
        atomic_set(&m_key2, -1);
    }
    T getData() const {
        while (!test_for_read(&m_key1));
        // critical section
        T res = m_data;
        atomic_set(&m_key1, -1);
        atomic_set(&m_key2, -1);
        return res;
    }
private:
    atomic_t m_key1;
    atomic_t m_key2;
    T m_data;
 
    static bool test_for_write(atomic_t *key1, atomic_t *key2) {
        bool res1 = atomic_inc_and_test(key1);
        bool res2 = atomic_inc_and_test(key2);
        atomic_set(key1, 0);
        atomic_set(key2, 0);
        return (res1 && res2);
    }
 
    static bool test_for_read(atomic_t *key1) {
        bool res = atomic_inc_and_test(key1);
        atomic_set(&m_key2, 0);
        atomic_set(key1, -1);
        return res;
    }
};
 
 
#endif // ATOMICDATA_H
 

Где atomic_inc_and_test - атомарный инкремент и возвращает true если результат равен нулю.
Флаги m_flag1 и m_flag2:
Если оба равны -1 то никто не читает и никто не пишет (данные свободны)
Если m_flag1 == -1 и m_flag2 != -1 то можно читать (более одного потока).

Но возникла проблема: Нигде не могу найти у себя хедер atomic.h
В каталоге asm его нет  
Где его искать?

[m_ax]

Вобщем найти этот atomic.h так и не удалось, но нашёл cstdatomic (c++0x) где реализован очень удобный шаблон atomic<T>

Код

C++ (Qt)
#ifndef ATOMICDATA_H
#define ATOMICDATA_H
 
#include <cstdatomic>
 
template <class T>
class AtomicData
{
private:
    typedef atomic<int> AtomicInt;
    AtomicData()  : m_key1(-1), m_key2(-1) {}
    void setData(const T &data) {
        while (!test_for_write(m_key1, m_key2));
        // critical section
        m_data = data;
 
        m_key1 = -1;
        m_key2 = -1;
    }
    T getData() const {
        while (!test_for_read(m_key1, m_key2));
        // critical section
        T res = m_data;
        m_key1 = -1;
        m_key2 = -1;
        return res;
    }
private:
    AtomicInt m_key1;
    AtomicInt m_key2;
    T m_data;
 
    static bool test_for_write(AtomicInt &key1, AtomicInt &key2) {
        bool res1 = (++key1 == 0);
        bool res2 = (++key2 == 0);
        key1 = 0;
        key2 = 0;
        return (res1 && res2);
    }
 
    static bool test_for_read(AtomicInt &key1, AtomicInt &key2) {
        bool res = (++key1 == 0);
        key2 = 0;
        key1 = -1;
        return res;
    }
};
 

[Igors]

Код

C++ (Qt)
    static bool test_for_read(AtomicInt &key1, AtomicInt &key2) {
        bool res = (++key1 == 0);
        key2 = 0;
        key1 = -1;
        return res;
    }
};
 

Грабли те же. Да, ++key1 атомарно, так что с того? В момент когда выполняется key2 = 0, др. нитка могла уже сделать с key1 все что угодно и возвращаемый res ничему не соответствует.

Без "идиомы CAS" не обойтись. Просто "присваивание" (напр key1 = -1) почти всегда неверно (хоть и атомарно).

И если уж взялись писать свой ReadWriteLocker, то делайте и "write pending" (запрос на запись) чтобы желающие, увидев этот флаг, не захватывали по чтению - иначе запись может не пробиться.

[m_ax]

Код

C++ (Qt)
    static bool test_for_read(AtomicInt &key1, AtomicInt &key2) {
        bool res = (++key1 == 0);
        key2 = 0;
        key1 = -1;
        return res;
    }
};
 

Грабли те же. Да, ++key1 атомарно, так что с того? В момент когда выполняется key2 = 0, др. нитка могла уже сделать с key1 все что угодно и возвращаемый res ничему не соответствует.

Без "идиомы CAS" не обойтись. Просто "присваивание" (напр key1 = -1) почти всегда неверно (хоть и атомарно).

И если уж взялись писать свой ReadWriteLocker, то делайте и "write pending" (запрос на запись) чтобы желающие, увидев этот флаг, не захватывали по чтению - иначе запись может не пробиться.

Смотрите: Другая нитка конечно можнет сделать с key1 всё что угодно, но результат то уже будет другой)
Например вначале key1 = -1. После первой проверки с инкрементом:

Код

C++ (Qt)
res1 = (++key == 0)
 

Мы получим res1 = true и key1 = 0; Далее другая нитка делает тоже, но key1 будет уже равен 1 и res вернёт false
    

[brankovic]

...

не понял задумки, по этой функции получается, что любой, кто выходит из критической секции её разлочивает. Т.е. 2 треда вошли в секцию, потом один заснул, а другой вышел. Пришёл третий и залочит на запись, SIGSEGV. Я правильно понимаю, что ридеров допускается несколько?

Код

C++ (Qt)
    T getData() const {
        while (!test_for_read(m_key1, m_key2));
        // critical section
        T res = m_data;
        m_key1 = -1;
        m_key2 = -1;
        return res;
    }
 

[Igors]

Код

C++ (Qt)
    static bool test_for_write(AtomicInt &key1, AtomicInt &key2) {
        bool res1 = (++key1 == 0);
        bool res2 = (++key2 == 0);
        key1 = 0;
        key2 = 0;
        return (res1 && res2); 
    }
 

Пусть res1 и res2 оказались равны true. Запрос на запись получен и выполняется m_data = data, В этот момент др. нитка захотела читать

Код

C++ (Qt)
    static bool test_for_read(AtomicInt &key1, AtomicInt &key2) {
        bool res = (++key1 == 0);
        key2 = 0;
        key1 = -1;
        return res;
    }
};
 

Это крутится в while, поэтому на втором витке запрос на чтение также будет успешно получен.
Итого: одна читает, др. (в это же время) пишет (кум рулюе, я газую, iдемо)

Если Вас не затруднит, не могли бы Вы дать хоть как-то осмысленные имена. Что такое key1, key2.- хз. "test_for" лучше заменить на "acquire", т.к. тестирование не имеет смысла при параллельном выполнении  

[m_ax]

brankovic , Igors, Вынужден признать, что Вы правы))
Но уверен, решение близко и грех его не найти))

Если Вас не затруднит, не могли бы Вы дать хоть как-то осмысленные имена. Что такое key1, key2.- хз. "test_for" лучше заменить на "acquire", т.к. тестирование не имеет смысла при параллельном выполнении  

Согласен, исправлю)

[Igors]

Но уверен, решение близко и грех его не найти))

0 - никто не читает и никто не пишет
-1 - одна (и только одна) нитка пишет  STATE_WRITE
> 0 - число читающих

Код

C++ (Qt)
bool AcquireWrite( AtomicInt & state )
{
  if (state > 0) return false;
  return CompareAndSwap(&state, 0, STATE_WRITE);
}
 
void ReleaseWrite( AtomicInt & state )
{
  state = 0;
}
 
bool AcquireRead( AtomicInt & state )
{
  int temp = state;
  if (temp == STATE_WRITE) return false;
  return CompareAndSwap(&state, temp, temp + 1);
}
 
void ReleaseRead( AtomicInt & state )
{
  assert(state > 0);
  --state;
}
 

Здесь нет write_pending - ну чтобы было о чем подумать  

[Akon]

Пришло в голову вот такое lockfree решение для вышеупомянутого DataManager. Это решение для одного писателя и нескольких читателей (если писателей несколько, то их пришлось бы синхронизировать).

Код:

struct Data 
{
	int a;
	int b;
	...

	Data& directAssignment(const Data& other)
	{
		a = other.a;
		b = other.b;
		...
		return *this;
	}

	Data& reverseAssignment(const Data& other)
	{
		b = other.b;
		a = other.a;
		...
		return *this;
	}
};

class DataManager
{
public:
	// called by reader threads (several threads)
	const Data data() const
	{
		const Data result = m_data1;

		while (result != m_data2)
			result = m_data1;

		return result;
	}

	// called by writer thread (single thread)
    void setData(const Data& value)
    {
		if (value == m_data1) return;

		m_data1.directAssignment(value);
		m_data2.reverseAssignment(value);
    }

private:
	volatile Data m_data1;
	volatile Data m_data2;
}

В коде нет ни одной блокировки! Имеются два присваивания - в прямом и инверсном порядке, что гарантирует консистентность Data для читателей.

Чем платим:
1. const Data data() const: одна операция !=, выполняемая всегда; тело цикла (с условием) выполняются только в момент записи писателем.
2. void setData(const Data& value): дополнительное инверсное присваивание.
3. Если класс Data достаточно "тяжел" в плане присваиваний, то эффективность, очевидно, падает.


 

[Igors]

Ну операции сравнения и присваивания для структур могут быть недешевы. Как я понял, в любом случае читатель получит "консистентный снапшот" (пусть не всегда обновленный), но тогда проще обойтись без 2 вариантов assignment, а просто сравнивать старую копию с новой. А вот на первый взгляд простой способ: пусть писатель взводит/сбрасывает флажок mDataValid здесь не пройдет 

[Akon]

...а просто сравнивать старую копию с новой...

В этом случае читатель может получить неконсистентные данные.

[brankovic]

Код

C++ (Qt)
	const Data data() const
	{
		const Data result = m_data1; /*B*/
 
		while (result != m_data2)
			result = m_data1;
 
		return result;
	}
 
    void setData (const Data & value)
    {
		if (value == m_data1) return;
 
		m_data1.directAssignment(value); /*A*/
		m_data2.reverseAssignment(value);
    }
 

void setData(const Data& value)
тред A дошёл до строки m_data1.directAssignment(value); в void setData(const Data& value);
тред B дошёл до строки const Data result = m_data1; в const Data data() const;

и они начали одновременно первый писать в m_data1, второй читать из него. В чём тогда синхронизация?
      

[Igors]

В этом случае читатель может получить неконсистентные данные.

Прошу показать каким образом.

и они начали одновременно первый писать в m_data1, второй читать из него. В чём тогда синхронизация?

Да, если напр будет член std::vector, то рухнет. Но если копирование thread-safe (напр то же Qt shallow copy), то это неопасно, будет копироваться еще пока 2 копии не совпадут. В общем тот же CAS (слегка извращенный  )

[brankovic]

Да, если напр будет член std::vector, то рухнет. Но если копирование thread-safe (напр то же Qt shallow copy), то это неопасно

Уверен и там не всё складно с этим присваиванием наоборот и operator==, который тоже не атомарен. Просто привёл самый очевидный изъян.

Edit: кстати, shallow копирование довольно сложно реализовать полностью thread safe. Вы уверены, что QString, например, не падает при одновременном чтении и присвоении?