Как избежать режима конкуренции в SharedArrayBuffers с помощью Atomics

Перевод третьей статьи из серии статей от Lin Clark:

  1. Ускоренный курс по управлению памятью
  2. Введение в ArrayBuffers и SharedArrayBuffers в картинках
  3. Как избежать режима конкуренции (race conditions) в SharedArrayBuffers с помощью Atomics

В прошлой статье я говорила о том, что использование SharedArrayBuffers может привести к появлению режима конкуренции (ориг.: race conditions). Это делает работу с SharedArrayBuffers не такой уж и простой. Ожидается, что разработчики приложений не будут использовать SharedArrayBuffers напрямую.

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

Хотя вы и не должны работать напрямую с SharedArrayBuffers и Atomics, я думаю, что довольно интересно узнать как они работают. И в этой статье я объясню какие типы режимов конкуренции (ориг.: race conditions) параллелизм может порождать и как Atomics помогает библиотекам избежать их.

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

Режим конкуренции: пример, с которым вы могли сталкиваться раньше

Довольно простой пример режима конкуренции можно увидеть в случае, если у вас есть переменная, которая является общей для двух потоков (ориг.: threads), которые выполняются параллельно. Например один поток хочет загрузить, а второй — проверить существует ли этот файл. И эти потоки общаются между собой с помощью переменной fileExists, которая, соответственно, является общей для них.

Изначально fileExists имеет значение false.

Если код из потока 2 выполнится первым (т.е. он проверит существование файла и установит переменной fileExists значение true) — файл будет загружен.

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

Но проблема же не в том, что файла не существует. Проблема в режиме конкуренции.

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

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

Различные типы режимов конкуренции и как Atomics может помочь

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

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

Итак, когда мы с этим разобрались…

Режим конкуренции при единых операциях (ориг.: single operation)

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

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

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

Все потоки имеют доступ к долгосрочной памяти (делят ее между собой). Но к краткосрочной памяти — реестру — общего доступа у потоков нет.

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

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

Но если потоки чередуются во времени (прим.пер.: имеется в виду параллелизм потоков), то значение, которое поток #2 скопировал к себе в реестр, не будет верным, т.е. не будет синхронизировано со значением в долгосрочной памяти. Таким образом поток #2, осуществляя какие то действия со значением из общей ячейки долгосрочной памяти, не принимает во внимание операции, которые поток #1 осуществляет над тем же значением. Вместо этого поток #2 просто переопределит значение в долгосрочной памяти, которое было туда записано потоком 1.

Итак, у нас есть некие операции, которые с точки зрения программиста являются едиными, но с точки зрения компьютера — нет. (прим.пер.: назовем их операциями Шредингера. Они и единые и нет одновременно). Единственная задача элементарных операций (прим.пер.: статические методы, предоставляемые объектом Atomic названы элементарными операциями) — сделать так, чтобы с точки зрения компьютера такие операции (прим.пер.: наши операции Шредингера) стали едиными.

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

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

Теперь, когда мы используем Atomics.add, инструкции, вовлеченные в процесс инкрементирования переменной двумя параллельными потоками, не будут пересекаться между двумя этими потоками. Вместо этого поток #1 закончит элементарную операцию над значением до того как поток #2 начнет выполнение своей операции над тем же значением.

Следующие методы объекта Atomics помогут избежать возникновения такого типа режима конкуренции:

Вы могли заметить, что этот список весьма ограниченный. В нем нет операций умножения и деления например. Несмотря на это, разработчики библиотек могут создавать свои типы элементарных операций (ориг.: atomic-like operations).

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

Режим конкуренции при множественных операциях (ориг.: multiple operations)

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

Объект Atomics напрямую не предоставляет никаких инструментов для обработки таких ситуаций. Но он предоставляет инструменты, которые могут быть использованы разработчиками библиотек для того, чтобы справиться с такими ситуациями. Т.е. разработчики библиотек могут использовать т.н. «блокиратор» для блокировки данных.

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

Для создания такого «блокиратора» разработчики библиотек могут использовать методы Atomics.wait и Atomics.wake, плюс еще некоторые другие, такие как Atomics.compareExchange и Atomics.store. Если вы хотите увидеть как это работает, взгляните на эту базовую реализацию блокировки.

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

Если потоку 1 нужно иметь доступ к данным, то он будет пытаться заполучить этот «блокиратор» и заблокировать те данные, с которыми хочет взаимодействовать. Но, поскольку «блокиратор» уже используется потоком 2, поток #1 не может этого сделать. В этом случае поток #1 будет ждать, т.е. будет как бы приостановлен, пока поток #2 не освободит «блокиратор».

Как только поток #2 закончит свои операции над заблокированными данными, он может их разблокировать и освободить «блокиратор». «Блокиратор» оповестит все те потоки, которые ждут его освобождения, что он теперь доступен.

Теперь поток #1 может подхватить «блокиратор» и заблокировать данные для собственных целей.

Библиотеки-блокираторы могут использовать множество методов объекта Atomics, но основными для реализации вышеописанного сценария это:

Режим конкуренции, вызванный изменением порядка выполнения инструкций.

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

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

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

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

Пока все происходит так, как запланировано.

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

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

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

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

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

Проблема в том что есть зависимость между инструкцией #1 и инструкцией #2.

Мы бы могли просто приостановить работу CPU до тех пор, пока инструкция #1 не обновит subTotal в реестре. Но это замедлит процесс выполнения кода в принципе.

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

Это обеспечивает постоянный поток инструкций, который движется по последовательности выполнения инструкций (ориг.: pipeline) и предотвращает «простой/ожидание» CPU.

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

Но, как только появляется второй поток выполнения, который выполняется на другом процессоре одновременно с первым, все меняется. Второй поток не обязан ждать окончания выполнения функции в первом потоке чтобы увидеть измененные ею значения. Он может видеть их почти сразу после того, как они были обратно записаны в память первым потоком. Т.е. может получится так, что второй поток увидит isDone === true еще до того, как будет вычислен total.

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

Atomics пытается решать подобные проблемы. Когда вы используете метод write объекта Atomic, это похоже на то, как-будто вы разделяете разные части своего кода забором.

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

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

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

Примечание: цикл while, который показан на рисунке, называется «стопором» (ориг.: spinlock) и он очень негативно влияет на скорость выполнения кода/эффективность. И если он расположен в основном потоке выполнения кода, то может приостановить ваше приложение. Вы безусловно не должны использовать такую конструкцию в реальном коде.

Еще раз, подразумевается, что вышеописанные методы не будут непосредственно использованы в коде приложение. Они должны использоваться библиотеками для реализации «блокираторов».

Заключение

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

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

SharedArrayBuffers и Atomics все еще довольно молоды. И библиотеки, о которых идет речь в предыдущем абзаце, еще не созданы. Но такой API предоставляет основу для их разработки.

О Lin Clark

Лин работает инженером в команде Mozilla Developer Relations. Она занимается JavaScript, WebAssembly, Rust и Servo, а также рисует комиксы про то, как работает наш код.

More articles by Lin Clark…


Originally published at muntianblog.wordpress.com on July 16, 2017.