Внеочередное выполнение и переупорядочивание: можно ли увидеть, что после барьера до барьера?

Согласно Википедии: Барьер памяти, также известный как инструкция membar, memory guard или filter, представляет собой тип барьерной инструкции, которая заставляет центральный процессор (ЦП) или компилятор применять ограничение порядка операций с памятью, выполняемых до и после барьерная инструкция. Обычно это означает, что операции, выполненные до барьера, гарантированно будут выполнены до операций, запущенных после барьера.

Обычно статьи говорят о чем-то вроде (я буду использовать мониторы вместо мембаров):

class ReadWriteExample {                                          
    int A = 0;    
    int Another = 0;                                                

    //thread1 runs this method                                    
    void writer () {                                              
      lock monitor1;   //a new value will be stored            
      A = 10;          //stores 10 to memory location A        
      unlock monitor1; //a new value is ready for reader to read
      Another = 20; //@see my question  
    }                                                             

    //thread2 runs this method                                    
    void reader () {                                              
      lock monitor1;  //a new value will be read               
      assert A == 10; //loads from memory location A
      print Another //@see my question           
      unlock monitor1;//a new value was just read              
   }                                                              
}       

Но мне интересно, возможно ли, что компилятор или процессор перемешают вещи таким образом, что код напечатает 20? Мне не нужна гарантия.

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

Спасибо


person Vadim Kirilchuk    schedule 08.04.2015    source источник
comment
Я довольно далек от эксперта в этой теме, но вот что я думаю: похоже, это будет зависеть от компилятора и ОС. Например, в C# есть идентификатор volatile, который можно использовать для переменных, которые могут быть получены из нескольких потоков. Но, в конечном счете, ОС должна передать обработку потоков ЦП, и этот порядок может зависеть от многих вещей.   -  person jwatts1980    schedule 08.04.2015
comment
Короткий ответ — да, в зависимости от языковой семантики монитора, ОС и ЦП. Даже если ничего не было переупорядочено, в вашем примере все равно будет гонка, где 20 может быть записано, а эффекты полностью распространены еще до того, как reader будет вызван.   -  person Cameron    schedule 08.04.2015
comment
На стороне процессора это зависит от того, что будет выдавать ваш компилятор и языковая семантика, а также от используемой архитектуры. x86, например. обеспечивает ограждающие барьеры, которые предотвращают переупорядочение операций с памятью в любом направлении (например, mfence), а также более строгие инструкции сериализации, которые также блокируют неупорядоченное переупорядочение (например, операция с префиксом блокировки). В IA64 были однонаправленные ограничения (захват/выпуск).   -  person Leeor    schedule 18.05.2015


Ответы (3)


Мой ответ ниже касается только модели памяти Java. Ответ действительно не может быть сделан для всех языков, поскольку каждый может определять правила по-разному.

Но мне интересно, возможно ли, что компилятор или процессор перемешают вещи таким образом, что код напечатает 20? Мне не нужна гарантия.

Ваш ответ, кажется, "Можно ли в магазине A = 20 сделать повторный заказ над монитором разблокировки?"

Ответ: да, может быть. Если вы посмотрите JSR 166 Cookbook, первая показанная таблица объясняет, как повторные заказы работают.

В вашем случае writer первой операцией будет MonitorExit, второй операцией будет NormalStore. Сетка объясняет, да, эту последовательность можно переупорядочить.

Это называется заказом Roach Motel. , то есть обращения к памяти могут быть перемещены в синхронизированный блок, но не могут быть перемещены из него.


А как насчет другого языка? Что ж, этот вопрос слишком широк, чтобы ответить на все вопросы, поскольку каждый может определять правила по-разному. Если это так, вам нужно уточнить свой вопрос.

person John Vint    schedule 08.04.2015

В Java есть понятие «происходит до». Вы можете прочитать все подробности об этом в Спецификация Java. Компилятор Java или механизм выполнения могут переупорядочивать код, но они должны соблюдать правила «происходит до». Эти правила важны для разработчика Java, который хочет иметь подробный контроль над тем, как переупорядочивается их код. Я сам был сожжен переупорядочиванием кода, оказалось, что я ссылался на один и тот же объект через две разные переменные, и механизм выполнения переупорядочил мой код, не понимая, что операции были на одном и том же объекте. Если бы у меня было либо «происходит-до» (между двумя операциями), либо использовалась бы одна и та же переменная, то переупорядочивания бы не произошло.

Конкретно:

Из вышеприведенных определений следует, что:

Разблокировка монитора происходит перед каждой последующей блокировкой этого монитора.

Запись в изменчивое поле (§8.3.1.4) происходит перед каждым последующим чтением этого поля.

Вызов start() в потоке происходит до любых действий в запущенном потоке.

Все действия в потоке происходят до того, как любой другой поток успешно вернется из функции join() в этом потоке.

Инициализация по умолчанию любого объекта происходит до любых других действий (кроме записи по умолчанию) программы.

person Jose Martinez    schedule 08.04.2015
comment
Спасибо за ваш вклад, я хорошо знаком со спецификацией ... но в ней нет ответа на мой вопрос. +1, потому что другим может понадобиться сначала прочитать спецификацию :) - person Vadim Kirilchuk; 08.04.2015

Краткий ответ - да. Это очень зависит от архитектуры компилятора и процессора. Здесь у вас есть определение состояния гонки. Планирование Quantum не заканчивается в середине инструкции (не может быть двух операций записи в одно и то же место). Однако - квант может закончиться между инструкциями - плюс то, как они выполняются не по порядку в конвейере, зависит от архитектуры (за пределами блока монитора).

Теперь приходит "это зависит" осложнений. ЦП мало что гарантирует (см. состояние гонки). Вы также можете взглянуть на NUMA (ccNUMA) — это метод масштабирования доступа к процессору и памяти путем группирования процессоров (узлов) с локальной оперативной памятью и владельцем группы — плюс специальная шина между узлами.

Монитор не препятствует запуску другого потока. Он только предотвращает ввод кода между мониторами. Поэтому, когда Writer выходит из секции монитора, он может выполнить следующий оператор — независимо от того, находится ли другой поток внутри монитора. Мониторы — это ворота, которые блокируют доступ. Кроме того, квант может прервать второй поток после оператора A==, позволяя другому изменить значение. Опять же - квант не будет прерывать инструкцию посередине. Всегда думайте о потоках, выполняющихся идеально параллельно.

Как вы это применяете? Я немного устарел (извините, C#/Java в наши дни) с текущими процессорами Intel и тем, как работают их конвейеры (гиперпоточность и т. д.). Несколько лет назад я работал с процессором под названием MIPS, и у него была возможность (благодаря порядку инструкций компилятора) выполнять инструкции, которые происходили последовательно ПОСЛЕ инструкции перехода (слота задержки). В этой комбинации процессор/компилятор - ДА - может произойти то, что вы описываете. Если Intel предложит то же самое - тогда да - может случиться. Например, с NUMA (это есть как у Intel, так и у AMD, я больше всего знаком с реализацией AMD).

Моя точка зрения - если потоки выполнялись через узлы NUMA - и доступ был к общей ячейке памяти, тогда это могло произойти. Конечно, ОС изо всех сил старается планировать операции в пределах одного и того же узла.

Возможно, вы сможете смоделировать это. Я знаю, что C++ на MS позволяет получить доступ к технологии NUMA (я играл с ней). Посмотрите, сможете ли вы распределить память между двумя узлами (разместив A на одном и Another на другом). Запланируйте выполнение потоков на определенных узлах.

Что происходит в этой модели, так это то, что есть два пути к оперативной памяти. Я полагаю, это не то, что вы имели в виду - вероятно, только модель с одним путем/узлом. В этом случае я возвращаюсь к описанной выше модели MIPS.

Я предположил процессор, который прерывается — есть и другие, у которых есть модель Yield.

person ripvlan    schedule 08.04.2015
comment
Вау, слишком сложно для меня, но +1) - person Vadim Kirilchuk; 08.04.2015
comment
Привет, Вадим. Я не был уверен, вы имеете в виду языки высокого уровня или процессоры низкого уровня. Как заявили другие, в компиляторах высокого уровня может произойти многое (уменьшение силы, порядок инструкций). Компилятор выводит инструкции для выполнения. Однако — CPU тоже может менять порядок выполнения в некоторых пределах — и это Pipelining. Виртуальные языки, такие как .NET и Java, добавляют еще один уровень. - person ripvlan; 08.04.2015
comment
Что ж, полезно знать о вещах на любом уровне, так что еще раз спасибо) - person Vadim Kirilchuk; 08.04.2015