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

в 8:58, , рубрики: Apache Ignite, concurrency, java, jmm, joker, jokerconf, JUG, open source, Блог компании Сбербанк, задачи для программистов, задачки, занимательные задачи, Занимательные задачки, ненормальное программирование, Программирование

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

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

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

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

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

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

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

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

Решение

Начиная с 13-го дня, образуется цикличность позволяющая Пете фиксить только каждую вторую свою ошибку.
СберТех ♥ Open Source, concurrency и надежные банковские операции — разбор решений задач с Joker 2018 - 2
Ответ
64 + 54 = 118;

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

Процессинг ненадежного банка при операциях над группой счетов блокирует ключи
счетов в порядке их объявления в операции, т.е. слева направо.
Каждый дедлок решается специалистами банка вручную и занимает в 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 ключа.
СберТех ♥ Open Source, concurrency и надежные банковские операции — разбор решений задач с Joker 2018 - 3
Решение

Если все ключи разные — параллельное выполнение возможно.
Если нет — то нет, и возможен дедлок.
СберТех ♥ Open Source, concurrency и надежные банковские операции — разбор решений задач с Joker 2018 - 4
Рассчеты

Ненадежный банк тратит на операцию 1 «такт», 2 в случае «сложностей» и целых 10 в случае дедлока.
Надежный банк тратит на операцию 2 «такта» и 4 в случае «сложностей». Дедлоков у надежного не бывает.
СберТех ♥ Open Source, concurrency и надежные банковские операции — разбор решений задач с Joker 2018 - 5
Ответ
Завершат одновременно.

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

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

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

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" - Сережа едет на Бали
}

Подсказка №1

— 131072?
— Нет, вылезай из ловушки :)
Подсказка №2

Какая минимальная ставка может принести Сереже выигрыш?
Подсказка №3

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

Тут нет интуитивно ожидаемых гарантий видимости.

Добавить их можно следуюшим образом:

volatile boolean checked;

Подсказка №4

Какая минимальная ставка может принести Сереже выигрыш?
Решение

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

java.lang.Integer#MIN_VALUE

Впрочем, «0» и даже «1» расценивались как верное решение.

Победители

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

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

Автор: randoom

Источник


* - обязательные к заполнению поля