Перейти к основному содержимому

Вопросы на собеседовании по Java Concurrency (+ ответы)

· 14 мин. чтения

Задача: Наибольшая подстрока палиндром

Для заданной строки s, верните наибольшую подстроку палиндром входящую в s. Подстрока — это непрерывная непустая последовательность символов внутри строки. Стока является палиндромом, если она читается одинаково в обоих направлениях...

ANDROMEDA 42

1. Введение​

Параллелизм в Java — одна из самых сложных и продвинутых тем, поднимаемых на технических собеседованиях. В этой статье даны ответы на некоторые вопросы интервью по теме, с которыми вы можете столкнуться.

Q1. В чем разница между процессом и потоком?​

И процессы, и потоки являются единицами параллелизма, но у них есть фундаментальное отличие: процессы не используют общую память, в отличие от потоков.

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

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

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

Q2. Как создать экземпляр потока и запустить его?​

Чтобы создать экземпляр потока, у вас есть два варианта. Сначала передайте экземпляр Runnable его конструктору и вызовите start() . Runnable — это функциональный интерфейс, поэтому его можно передать как лямбда-выражение:

Thread thread1 = new Thread(() ->
  System.out.println("Hello World from Runnable!"));
thread1.start();

Thread также реализует Runnable , поэтому другой способ запустить поток — создать анонимный подкласс, переопределить его метод run() и затем вызвать start() :

Thread thread2 = new Thread() {
    @Override
    public void run() {
        System.out.println("Hello World from subclass!");
    }
};
thread2.start();

Q3. Опишите различные состояния потока и когда происходят переходы между состояниями.​

Состояние потока можно проверить с помощью метода Thread.getState () . Различные состояния потока описаны в перечислении Thread.State . Они есть: ``

  • NEW — новый экземпляр Thread , который еще не был запущен через Thread.start()
  • RUNNABLE — запущенный поток. Он называется исполняемым, потому что в любой момент времени он может либо выполняться, либо ожидать следующего кванта времени от планировщика потоков. НОВЫЙ поток переходит в состояние RUNNABLE , когда вы вызываете него Thread.start().
  • BLOCKED — работающий поток блокируется, если ему нужно войти в синхронизированный раздел, но он не может этого сделать из-за того, что другой поток удерживает монитор этого раздела.
  • WAITING — поток входит в это состояние, если он ожидает, пока другой поток выполнит определенное действие. Например, поток входит в это состояние при вызове метода Object.wait() на мониторе, который он содержит, или метода Thread.join() в другом потоке
  • TIMED_WAITING — то же, что и выше, но поток входит в это состояние после вызова временных версий Thread.sleep() , Object.wait() , Thread.join() и некоторых других методов
  • TERMINATED — поток завершил выполнение своего метода Runnable.run() и завершился

Q4. В чем разница между Runnable и Callable интерфейсами? Как они используются?​

Интерфейс Runnable имеет единственный метод запуска . Он представляет собой единицу вычислений, которая должна выполняться в отдельном потоке. Интерфейс Runnable не позволяет этому методу возвращать значение или создавать непроверенные исключения.

Интерфейс Callable имеет единственный метод вызова и представляет собой задачу, имеющую значение. Вот почему метод вызова возвращает значение. Он также может генерировать исключения. Callable обычно используется в экземплярах ExecutorService для запуска асинхронной задачи и последующего вызова возвращаемого экземпляра Future для получения его значения.

Q5. Что такое поток демона, каковы варианты его использования? Как создать поток демона?​

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

Чтобы запустить поток как демон, вы должны использовать метод setDaemon() перед вызовом start() :

Thread daemon = new Thread(()
  -> System.out.println("Hello from daemon!"));
daemon.setDaemon(true);
daemon.start();

Любопытно, что если вы запустите это как часть метода main() , сообщение может не быть напечатано. Это может произойти, если поток main() завершится до того, как демон доберется до точки вывода сообщения. Как правило, вы не должны выполнять ввод-вывод в потоках демона, поскольку они даже не смогут выполнить свои блоки finally и закрыть ресурсы, если они будут брошены.

Q6. Что такое флаг прерывания потока? Как вы можете установить и проверить это? Как это связано с InterruptedException?​

Флаг прерывания или статус прерывания — это внутренний флаг потока, который устанавливается, когда поток прерывается. Чтобы установить его, просто вызовите thread.interrupt() для объекта потока .

Если поток в данный момент находится внутри одного из методов, выбрасывающих InterruptedException ( wait , join , sleep и т. д .), то этот метод немедленно выбрасывает InterruptedException. Поток может обрабатывать это исключение в соответствии со своей логикой.

Если поток не находится внутри такого метода и вызывается thread.interrupt() , ничего особенного не происходит. Поток обязан периодически проверять состояние прерывания с помощью статического метода Thread.interrupted() или экземпляра метода isInterrupted() . Разница между этими методами заключается в том, что статический Thread.interrupted() очищает флаг прерывания, а isInterrupted() — нет.

Q7. Что такое Executor и Executorservice? Каковы различия между этими интерфейсами?​

Executor и ExecutorService — это два связанных интерфейса фреймворка java.util.concurrent . Executor — это очень простой интерфейс с одним методом execute , принимающим экземпляры Runnable для выполнения. В большинстве случаев это интерфейс, от которого должен зависеть ваш код выполнения задачи.

ExecutorService расширяет интерфейс Executor несколькими методами для обработки и проверки жизненного цикла службы выполнения параллельных задач (прекращение задач в случае завершения работы) и методами для более сложной асинхронной обработки задач, включая Futures .

Дополнительные сведения об использовании Executor и ExecutorService см. в статье A Guide to Java ExecutorService .

Q8. Каковы доступные реализации Executorservice в стандартной библиотеке?​

Интерфейс ExecutorService имеет три стандартные реализации:

  • ThreadPoolExecutor — для выполнения задач с использованием пула потоков. Как только поток завершает выполнение задачи, он возвращается в пул. Если все потоки в пуле заняты, задача должна ждать своей очереди.
  • ScheduledThreadPoolExecutor позволяет планировать выполнение задачи, а не запускать ее немедленно, когда поток доступен. Он также может планировать задачи с фиксированной скоростью или фиксированной задержкой.
  • ForkJoinPool — это специальный ExecutorService для решения задач рекурсивных алгоритмов. Если вы используете обычный ThreadPoolExecutor для рекурсивного алгоритма, вы быстро обнаружите, что все ваши потоки заняты ожиданием завершения нижних уровней рекурсии. ForkJoinPool реализует так называемый алгоритм кражи работы, который позволяет более эффективно использовать доступные потоки.

Q9. Что такое модель памяти Java (Jmm)? Опишите его цель и основные идеи.​

Модель памяти Java является частью спецификации языка Java, описанной в главе 17.4 . Он определяет, как несколько потоков получают доступ к общей памяти в параллельном приложении Java и как данные, измененные одним потоком, становятся видимыми для других потоков. Будучи довольно кратким и лаконичным, JMM может быть трудно понять без сильной математической подготовки.

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

Это может привести к нелогичным результатам, когда ваше приложение масштабируется до нескольких потоков, потому что большинство этих оптимизаций учитывают один поток выполнения (оптимизаторы для нескольких потоков все еще чрезвычайно сложны в реализации). Еще одна огромная проблема заключается в том, что память в современных системах является многоуровневой: несколько ядер процессора могут хранить некоторые несброшенные данные в своих кешах или буферах чтения/записи, что также влияет на состояние памяти, наблюдаемое от других ядер.

Что еще хуже, существование разных архитектур доступа к памяти нарушило бы обещание Java «написать один раз, работать везде». К счастью для программистов, в JMM указаны некоторые гарантии, на которые можно положиться при разработке многопоточных приложений. Соблюдение этих гарантий помогает программисту писать многопоточный код, который является стабильным и переносимым между различными архитектурами.

Основные понятия JMM:

  • Действия — это действия между потоками, которые могут выполняться одним потоком и обнаруживаться другим потоком, например, чтение или запись переменных, блокировка/разблокировка мониторов и т. д.
  • Действия синхронизации , определенное подмножество действий, таких как чтение/запись изменчивой переменной или блокировка/разблокировка монитора.
  • Порядок программы (PO), наблюдаемый общий порядок действий внутри одного потока.
  • Порядок синхронизации (SO), общий порядок между всеми действиями синхронизации — он должен соответствовать порядку программ, то есть, если два действия синхронизации идут одно перед другим в PO, они происходят в том же порядке в SO
  • синхронизируется с (SW) отношением между определенными действиями синхронизации, такими как разблокировка монитора и блокировка того же монитора (в другом или том же потоке)
  • Happens-before Order — объединяет PO с SW (это называется транзитивным замыканием в теории множеств) для создания частичного упорядочения всех действий между потоками. Если одно действие происходит раньше другого, то результаты первого действия наблюдаются вторым действием (например, запись переменной в одном потоке и чтение в другом)
  • Согласованность « происходит до» - набор действий является HB-согласованным, если при каждом чтении наблюдается либо последняя запись в это место в порядке «происходит до», либо какая-либо другая запись через гонку данных.
  • Исполнение — определенный набор упорядоченных действий и правил согласованности между ними.

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

Q10. Что такое изменчивое поле и какие гарантии дает Jmm для такого поля?​

Изменчивое поле имеет специальные свойства в соответствии с моделью памяти Java (см. Q9) . Чтение и запись volatile - переменной являются действиями синхронизации, что означает, что они имеют общий порядок (все потоки будут соблюдать согласованный порядок этих действий). При чтении volatile-переменной гарантируется последняя запись в эту переменную в соответствии с этим порядком.

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

Еще одна гарантия для volatile — атомарность записи и чтения 64-битных значений ( long и double ). Без модификатора volatile при чтении такого поля может наблюдаться значение, частично записанное другим потоком.

Q11. Какие из следующих операций являются атомарными?​

  • запись в энергонезависимое целое ;
  • запись в volatile int ;
  • запись в энергонезависимый long ;
  • запись в volatile long ;
  • увеличение volatile long ?

Запись в переменную типа int (32-разрядная) гарантированно будет атомарной, независимо от того, изменчива она или нет. Длинная (64-разрядная) переменная может быть записана в два отдельных шага , например, в 32-разрядных архитектурах, поэтому по умолчанию нет гарантии атомарности. Однако, если вы укажете модификатор volatile , доступ к длинной переменной гарантированно будет атомарным.

Операция приращения обычно выполняется в несколько шагов (извлечение значения, его изменение и обратная запись), поэтому никогда не гарантируется, что она будет атомарной, независимо от того, является ли переменная изменчивой или нет. Если вам нужно реализовать атомарное приращение значения, вы должны использовать классы AtomicInteger , AtomicLong и т. д.

Q12. Какие специальные гарантии дает Jmm для последних полей класса?​

JVM в основном гарантирует, что конечные поля класса будут инициализированы до того, как какой-либо поток получит доступ к объекту. Без этой гарантии ссылка на объект может быть опубликована, т. е. стать видимой, для другого потока до того, как все поля этого объекта будут инициализированы из-за переупорядочения или других оптимизаций. Это может привести к гонкам на доступ к этим полям.

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

Q13. Что означает синхронизированное ключевое слово в определении метода? статического метода? Перед блоком?​

Синхронизированное ключевое слово перед блоком означает, что любой поток, входящий в этот блок, должен получить монитор (объект в скобках). Если монитор уже захвачен другим потоком, предыдущий поток перейдет в состояние BLOCKED и будет ждать освобождения монитора.

synchronized(object) {
    // ...
}

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

synchronized void instanceMethod() {
    // ...
}

Для статического синхронизированного метода монитор — это объект класса , представляющий объявляющий класс.

static synchronized void staticMethod() {
    // ...
}

Q14. Если два потока одновременно вызывают синхронизированный метод для разных экземпляров объекта, может ли один из этих потоков заблокироваться? Что делать, если метод статический?​

Если метод является методом экземпляра, то экземпляр действует как монитор для метода. Два потока, вызывающие метод в разных экземплярах, получают разные мониторы, поэтому ни один из них не блокируется.

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

Q15. Какова цель методов ожидания, уведомления и уведомления всех классов объектов?​

Поток, владеющий монитором объекта (например, поток, вошедший в синхронизированную секцию, охраняемую объектом), может вызвать object.wait() , чтобы временно освободить монитор и дать другим потокам возможность получить монитор. Это может быть сделано, например, для ожидания определенного условия.

Когда другой поток, получивший монитор, выполняет условие, он может вызвать object.notify() или object.notifyAll() и освободить монитор. Метод notify пробуждает один поток в состоянии ожидания, а метод notifyAll пробуждает все потоки, ожидающие этого монитора, и все они конкурируют за повторное получение блокировки.

Следующая реализация BlockingQueue показывает, как несколько потоков работают вместе с помощью шаблона ожидания-уведомления . Если мы поместим элемент в пустую очередь, все потоки, ожидавшие в методе take , проснутся и попытаются получить значение. Если мы поместим элемент в полную очередь, метод put будет ждать вызова метода get . Метод get удаляет элемент и уведомляет потоки, ожидающие в методе put , о том, что в очереди есть свободное место для нового элемента.

public class BlockingQueue<T> {

    private List<T> queue = new LinkedList<T>();

    private int limit = 10;

    public synchronized void put(T item) {
        while (queue.size() == limit) {
            try {
                wait();
            } catch (InterruptedException e) {}
        }
        if (queue.isEmpty()) {
            notifyAll();
        }
        queue.add(item);
    }

    public synchronized T take() throws InterruptedException {
        while (queue.isEmpty()) {
            try {
                wait();
            } catch (InterruptedException e) {}
        }
        if (queue.size() == limit) {
            notifyAll();
        }
        return queue.remove(0);
    }
    
}

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

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

Livelock — это случай, когда несколько потоков реагируют на условия или события, сгенерированные ими самими. Событие происходит в одном потоке и должно быть обработано другим потоком. Во время этой обработки возникает новое событие, которое должно быть обработано в первом потоке, и так далее. Такие потоки живы и не заблокированы, но все равно не продвигаются вперед, потому что заваливают друг друга бесполезной работой.

Голодание — это случай, когда поток не может получить ресурс, потому что другой поток (или потоки) занимает его слишком долго или имеет более высокий приоритет. Поток не может продвигаться вперед и, следовательно, не может выполнять полезную работу.

Q17. Опишите цель и варианты использования платформы Fork/Join.​

Фреймворк fork/join позволяет распараллеливать рекурсивные алгоритмы. Основная проблема с распараллеливанием рекурсии с использованием чего-то вроде ThreadPoolExecutor заключается в том, что вы можете быстро исчерпать потоки, потому что для каждого рекурсивного шага потребуется свой собственный поток, в то время как потоки вверх по стеку будут бездействовать и ждать.

Точка входа фреймворка fork/join — это класс ForkJoinPool , который является реализацией ExecutorService . Он реализует алгоритм кражи работы, при котором бездействующие потоки пытаются «украсть» работу у занятых потоков. Это позволяет распределять вычисления между разными потоками и добиваться прогресса, используя меньшее количество потоков, чем потребовалось бы при обычном пуле потоков.

Дополнительную информацию и примеры кода для фреймворка fork/join можно найти в статье «Руководство по фреймворку Fork/Join в Java» .