Собеседование по Java concurrency

Нашел интересный список из over 50 вопросов к интервью по Java concurrency и многопоточности. На все старался отвечать честно, что совсем не знал - гугл (~11 вопросов в основном на тему хитрых названий).

Ниже то что получилось.

Назовите различия между Collections.synchronizedMap(new HashMap()) и ConcurrentHashMap.

SynchronizedMap оборачивает обычный Map используя единственный монитор для блокировки,
тогда как ConcurrentHashMap

• позволяет делать неблокирующее чтение (но можно увидеть старые\невалидные данные)
• на запись делит map на секции, к каждой из которых идет свой объект блокировки (это уменьшает общее время ожидания)

Что такое кооперативная многозадачность и есть ли она в Java. Если да, то какие преимущества. Если нет, то какая тогда в Java?

Способ деление времени CPU между потоками при котором каждый поток обязан отдавать управление следующему добровольно.

Преимущества - возможно меньшие накладные расходы на переключение контекста если среда исполнения полностью нами контролируется (нет лишних переключений контекста)

Недостатки - если один поток завис или ведет себя некорректно то вся система зависла и другие потоки никогда не получат управление.

В Java - вытесняющая многопоточность.

Что такое "зеленый потоки" и есть ли они в Java (в HotSpot JVM.6)?

Легковесные потоки (эмулируемые) виртуальной машиной или средой исполнения..

не подрузамевают под собой реального создания соотв. потоков ОС, как следсвие нет переключения между USER и KERNEL режимами ядра ос. В Java6 нету.

Различия в интерфейсах Runnable и Callable.

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

Напишите минимальный неблокирующий стек (всего два метода — push() и pop()).

Напишите минимальный copy-on-write ArrayList (всего четыре метода — void add(int indx, int item), int get(int indx), void remove(int indx), int size()).

Различя между Thread.isInterrupded() и Thread.interrupted().

interrupted() проверяет флаг того что поток прерван и сбрасывает его, isInterrupded() ничего не трогает и можно вызывать несколько раз

Что происходит при вызове Thread.interrupt()?

Если поток

• заблокирован на мониторе, ждет другой поток итп (wait, notify) - вылетит InterruptedException но флаг interrupted потока не поставится
• Если поток ждет ввод-вывод на InterruptableChannel то тоже вылетит exception
• Ecли поток ждет ввод-вывод то он тут же прекратится и выставится флаг Interrupted
• Либо просто ставится статус Interrupted

Некоторые из следующих методов deprecated а некоторые и не были никогда реализованы. Какие? Thread.interrupt(), Thread.stop(), Thread.yield(), Thread.suspend(), Thread.resume(), Thread.join(), Thread.start(), Thread.run(), Thread.sleep().

• stop(), suspend(), resume() - deprecated т.к. могут убить\остановить поток оставив его ресурсы в неизвестном\промежуточном состоянии которое не является валидным
• interrupt() - прерывает поток если он занимается I/O и выставляет флаг interrupted
• yield() - принудительно передает квант времени следующему потоку
• join() - текущий поток ждет другой поток
• start() - стартует нитку
• run() - стартует код в текущей нитке без порождения отдельного потока
• sleep() - усыпить поток на некоторое время, не отпуская захваченные локи\мониторы\ресурсы

Что Вы знаете о асинхронных вызовов методов? Есть ли это в самом языке Java? Если есть, то как реализовано? Если нет, то как бы Вы реализовали?

Есть ExecutorService который принимает Callable, и возвращает интерфейс Future; это позволяет

• заблокироваться и подождать завершения вычислений
• следить за тем выполнен Callable или нет
• отменить вычисление если оно не закончислось

Перечислите ВСЕ причины по которым может выскочить InterruptedException.

Поток ждет в wait, sleep(...), join() или заблокирован на длительное время аналогичным вызовом.. и из соседнего потока дернули interrupt()

Что изменилось между JMM до Java 5 и NewJMM после Java 5?

volatile дает более внятные happens before гарантии, не только на порядок присвоения самих volatile переменных но и на side-эффекты. Плюс стало возможным писать код вида и быть уверенным что в момент когда из другого потока обратятся к полю obj, ссылка будет присвоена уже проинициализированному объекту и конструктор полностью отработает. В старой Memory model ссылка могла присвоиться не полностью собранному объекту из за эффекта переупорядочивания инструкции VM и CPU.

В классе String все поля финальные. Можно ли убрать ключевое слово финал? Ведь сеттеров все равно нет — следовательно поля нельзя переустановить.

Нет, т.к. final поля нужны для безопасной "публикации" объектов между потоками.

Что такое ordering, visibility, atomicity, happens-before, mutual exclusion. И показать на примерах volatile, AtomicInteger, synchronize{} — что из вышеперечисленного списка присутствует и при каких вариантах использования.

• ordering - определяет когда один поток может увидеть out-of-order (т.е. неправильный) порядок исполнения инструкций другого потока. CPU может переупорядочивать и выполнять x86 инструкции в произвольном порядке для повышения пифоманса до тех пор пока для потока внутри не видно никаких отличий. Называется такая гарантия as-if-serial semantics. Проблемы же появляются когда нужно получать доступ из нескольких потоков к общей памяти - все эти side-эффекты вылезают. Решается с помощью механизмов публикации\синхронизации\гарантий Java Memory Model
• visibility - определяет когда действия в одном потоке станут видны в другом потоке
• atomicity - атомарность операций, операция выглядит как единая и неделимая операция которая либо выполнилась либо еще нет
• Как правило все ошибки в многопоточном приложении попадают из за несоблюдения одного из 3х - visibility, atomicity, ordering
• happens-before - логическое ограничение на порядок выполнения программы, термин используется в спеке по Java Memory Model. Например если мы говорим что запись в переменную A и последующее ее чтение связаны чз эту зависимость - то как бы не переупорядочивались инструкции в момент чтения мы должны видеть все size-эффекты от выполненной ранее операции записи.
• volatile - дает гарантии happens-before на все присвоения переменных до текущего момента (так называемый read memory barrier)/li>
• AtomicInteger - позволяет выполнять атомарные Compare-and-swap операции реализованные аппаратно в CPU. Основная выгода от CAS операций появляется только при условии что переключать контекст процессора с потока на поток менее выгодно чем немного покрутиться в цикле while пытаясь выполнить апдейт вида boolean compareAndSwap(oldValue, newValue). Если время потраченное в таком цикле превышает 1 квант потока то atomic переменные может быть невыгодно использовать с точки зрения производительности..
• synchronize - создает mutex (взаимоисключающую блокировку) некоторого объекта, каждый поток которые не может захватить объект блокируется на неопределенное время. mutex - частный случай semaphore с единственным состоянием.

Назовите отличия synchronize{} и ReentrantLock.

• synchronize - более примитивная конструкция которая обязывает нас отпустить monitor по окончании секции. Таким образом захват\освобождение всегда идут парами и всегда связаны с некоторым блоком кода
• ReentrantLock - можно захватывать и освобождать мониторы в произвольном порядке, дает гибкость но сложнее сделать все правильно. Также есть опция fair - следить ли за "честным" порядком предоставления доступа\времени ожидания потоков на мониторе.
• ReentrantLock - лучше масштабируется при росте числа потоков

Что из данных вызовов создает happend-before: Thread.sleep(), Thread.join(), Thread.yield(), Thread.start(), Thread.run(), Thread.isAlive(), Thread.getState()?

Только join(), start(), isAlive()

Перечислите известные Вам способы борьбы с priority inversion, назовите классы систем где они особенно опасны.

Опасны в real time системах, возникают из за особенностей планировщиков задач\прерываний. Способов предотвращения несколько -

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

Перечислите известные Вам способы 1)избежать 2)побороть возникшие deadlock-и (представьте, что вы пишете ядро RDBMS).

Чтобы избежать дедлоков -

• Захватывать везде ресурсы в одинаковом порядке
• или знать заранее какие ресурсы в каком порядке будут захвачены - строить граф переходов м-ду состояниями

Чтобы побороть дедлок

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

Расскажите о паттернах Reactor/Proactor?

Оба паттерна используются для высокопроизводительной обработки данных и разделения потока данных по worker-потокам. Основное отличие в том вычитывает ли listener сам данные или ждет пока это сделает callback, во многом на производительность и предпочтительный шаблон влияет наличие в ОС асинхронного ввода вывода и насколько хорошо он реализован. В Win - выигрывает Proactor, в *nix - Reactor.

• Reactor - получил нотификацию что данные пришли, уведомил user callback, callback сам вычитал нужные данные, callback их обрабатывает
• Proactor - полчил нотификацию что данные пришли, сам вычитал нужные данные в буфер, уведомил user callback чтобы тот забрал данные, callback их обрабатывает

Что такое "monitor"?

Объект для синхронизации. Используется для безопасного разделения ресурсов между потоками (Mutex).

Что такое "private mutex"?

Объект для синхронизации делается private, чтобы сторонний код не мог на него синхронизироваться и вдруг случайно получить deadlock.

Что такое "priority inheritance"?

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

Что такое "backoff protocol (exponential backoff)"?

Некоторая договоренность (алгоритм) между потоками (или нодами) что делать в случае конфликта. Например после неудачной попытки захватить ресурс интервал повторной попытки на каждом ноде должен вычисляться так чтобы минимизировать вероятность повторного конфликта\совпадения по времени с другими нодами.

Что такое "task stealing"?

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

Что такое "ABA problem"?

Возникает при compare-and-swap вызовах если значение переменной переполнилось (или совершило цикл\вернулось к старому значению). В этом случае механизм compare-and-swap перестает быть надежным.

Что такое "test-and-set"?

Аналогично compare-and-swap но при сравнении значение проверяется на 0.

Что такое "test-and-test-and-set"?

Перед использованием test-and-set стараемся предварительно проверить занят ли лок кем либо другим (например выполняем цикл пока некоторая shared-переменная не покажет что ресурс свободен)

Что такое "spin lock"?

Поток ждет освобождения lock'a проверяя в цикле условие\ресурс.

Что такое "sequential consistency"?

То же что и as-if-serial semantics, гарантии что в рамках одного потока побочные эффекты от всех операций будут такие, как будто все операции выполняются последовательно.

Что такое "sense-reversing barrier"?

Способ повторного использования для Barrier. В барьере хранится флаг sence, и в каждом потоке его использующем хранится аналогичный флаг в ThreadLocal переменной. Идея в том чтобы меняя эти флаги при вызове await() использовать барьер для поочередной разблокировки то одного потока то другого.

Что такое "safe publication"?

Показ объектов другим потокам из текущего, не нарушая ограничений visibility. Способы публикации в Java:

• static{} инициализатор
• volatile переменные
• atomic переменные
• сохранение в shared переменной, корректно защищенной с использованием synchronized()или Lock'и и другие конструкции создающие read/write memory barrier
• final переменные в shared-объекте который был корректно проинициализирован

Что это за свойство — "reentrancy"?

Возможен повторный захват монитора, владельцем которого текущий поток уже является. Сильно упрощает код и позволяет делать рекурсивные вызовы, легче избежать deadlock'a.

Что такое "recursive parallelism"?

Разбиение задачи на подзадачи по методу разделяй-и-властвуй (divide-and-conqueer). Каждая задача решается в отдельном потоке.

Что такое "iterative parallelism"?

Разбиение задачи на независимые итерации, каждая итерация может считаться независимо в своем потоке.

Что это за вариант архитектуры "pipeline"?

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

Что такое "poison message"?

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

Что такое "mutual exclusion"? Примеры как добиться в Java.

Критическая секция, семафор с одним состоянием; простейший пример - synchronized(obj) { ... }

Что такое "condition waiting"? Примеры как добиться в Java.

Вообще это называется guarded lock. Если поток захватил монитор и позвал wait() на нем чтобы дождаться некоторого состояния, проверка наступления этого события должна быть завернута в цикл вида

Преимущества ScheduledThreadPool перед java.util.Timer.

• Timer имеет только один фоновый поток для исполнения, т.е. если задач много или они долгие - поток не справляется, время запуска других задачек сдвигается
• Timer может умереть из за неожиданного RuntimeException полученного на выходе любой из TimerTask'ов
• Timer криво работает если меняется системное время, т.к. он использует object.wait() чтобы дожидаться следующего момента исполнения
• ScheduledThreadPool использует System.nanotime() который глючит на старых OC (winxp) и сильно зависит от версии OS и CPU

Различия между java.util.concurrent.Atomic*.compareAndSwap() и java.util.concurrent.Atomic*.weakCompareAndSwap().

• weak не создает memory barrier и не дает гарантии happens-before
• weak сильно зависит от нижележащего кеша\CPU, и может возвращать false без видимых причин и делать это часто
• weak, как следствие, более легкая операция, но поддерживаемая далеко не всеми архитектурами и не всегда эффективная

Что в SynchronousQueue уникально для BlockingQueue.

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

Что такое "рандеву"? При помощи каких классов в Java его можно организовать?

Способ собрать запущенные потоки в "одном месте". Можно использовать Barrier, Latch, spin lock..

Что такое "false sharing". Может ли происходит в Java. Если есть, то приведите примеры и как бороться. Если нет, то как побороли разработчики JVM.

Эффект который происходит если данные\переменные нескольких потоков попадают в один cache line процессора. В этом случае на многопроцессорной системе контроллеру кеша приходится делать много лишних действий чтобы каждый раз удостовериться что линии кеша на различных CPU не рассинхронизовались. Решить проблему вроде как можно изменив layout конечной памяти\добавив данных для padding'a. В JVM вроде никак не решено.

Thread.getState() возвращает экземпляр Thread.State. Какие возможны значения?

new, runnable, waiting, time_wait, terminated, blocked

Напишите простейший ограниченный буфер для многих производителей/многих потребителей с использованием synchronize{}. С использованием ReentrantLock.

вариант с synchronized()

вариант с ReentrantLock

Напишите реализацию класса с неблокирующим методом BigInteger next(), который возвращает элементы последовательности: [1, 2, 4, 8, 16, ...]. Код должен корректно работать в многопоточной среде.

У ReentrantLock созданного с аргументом true все же один из методов захвата блоктровки — не fair. Какой? Как это обойти?

tryLock(), использовать tryLock(long,TimeUnit)

Приведите наиболее существенное отличие между CountDownLatch и Barrier.

Barrier накапливает потоке в точке вызова await() пока их количество не превысит заданное. CountDownLatch ждет пока количество вызовов countDown() не превысит нужное, и тогда разблокирует await().

Что Вы знаете о Erlang? Что в нем есть существенного связанного с многопоточностью такого, чего нет в Java?

Функциональный язык программирования, с неизменяемыми переменными, легковесными потоками, заточенный на параллелизм и многопоточность. Все "потоки" общаются посредством посылки сообщений, разделяемые переменные\память отсутствуют как класс. Разработан для коммутаторов в Ericsson. Имеет внутреннюю встроенную базу, довольно быструю и устойчивую.

Что Вы знаете о CSP? Что в нем есть существенного связанного с многопоточностью такого, чего нет в Java?

Это язык для описания паттернов взаимодействия потоков исполнения в параллельных вычислениях. В CSP есть формальный мат аппарат для описания и проверки\доказательства непротиворечивости свойств задуманной "системы" параллельной разработки .

Отличие Thread.start() и Thread.run()?

start() порождает новый поток в котором исполняет код run().

Книжки по теме

The Art of Multiprocessor Programming

Java Concurrency in Practice

Pattern-Oriented Software Architecture Volume 2: Patterns for Concurrent and Networked Objects

The Little Book of Semaphores