Можете ли вы объяснить, почему нескольким потокам требуются блокировки на одноядерном процессоре?

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

Это лучше всего иллюстрируется на примере.

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

Когда каждый поток достигает точки, в которой он увеличивает счетчик, его выполнение будет выглядеть так:

1. Считать количество попаданий из памяти в регистр процессора
2. Увеличьте это число.
3. Запишите этот номер обратно в память

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

Кроме того, любое количество других потоков могло работать в течение времени, когда поток A был приостановлен, так что поток подсчета, записывающий A в конце, может быть значительно ниже правильного числа.

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

Но что, если операция была атомной?

Да, в стране волшебных единорогов и радуг, где операция приращения является атомарной, блокировка не понадобится для приведенного выше примера.

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

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

Изменчивые переменные

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

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

Таким образом, переменная, помеченная как volatile, не приведет нас к земле операций атомарного приращения, она только приблизит нас к тому, что мы уже думали.

Делая прирост атомным

После того, как мы используем переменную volatile, мы можем сделать нашу операцию приращения атомарной, используя низкоуровневую операцию условного набора, которую поддерживает большинство современных процессоров (часто называемые сравнить и установить или сравнить и поменять местами ). Этот подход используется, например, в классе Java AtomicInteger :

197       /**
198        * Atomically increments by one the current value.
199        *
200        * @return the updated value
201        */
202       public final int incrementAndGet() {
203           for (;;) {
204               int current = get();
205               int next = current + 1;
206               if (compareAndSet(current, next))
207                   return next;
208           }
209       }

Вышеупомянутый цикл многократно выполняет следующие шаги, пока шаг 3 не будет выполнен успешно:

1. Считайте значение изменчивой переменной непосредственно из памяти.
2. Увеличьте это значение.
3. Измените значение (в основной памяти) тогда и только тогда, когда его текущее значение в основной памяти совпадает со значением, которое мы первоначально прочитали, используя специальную атомарную операцию.

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

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

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

Так, когда блокировка строго необходима?

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

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

Давайте рассмотрим пример, в котором каждый поток сначала добавляет 2 к переменной X, а затем умножает X на два.

Если X изначально один, и два потока выполняются, мы ожидаем, что результат будет (((1 + 2) * 2) + 2) * 2 = 16.

Однако, если потоки чередуются, мы могли бы, даже если бы все операции были атомарными, вместо этого сначала имели бы место оба сложения, а затем умножения, что привело бы к (1 + 2 + 2) * 2 * 2 = 20.

Это происходит потому, что умножение и сложение не являются коммутативными операциями.

Итак, самих атомарных операций недостаточно, мы должны сделать комбинацию атомарных операций.

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

Здесь есть несколько компромиссов: по мере того, как вычисления становятся длиннее, становится намного более вероятным, что работающий поток будет приостановлен, а значение будет изменено другим потоком, прежде чем мы возобновим, что означает, что сбои становятся намного более вероятными, что приводит к потере времени процессорное время. В крайнем случае большого количества потоков с очень длительными вычислениями, мы могли бы иметь 100 потоков, читающих переменную, и участвовать в вычислениях, и в этом случае только первый завершивший сможет записать новое значение, остальные 99 все равно будут завершите свои вычисления, но обнаружите после завершения, что они не могут обновить значение ... в этот момент каждый из них прочитает значение и начнет вычисление заново. Вероятно, оставшиеся 99 потоков повторяют ту же проблему, тратя огромное количество процессорного времени.

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

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

Рассмотрим эту цитату:

Некоторые люди, сталкиваясь с проблемой, думают: «Я знаю, я буду использовать темы», а затем у них две проблемы.

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

Кажется, многие ответили попытку объяснить блокировку, но я думаю, что OP нуждается в объяснении того, что на самом деле является многозадачностью.

Если в системе запущено более одного потока, даже с одним ЦП, существуют две основные методологии, которые определяют, как эти потоки будут планироваться (т. Е. Помещаться для запуска в одноядерный ЦП):

• Совместная многозадачность - в Win9x требуется, чтобы каждое приложение явно отказывалось от управления. В этом случае вам не нужно беспокоиться о блокировке, поскольку, пока поток A выполняет какой-либо алгоритм, вы гарантированно никогда его не прервете.
• Вытесняющая многозадачность - используется в большинстве современных ОС (Win2k и выше). Он использует временные интервалы и прерывает потоки, даже если они все еще работают. Это гораздо более надежно, потому что один поток никогда не сможет повесить всю вашу машину, что было реальной возможностью при совместной многозадачности. С другой стороны, теперь вам нужно беспокоиться о блокировках, потому что в любой момент один из ваших потоков может быть прерван (то есть прерван), и ОС может запланировать запуск другого потока. При кодировании многопоточных приложений с таким поведением вы ДОЛЖНЫ учитывать, что между каждой строкой кода (или даже каждой инструкцией) может выполняться другой поток. Теперь даже с одним ядром блокировка становится очень важной для обеспечения согласованного состояния ваших данных.

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

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

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

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

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

За исключением установки 'bool', нет гарантии (по крайней мере, в c), что чтение или запись переменной занимает только одну инструкцию - или, скорее, не может быть прервана во время чтения / записи.

Общая память.

Это определение ... потоков : группа параллельных процессов с общей памятью.

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

(общая память в UNIX-подобных ядрах действительно обычно реализовывалась с использованием поддельного файлового дескриптора, представляющего адрес общей памяти)

Процессор выполняет одну инструкцию за раз, но что, если у вас есть два или более процессоров?

Вы правы в том, что блокировки не нужны, если вы можете написать программу так, чтобы она использовала атомарные инструкции: инструкции, выполнение которых не прерывается на данном процессоре и не было помех для других процессоров.

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

Например, вставка узла в двусвязный список требует обновления нескольких областей памяти. До вставки и после вставки некоторые инварианты сохраняют структуру списка. Однако во время вставки эти инварианты временно разрушаются: список находится в состоянии «находится в стадии разработки».

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

Соответствующим образом составленные списки могут управляться атомарными инструкциями, так что блокировки не нужны. Алгоритмы для этого называются «без блокировки». Тем не менее, обратите внимание, что атомарные инструкции являются формой блокировки. Они специально реализованы на аппаратном уровне и работают через связь между процессорами. Они дороже, чем аналогичные инструкции, которые не являются атомарными.

В мультипроцессорах, в которых отсутствует роскошь атомарных инструкций, примитивы для взаимного исключения должны быть построены из простых обращений к памяти и циклов опроса. Над такими проблемами работали Эдсгер Дейкстра и Лесли Лампорт.