Как предотвратить возникновение состояния гонки в SharedArrayBuffers при помощи атомарных операций (часть 3)

121

В прошлой статье я писал о том, как использование SharedArrayBuffer может приводить к появлению состояний гонки. Из-за этого работать с SharedArrayBuffer не просто. Мы не ожидаем, что разработчики приложений будут использовать SharedArrayBuffer напрямую.

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

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

Но для начала рассмотрим, что же такое состояние гонки?

Состояние гонки: пример, который вы уже раньше видели
Самый очевидный пример состояния гонки, это когда у нас есть одна переменная, которую могут использовать два треда. Скажем, один тред загружает файл, а другой тред проверяет его существование. Для общения они пользуются одной переменной, fileExists.
Изначально значение fileExists установлено на false.

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

Но проблема не в этом. Дело не в том, что файла не существует. Настоящая проблема это состояние гонки.

Многие JavaScript-разработчики сталкивались с подобным состоянием гонки даже в коде, в котором всего один тред. Вам не нужно разбираться в многопоточности, чтобы понимать, что это за гонка.

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

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

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

Разъяснив это…

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

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

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

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

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

Если сначала пройдут все операции в треде 1, а затем все операции в треде 2, то мы получим тот результат, который хотим.

Но если они чередуются по времени, то значение, которое тред 2 записал в регистр, рассогласуется со значением в памяти. То есть, тред 2 не будет учитывать результаты вычислений, полученных тредом 1. Вместо этого он просто затрёт значение, записанное в память тредом 1, и запишет своё собственное.

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

Именно поэтому их и называют атомарными операциями. Они берут операцию, в которой обычно есть много команд по приостановки и возобновления, и делают так, что всё как будто бы происходит моментально – то есть так, как будто бы команда всего одна. Она становится как неделимый атом.

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

Сейчас, когда мы используем Atomics.add, треды не будут путать шаги, которые нужно сделать для наращивания переменной. Наоборот, один тред будет завершать свою атомарную операцию, и не будет давать другому начать выполнять эту же операцию. Тогда другой начнёт свою собственную атомарную операцию.

Методы атомарных операций, которые могут помочь предотвратить гонки:
Atomics.add
Atomics.sub
Atomics.and
Atomics.or
Atomics.xor
Atomics.exchange

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

Чтобы это сделать, разработчики могут использовать метод Atomics.compareExchange. При помощи него можно извлечь значение из SharedArrayBuffer, провести над ним операцию и, если никакой другой тред не обновил его со времени первой проверки, записать его обратно в SharedArrayBuffer. Если другой тред его обновил, то можно извлечь это новое значение и попробовать снова.

Состояния гонки между многократными операциями
Таким образом, атомарные операции помогают избегать появления состояния гонки при «однократных операциях». Но иногда у одного объекта нужно изменить множество значений (используя многократные операции) и при этом сделать так, что никто другой не совершает изменения в этом объекте в то же самое время. По сути, это значит, что во время проведения каждого комплекса изменений в объекте, этот объект должен быть блокирован и недоступен для других тредов.

У атомарного объекта нет никаких инструментов, чтобы сделать это напрямую. Но у него есть инструменты, которые авторы библиотек могут использовать, чтобы справиться с этой задачей. Они могут создать замок (lock).

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

Чтобы сделать замок, авторы библиотек могут использовать методы Atomics.wait и Atomics.wake, плюс другие, например, Atomics.compareExchange и Atomics.store. Если вы хотите посмотреть, как они работают, взгляните на примеры простейших замков.

В нашем случае тред 2 мог бы получить замок для своих данных и поставить locked значение true. Это значит, что тред 1 не сможет получить доступ к данным до тех пор, пока тред 2 его не откроет.

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

Когда тред 2 сделает всё необходимое, он разблокирует данные (вызовет unlock). Замок сообщит всем ожидающим тредам, что теперь он свободен.

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

В библиотеке замков для атомарных объектов можно использовать множество различных методов, но самыми важными из них являются:
Atomics.wait
Atomics.wake

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

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

Например, скажем, мы написали программку для подсчёта суммы. И мы хотим, чтобы, когда подсчёт завершается, устанавливался флажок.

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

Пока что всё идёт так, как задумано.

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

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

Вот пример шагов, по которым выполняется команда:
1. Получить следующую команду из памяти
2. Понять, что мы должны делать в соответствии с этой командой (т.е. декодировать команду) и получить значения из регистров
3. Выполнить команду
4. Записать результат обратно в регистр

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

Проблема состоит в том, между командой №1 и командой №2 существует взаимозависимость.

Мы могли бы просто приостановить процессор, пока команда №1 не обновит subTotal в регистре. Но тогда всё будет работать очень медленно.

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

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

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

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

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

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

Атомарные операции не переставляются друг относительно друга, и другие операции не вклиниваются перед ними. В частности, две операции, которые часто используются для того, чтобы задавать порядок выполнения, это:
Atomics.load
Atomics.store

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

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

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

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

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

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

SharedArrayBuffer и атомарные операции только начинают свою жизнь. Нужные библиотеки ещё не созданы. Но эти новые API уже заложили основу, на которой можно будет строить и само здание.