В прошлом году я собеседовался в штаб-квартиру 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. Прежде чем углубиться в решения, давайте рассмотрим простой пример. Предположим, у нас есть функция 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 способами.
