Санкт-Петербургская группа тестирования JVM

Тайна случайных пробуждений

В одном из наших постов мы уже писали про так называемые "случайные пробуждения" (spurious wakeups) функции Object.wait().

Откуда они взялись? В Java они пришли из библиотеки pthreads и примитивов синхронизации в Солярисе¹, через которые Object.wait() был реализован.

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

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

В качестве примера, документация на pthreads приводит неудачную реализацию нотификаций в разделе RATIONALE pthread_cond_broadcast().

А теперь мы ответим на вопросы, которые могут вас беспокоить в связи со сказанным выше.

Каким образом случайные пробуждения дисциплинируют программиста?

Как правило, ожидания и нотификации связаны с изменением состояния объекта. Именно по этой причине Java предписывает делать Object.wait() и notify() внутри блока synchronized. А при выходе из wait() было бы логичным проверять новое состояние, особенно зная о возможности случайного пробуждения.

Если мы попытаемся декомпозировать сущности объекта связанные с взаимодействием нитей, то получится следующая структура:

• Переменные состояния объекта.
• Блокировка объекта, позволяющая нам изменять состояние объекта или же гарантировать его неизменность. В целях эффективности блокировки могут разбиты на несколько или объединены в блокировку более высокого в иерархии объекта, или же заменены неблокирующими примитивами CAS, но это не меняет сути.
• Предикаты (или условные переменные), отражающие особые состояния объекта, например "буфер полон" или "буфер пуст"².

Как правило, нотификация связана со "сработавшим" вследствии изменения состояния объекта условием (предикатом). Конечно, с целью исключения случайных пробуждений в языке Java возможно ввести специальные внутренние предикаты в реализацию java.lang.Object, но они будут лишь дублировать переменные состояния объекта, что избыточно и черевато.

Проверяя состояние объекта после wait(), мы осуществляем фильтрацию случайных пробуждений на уровне методов объекта, таким образом изолируя другие объекты от подробностей пробуждения данного. Так делает, например, java.util.concurrent.CyclicBuffer, где случайные выходы из метода await() были бы совсем неприемлемыми.

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

Почему случайные пробуждения приводят к более эффективным реализациям?

Вот один пример: pthread_cond_wait в linux.

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

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

Кстати говоря, "лакмусовой бумажкой" определяющей коррекную реализацию блокировок на основе вызовов park/unpark является сохранение работоспособности программы при замене этих вызовов пустой операцией (nop). А что это, как не имитация случайных пробуждений?

Ссылки

1. http://www.cs.umd.edu/~pugh/java/memoryModel/archive/1328.html
   David Holmes объясняет, почему в Java появились случайные пробуждения
2. http://groups.google.de/group/comp.programming.threads/msg/bb8299804652fdd7
   Ссылки на различные обсуждения данной проблемы в pthreads

Кирилл Широков

¹Синхронизация в Java была реализована на Солярисе через примитивы lwp_ (например, lwp_cond_wait()), которые, в какой-то момент основывались на старых примитивах sleep и wakeup ядра System V. Sleep принимал в качестве аргумента ключ, который обычно являлся адресом объекта синхронизации, а wakeup будил процессы по тому же ключу. Однако в своих таблицах ядро не учитывало PID и будило все подходящие процессы. Конечно же, этот баг был впоследствии исправлен.

²Надо заметить, что в отличие от "родной" синхронизации в Java, в библиотеке java.util.concurrent есть поддержка множества предикатов связанных с одной блокировкой.