Все чаще и чаще при найме в крупные (и не очень) компании кандидатам задают алгоритмические задачи и System Design. Как проходить System Design в контексте мобильной разработки я подробно описывал тут. Помимо сугубо алгоритмических задач, могут встретиться задачи по параллельному программированию где нужно вспомнить java.util.concurrent. В этой статье мы разберем одну из таких задач.

В одной из прошлых статей я подробно описывал из чего состоит System Design интервью в контексте мобильной разработки. Ознакомиться можно тут. Ну, а в этой статье мы разберем одну из задач, где нужно вспомнить java.util.concurrent.

Задача звучит так: предположим у вас есть класс

public class Foo {
  public void first() { print("first"); }
  public void second() { print("second"); }
  public void third() { print("third"); }
}

Один и тот же экземпляр Foo будет передан трем разным потокам. Поток A вызовет метод first(), поток B вызовет метод second(), а поток C вызовет метод third(). Нужно написать программу так, чтобы метод second() выполнился после first(), а third() выполнился после second(). Кстати, если вы готовитесь к собеседованиям прямо сейчас или хотите структурировать свои знания, то приглашаю на короткий практический курс по System Design адаптированный специально для мобильных разработчиков.

Проблемы параллелизма

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

• Состояние гонки/Race Condition: программа завершается с неверным результатом, возникающим в результате последовательного выполнения разными потоками.

• Deadlocks/ Дэдлоки: параллельные потоки ждут друг от друга необходимых ресурсов. В результате ни один из них не может продолжить свою работу.

• Ресурсное голодание: процессу постоянно отказывают в ресурсах, необходимых для выполнения его работы.

В частности, нашу задачу можно отнести к проблеме Race Condition. Прежде чем углубиться в решения, давайте рассмотрим простой пример. Предположим, у нас есть функция fun withdraw(amount), которая выводит определенную сумму денег из баланса, если требуемая сумма меньше текущего баланса. В конце функция возвращает остаток баланса. Функция определяется следующим образом:

int balance = 500;
int withdraw(int amount) {
  if (amount < balance) {
    balance -= amount;
  }
  return balance;
}

Мы ожидаем, что баланс никогда не станет отрицательным после выполнения функции, что также является желаемым поведением функции. Однако здесь мы можем столкнуться с Race Condition, когда баланс станет отрицательным.

Вот как это могло произойти: представьте, что у нас есть два потока, вызывающих функцию одновременно с разными входными параметрами, например: для потока №1 будет вызван метод withdraw(amount = 400), а для потока №2 метод withdraw(amount = 200). Вызвав 2 потока мы можем получить картину как показано ниже:

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

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

Идея состоит в том, что если бы мы могли гарантировать что в один момент времени только один поток может работать с критической секцией кода (например, оператор для проверки и определения баланса), мы могли бы предотвратить несогласованное состояние изменяемого ресурса (в нашем случае баланса)

Механизм который может помочь нам в этом, можно рассматривать как своего рода замок, ограничивающий доступ к критической секции. Следуя предыдущему примеру, мы применяем блокировку критической секции, то есть операторов проверки баланса и списания баланса. Затем мы повторно запускаем два потока, что может привести к следующему взаимодействию:

Благодаря этому механизму, как только поток входит в критическую секцию, он предотвращает попадание других потоков в ту же критическую секцию. Например, в момент времени №3 поток №2 входит в критическую секцию.Затем при следующей временной метке №4 поток №1 мог бы проникнуть в критическую секцию, если бы оператор не был защищен блокировкой. В конце концов, два потока выполняются одновременно, при этом сохраняется согласованность системы, т. е. баланс остается положительным.

Если потоку не предоставлен доступ к критической секции, мы можем сказать, что поток заблокирован или переведен в режим сна, например. поток №1 блокируется по временной метке №4. Как можно себе представить, как только критический раздел будет освобожден, было бы неплохо уведомить об этом ожидающие потоки. Например, как только поток №2 освобождает критическую секцию в момент времени №5, поток №1 получает уведомление о необходимости взять на себя управление критической секцией.

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

• контроль доступа к критической секции

• уведомление блокирующих потоков

Парная синхронизация для решения задачи

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

public class Foo {
  public void first() { print("first"); }
  public void second() { print("second"); }
  public void third() { print("third"); }
}

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

Зависимость может быть реализована с помощью механизма параллелизма, как мы обсуждали в предыдущем разделе. Идея состоит в том, что мы могли бы использовать общую переменную с именем firstJobDone для координации порядка выполнения между первым и вторым методом. Аналогичным образом мы могли бы использовать другую переменную secondJobDone, чтобы обеспечить порядок выполнения второго и третьего метода.

Алгоритм решения задачи:

1. Прежде всего, нам нужно создать координационные переменные firstJobDone и secondJobDone, чтобы указать, что методы еще не выполнены.

2. В функции first() у нас нет зависимостей, поэтому мы можем сразу приступить к работе. В конце функции мы обновляем переменную firstJobDone, чтобы указать, что первый метод завершил работу.

3. В методе second() мы проверяем статус firstJobDone. Если не обновилось, то ждем, иначе переходим к выполнению логики метода. И в конце функции мы обновляем переменную secondJobDone, чтобы отметить завершение второго задания.

4. В методе third() мы проверяем статус secondJobDone. Как и в случае с методом second(), мы ждем сигнала secondJobDone, прежде чем приступить к выполнению третьего метода.

class Foo {
  private AtomicInteger firstJobDone = new AtomicInteger(0);
  private AtomicInteger secondJobDone = new AtomicInteger(0);
  public Foo() {}
  public void first(Runnable printFirst) throws InterruptedException {
    // printFirst.run() outputs "first".
    printFirst.run();
    // mark the first job as done, by increasing its count.
    firstJobDone.incrementAndGet();
  }
  public void second(Runnable printSecond) throws InterruptedException {
    while (firstJobDone.get() != 1) {
      // waiting for the first job to be done.
    }
    // printSecond.run() outputs "second".
    printSecond.run();
    // mark the second as done, by increasing its count.
    secondJobDone.incrementAndGet();
  }
  public void third(Runnable printThird) throws InterruptedException {
    while (secondJobDone.get() != 1) {
      // waiting for the second job to be done.
    }
    // printThird.run() outputs "third".
    printThird.run();
  }
}

Плюсы решения:

Lock-free: Отсутствие блокировок. Это решение позволяет избежать блокировок или явной блокировки, уменьшая потенциальную конкуренцию и повышая производительность в некоторых сценариях.

Простота: Использование AtomicInteger делает реализацию простой и лаконичной.

Минусы решения:

1. Холостой цикл (Busy-wait): Цикл while работает вхолостую при этом потребляет циклы процессора. Это может быть уменьшено с помощью небольшой задержки(например, Thread.yield() или Thread.sleep())) внутри цикла.

2. Проблемы с масштабированием: Холостой цикл может быть неэффективным при масштабировании до более сложных cценариев синхронизации.

Нужно понимать, что это одно из множества решений. Цель статьи - объяснить проблему простым языком и предложить решение реальной задачи, которую могут спросить на собеседовании. Ну, а если вы готовитесь к собеседованиям прямо сейчас или хотите структурировать свои знания, то приглашаю на короткий практический курс по System Design адаптированный специально для мобильных разработчиков. Чтобы не пропустить следующие статьи на тему Android и мобильной разработки подписывайтесь на Telegram-канал