Разбор Интервью
Разбор задачи из реального собеседования в TikTok.
Исправляем Race Condition
В прошлом году я собеседовался в штаб-квартиру TikTok которая находится в Сингапуре. К сожалению, оффер я не получил, однако получил как говорится бесценный опыт. Было несколько этапов, один из них был этап live-кодинга, на котором нужно было решить несколько задач разного уровня. Большинство задач были алгоритмические, но в одной из них нужно было вспомнить 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().
Проблемы параллелизма
Для начала давайте разберемся с проблемами, которые могут возникнуть. Проблемы параллелизма возникают когда выполнение программы выполняется в нескольких потоках одновременно. Из-за параллелизма процессы или потоки не обязательно выполняются независимо на разных физических процессорах, но чаще всего они чередуются на одном и том же физическом процессоре. Обратите внимание, что параллелизм может применяться как к процессу, так и к потоку. В следующих разделах слова «процесс» и «поток» используются как взаимозаменяемые. Параллелизм предназначен, прежде всего, для обеспечения многозадачности, однако, если не учитывать, что кусок вашего кода может быть вызван из нескольких потоков можно наткнуться на ряд проблем. В зависимости от последствий, проблемы вызванные параллелизмом, можно разделить на три типа:
  • Состояние гонки/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 получает уведомление о необходимости взять на себя управление критической секцией.
Подводя итог, чтобы предотвратить состояние гонки при параллельном выполнении, нам нужен механизм, обладающий двумя возможностями: 1) контроль доступа к критической секции. 2) уведомление блокирующих потоков
Парная синхронизация для решения задачи
Теперь, обладая минимальной теорией давайте вернемся к задаче. В задаче требуется выполнить три метода по порядку, при этом каждый методы выполняется в отдельном потоке.

Чтобы обеспечить последовательность выполнения, мы могли бы создать некоторые зависимости между парами методов, т. е. второй метод должен зависеть от завершения первого метода, а третий метод должен зависеть от завершения второго.
Зависимость может быть реализована с помощью механизма параллелизма, как мы обсуждали в предыдущем разделе. Идея состоит в том, что мы могли бы использовать общую переменную с именем 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. Проблемы с масштабированием: Холостой цикл может быть неэффективным при масштабировании до более сложныхс ценариев синхронизации.

Чтобы не пропустить следующие статьи на тему Android и мобильной разработки подписывайтесь на Telegram-канал
Интенсивный курс по Android c код-ревью

Если вы хотите научиться строить многомодульную архитектуру Android-приложений, использовать разные подходы в зависимости от задачи и профилировать Android-приложения, обратите внимание на интенсивный курс по Android-разработке с code-review и консультациями.
Made on
Tilda