Простая программа на C для иллюстрации выполнения вне очереди?

Я использую x86, и я хочу практически увидеть ошибку, вызванную некорректным выполнением на моей машине. Я попытался написать один, на основе этой статьи в вики, но я всегда вижу, что «значение x равно 33 ":

#include<stdio.h>
#include<pthread.h>
#include <sys/types.h>

int x, f;

void *handler(void *ptr) { 
  while (f == 0); 
  // Expectation: Sometimes, this should print 11 due to out-of-order exec
  printf("value of x is %d \n", x);
  return NULL;
}

int main() {
     pthread_t thread1;
     while(1) {
       x = 11; f = 0;
       pthread_create(&thread1, NULL, handler, NULL);
       x = 33; 
       f = 1;
       pthread_join(thread1, NULL);
     }   
     return 0;
}

Какая самая простая программа на c может проиллюстрировать ошибку выполнения вне очереди? Почему это иногда не выводит «значение x равно 11»?


c multithreading x86 memory-barriers
person Sush    schedule 07.10.2018    source источник
comment
поток не запускается достаточно быстро. Просто добавьте sleep() после его создания в основной функции, чтобы получить значение 11   -  person Jean-François Fabre    schedule 07.10.2018
comment
другой способ - (возможно) загрузить систему некоторыми процессами, интенсивно использующими процессор, чтобы изменить состояние гонки.   -  person Jean-François Fabre    schedule 07.10.2018
comment
@ Jean-FrançoisFabre, но handler ничего не делает, пока f = 1; не будет завершено, а к этому времени x = 33; уже было сделано.   -  person Weather Vane    schedule 07.10.2018
comment
@ Jean-FrançoisFabre Не думаю, что здесь есть условия гонки.   -  person Sush    schedule 07.10.2018
comment
@WeatherVane why doesn't this sometimes print "value of x is 11"?, возможно, это и есть ответ.   -  person kiran Biradar    schedule 07.10.2018
comment
@kiranBiradar но ваша программа работает - это не ответ. Должен ли вопрос быть по CodeReview?   -  person Weather Vane    schedule 07.10.2018
comment
@WeatherVane Я не уверен, хотя в вопросе есть what.   -  person kiran Biradar    schedule 07.10.2018
comment
@kiranBiradar, который запрашивает код. Возможно, OP стоит поэкспериментировать, возможно, сняв условие while (f == 0);.   -  person Weather Vane    schedule 07.10.2018
comment
@WeatherVane Пробовал все равно выдает 33. Возможно, потребуется подробное объяснение того, почему последовательность выполнения потока не гарантируется.   -  person kiran Biradar    schedule 07.10.2018
comment
Чтобы уточнить, мой вопрос не о состоянии гонки между основным потоком и thread1 - я не думаю, что он есть. Однако я понимаю, что приведенный выше код по-прежнему неверен, поскольку x86 (и другие процессоры) выполняются не по порядку - другими словами, printf может быть уже выполнен до while (f == 0); цикл заканчивается, используя старое значение x = 11 (из-за буфера переупорядочения). Моя цель - найти простой пример, иллюстрирующий это.   -  person Sush    schedule 07.10.2018
comment
@kiranBiradar после снятия этого while (f == 0); ограничения, если вы запустите программу много раз, возможно, рано или поздно планирование временного интервала отделит pthread_create(&thread1, NULL, handler, NULL); от x = 33; и запустит handler в этом крэке, чтобы сообщить 11.   -  person Weather Vane    schedule 07.10.2018
comment
@WeatherVane Да, верно.   -  person kiran Biradar    schedule 07.10.2018
comment
Везде, где вы говорите о нарушении порядка выполнения, вы, вероятно, хотели сказать упорядочение памяти. Выполнение вне порядка - это метод реализации, который имеет лишь слабую связь с упорядочением памяти, и эффект, который вы ищете, в значительной степени связан с упорядочением памяти. Внедрите алгоритм Деккера, и вы очень быстро это увидите.   -  person BeeOnRope    schedule 08.10.2018

Ответы (1)


arrow_upward
6
arrow_downward

Эффект, который вы пытаетесь создать, не зависит от неупорядоченного выполнения. Это только одна из вещей, которые могут вызвать переупорядочение памяти. Кроме того, современная x86 выполняет выполнение вне очереди, но использует буфер порядка памяти, чтобы гарантировать, что хранилища фиксируются в L1d / становятся глобально видимыми в порядке выполнения программы. (Поскольку модель памяти x86 позволяет переупорядочивать только StoreLoad, но не StoreStore.)

Переупорядочение памяти отделено от переупорядочения инструкций выполнение, потому что даже упорядоченные процессоры используют буфер хранилища, чтобы избежать остановки в хранилищах промахов кэша.

Выполнение инструкции вне очереди: сохраняется ли порядок фиксации? < / а>

Загружаются и сохраняются единственные инструкции, которые переупорядочиваются. ?

Реализация C на работающем процессоре ARM могла бы вывести 11 или 33, если x и f оказались в разных строках кэша.

Я предполагаю, что вы скомпилировали с отключенной оптимизацией, поэтому ваш компилятор эффективно обрабатывает все ваши переменные volatile, т.е. volatile int x,f. В противном случае цикл while(f==0); будет компилироваться в if(f==0) { infloop; }, проверяя только f один раз. (UB гонки данных для неатомарных переменных - это то, что позволяет компиляторам выводить нагрузки из циклов, но volatile нагрузки должны выполняться всегда. https://electronics.stackexchange.com/questions/387181/mcu-programming-c-o2-optimization-breaks- while-loop#387478 ).

Хранилища в результирующем asm / машинном коде появятся в исходном порядке C.

Вы компилируете для x86, который имеет сильную модель памяти: хранилища x86 - это хранилища релизов, а загрузки x86 - загрузки запросов. Вы не получите последовательной согласованности, но получите acq_rel бесплатно. (А с неоптимизированным кодом это происходит, даже если вы этого не просите.)

Таким образом, при компиляции без оптимизации для x86 ваша программа эквивалентна

_Atomic int x, f;

int main(){
    ...
    pthread_create
    atomic_store_explicit(&x, 33, memory_order_release);
    atomic_store_explicit(&f, 1, memory_order_release);
    ...
}

То же самое и со стороны нагрузки. while(f==0){} - это загрузка-загрузка на x86, поэтому ожидание стороны чтения, пока она не увидит ненулевое значение f, гарантирует, что она также увидит x==33.

Но если вы скомпилировали ISA со слабым упорядочением, например ARM или PowerPC, гарантии упорядочения памяти на уровне asm позволяют переупорядочивать StoreStore и LoadLoad, так что ваша программа может печатать 11, если скомпилирована без оптимизации.

См. Также https://preshing.com/20120930/weak-vs-strong-memory-models/

person Peter Cordes    schedule 07.10.2018