C++ (Qt)
class mutex
{
   atomic_int key = -1;
 public:
   lock ()
   {
       int tmp = 0;
       do {
          tmp = ++key;
          if (tmp) key--;
      } while (tmp != 0);
   }
 
   unlock ()
   {
      key = -1;
   }
};
 

Цитата: Akon от Март 30, 2011,  09:08

Нужно увеличивать скважность импульса, например, отказаться от остатка кванта

кажется я понимаю! ..да нет, кого я обманываю..

Но интересный вариант Вы описали, правда смущает ограничение на одного пишущего и завис писателя, если поток читателей постоянный. Но в реализации подкопаться не к чему (кроме опечатки . А работает это потому, что каждая атомарная переменная используется только в атомарных операциях, а m_ax всё время компрометировал атомарность присвоением. Если отказаться от присвоений, то задача становится проще, потому что огород городить сложнее.

Цитата: Igors от Март 30, 2011,  17:32

1) Ну "только один писатель" вполне usable, а вот без pending (запрос на запись) прожить трудно.

Кстати, зачем write_pending, почему нельзя просто ставить write (как у Akon, только CAS вместо fetchAndXor)? Ну то есть чтобы читатели не подвесили писателя, как я понял понял, но вроде бы одного write достаточно и короче получится, нет?


Собственно с CAS это другой класс задач уже, тут можно уже делать wait-free, не то что спинлоки (кстати, CAS сам по себе такое же wait-free, как и атомарный ++).

Теперь по сути задачи, которую решал m_ax: как сделать рв-спинлок без CAS? Как известно в математике и некоторых дугих религиях, задача станет ещё проще, если отказаться от задачи. А именно, реализовать обычный, а не рв-лок, например так:

Код

C++ (Qt)
struct mutex
{
   atomic_int n = 0;
   int level = 1;
 
   lock ()
   {
       int nn = ++n; //atomic pre increment
       while (nn != level);
   }
 
   unlock ()
   {
      level = nn + 1; //non-atomic, but protected by our newborn mutex!
   }
};
 

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

C++ (Qt)
void unlock ()
{
    level++;
}
 

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
 

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
 

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;
    }
 

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
 

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) {
 
        if (!readers) {
            int tmp = (++state_write == 0);
            readers = tmp;
        }
        else
            readers++;
 
        return readers;
    }
    //-------------------------------------------------------------------------
 
    static void releaseRead(AtomicInt &readers, AtomicInt &state_write) {
        if (--readers == 0)
            state_write = -1;
    }
    //-------------------------------------------------------------------------
};
 
#endif // SPINLOCK_H
 

C++ (Qt)
static bool acquireRead(AtomicInt &readers, AtomicInt &state_write) {
 
        if (!readers) {
            int tmp = (++state_write == 0);
            readers = tmp;
        }
        else
            readers++;
 
        return readers;
    }
 

C++ (Qt)
        if (!readers)
            readers = (state_write == -1);
 

C++ (Qt)
static bool acquireRead(AtomicInt &readers, AtomicInt &state_write) {
 
        if (!readers)
            readers = 1; // атомарно
            int tmp = (state_write == -1); // атомарно
            readers = tmp; // атомарно
        else
            readers++;
 
        return readers;
    }