СберТех ♥ Open Source, concurrency и надежные банковские операции — разбор решений задач с Joker 2018

В эти выходные прошел Joker 2018, было интересно! Но не одними выступлениями была богата конференция. Все компании-спонсоры старались выделиться на фоне «конкурентов» и мы — не исключение.

Много интересного было на стенде Сбербанк-Технологий, но я хочу рассказать о том чем выделились именно мы. Наша команда, занимающаяся развитием Apache Ignite в СберТехе, подготовила задачи и провела розыгрыш среди тех, кто отважился их решить.

Под катом вас ожидают задачи, разбор решений и возможность обосновать собственный вариант решения в комментариях.

Горе-коммитеры

Петя и Коля коммитят в Apache Ignite по одной фиче в сутки.

Маша оперативно тестирует каждую фичу и откатывает коммиты, содержащие ошибки.
Каждый третий первоначальный коммит от Пети и пятый от Коли содержат ошибку.
Петя тратит на исправление ошибки дополнительные 2 дня, Коля 3, и они снова делают
коммит.

Cколько фич будет закоммичено за 86 рабочих дней, если Маше нравится Петя,
и она замечает его ошибку лишь в тот день, когда ошибается только он?

Решение

Начиная с 13-го дня, образуется цикличность позволяющая Пете фиксить только каждую вторую свою ошибку.

Вилларибо и Виллабаджо

Процессинг ненадежного банка при операциях над группой счетов блокирует ключи
счетов в порядке их объявления в операции, т.е. слева направо.
Каждый дедлок решается специалистами банка вручную и занимает в 10 раз больше
времени, чем обычная операция.
Процессинг надежного банка всегда блокирует ключи по возрастанию, но тратит в 2
раза больше времени, чем на обычную операцию в ненадежном банке.
В обоих банках 10 счетов, ключи счетов — числа от 1 до 10.
Процессингу каждого банка необходимо провести 12 операций.
Операции проводятся параллельно, по две за раз. Каждая операция затрагивает до 3-х
счетов:
— операция №1 (счета: A,B,C), где A=i, B=A+1, C=(A+B)%10,
— операция №2 (счета: D,E,F), где D=11-i, E=D-1, F=(D+E)%10,
i меняется от 1 до 6.
Выполнение последующей пары операций начинается только после полного завершения
предыдущей.
Ключи блокируются согласно политике банка, по одному в каждой из операций, начиная
с операции №1.
Если ключ уже заблокирован в одной из операций, но требуется для выполнения другой,
то сначала полностью завершается первая операция, затем продолжается вторая.
Вынужденное выполнение пары операций в последовательном режиме, ожидаемо, происходит в 2 раза медленнее чем в параллельном.
Какой банк и во сколько раз быстрее завершит проводить операции?

Подсказка

Итого:
— 6 итераций,
— 12 операций,
— во всех операциях, кроме одной, по 3 ключа.

Решение

Если все ключи разные — параллельное выполнение возможно.
Если нет — то нет, и возможен дедлок.

Рассчеты

Ненадежный банк тратит на операцию 1 «такт», 2 в случае «сложностей» и целых 10 в случае дедлока.
Надежный банк тратит на операцию 2 «такта» и 4 в случае «сложностей». Дедлоков у надежного не бывает.

Риски публичных репозиториев

Сережа очень опытный программист, крайне азартный и бесконечно жадный.
Однажды он нашел исходный код своего любимого тотализатора на гитхабе.
Какая минимальная ставка может принести Сереже выигрыш?

Упрощенный листинг тотализатора прилагается:

class Bid { // Ставка
	int amount;
	boolean checked;
	boolean restricted;
	Bid(int amount) {this.amount = amount;}
}
~~~
AtomicReference<Bid> ref = new AtomicReference<>();
volatile boolean winner = false;
~~~
Thread validator = new Thread(() -> { // Запущен заранее!
	while (true) {
		Bid bid = ref.get();
		if (bid == null) continue;
		if ((((bid.amount << 5) ^ 1_000_000) >>> 6) < (2 << 15))
			bid.restricted = true;
		bid.checked = true;
	}
});
Thread payer = new Thread(() -> { // Запущен заранее!
	while (true) {
		Bid bid = ref.get();
		if (bid == null) continue;
		if (bid.checked) {
			if (!bid.restricted)
				winner = true; // Выигрыш!
			ref.set(null);
		}
	}
});
~~~
synchronized boolean makeMeRich(int amount){ // Какую ставку сделает Сережа?
	if (winner) return false; // Сережа должен торопиться - приз всего один
	ref.set(new Bid(amount)); 
	while(ref.get() != null) sleep(1);
	return winner; // Если вернется "true" - Сережа едет на Бали
}

th1{
	bid.restricted = true;
	bid.checked = true;
}
...
th2{
	while (!bid.checked) {
		sleep(1);
	}
	assert bid.restricted; // 99.999%
}

volatile boolean checked;

Решение

java.lang.Integer#MIN_VALUE

Победители

Лучше всех задачи решили
— Евгений Зубенко
— Александр Новиков
— Андрей Голиков

Ребята получили фирменные рюкзаки, футболки и, конечно же, книги.

Автор: randoom

Источник