В статье с тем же названием, что и у этого вопроса, авторы описывают, как построить неблокирующую линеаризуемую операцию CAS с несколькими словами, используя только CAS с одним словом. Сначала они вводят операцию двойного сравнения-одиночного обмена - RDCSS следующим образом:
word_t RDCSS(RDCSSDescriptor_t *d) {
do {
r = CAS1(d->a2, d->o2, d);
if (IsDescriptor(r)) Complete(r);
} while (IsDescriptor(r));
if (r == d->o2) Complete(d); // !!
return r;
}
void Complete(RDCSSDescriptor_t *d) {
v = *(d->a1);
if (v == d->o1) CAS1(d->a2, d, d->n2);
else CAS1(d->a2, d, d->o2);
}
где RDCSSDescriptor_t
это структура со следующими полями:
a1
- адрес первого условияo1
- значение ожидается по первому адресуa2
- адрес второго условияo2
- значение ожидается по второму адресуn2
- новое значение записывается по второму адресу
Этот дескриптор создается и инициализируется один раз в потоке, который инициирует операцию RDCSS - ни один другой поток не имеет ссылки на него, пока не выполнится первый CAS1 в функции RDCSS
, что сделает дескриптор достижимым (или активным в терминологии статьи).
Идея алгоритма заключается в следующем: замените вторую ячейку памяти дескриптором, сообщающим, что вы хотите сделать. Затем, учитывая, что дескриптор присутствует, проверьте первую ячейку памяти, чтобы увидеть, изменилось ли ее значение. Если это не так, замените дескриптор во второй ячейке памяти новым значением. В противном случае установите вторую ячейку памяти обратно к старому значению.
Авторы не объясняют, почему !!
в статье необходима строка с комментарием. Мне кажется, что CAS1
инструкции в Complete
функции всегда будут давать сбой после этой проверки, при условии, что нет одновременной модификации. И если произошла одновременная модификация между проверкой и входом CAS Complete
, то поток, выполняющий проверку, все равно должен потерпеть неудачу со своим CAS Complete
, так как одновременная модификация не должна использовать тот же дескриптор d
.
Мой вопрос: можно ли пропустить проверку в функции RDCSSS
, if (r == d->o2)...
если RDCSS по-прежнему поддерживает семантику инструкции двойного сравнения с одним свопом, которая является линеаризуемой и свободной от блокировки ? (строка с !!
комментарием)
Если нет, можете ли вы описать сценарий, где эта строка действительно необходима для обеспечения правильности?
Спасибо.
источник
Ответы:
В параллельной среде выполнения простые вещи могут показаться странными ... надеюсь, это поможет.
У нас есть ВСТРОЕННЫЙ АТОМНЫЙ CAS1, имеющий эту семантику:
Нам нужно определить функцию ATOMIC RDCSS с использованием CAS1 и иметь следующую семантику:
Интуитивно понятно: нам нужно ПОСТОЯННО изменять значение в addr2, только если * addr1 == oldval1 ... если другой поток изменяет его, мы можем помочь другому потоку завершить операцию, затем мы можем повторить попытку.
Функция RDCSS будет использоваться (см. Статью) для определения CASN. Теперь мы определим дескриптор RDCSS следующим образом:
Затем мы реализуем RDCSS следующим образом:
ОТВЕТЬТЕ НА ВАШ ВОПРОС
Если мы пропустим STEP4, тогда часть if (... && * addr1 == oldval1) * addr2 = newval2 семантики RDCSS никогда не будет выполнена (... или лучше: она может выполняться непредсказуемым образом другими потоками, помогая текущий).
Как вы указали в своем комментарии, условие, если (res == d1-> oldval2) в STEP4 не нужно: даже если мы его опускаем, оба CAS1 в Complete () завершатся неудачно, потому что * (d-> addr2)! = D , Его единственная цель - избежать вызова функции.
Пример T1 = резьба1, T2 = резьба2:
источник
addr2
содержитd2->newval2
. Но мне кажется, что CAS1 в состоянииComplete
просто потерпит неудачу, потому что он ожидает, что старое значение будет дескрипторомd1
- ничего не будет записано T1. Правильно?