Можно ли реализовать CompareExchange с помощью CompareAndSwap?

Question

Предполагая, что CompareAndSwap (или CAS) никогда не завершается сбоем, может ли CompareExchange быть реализован с CAS?

CompareExchange принимает указатель, ожидаемое значение и новое значение и атомарно устанавливает в памяти, на которую ссылается указатель, новое значение, если оно соответствует ожидаемому значению. Разница между ними заключается в том, что CompareExchange возвращает предыдущее значение области памяти, а CompareAndSwap возвращает логическое значение, указывающее успех или неудачу.

Реализовать CAS с CompareExchange тривиально:

int CompareExchange (int* p, int expected, int newvalue);

bool CAS (int* p, int expected, int newvalue)
{
   return CompareExchange (p, expected, newvalue) != expected;
}

... но возможно ли реализовать CompareExchange с CAS? Все попытки, которые я видел, либо имеют условия гонки, либо не гарантируют свойства без блокировки. Я не верю, что это возможно.

Answer 1

Я не понимаю, как это возможно. В случае сбоя CAS вам потребуется отдельная операция для получения предыдущего значения. Эта отдельная операция не будет атомарной по отношению к CAS.

Вы можете получить часть пути туда:

int CompareExchnage(int *p, int expected, int newvalue)
{
    if (CAS(p, expected, newvalue))
        return expected;
    else
        ???;
}

Это тот случай, когда CAS дает сбой, когда у вас есть проблемы. Получение *p для определения того, что является предыдущим значением, не будет атомарным относительно CAS, поэтому у вас либо есть состояние гонки, либо вам придется ограничиться CAS и разыменованием *p.

Answer 2

Вы можете, и это без блокировки, но это не без ожидания:

int CompareExchange(int *p, int expected, int newvalue)
{
    for (;;) {
        oldValue = *p;
        if (oldValue != expected)
            return oldValue;
        if (CAS(p, expected, newvalue))
            return expected;
    }
}

Идея состоит в том, что модификация * p после возврата из CompareExchange неотличима от модификации между двумя ifs.

Точно так же вы можете реализовать атомарный обмен и атомарную выборку и операцию на основе CAS, но она не будет без ожидания.