Russian Qt Forum
Июнь 15, 2024, 23:18 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: 1 ... 3 4 [5] 6 7   Вниз
  Печать  
Автор Тема: AtomicData или механизм атомарной операции записи данных  (Прочитано 44135 раз)
Akon
Гость
« Ответ #60 : Март 28, 2011, 23:10 »

Да нет, тоже не пойдет
Записан
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« Ответ #61 : Март 29, 2011, 10:20 »

Хм.. Ещё один вариант, надеюсь последний)
Код
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 пишет
исключена.
« Последнее редактирование: Март 29, 2011, 10:23 от m_ax » Записан

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
brankovic
Гость
« Ответ #62 : Март 29, 2011, 10:45 »

Хм.. Ещё один вариант, надеюсь последний)
Код
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
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #63 : Март 29, 2011, 10:58 »

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

а, понятно, думал о wait-free речь пойдёт. Никогда такую оптимизацию в действии не видел. Но интересно, что здесь сложного? Казалось бы раз в n циклов вызывать yeild, и всё?
Пробовал  Улыбающийся Довольно трудно найти баланс, просто yield ощутимо тормозит текущую задачу, просто прокрутка - остальные, причем нужно подстраиваться под конкретную машину. Ну и вся эта песня платформо-зависима.
Записан
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« Ответ #64 : Март 29, 2011, 10:58 »

Цитировать
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;
   }
 
Улыбающийся
Записан

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« Ответ #65 : Март 29, 2011, 11:10 »

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

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
brankovic
Гость
« Ответ #66 : Март 29, 2011, 11:49 »

а мы вот так:
Код
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), легко реализовать?
« Последнее редактирование: Март 29, 2011, 11:53 от brankovic » Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #67 : Март 29, 2011, 11:50 »

а мы вот так:
Код
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
Гость
« Ответ #68 : Март 29, 2011, 12:02 »

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

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

Сообщений: 2094



Просмотр профиля
« Ответ #69 : Март 29, 2011, 12:22 »

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

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

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

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« Ответ #70 : Март 29, 2011, 18:07 »

Никак не даёт покоя идея реализации этого злосчастного 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 нужин лишь для того, чтобы отобрать какой либо один поток для записи.  

Как Вам такой вариант?  Улыбающийся
« Последнее редактирование: Март 29, 2011, 18:10 от m_ax » Записан

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Akon
Гость
« Ответ #71 : Март 29, 2011, 18:56 »

R0 читает; state == STATE_READ
R1 читает; state == STATE_READ и дочитывает; state == STATE_FREE
W0 начинает писать (в то время как R0 все еще читает)
Записан
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2094



Просмотр профиля
« Ответ #72 : Март 29, 2011, 19:12 »

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
 
Вот так)
Записан

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #73 : Март 29, 2011, 20:32 »

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
Гость
« Ответ #74 : Март 30, 2011, 00:06 »

Код
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 и завис
« Последнее редактирование: Март 30, 2011, 00:25 от brankovic » Записан
Страниц: 1 ... 3 4 [5] 6 7   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.254 секунд. Запросов: 22.