Почему кто-то может назвать состояние гонки приятным?

Условия гонки — горькая правда о параллельных приложениях. Но почему кто-то может назвать состояние гонки приятным? Очарование этого гоночного состояния заключается в его утонченности снаружи, которой противостоят замысловатые сложности под капотом. Вероятно, именно поэтому люди называют это хорошим состоянием гонки.

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

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

Давайте начнем…

Рассмотрим следующий код Java:

public class NiceRC {

    public static void main(String[] args) {
        final Map<Object, Object> unsafeMap = new HashMap<>();
        final List<Thread> threads = new ArrayList<>();
        for (int i = 0; i < 5; ++i) {
            threads.add(new Thread(() -> {
                for (int j = 0; j < 100000; ++j) {
                    unsafeMap.put(new Object(), new Object());
                }
            }));
        }
        threads.forEach(Thread::start);
        threads.forEach(thread -> {
            try {
                thread.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });
        System.out.println("Size of unsafeMap: " + unsafeMap.size());
    }

}

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

В этом коде мы запускаем 5 потоков, и каждый поток добавляет около 100 тысяч записей на общую карту под названием unsafeMap.

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

Оказывается, здесь действует состояние гонки.

Но прежде чем говорить о состоянии гонки, давайте еще раз вспомним Java HashMap. Это понадобится, чтобы понять, что происходит под капотом!

Внутренняя часть HashMap

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

Ниже приведено определение класса Entry, используемого для представления узлов связанного списка внутри HashMap.

static class Entry<K,V> implements Map.Entry<K,V> 
{
        final K key;
        V value;
        Entry<K,V> next;
        int hash;
}

Когда количество пар ключ-значение, хранящихся в HashMap, превышает пороговое значение, ему необходимо изменить размер внутреннего массива и повторно хешировать все элементы. Этот процесс называется перефразированием или изменением размера.

Вот часть кода, выполняющая это изменение размера:

  // Transfer method in java.util.HashMap -
  // called to resize the hashmap

  for (int j = 0; j < src.length; j++) {
    Entry e = src[j];
    if (e != null) {
      src[j] = null;
      do {
        Entry next = e.next;
        int i = indexFor(e.hash, newCapacity);
        e.next = newTable[i];
        newTable[i] = e;
        e = next;
     } while (e != null);
   }
 }

Давайте рассмотрим пример, чтобы понять, как работает этот код перефразирования.

Рассмотрим карту с двумя сегментами и тремя элементами.

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

Все три элемента карты будут перефразированы. Ключи A и B будут хешированы с сегментом 3, а ключ C — с сегментом 1.

После одной итерации цикла состояние этой карты будет следующим.

Узел A извлекается из исходного сегмента и добавляется в начало нового сегмента.

После еще одной итерации этого цикла к заголовку сегмента 3 будет добавлен узел B.

Еще одной итерацией процесс перефразирования завершается. Это окончательное состояние карты.

К состоянию гонки…

Обладая всеми этими знаниями внутреннего устройства HashMap, мы готовы выявить состояние гонки, которое поразило наш класс NiceRC.

Рассмотрим еще раз следующую карту с двумя сегментами и тремя элементами.

Но на этот раз два потока пытаются выполнить операцию изменения размера/перефэширования одновременно. Назовем эти потоки «Потоком 1» и «Потоком 2».

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

Сначала рассмотрим первый поток, входящий в цикл изменения размера. Он инициализирует переменные e и next. Затем по какой-то причине поток 1 останавливается. Его выкидывают из процессора по любой возможной причине.

(Для ясности к переменным потока добавляется номер потока)

// Transfer method in java.util.HashMap -
  // called to resize the hashmap

  for (int j = 0; j < src.length; j++) {
    Entry e = src[j];
    if (e != null) {
      src[j] = null;
      do {
        Entry next = e.next;
        // THREAD 1 STOPS HERE
        int i = indexFor(e.hash, newCapacity);
        e.next = newTable[i];
        newTable[i] = e;
        e = next;
     } while (e != null);
   }
 }

Это состояние локальных переменных потока 1 на момент вытеснения.

Предположим, что поток 1 вытесняется из ЦП, а поток 2 — нет и завершает процесс изменения размера. Теперь это новое состояние нашей карты.

:::информация Обратите внимание, что процесс изменения размера не клонирует объекты Entry, поэтому e1 и next1 по-прежнему ссылаются на допустимые объекты в новом состоянии. Однако следующее соотношение теперь изменилось неправильным образом.

:::

В этот момент поток 1 снова запланирован и начинает выполнение с того места, где остановился.

Он добавляет узел A в начало нового сегмента.

На следующей итерации переменные e1 и next1 обновляются, чтобы указывать на узел B и узел A соответственно. При этом мы добавляем узел B в начало нового сегмента.

Затем мы обновляем переменную e1, чтобы она указывала на узел A. Поскольку у узла A нет следующего узла, next1 теперь имеет указатель на ноль.

Наш алгоритм (снова) пытается добавить узел A в начало нового сегмента.

При этом структура нашей карты успешно повреждена!

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

Именно это произошло с нашим классом NiceRC.

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

:::информация Также опубликовано здесь.

:::