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

[Akon]

Да нет, тоже не пойдет

[m_ax]

Хм.. Ещё один вариант, надеюсь последний)

Код

C++ (Qt)
#ifndef SPINLOCK_H
#define SPINLOCK_H
 
#include <assert.h>
#include <cstdatomic>
 
template <class T>
class SpinLock
{
public:
    typedef atomic<int> AtomicInt;
    SpinLock()  : m_count_readers(0), m_state_write(-1) {}
 
    void setData(const T &data) {
        while (!acquireWrite(m_count_readers, m_state_write));
        m_data = data;
        releaseWrite(m_state_write);
    }
    T getData() const {
        while (!acquireRead(m_count_readers, m_state_write));
        T data = m_data;
        releaseRead(m_count_readers, m_state_write);
        return data;
    }
private:
    AtomicInt m_count_readers;
    AtomicInt m_state_write;
    T m_data;
 
    static bool acquireWrite(AtomicInt &readers, AtomicInt &state_write) {
 
        bool tmp = (++state_write == 0);
        state_write = 0;
 
        return (tmp && !readers);
    }
    //-------------------------------------------------------------------------
 
    static void releaseWrite(AtomicInt &state_write) {
        state_write = -1;
    }
    //-------------------------------------------------------------------------
 
    static bool acquireRead(AtomicInt &readers, AtomicInt &state_write) {
 
        readers++;
        bool tmp = (++state_write == 0);
        state_write = 0;
 
        if (tmp) {
            state_write = -1;
            return true;
        }
        readers--;
        return false;
    }
    //-------------------------------------------------------------------------
 
    static void releaseRead(AtomicInt &readers, AtomicInt &state_write) {
        if(--readers == 0)
            state_write = -1;
    }
    //-------------------------------------------------------------------------
};
 
 
#endif // SPINLOCK_H
 

Во всяком случае, ситуация описанная brankovic:

R0 читал
R1 дошёл до if, увидел, что кто-то читает, отправился на else
R1 заснул
R0 ушёл (readers == 0)
W пришёл и захватил на запись
R1 проснулся, сделал ++readers и вернул true

теперь R0 читает, а W пишет

исключена.

[brankovic]

Хм.. Ещё один вариант, надеюсь последний)

Код

C++ (Qt)
    static bool acquireWrite(AtomicInt &readers, AtomicInt &state_write) {
 
        bool tmp = (++state_write == 0);
        state_write = 0;
 
        return (tmp && !readers);
    }
 
    static void releaseRead(AtomicInt &readers, AtomicInt &state_write) {
        if(--readers == 0)
            state_write = -1;
    }
};
 

R читает
W пришёл и сделал bool tmp = (++state_write == 0);
R вышел и установил state_write = -1
W установил state_write = 0 и завис навсегда

[Igors]

Если удасца реализовать первоночальный SpinLock, то его можно будет ускорить создав буфер даных. Тогда простои при записи и чтении можно будет существенно сократить. 

Не понял, расскажите подробнее

а, понятно, думал о wait-free речь пойдёт. Никогда такую оптимизацию в действии не видел. Но интересно, что здесь сложного? Казалось бы раз в n циклов вызывать yeild, и всё?

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

[m_ax]

R читает
W пришёл и сделал bool tmp = (++state_write == 0);
R вышел и установил state_write = -1
W установил state_write = 0 и завис навсегда

а мы вот так:

Код

C++ (Qt)
static bool acquireWrite(AtomicInt &readers, AtomicInt &state_write) {
 
        bool tmp = (++state_write == 0);
        if (tmp && !readers)
            return true;
 
        state_write = 0;
        return false;
    }
 

[m_ax]

Если удасца реализовать первоночальный SpinLock, то его можно будет ускорить создав буфер даных. Тогда простои при записи и чтении можно будет существенно сократить. 

Не понял, расскажите подробнее

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

[brankovic]

а мы вот так:

Код

C++ (Qt)
static bool acquireWrite(AtomicInt &readers, AtomicInt &state_write) {
 
        bool tmp = (++state_write == 0);
        if (tmp && !readers)
            return true;
 
        state_write = 0;
        return false;
    }
 

никого не было
W вызвал acquireWrite и дошёл до if (tmp && !readers)
R вызвал acquiteRead и сделал ++readers
W испугался и вернул false

теперь state_write == 0 и никогда не станет равным -1, R и W зависли

Edit: вообще как на счёт обычного лока (не rw), легко реализовать?

[Igors]

а мы вот так:

Код

C++ (Qt)
static bool acquireWrite(AtomicInt &readers, AtomicInt &state_write) {
 
        bool tmp = (++state_write == 0);
        if (tmp && !readers)
            return true;
 
        state_write = 0;
        return false;
    }
 

Так то же самое: перед выполнением state_write = 0; все readers могли отстреляться, имеем deadlock, т.к. никто не может снять state_write с нуля. И как бы Вы ни крутили, без CAS дырка всегда найдется  

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

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

[SimpleSunny]

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

Отдаленно похожая, но тоже интересная, идея обсуждалась тут (http://alenacpp.blogspot.com/2010/07/blog-post_30.html).

[m_ax]

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

Отдаленно похожая, но тоже интересная, идея обсуждалась тут (http://alenacpp.blogspot.com/2010/07/blog-post_30.html).

Интересно) Спасибо, меня тут как раз одна идея осинила)

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

Хорошо, как освобожусь так напишу в отдельную тему)

[m_ax]

Никак не даёт покоя идея реализации этого злосчастного SpinLock.
Несколько пересмотрел логику и теперь это выглядит так:

Код

C++ (Qt)
#ifndef SPINLOCK_H
#define SPINLOCK_H
 
#include <assert.h>
#include <cstdatomic>
 
template <class T>
class SpinLock
{
public:
    typedef atomic<int> AtomicInt;
    SpinLock()  : m_key(-1), m_state(STATE_FREE) {}
 
    void setData(const T &data) {
        while (!acquireWrite(m_key, m_state));
        m_data = data;
        releaseWrite(m_key, m_state);
    }
    T getData() const {
        while (!acquireRead(m_key, m_state));
        T data = m_data;
        releaseRead(m_key, m_state);
        return data;
    }
private:
    enum { STATE_FREE = 0, STATE_READ = 1, STATE_WRITE = 2, STATE_READ_AND_WRITE = 3 };
    AtomicInt m_key;
    AtomicInt m_state;
    T m_data;
    //-------------------------------------------------------------------------
 
    static bool acquireWrite(AtomicInt &key, AtomicInt &state) {
 
        int tmp = (state |= STATE_WRITE);
        if (tmp == STATE_READ_AND_WRITE) {
            state = STATE_READ;
            return false;
        }
        bool tmp2 = (++key == 0);
        key = 0;
        return tmp2;
    }
    //-------------------------------------------------------------------------
 
    static void releaseWrite(AtomicInt &key, AtomicInt &state) {
        state = STATE_FREE;
        key = -1;
    }
    //-------------------------------------------------------------------------
 
    static bool acquireRead(AtomicInt &/*key*/, AtomicInt &state) {
 
        int tmp = (state |= STATE_READ);
        if (tmp == STATE_READ)
            return true;
        state = STATE_WRITE;
        return false;
 
    }
    //-------------------------------------------------------------------------
 
    static void releaseRead(AtomicInt &/*key*/, AtomicInt &state) {
       state = STATE_FREE;
    }
    //-------------------------------------------------------------------------
};
 
 
#endif // SPINLOCK_H
 

Краткое описание:
Есть две переменные key и state.
state может принимать следующие значения:
00 = 0 - STATE_FREE;
01 = 1 - STATE_READ;
10 = 2 - STATE_WRITE;
11 = 3 - STATE_READ_AND_WRITE; (виртуальное состояние)

key нужин лишь для того, чтобы отобрать какой либо один поток для записи.  

Как Вам такой вариант?  

[Akon]

R0 читает; state == STATE_READ
R1 читает; state == STATE_READ и дочитывает; state == STATE_FREE
W0 начинает писать (в то время как R0 все еще читает)

[m_ax]

R0 читает; state == STATE_READ
R1 читает; state == STATE_READ и дочитывает; state == STATE_FREE
W0 начинает писать (в то время как R0 все еще читает)

Согласен 

Исправил этот момент, введя счётчик читающих потоков: m_counter. Теперь state = STATE_FREE только когда все читатели перестанут читать:

Код

C++ (Qt)
#ifndef SPINLOCK_H
#define SPINLOCK_H
 
#include <assert.h>
#include <cstdatomic>
 
template <class T>
class SpinLock
{
public:
    typedef atomic<int> AtomicInt;
    SpinLock()  : m_key(-1), m_state(STATE_FREE), m_counter(0) {}
 
    void setData(const T &data) {
        while (!acquireWrite(m_key, m_state));
        m_data = data;
        releaseWrite(m_key, m_state);
    }
    T getData() const {
        while (!acquireRead(m_counter, m_state));
        T data = m_data;
        releaseRead(m_counter, m_state);
        return data;
    }
private:
    enum { STATE_FREE = 0, STATE_READ = 1, STATE_WRITE = 2, STATE_READ_AND_WRITE = 3 };
    AtomicInt m_key;
    AtomicInt m_state;
    AtomicInt m_counter;
    T m_data;
    //-------------------------------------------------------------------------
 
    static bool acquireWrite(AtomicInt &key, AtomicInt &state) {
 
        int tmp = (state |= STATE_WRITE);
        if (tmp == STATE_READ_AND_WRITE) {
            state = STATE_READ;
            return false;
        }
        bool tmp2 = (++key == 0);
        key = 0;
        return tmp2;
    }
    //-------------------------------------------------------------------------
 
    static void releaseWrite(AtomicInt &key, AtomicInt &state) {
        state = STATE_FREE;
        key = -1;
    }
    //-------------------------------------------------------------------------
 
    static bool acquireRead(AtomicInt &counter, AtomicInt &state) {
 
        int tmp = (state |= STATE_READ);
        if (tmp == STATE_READ) {
            counter++;
            return true;
        }
        state = STATE_WRITE;
        return false;
 
    }
    //-------------------------------------------------------------------------
 
    static void releaseRead(AtomicInt &counter, AtomicInt &state) {
        if (--counter == 0)
            state = STATE_FREE;
    }
    //-------------------------------------------------------------------------
};
 
 
#endif // SPINLOCK_H
 

Вот так)

[Igors]

m_ax, просьба: давайте по пустому не месить и форум понапрасну не утомлять.

Догнать а что же такое STATE_READ_AND_WRITE - мудрено. Что-то типа "Rat but blue"?  

Код

C++ (Qt)
    static bool acquireRead(AtomicInt &counter, AtomicInt &state) {
 
        int tmp = (state |= STATE_READ);
        if (tmp == STATE_READ) {
 

Как уже не раз говорилось, между этими 2-мя строчками может произойти многое, "просто if" здесь не катит (поезд уже ушел)

Я уважаю желание "докопаться самому" и с подозрением отношусь к "начитавшимся классов", но чего ж об один камень 10 раз спотыкаться?    Зачем упорно избегать CAS который предназначен для решения таких коллизий? Зачем рыть себе яму привлекая вторую переменную за которой надо (мучительно) следить?

[brankovic]

Код

C++ (Qt)
    static bool acquireWrite(AtomicInt &key, AtomicInt &state) {
 
        int tmp = (state |= STATE_WRITE);
        if (tmp == STATE_READ_AND_WRITE) {
            state = STATE_READ;
            return false;
        }
 

R читал
W пришёл и сделал state |= STATE_WRITE, state == STARE_READ_WRITE
R закончил чтение, state = STATE_FREE
W сделал state = STATE_READ и завис