При участии Тима Перлса, Джошуа Блоха, Джозева Боубира, Дэвида Холмса и Дага Ли Параллельное программирование в java на
 Скачать 4.97 Mb.
|
|
15.2 Аппаратная поддержка параллелизма Эксклюзивная блокировка является пессимистичным подходом - она предполагает худшее (если вы не запрете дверь, гремлины войдут и переставят ваши вещи) и не позволит продолжить, пока вы можете гарантировать, захватив соответствующую блокировку, что другие потоки не будут оказывать влияние. Для хорошо детализированных операций существует альтернативный подход, который часто является более эффективным - оптимистичный подход, при котором вы продолжаете обновление, надеясь, что вы можете завершить его без постороннего вмешательства. Этот подход основан на обнаружении коллизий (collision detection) путём определения наличия помех со стороны других взаимодействующих сторон, во время выполнения обновления, в случае наличия таковых - операция завершается неудачно и может быть повторена (или нет). Оптимистичный подход подобен старой поговорке “легче получить прощение, чем разрешение”, где “легче” здесь означает “эффективнее”. Процессоры, предназначенные для работы в многопроцессорных системах, предоставляют специальные инструкции для управления параллельным доступом к совместно используемым переменным. Процессоры ранних лет имели атомарные инструкции проверить-и-установить (test-and-set), получить-и-увеличить (fetch-and- increment) или обменять (swap), достаточные для реализации мьютексов, которые, в свою очередь, могли использоваться для реализации более сложных параллельных объектов. Сегодня почти каждый современный процессор имеет атомарную инструкцию прочитать-изменить-записать (read-modify-write), такую как сравнить- и-обменять (compare-and-swap) или загрузка-с-пометкой /попытка-записи (load- linked/store-conditional). Операционные системы и среда JVM используют эти инструкции для реализации блокировок и параллельных структур данных, но до Java 5.0 они не были непосредственно доступны классам Java. 15.2.1 Сравнить и обменять Подход, используемый большинством процессорных архитектур, включая IA32 и Sparc, заключается в реализации инструкции сравнить-и-обменять (CAS). (Другие процессоры, такие как PowerPC, реализуют ту же функциональность с помощью пары инструкций: загрузка-с-пометкой и попытка-записи.) CAS имеет три операнда - ячейку памяти V, с которой следует работать, ожидаемое старое значение A и новое значение B. CAS атомарно обновляет V до нового значения B, но только если значение в V соответствует ожидаемому старому значению A; в противном случае операция ничего не делает. В любом случае операция возвращает значение, находящееся в текущий момент в V. (Вариант, называемый сравнить-и-обменять, вместо этого возвращает результат, указывающий на то, была ли операция выполнена успешно.) CAS означает “Я думаю, что V должно иметь значение A; если это так, поставьте там B, иначе не меняйте значение, но скажите мне, что я ошибался”. Операция CAS является оптимистичным подходом - она продолжает обновление в надежде на успех и может обнаружить сбой, если другой поток обновил переменную с момента ее последнего получения. Класс SimulatedCAS приведённый в листинге 15.1 иллюстрирует семантику (но не реализацию или производительность) операции CAS. @ThreadSafe public class SimulatedCAS { @GuardedBy("this") private int value; public synchronized int get() { return value; } public synchronized int compareAndSwap(int expectedValue, int newValue) { int oldValue = value; if (oldValue == expectedValue) value = newValue; return oldValue; } public synchronized boolean compareAndSet(int expectedValue, int newValue) { return (expectedValue == compareAndSwap(expectedValue, newValue)); } } Листинг 15.1 Симуляция операции CAS Когда несколько потоков пытаются обновить одну и ту же переменную с помощью CAS одновременно, один выигрывает и обновляет значение переменной, а остальные проиграют. Но проигравшие не наказываются отстранением, как это могло бы быть, если бы они не смогли захватить блокировку; вместо этого им говорят, что они не выиграли гонку на этот раз, но могут попробовать еще раз. Поскольку поток, который проигрывает в операции CAS, не блокируется, он может решить, хочет ли он повторить попытку, выполнить какое-либо другое действие по восстановлению или не делать ничего. 164 Эта гибкость позволяет исключить множество из угроз живучести, связанных с блокировками (хотя в нетипичных случаях может привести к введению риска возникновения динамической взаимоблокировки (livelock) - см. раздел 10.3.3 ). Типичный шаблон использования CAS заключается в том, чтобы сначала прочитать значение из V, вывести новое значение B из A, а затем использовать операцию CAS для атомарного изменения значения V с A на B, до того момента, когда на значение V перестанут оказывать влияние другие потоки. Операция CAS решает проблему реализации атомарных последовательностей прочитать-изменить- записать без использования блокировки, потому что она может обнаруживать внесение помех другими потоками. 164 Бездействие может быть вполне разумным ответом на провал операции CAS; в некоторых неблокирующих алгоритмах, подобных алгоритму связанной очереди из раздела 15.4.2, провал операции CAS означает, что кто-то уже выполнил работу, которую вы планировали выполнить. 15.2.2 Неблокирующий счётчик Класс CasCounter из листинга 15.2, реализует потокобезопасный счетчик с помощью операции CAS. Операция инкремента следует канонической форме - извлечь старое значение, преобразовать его в новое значение (добавив единицу) и использовать операцию CAS для установки нового значения. Если операция CAS проваливается, операция немедленно повторяется. Осуществление повторной попытки, как правило, является разумной стратегией, хотя в случаях жёсткой конкуренции может быть желательным подождать некоторое время или откатится, прежде чем повторять попытку, с целью избежания возникновения динамической взаимоблокировки. @ThreadSafe public class CasCounter { private SimulatedCAS value; public int getValue() { return value.get(); } public int increment() { int v; do { v = value.get(); } while (v != value.compareAndSwap(v, v + 1)); return v + 1; } } Листинг 15.2 Неблокирующий счётчик с использованием операции CAS Класс CasCounter не блокируется, хотя, возможно, операцию и придется повторить несколько 165 раз, если другие потоки будут обновлять значение счетчика в то же самое время. (На практике, если все, что вам нужно, это счетчик или генератор последовательности, просто используйте классы AtomicInteger или AtomicLong , которые предоставляют методы для атомарного увеличения и другие арифметические методы.) На первый взгляд счетчик на основе CAS выглядит так, как будто он должен работать хуже, чем счетчик на основе блокировки; он состоит из большего количества операций и поток управления в нём более сложен, и он зависит от кажущейся сложной операции CAS. Но на самом деле счетчики на основе CAS значительно превосходят счетчики на основе блокировок, если существует даже небольшое количество конфликтов, и часто даже при отсутствии конфликтов. Для быстрого неконкурентного захвата блокировки, требуется, по крайней мере, одна операция CAS плюс другие связанные с блокировкой служебные действия, так что в лучшем случае для счетчика на основе блокировки выполняется больше работы, чем в нормальной ситуации для счетчика на основе операции CAS. Так как 165 Теоретически, операция может повторяться произвольно большое количество раз, если другие потоки продолжают выигрывать гонку в операции CAS; на практике, голодание такого рода случается редко. операция CAS преуспевает большую часть времени (при условии низкой и умеренной конкуренции), железо будет корректно предсказывать возникновение неявной ветви в цикле while , минимизируя издержки, введённые более сложной логикой управления. Синтаксис языка для блокировки может быть компактным, но работа, выполняемая JVM и ОС для управления блокировками, таковой не является. Блокировка влечёт за собой пересечение относительно сложных веток кода в JVM и может повлечь за собой блокировку на уровне ОС, приостановку потока и переключение контекста. В лучшем случае блокировка требует, по крайней мере, выполнения одной операции CAS, поэтому использование блокировок выводит операции CAS из поля зрения, но не сохраняет фактическую стоимость выполнения. С другой стороны, выполнение операции CAS из программы не включает в себя код JVM, системные вызовы или планирование действий. То, что выглядит как более длинная ветка выполнения кода на уровне приложения, на самом деле является гораздо более короткой веткой кода, когда учитывается активность JVM и ОС. Основным недостатком операции CAS является то, что она вынуждает вызывающий объект сталкиваться с конкуренцией (повторение попытки, откат или отказ от выполнения операции), в то время как блокировки сталкиваются с конкуренцией за блокирование автоматически, пока блокировка доступна. 166 Производительность операции CAS широко варьируется между различными процессорами. В системе с одним процессором операция CAS обычно занимает порядка нескольких тактовых циклов, так как синхронизация между процессорами не требуется. На момент написания этой статьи, затраты на неконкурентную операцию CAS, в системе с несколькими ЦП, составляли примерно от десяти до 150 циклов; производительность CAS является быстро движущейся целью и варьируется не только между архитектурами, но даже между версиями одного и того же процессора. Конкурирующие силы, скорее всего, приведут к дальнейшему повышению эффективности CAS в течение следующих нескольких лет. Хорошее эмпирическое правило заключается в том, что затраты на “короткий путь” для неконкурентного захвата и освобождения блокировки на большинстве процессоров примерно в два раза превышает стоимость операции CAS. 15.2.3 Поддержка операций CAS в среде JVM Итак, каким образом Java-код убеждает процессор выполнить операции CAS от его имени? До Java 5.0 не было способа сделать это короче, чем написать нативный (native) код. В Java 5.0 была добавлена низкоуровневая поддержка для предоставления операций CAS для типов int , long и объектных ссылок, и JVM компилирует их в наиболее эффективные средства, предоставляемые железом. На платформах, поддерживающих CAS, среда выполнения помещает их в соответствующие машинные инструкции; в худшем случае, если CAS-подобная инструкция недоступна, JVM использует спин-блокировку 167 . Эта низкоуровневая поддержка JVM используется классами атомарных переменных ( AtomicXxx в пакете java.util.concurrent.atomic ) для обеспечения эффективной работы CAS с числовыми и ссылочными типами; эти классы атомарных переменных 166 На самом деле, самым большим недостатком CAS является сложность корректного построения окружающих алгоритмов. 167 Блокировка с повторами или блокировка с вращением. используются, прямо или косвенно, для реализации большинства классов в пакете java.util.concurrent 15.3 Классы атомарных переменных Атомарные переменные являются более детализированными и облегченными, чем блокировки, и критически важны для реализации высокопроизводительного параллельного кода в многопроцессорных системах. Атомарные переменные ограничивают область конкуренции одной переменной; это настолько детализировано, насколько возможно получить (даже предполагая, что ваш алгоритм может быть реализован с использованием такой тонкой детализации). Быстрый (неконкурентный) путь для обновления атомарной переменной не медленнее, чем быстрый путь для захвата блокировки, и обычно быстрее; медленный путь определенно быстрее, чем медленный путь в случае использования блокировок, поскольку он не включает приостановку и перепланирование потоков. С алгоритмами, основанными на атомарных переменных вместо блокировок, потоки с большей вероятностью смогут продолжить работу без задержек и затратить меньшее время на восстановление, если столкнутся с конкуренцией. Классы атомарных переменных предоставляют обобщение volatile переменных для поддержки атомарных условных операций прочитать-изменить- записать. Класс AtomicInteger представляет значение int и предоставляет методы get и set с той же семантикой памяти, как при чтении и записи volatile int . Он также предоставляет атомарный метод compareAndSet (который в случае успешного выполнения обладает теми же эффектами памяти, как при чтении и записи volatile переменной) и, для удобства, атомарные методы добавления (add), увеличения (increment) и уменьшения (decrement). Класс AtomicInteger имеет поверхностное сходство с расширенным классом Counter , но предлагает значительно лучшую масштабируемость при конкуренции, поскольку он может напрямую использовать аппаратную поддержку параллелизма железом. Существует двенадцать классов атомарных переменных, разделенных на четыре группы: скаляры (scalars), средства обновления полей (field updaters), массивы и составные переменные. Наиболее часто используемыми атомарными переменными являются скаляры: AtomicInteger , AtomicLong , AtomicBoolean , и AtomicReference . Все поддерживают операции CAS; Integer и Long версии также поддерживают арифметику. (Для имитации атомарных переменных других примитивных типов можно привести short или byte значения к типу int и из него, и использовать методы floatToIntBits или doubleToLongBits для чисел с плавающей запятой.) Классы атомарных массивов (доступные в Integer , Long и Reference версиях) - это массивы, элементы которых можно обновлять атомарно. Классы атомарных массивов предоставляют volatile семантику доступа к элементам массива, функцию, недоступную для обычных массивов - volatile массив обладает volatile семантикой только для ссылок на массив, а не для содержащихся в нём элементов. (Другие типы атомарных переменных обсуждаются в разделах 15.4.3 и 15.4.4 .) В то время как атомарные скалярные классы расширяют класс Number , они не расширяют примитивные классы-обёртки, такие как Integer или Long Фактически, они не могут: примитивные классы-обёртки неизменяемы, тогда как классы атомарных переменных изменяемы. Классы атомарных переменных также не переопределяют методы hashCode или equals ; каждый экземпляр индивидуален. Как и большинство изменяемых объектов, они не являются хорошими кандидатами на роль ключей в коллекциях, основанных на хэшах. 15.3.1 Atomics as “better volatiles” В разделе 3.4.2 мы использовали volatile ссылку на неизменяемый объект для атомарного обновления нескольких переменных состояния. Этот пример опирался на операцию проверить-затем-выполнить, но в этом конкретном случае гонка данных была безвредной, потому что нам было все равно, если мы иногда теряли обновление. В большинстве других ситуаций такая проверка не была бы безвредной и могла бы поставить под угрозу целостность данных. Например, класс NumberRange из раздела 4.3.3 , не может быть безопасно реализован с помощью volatile ссылки на неизменяемый объект холдера для верхней и нижней границ, а также с использованием атомарных целых чисел для хранения границ. Поскольку инвариант ограничивает два числа, и они не могут быть обновлены одновременно, пока инвариант сохраняется, класс диапазона чисел, использующий volatile ссылки или несколько атомарных целых чисел, столкнётся с небезопасной последовательностью операций проверить-затем-выполнить. Мы можем скомбинировать подход, принятый в классе OneValueCache с атомарными ссылками, чтобы исключить возможность возникновения условий гонки, атомарно обновляя ссылку на неизменяемый объект, содержащий значения нижней и верхней границ. Класс CasNumberRange из листинга 15.3 использует класс AtomicReference для хранения состояния экземпляра IntPair ; с помощью метода compareAndSet он может обновлять верхнюю или нижнюю границы без возникновения условий гонки, в отличие от класса NumberRange public class CasNumberRange { @Immutable private static class IntPair { final int lower; // Invariant: lower <= upper final int upper; } private final AtomicReference IntPair oldv = values.get(); if (i > oldv.upper) throw new IllegalArgumentException( "Can’t set lower to " + i + " > upper"); IntPair newv = new IntPair(i, oldv.upper); if (values.compareAndSet(oldv, newv)) return; } } // similarly for setUpper } Листинг 15.3 Сохранение инвариантов из множества переменных с использованием CAS 15.3.2 Производительность: блокировки против атомарных переменных Чтобы продемонстрировать различия в масштабируемости между блокировками и атомарными переменными, мы построили бенчмарк, сравнивающий несколько реализаций генератора псевдослучайных чисел (PRNG). В PRNG следующее "случайное" число является детерминированной функцией предыдущего числа, поэтому PRNG должен запоминать предыдущее число как часть своего состояния. В листингах 15.4 и 15.5 приведены две реализации потокобезопасного PRNG, одна из которых использует класс ReentrantLock , а другая использует класс AtomicInteger @ThreadSafe public class ReentrantLockPseudoRandom extends PseudoRandom { private final Lock lock = new ReentrantLock(false); private int seed; ReentrantLockPseudoRandom(int seed) { this.seed = seed; } public int nextInt(int n) { lock.lock(); try { int s = seed; seed = calculateNext(s); int remainder = s % n; return remainder > 0 ? remainder : remainder + n; } finally { lock.unlock(); } } } Листинг 15.4 Генератор случайных чисел с использованием класса ReentrantLock Тестовый драйвер каждый раз вызывается повторно; каждая итерация генерирует случайное число (которое извлекает и изменяет совместно используемое состояние переменной seed ), а также выполняет ряд итераций “занят выполнением работы”, которые работают строго с локальными для потока данными. Такое поведение позволяет имитировать типичные операции, которые включают в себя некоторую часть работы с совместно используемым состоянием и некоторую часть работы с состоянием, локальным для потока. @ThreadSafe public class AtomicPseudoRandom extends PseudoRandom { private AtomicInteger seed; AtomicPseudoRandom(int seed) { this.seed = new AtomicInteger(seed); } public int nextInt(int n) { while (true) { int s = seed.get(); int nextSeed = calculateNext(s); if (seed.compareAndSet(s, nextSeed)) { int remainder = s % n; return remainder > 0 ? remainder : remainder + n; } } } } Листинг 15.5 Генератор случайных чисел с использованием класса AtomicInteger На рисунках 15.1 и 15.2 показана пропускная способность с низким и умеренным уровнями моделируемой работы в каждой итерации. При низком уровне локальных для потока вычислений, блокировка или атомарная переменная испытывают большую конкуренцию; при большем количестве локальных для потока вычислений, блокировка или атомарная переменная испытывают меньшую конкуренцию, так как каждый поток реже обращается к совместно используемым данным. Рисунок 15.1 Производительность классов Lock и AtomicInteger при высокой конкуренции Как показывают эти графики, при высоких уровнях конкуренции блокировка имеет тенденцию превосходить атомарные переменные, но при более реалистичных уровнях конкуренции, атомарные переменные превосходят блокировки. 168 Это вызвано тем, что блокировка реагирует на конкуренцию путем 168 То же самое справедливо и в других областях: светофоры обеспечить лучшую производительность для высокого трафика, но роторы обеспечивают лучшую пропускную способность при низкой интенсивности движения; конкурентная схема используемая в Ethernet сетях работает лучше при низкой приостановки потоков, уменьшая, таким образом, использование ЦП и трафик синхронизации в совместно используемой шине памяти. (Это похоже на то, как блокировка производителя в дизайне производитель-потребитель снижает нагрузку на потребителей и тем самым позволяет им догнать производителя.) С другой стороны, в случае использования атомарных переменных управление конфликтами перекладывается на вызывающий класс. Подобно большинству алгоритмов на основе CAS, класс AtomicPseudoRandom реагирует на конкуренцию, немедленно повторяя попытку, что обычно является правильным подходом, но в среде с высокой конкуренцией просто приводит к большему количеству конфликтов. Рисунок 15.2 Производительность классов Lock и AtomicInteger при умеренной конкуренции Прежде чем мы осудим класс AtomicPseudoRandom как плохо написанный или атомарные переменные как худший выбор по сравнению с блокировками, мы должны понять, что уровень конкуренции, приведённый на рисунке 15.1 нереально высок: никакая реальная программа не занимается только тем, что борется за блокировку или атомарную переменную. На практике атомики (atomics), как правило, масштабируется лучше, чем блокировки, потому что атомики более эффективно справляется с типичными уровнями конкуренции. Изменение производительности между блокировками и атомиками при разных уровнях конкуренции, иллюстрирует сильные и слабые стороны каждого из них. При низкой и умеренной конкуренции, атомики обеспечивает лучшую масштабируемость; при высокой конкуренции, блокировки обеспечивают лучшее предотвращение конфликтов. (Алгоритмы на основе CAS, в системе с одним процессором, также превосходят основанные на блокировке алгоритмы, так как CAS всегда преуспевает, за исключением маловероятного случая, что поток будет вытеснен в середине операции чтение-изменение-запись.) Рисунки 15.1 и 15.2 включают в себя третью кривую; реализацию класса PseudoRandom , использующего класс ThreadLocal для вывода состояния PRNG. Такой подход к реализации изменяет поведение класса - каждый поток видит свою собственную частную последовательность псевдослучайных чисел вместо всех потоков, совместно использующих одну последовательность, - но иллюстрирует, что часто дешевле вообще не использовать состояние, если этого можно избежать. интенсивности траффика, но схема с передачей маркера, используемая в кольцевых сетях с маркером лучше подходит при высокой интенсивности траффика. Мы можем улучшить масштабируемость, более эффективно справляясь с конкуренцией, но истинная масштабируемость достигается только за счет полного устранения конкуренции. 15.4 Неблокирующие алгоритмы Алгоритмы, основанные на блокировках, подвержены риску возникновения ряда сбоев живучести. Если поток, удерживающий блокировку, задерживается из-за блокировки ввода/вывода, ошибки страницы или по другой причине, возможна ситуация, при которой поток не будет прогрессировать. Алгоритм называется неблокирующим (nonblocking), если сбой или приостановка какого-либо потока не может привести к сбою или приостановке другого потока; алгоритм называется свободным от блокировок (lock-free), если при выполнении каждого шага какой- либо поток сможет прогрессировать. Алгоритмы, использующие операции CAS исключительно для координации между потоками, при правильном построении могут быть как неблокирующими, так и свободными от блокировок. Конкуренция в операциях CAS всегда завершаются успешно, и если несколько потоков конкурируют за операцию CAS, один всегда выигрывает и, следовательно, прогрессирует. Неблокирующие алгоритмы также невосприимчивы к взаимоблокировке или инверсии приоритета (хотя они могут сталкиваться с голоданием или динамической взаимоблокировкой, потому что могут выполнять повторные попытки). До сих пор мы видели один неблокирующий алгоритм: класс CasCounter . Хорошие неблокирующие алгоритмы известны для многих распространенных структур данных, включая стеки, очереди, приоритетные очереди и хэш-таблицы - хотя проектирование новых алгоритмов представляет собой задачу, которую лучше оставить экспертам. 15.4.1 Неблокирующий стек Неблокирующие алгоритмы значительно сложнее, чем их эквиваленты на основе блокировок. Ключом к созданию неблокирующих алгоритмов является выяснение того, как ограничить область атомарных изменений одной переменной при сохранении согласованности данных. В классах связанных коллекций, подобных очередям, иногда можно избежать выражения изменяемых состояний в виде изменений отдельных ссылок и использования класса AtomicReference для представления каждой ссылки, которая должна обновляться атомарно. Стек представляют собой простейшую связанную структуру данных: каждый элемент ссылается только на один другой элемент, а на каждый элемент ссылается только одна объектная ссылка. В класс ConcurrentStack из листинга 15.6 демонстрируется, как построить стек с использованием атомарных ссылок. Стек представляет собой связанный список элементов Node , вершина которого хранится в переменной top , каждый элемент списка содержит значение и ссылку на следующий элемент. Метод push подготавливает новую ссылку на элемент, следующее поле которого ссылается на текущую вершину стека, и затем использует операцию CAS, чтобы попытаться установить его качестве вершины стека. Если тот же самый узел все еще находится на вершине стека, как и в тот момент, когда мы начали, операция CAS выполняется успешно; если верхний узел изменился (потому что другой поток добавил или удалил элементы, во время начала выполнения операции), операция CAS завершается сбоем и метод push обновляет информацию о новом элементе на основе текущего состояния стека и повторяет операцию вновь. В любом случае, стек все еще находится в согласованном состоянии, после выполнения операции CAS. @ThreadSafe public class ConcurrentStack AtomicReference Node Node } while (!top.compareAndSet(oldHead, newHead)); } public E pop() { Node Node } while (!top.compareAndSet(oldHead, newHead)); return oldHead.item; } private static class Node } } } Листинг 15.6 Неблокирующий стек использующий алгоритм Трейбера (Treiber, 1986) Классы CasCounter и ConcurrentStack иллюстрируют характеристики всех неблокирующих алгоритмов: некоторая работа выполняется спекулятивно и, возможно, её придется переделывать. В классе ConcurrentStack , при создании экземпляра Node , представляющего собой новый элемент, мы надеемся, что значение ссылки next , к моменту установки в стеке, будет по-прежнему корректным, но готовы повторить попытку в случае возникновения конкуренции. Неблокирующие алгоритмы, подобные классу ConcurrentStack , выводят свою потокобезопасность из того факта, что, подобно блокировке, метод compareAndSet предоставляет гарантии как атомарности, так и видимости. Когда поток изменяет состояние стека, он делает это с помощью метода compareAndSet , который обладает теми же эффектами памяти при записи, что и volatile . Когда поток проверяет стек, он делает это, вызывая метод get на том же экземпляре AtomicReference , который обладает теми же эффектами памяти при чтении, что и volatile . Таким образом, любые изменения, сделанные одним потоком, безопасно публикуются в любом другом потоке, который проверяет состояние списка. И список модифицируется методом compareAndSet , который атомарно обновляет ссылку на элемент top или завершает своё выполнение сбоем, если обнаруживает влияние другого потока. 15.4.2 Неблокирующий связанный список Два неблокирующих алгоритма, которые мы видели до сих пор, счетчик и стек, иллюстрируют основную схему использования операций CAS для спекулятивного обновления значения, с повторной попыткой, если выполнить обновление не удается. Хитрость построения неблокирующих алгоритмов заключается в ограничении области атомарных изменений одной переменной. Со счетчиками это тривиально, и со стеком всё достаточно прямолинейно, но для более сложных структур данных, подобных очередям, хэш-таблицам или деревьям, всё может быть намного сложнее. Связанная очередь сложнее, чем стек, поскольку она должна поддерживать быстрый доступ как к голове (head), так и к хвосту (tail). Для этого она сохраняет отдельные указатели на голову и хвост. Два указателя ссылаются на узел в хвосте: next, указывающий на текущий последний элемент и указатель хвоста. Для успешной вставки нового элемента, оба указателя должны обновляться атомарно. На первый взгляд, это невозможно сделать с помощью атомарных переменных; для обновления двух указателей требуются отдельные операции CAS, и если первая завершается успешно, но второй это сделать не удаётся, очередь остается в несогласованном состоянии. И, даже если обе операции выполняются успешно, другой поток может попытаться получить доступ к очереди между первой и второй операциями. Построение неблокирующего алгоритма для связанной очереди требует конкретного плана для обеих ситуаций. Для разработки этого плана нам необходимо несколько трюков. Во-первых, убедитесь, что структура данных всегда находится в согласованном состоянии, даже в процессе многоэтапного обновления. Таким образом, если поток A находится в процессе обновления, когда поток B выходит на сцену, потоку B могут сообщить, что операция была частично завершена, и он будет знать, что нельзя пытаться немедленно применить свое собственное обновление. Затем поток B может ожидать (многократно проверяя состояние очереди) до тех пор, пока поток A не завершит своё выполнение, чтобы они не мешали друг другу. В то время как этого трюка самого по себе будет достаточно, чтобы позволить потокам получать доступ к структуре данных “по очереди” без её повреждения, если у одного потока произошёл сбой в середине выполнения обновления, ни один поток не сможет получить доступ к очереди. Чтобы сделать алгоритм неблокирующим, мы должны гарантировать, что сбой потока не помешает другим потокам добиться прогресса. Таким образом, второй трюк состоит в том, чтобы убедиться, что если поток B прибывает, чтобы получить доступ к структуре данных в середине операции обновления потока A, в структуре данных для потока B воплощено достаточно информации, чтобы завершить операцию обновления потока A. Если поток B “помогает” потоку A, завершая операцию A, поток B может продолжить свою собственную операцию, не дожидаясь потока A. Когда поток A завершит свою работу, он обнаружит, что поток B уже выполнил эту работу за него. Класс LinkedQueue из листинга 15.7, демонстрирует часть неблокирующего алгоритма Майкла-Скотта (Michael and Scott, 1996), касающуюся вставки в связанную очередь, который используется в классе ConcurrentLinkedQueue . Как и во многих других алгоритмах очередей, пустая очередь состоит из “дозорного” (sentinel) или “фиктивного” (dummy) узла, а указатели на голову и хвост инициализируются ссылками на дозорный узел. Указатель хвоста всегда ссылается на дозорный узел (если очередь пуста), последний элемент в очереди или (в случае, если операция находится в процессе обновления) предпоследний элемент. @ThreadSafe public class LinkedQueue } } private final Node = new AtomicReference = new AtomicReference Node Node Node // Queue in intermediate state, advance tail tail.compareAndSet(curTail, tailNext); B } else { // In quiescent state, try inserting new node if (curTail.next.compareAndSet(null, newNode)) { // Insertion succeeded, try advancing tail tail.compareAndSet(curTail, newNode); return true; } } } } A B C D } } Листинг 15.7 Фрагмент неблокирующего алгоритма Michael-Scott, касающийся вставки в очередь На рисунке 15.3 иллюстрируется очередь с двумя элементами в нормальном, или спокойном (quiescent) состоянии. Рисунок 15.3 Очередь с двумя элементами в спокойном состоянии Вставка нового элемента предполагает обновление двух указателей. Первый связывает новый узел с концом списка, обновляя указатель next на текущий последний элемент; второй перемещает указатель хвоста в обход, чтобы указать на новый последний элемент. Между этими двумя операциями, очередь находится в промежуточном (intermediate) состоянии, показанном на рис. 15.4. Рисунок 15.4 Очередь в промежуточном состоянии в процессе вставки После второго обновления очередь снова находится в состоянии покоя, показанном на рисунке 15.5. Рисунок 15.5 Очередь вновь в состоянии покоя, после завершения вставки Ключевое наблюдение, которое включает оба из требуемых трюков, состоит в том, что, если очередь находится в состоянии покоя, связующее поле элемента next , на который указывает хвост, содержит null , и если это промежуточное состояние, значение поля tail.next не null . Таким образом, любой поток может сразу определить состояние очереди, проверяя значение поля tail.next . Кроме того, если очередь находится в промежуточном состоянии, ее можно восстановить tail head dummy 1 2 tail head dum my 1 3 1 tail head dum my 1 3 1 в состояние покоя, переместив указатель хвоста вперед на один узел, таким образом, завершив операцию для любого потока, находящегося в процессе вставки элемента. 169 Метод LinkedQueue.put сначала проверяет, находится ли очередь в промежуточном состоянии, прежде чем вставлять новый элемент (шаг A). Если это так, то какой-то другой поток уже находится в процессе вставки элемента (между шагами C и D). Вместо того чтобы ожидать завершения этого потока, текущий поток помогает ему, завершая операцию для него, продвигая указатель хвоста (шаг B). Затем он повторяет эту проверку в том случае, если другой поток начал вставлять новый элемент, продвигая указатель хвоста, пока он не обнаружит очередь в состоянии покоя, чтобы он мог начать свою собственную вставку. Операция CAS на шаге C, в котором новый узел связывается хвостом очереди, может завершиться сбоем, если в одно и то же время два потока пытаются вставить элемент. В этом случае ничего страшного не происходит: никаких изменений не было сделано, и текущий поток может просто повторно загрузить указатель на хвост и повторить попытку. После успешного завершения шага C, вставка считается вступившей в силу; второй операцией CAS (стадия D) является “очистка”, поскольку она может быть выполнена либо вставляющим элемент потоком, либо любым другим потоком. Если на шаге D происходит сбой, вставляющий поток так или иначе возвращается, вместо того, чтобы повторно выполнить операцию CAS, потому что в повторной попытке нет необходимости - другой поток уже выполнил задание на шаге B! Это работает потому, что прежде чем какой-либо поток попытается связать новый узел с очередью, он сначала проверяет, нуждается ли очередь в очистке, проверяя, что значение поля tail.next не null . Если это так, он сначала перемещает указатель хвоста (возможно, несколько раз), до тех пор, пока очередь не будет находиться в состоянии покоя. 15.4.3 Обновления атомарного поля В листинге 15.7 показан алгоритм, используемый классом ConcurrentLinkedQueue , но фактическая реализация немного отличается. Вместо представления каждого экземпляра Node с помощью атомарной ссылки, класс ConcurrentLinkedQueue использует volatile ссылку и обновляет ее с помощью основанного на reflection класса AtomicReferenceFieldUpdater , как показано в листинге 15.8. private class Node } } private static AtomicReferenceFieldUpdater 169 Полный отчет о корректности этого алгоритма см. (Michael and Scott, 1996) или (Herlihy and Shavit, 2006). = AtomicReferenceFieldUpdater.newUpdater( Node.class, Node.class, "next"); Листинг 15.8 Использование обновлений атомарных полей в классе ConcurrentLinkedQueue Классы-апдейтеры (updater classes) атомарных полей (доступные в Integer , Long и Reference версиях) представляют основанное на reflection “представление” существующего поля volatile так, чтобы операция CAS могла использоваться на существующих volatile полях. Классы-апдейтеры не имеют конструкторов; для их создания необходимо вызвать фабричный метод newUpdater , указав класс и имя поля. Классы-апдейтеры полей не привязаны к определенному экземпляру; их можно использовать для обновления целевого поля в любом экземпляре целевого класса. Гарантии атомарности для классы-апдейтеров слабее, чем для обычных атомарных классов, потому что вы не можете гарантировать, что базовые поля не будут изменены непосредственно - метод compareAndSet и арифметические методы гарантируют атомарность только по отношению к другим потокам, использующим методы апдейтеров для обновления атомарных полей. В классе ConcurrentLinkedQueue , для обновления поля next экземпляра Node используется метод compareAndSet , вызываемый из метода nextUpdater . Этот, в некоторой степени, окольный подход используется исключительно по соображениям производительности. Для часто выделяемых (allocated) короткоживущих объектов, подобных связываемым узлам в очереди, исключение создания экземпляра AtomicReference для каждого экземпляра Node приводит к достаточно значительному снижению затрат на операции вставки. Тем не менее, практически во всех ситуациях обычные атомарные переменные работают просто отлично - только в нескольких случаях будут требоваться апдейтеры атомарных полей. (Апдейтеры атомарных полей также полезны тогда, когда вы хотите выполнить атомарные обновления, сохраняя сериализованную форму существующего класса.) 15.4.4 Проблема ABA Проблема ABA является аномалией, которая может возникнуть из-за наивного использования алгоритмов сравнить-и-обменять, в которых узлы могут быть переработаны 170 (в основном в средах без сборки мусора). Операция CAS фактически спрашивает "Значение V все еще A?” , и продолжает обновление, если это так. В большинстве ситуаций, включая примеры, представленные в этой главе, этого вполне достаточно. Однако иногда мы хотим спросить: “Изменялось ли значение V с тех пор, как я наблюдал, что оно было A?”. Для некоторых алгоритмов изменение значения V с A на B, а затем обратно на A по-прежнему считается изменением, которое требует от нас повторения некоторых алгоритмических шагов. Проблема ABA может возникнуть в алгоритмах, которые выполняют своё собственное управление памятью для объектов связываемых узлов. В этом случае недостаточно того, что голова списка все еще ссылается на ранее наблюдаемый узел, чтобы подразумевать, что содержимое списка не изменилось. Если вы не можете избежать проблемы ABA, разрешив сборщику мусора управлять ссылочными узлами, существует относительно простое решение: вместо обновления значения ссылки, обновите пару значений, ссылку и номер версии. 170 Каким-то образом «очищены» и снова пущены в работу, вместо уничтожения старого экземпляра и создания нового. Даже если значение изменяется с A на B и обратно на A, номера версий будут отличаться. Класс AtomicStampedReference (и его кузен AtomicMarkableReference ) обеспечивают условное атомарное обновление пары переменных. Класс AtomicStampedReference обновляет объект пары “ссылка - целое число”, позволяя “версионированным” ссылкам стать нечувствительными 171 к проблеме ABA. Аналогично, класс AtomicMarkableReference обновляет пару “ссылка на объект - булево значение”, которая используется некоторыми алгоритмами, чтобы позволить узлу оставаться в списке, когда он помечен как удаленный. 172 15.5 Итого Неблокирующие алгоритмы поддерживают потокобезопасность, используя вместо блокировок низкоуровневые примитивы параллелизма, такие как сравнить-и- поменять. Эти низкоуровневые примитивы предоставляются через классы атомарных переменных, которые также могут использоваться как “лучшие volatile переменные”, обеспечивая атомарные операции обновления для целых чисел и ссылок на объекты. Неблокирующие алгоритмы трудно разработать и реализовать, но они могут предложить лучшую масштабируемость в типичных условиях и большую устойчивость к сбоям живучести. Многие достижения в области параллельной производительности от одной версии JVM к другой, связаны с использованием неблокирующих алгоритмов как в JVM, так и в библиотеках платформы. 171 На практике, в любом случае; теоретически счетчик можно обернуть. 172 Многие процессоры предоставляют операцию CAS двойной ширины (CAS2 или CASX), которая может работать с парой “ указатель - целое”, что делает выполнение это операции достаточно эффективным. Начиная с Java 6, класс AtomicStampedReference не использует операцию CAS двойной ширины даже на платформах, которые его поддерживают. (Двойная операция CAS отличается от DCAS, который работает с двумя несвязанными расположениями памяти; на момент написания статьи ни один текущий процессор не реализует операцию DCAS.) |