Варианты реализации lock-free алгоритма

#cpp #c #lock_free

Допустим, есть класс:

class LockFree 
{
   LockFree(int num) : n(num) {}
   int next() {n += 1; return n;}
private:
   int n;
};


Какие есть стандартные методы организовать lock-free доступ к n?
То есть, интересует lock-free (без мьютексов) реализация функции next(), которую
можно было бы использовать в многопоточной многоядерной системе.

Было бы круто узнать как о возможностях современного стандарта (вероятно это std::atomic
+ варианты compare_exchange), так и о самопальных велосипедах, которые можно было бы
использовать в plain c.
    

Ответы

Ответ 1

Самый простой метод:

class LockFree 
{
   LockFree(int num) : n(num) {}
   int next() {return ++n;}
private:
   std::atomic n;
};


Это покроет все Ваши нужды в 99% случаев.




  а если next() будет вида next() { return n + n^2 + n^3; }


Тогда будет так:

int next()
{
    int oldN = n;
    while(true)
    {
        int newN = oldN + oldN*oldN + oldN*oldN*oldN;
        if(n.compare_exchange_strong(oldN, newN))
            return newN;
    }
}


Ответ 2

Больше чтобы не забыть, вариант ответа от ixSci на С:

#include 

int next(atomic_int *n)
{
    int oldN = atomic_load(&n);
    while (1)
    {
        int newN = oldN + oldN*oldN + oldN*oldN*oldN;
        if (atomic_compare_exchange_strong(n, &oldN, newN))
        {
            return newN;
        }
    };
}