Семафор должен быть атомарным. Это?

Этот фрагмент кода исходит от источника Pintos: https://www.cs.usfca.edu/~benson/cs326/pintos/pintos/src/threads/synch.c

void
sema_down (struct semaphore *sema) 
{
  enum intr_level old_level;

  ASSERT (sema != NULL);
  ASSERT (!intr_context ());

  old_level = intr_disable ();
  while (sema->value == 0) 
    {
      list_push_back (&sema->waiters, &thread_current ()->elem);
      thread_block ();
    }
  sema->value--;
  intr_set_level (old_level);
}

Факт принятия семафора sema->value--;. Если он работает, это должна быть атомная операция. Как мы можем знать, что это атомная операция? Я знаю, что современный процессор гарантирует, что операция с совмещенной памятью (для слова/двойного слова/квад-слова - это зависит от) - атомарная. Но здесь я не уверен, почему он атомный.

Ответы

Ответ 1

TL: DR: все атомарно, если вы делаете это с отключенными прерываниями в системе UP, если вы не учитываете системные устройства, наблюдающие память с DMA.

Обратите внимание на intr_disable();/intr_set_level (old_level); вокруг операции.

современный процессор гарантирует, что согласованная работа памяти является атомарной

Для многопоточных наблюдателей это относится только к отдельным загрузкам или хранилищам, а не к операциям чтения-изменения-записи.

Чтобы что-то было атомарным, мы должны рассмотреть, о каких потенциальных наблюдателях мы заботимся. Важно то, что ничто не может наблюдать за операцией как за частично произошедшей. Самый простой способ достичь этого - это чтобы операция была физически/электрически мгновенной и влияла на все биты одновременно (например, нагрузка или накопитель на параллельной шине переходят от незапущенного к завершенному на границе тактового цикла, поэтому это атомно "бесплатно" до ширины параллельной шины). Это невозможно для чтения-изменения-записи, где лучшее, что мы можем сделать, это помешать наблюдателям смотреть между загрузкой и хранилищем.

Мой ответ на атомарность на x86 объяснил то же самое по-другому, о том, что значит быть атомным.

В однопроцессорной (UP) системе единственными асинхронными наблюдателями являются другие системные устройства (например, DMA) и обработчики прерываний. Если мы можем исключить наблюдателей без CPU из записи в наш семафор, то это просто атомарность по отношению к прерываниям, которые нас интересуют.

Этот код выбирает легкий путь и отключает прерывания. Это не обязательно (или, по крайней мере, не было бы, если бы мы писали в asm).

Прерывание обрабатывается между двумя инструкциями, а не в середине инструкции. Архитектурное состояние машины либо включает декремент памяти, либо его нет, потому что dec [mem] либо работал, либо нет. Нам на самом деле не нужна lock dec [mem] для этого.

Кстати, это cmpxchg использования cmpxchg без префикса lock. Я всегда удивлялся, почему они не просто делают lock неявной в cmpxchg, и причина в том, что системы UP часто не нуждаются в префиксах lock.

Не существует надежного способа убедиться, что компилятор выдает dec [value] вместо чего-то вроде этого:

mov   eax, [value]
                           ;; interrupt here = bad
dec   eax
                           ;; interrupt here = bad
mov   [value], eax

Я не думаю, что C11/С++ 11 предоставляют способ запрашивать атомарность в отношении обработчиков/прерываний сигналов, но не других потоков. Они предоставляют atomic_signal_fence в качестве барьера компилятора, но я не помню тип, который в x86 избежал бы префиксов lock сохраняя при этом другую семантику атомарных типов.

C11/С++ 11 volatile sig_atomic_t имеет в виду эту идею, но обеспечивает атомарность только для отдельных загрузок/хранилищ, а не для RMW. Это typedef для int в Linux x86. Смотрите этот вопрос для некоторых цитат из стандарта.