Практическая операция сравнения и замены нескольких слов

10

В статье с тем же названием, что и у этого вопроса, авторы описывают, как построить неблокирующую линеаризуемую операцию 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 по-прежнему поддерживает семантику инструкции двойного сравнения с одним свопом, которая является линеаризуемой и свободной от блокировки ? (строка с !!комментарием)

Если нет, можете ли вы описать сценарий, где эта строка действительно необходима для обеспечения правильности?

Спасибо.

axel22
источник
Во-первых, чтобы понять, что происходит, нам нужно увидеть структуру данных RDCSSDescriptor_t. Во-вторых, это, вероятно, не по теме здесь, поскольку это не имеет отношения к теоретической информатике; было бы лучше спросить об этом на stackoverflow.com.
Дэйв Кларк,
Ссылка на статью не работает.
Аарон Стерлинг
1
Прошу прощения за ссылку - теперь должно работать. Я обновил вопрос, чтобы описать, что такое дескриптор. Причина, по которой я не разместил это на stackoverflow.com, состоит в том, что в FAQ говорится, что этот сайт предназначен для вопросов исследовательского уровня в области компьютерных наук. Я думал, что вопросы свободы блокировки и линеаризуемости алгоритма квалифицируются как таковые. Я надеюсь, что неправильно понял FAQ.
axel22
Ключевое слово, которое вы пропустили в FAQ, было «теоретическим». Поскольку некоторые люди находят этот вопрос интересным, я оставлю его открытым.
Дейв Кларк,
3
@Dave: я не эксперт в этой области, но для меня это звучит как очень типичный вопрос TCS. Вам дают две модели вычислений (A: с CAS с одним словом, B: с CAS с несколькими словами) и меру сложности (количество CAS), и вас спрашивают, можете ли вы смоделировать модель B в модели A, и с какими наихудшими накладными расходами. (Здесь может быть немного вводит в заблуждение, что симуляция дается как кусок кода на C, а не псевдокод; это может указывать на то, что это связано с реальными задачами программирования.)
Юкка Суомела

Ответы:

9

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

У нас есть ВСТРОЕННЫЙ АТОМНЫЙ CAS1, имеющий эту семантику:

int CAS1(int *addr, int oldval, int newval) {
  int currval = *addr;
  if (currval == oldval) *addr = newval;
  return currval;
}

Нам нужно определить функцию ATOMIC RDCSS с использованием CAS1 и иметь следующую семантику:

int RDCSS(int *addr1, int oldval1, int *addr2, int oldval2, int newval2) {
  int res = *addr;
  if (res == oldval2 && *addr1 == oldval1) *addr2 = newval2;
  return res;
}

Интуитивно понятно: нам нужно ПОСТОЯННО изменять значение в addr2, только если * addr1 == oldval1 ... если другой поток изменяет его, мы можем помочь другому потоку завершить операцию, затем мы можем повторить попытку.

Функция RDCSS будет использоваться (см. Статью) для определения CASN. Теперь мы определим дескриптор RDCSS следующим образом:

RDCSSDESCRI
int *addr1   
int oldval1
int *addr2   
int oldval2
int newval2

Затем мы реализуем RDCSS следующим образом:

int RDCSS( RDCSSDESCRI *d ) {
  do {
    res = CAS1(d->addr2, d->oldval2, d);  // STEP1
    if (IsDescriptor(res)) Complete(res); // STEP2
  } while (IsDescriptor(res);             // STEP3
  if (res == d->oldval2) Complete(d);     // STEP4
  return res;
}

void Complete( RDCSSDESCRI *d ) {
  int val = *(d->addr1);
  if (val == d->oldval1) CAS1(d->addr2, d, d->newval2);
    else CAS1(d->addr2, d, d->oldval2);  
}
  • ШАГ1: сначала мы пытаемся изменить значение * addr2 на наш (собственный) дескриптор d, если CAS1 завершается успешно, то res == d-> oldval2 (т.е. res НЕ является дескриптором)
  • STEP2: проверить, является ли res дескриптором, т. Е. Произошел сбой STEP1 (другой поток изменил addr2) ... помочь другому потоку завершить операцию
  • ШАГ3: повторите попытку ШАГ1, если нам не удалось сохранить наш дескриптор d
  • ШАГ 4: если мы получили ожидаемое значение из addr2, то нам удалось сохранить наш дескриптор (указатель) в addr2, и мы можем завершить нашу задачу сохранения newval2 в * addr2 iif * addr1 == oldval1

ОТВЕТЬТЕ НА ВАШ ВОПРОС

Если мы пропустим STEP4, тогда часть if (... && * addr1 == oldval1) * addr2 = newval2 семантики RDCSS никогда не будет выполнена (... или лучше: она может выполняться непредсказуемым образом другими потоками, помогая текущий).

Как вы указали в своем комментарии, условие, если (res == d1-> oldval2) в STEP4 не нужно: даже если мы его опускаем, оба CAS1 в Complete () завершатся неудачно, потому что * (d-> addr2)! = D , Его единственная цель - избежать вызова функции.

Пример T1 = резьба1, T2 = резьба2:

remember that addr1 / addr2 are in a shared data zone !!!

T1 enter RDCSS function
T2 enter RDCSS function
T2 complete STEP1 (and store the pointer to its descriptor d2 in addr2)
T1 at STEP1 the CAS1 fails and res = d2
T2 or T1 completes *(d2->addr2)=d2->newval2 (suppose that *(d2->addr1)==d2->oldval1)
T1 execute STEP1 and now CAS1 can fail because *addr2 == d2->newval2
   and maybe d2->newval2 != d1->oldval2, in every case at the end 
   res == d2->newval2 (fail) or
   res == d1->oldval2 (success)
T1 at STEP2 skips the call to Complete() (because now res is not a descriptor)
T1 at STEP3 exits the loop (because now res is not a descriptor)
T1 at STEP4 T1 is ready to store d1->newval2 to addr2, but only if
   *(d1->addr2)==d (we are working on our descriptor) and *(d1->addr1)==d1->oldval1
   ( Custom() function)
Марцио де Биаси
источник
Спасибо, хорошее объяснение. Я полностью упустил момент, что CAS1 возвращает старое значение, а не новое.
axel22
Но в сценарии последние 2 строки говорят, что: без условия в STEP4, T1 может хранить значение, потому что addr2содержит d2->newval2. Но мне кажется, что CAS1 в состоянии Completeпросто потерпит неудачу, потому что он ожидает, что старое значение будет дескриптором d1- ничего не будет записано T1. Правильно?
axel22
@ axel22: я пропустил CAS1 в Complete () :-D. Да, вы правы ... мой пример неверен, условие if используется только для того, чтобы избежать вызова функции, если мы отбрасываем if (), ничего не меняется. Очевидно, что Complete (d) на STEP4 необходимо. Теперь я модифицирую пример.
Марцио Де Биаси
Насколько я знаю, избегать CAS, который мы ожидаем, - это метод оптимизации кэша, поскольку на реальном оборудовании это обычно имеет негативные последствия, такие как очистка строк кэша и получение эксклюзивного доступа к строке кэша. Я предполагаю, что автор статьи хотел, чтобы алгоритм был как можно более практичным в дополнение к правильности.
Тим Сегин