13 апреля 2011 г.

Biased locking

У стендов на Java One замечательные люди Алексей Шипилёв и Сергей Куксенко рассказывали много всего интересного. Например, узнал, как именно работает biased locking, и зачем он нужен.

По словам Сергея, история с оптимизацией блокировок началась с того, что лазить syscall-ами в ОС за platform-dependent мьютексами в какой-то момент показалось не очень оптимально -- большое число блокировок берется на малое время, и даже при большом числе потоков contention оказывается весьма мал. Для разруливания этого в JVM были реализованы спин-локи (Сергей называл их thin-locks) -- мы просто заводим поле ownerThreadId, и, пытаясь захватить монитор, CAS(-1, threadId)-им туда свой threadId. Если CAS удался -- мы захватили монитор. Если нет -- мы делаем еще несколько попыток в цикле (а вдруг нынешний владелец отпустит монитор буквально через пару тактов?). Количество итераций это предмет тонкого тюнинга, возможно даже адаптивного, на базе профиля предыдущих попыток. Если даже со спиннингом мы не захватили монитор -- откатываемся к OS-specific locks (Сергей назвал их fat locks).

Такие "тонкие" блокировки хорошо работали в одноядерных процессорах, где CAS был дешев. С появлением многоядерных и NUMA систем CAS подорожал :) -- поначалу весьма прилично (со временем ситуация улучшилась -- сейчас CAS в многоядерных системах уже гораздо дешевле). Чтобы как-то адаптироваться и к этому вызову и были придуманы "привязанные" блокировки, которые являются естественным продолжением спин-локов, минимизирующим количество сравнительно-дорогих-CAS-ов для случая, когда монитор долгое время (или вообще всегда) используется одним и тем же потоком.

Как я уже говорил, привязанную блокировку можно рассматривать как продолжение спин-лока. Мы захватываем блокировку в собственность (привязываем ее) точно так же, CAS-ом записывая свой threadId. Только в отличие от спин-лока мы не отдаем ее назад. Вместо этого мы рядом заводим дополнительное поле, reetranceCount -- где будет 0, если реально мы сейчас блокировку не используем, и глубина захвата (для поддержания реентрабельности) в случае, если используем. Это поле thread-local, пишется-читается обычными store/load, безо всяких волшебных CAS и специальных мембаров.

Самое интересное здесь это процедура отзыва привязки -- если на привязанную блокировку пришел посторонний поток, и пытается ее взять. Необычно то, что не "владеющий" блокировкой поток ее отдает -- а "пришлый" поток ее "отбирает". Выглядит это так: пришлый смотрит поле типа блокировки -- видит там "biased", смотрит ownerID, и останавливает поток с таким ID (sic!). Остановив этот поток мы гарантируем себя от изменения состояния этого монитора -- ведь только поток-владелец может его изменить. (На самом деле здесь все не так просто. Нам нужно не просто остановить поток, но и вынудить его сбросить в память все свои store buffers -- чтобы убедиться, что он не находится в процессе обновления reentranceCount. Сделать это для другого потока -- довольно нетривиальная задача, для которой готовых решений разработчиками процессоров не предусмотрено. Приходится это делать через совершенно эзотерические, заточенные под конкретный процессор "хаки" -- некоторые действия, у которых основное назначение совсем другое, но побочный эффект которых -- на данной архитектуре -- сброс буферов. Краткий обзор этих хаков, встретившийся мне в статье, способен лишить вас сна на пару дней, и опустить ЧСВ ниже плинтуса) Гарантировав себе stop-the-world для отдельно взятого монитора мы теперь считываем reentranceCount (как я понял, здесь все так легко и просто только в случае архитектур с аппаратной когерентностью кэша -- как интеловские и AMD-шные). Если reentranceCount=0, значит поток-бывший-владелец сейчас монитор не использовал, и мы можем просто сменить тип монитора на thin (spin-lock), захватить его уже на себя, и разбудить назад бывшего владельца. Если же reentranceCount > 0 -- все серьезно, и мы вынуждены откатиться к fat (OS-specific) блокировкам.

Таким образом получается, что для biased locks начальный захват умеренно дорог (один CAS), дальнейший захват очень дешев ( обычный store), отзыв привязки очень дорог (требует syscall для остановки владельца, плюс несколько CAS-ов для смены типа блокировки и захвата под себя).

Любопытные вещи -- biased locks оказывается активируются не сразу ("по-умолчанию") а лишь после некоторого прогрева JVM. Почему так Сергей сказать точно не смог, предположил, что так удается избежать привязки объектов к инициализирующему потоку, который, часто, больше на протяжении всей работы приложения никогда с созданными объектами и не работает. Правда, флагами запуска JVM это можно переопределить.

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

6 комментариев:

  1. Спасибо за последние 3 поста, очень редкая информация! А ребята на JavaOne не говорили где про эти механизмы можно еще почитать? (Эту уже нашел - http://blogs.sun.com/dave/entry/biased_locking_in_hotspot)

    ОтветитьУдалить
  2. Наши правильные имена: Алексей Шипилёв и Сергей Куксенко :)

    ОтветитьУдалить
  3. >А ребята на JavaOne не говорили где про эти механизмы можно еще почитать?

    У меня несколькими постами позже есть ссылка на диссертацию по этому вопросу :)

    >Наши правильные имена: Алексей Шипилёв и Сергей Куксенко :)

    Ой :) Дико извиняюсь, сейчас исправлю.

    ОтветитьУдалить
  4. Этот комментарий был удален автором.

    ОтветитьУдалить
  5. Я извиняюсь за некропостерство, но раз уж наткнулся на эту статью дополню из статьи Глеба Смирнова (http://habrahabr.ru/post/143237/) для остальных, кто также попадёт сюда по первой ссылке с запроса "biased locking":
    Biased locking включается не сразу после запуска виртуальной машины, а спустя BiasedLockingStartupDelay миллисекунд (4000 по умолчанию). Это сделано, поскольку иначе в процессе запуска и инициализации виртуальной машины, загрузки классов и всего прочего появилось бы огромное число safepoints, вызванных постоянным revoke bias у живых объектов.

    ОтветитьУдалить
    Ответы
    1. Извиняться не нужно. Материал живее всех живых!

      Удалить