2 Phase Locking

2021-07-16T16:06:00Z

139.45.249.101: Убрал лишнее слово

[[Категория: Параллельное программирование]]
'''Алгоритм двухфазной блокировки''' используется для взятия блокировок при выполнении [[Транзакции в распределённых системах|распределённых транзакций]] (например, в СУБД).

Алгоритм требует, чтобы каждая транзакция состояла из двух фаз: на первой мы только набираем блокировки (в любом порядке), а на второй фазе мы их только отпускаем (в любом порядке).
Например, если мы работаем с элементами $x$ и $y$, то мы можем сначала взять блокировку на $x$, потом поработать с $x$, потом взять блокировку на $y$, поработать с ним, а потом отпустить все блокировки.

[[Файл:distributed-2pl.png|400px]]

Если все транзакции устроены таким образом, то гарантируется сериализуемость транзакции.

== Применение ==
Так можно брать не все блокировки, а только нужные.
Это особенно удобно в СУБД, когда движок заранее не знает, какие блокировки потребуются: он может просто набирать блокировки, как появляются запросы, а в конце, при применении транзакции, их разом отпустить.

Из-за этого могут возникнуть проблемы с взаимными блокировками (потому что порядок взятия блокировок может отличаться в разных транзакциях), поэтому:
* [[Определение взаимной блокировки|Детектор взаимных блокировок]] всё равно нужен. Если нашли — то отменяем одну из транзакций и снимаем все её блокировки. Есть разные стратегии выбора, какую транзакцию отменять. Можно самую новую (тогда мы будем дожидаться старой), можно самую долго работающую (тогда у коротких запросов приоритет), можно ещё как-то.
* В некоторых СУБД есть даже специальный SQL-синтаксис для deadlock avoidness, вроде <code>SELECT FOR UPDATE</code>

Проблемы, конечно, в том, что если у нас большой запрос по всем строкам таблицы, то нам нужно всё заблокировать, но для этого есть [[Транзакции в распределённых системах#Согласованность и изоляция|MVCC]] или пониженные уровни изоляции.

Алгоритм Скина

2021-07-02T16:09:16Z

139.45.249.101:

[[Категория: Параллельное программирование]]
'''Алгоритм Скина'''<ref>https://doi.org/10.1109/TSE.1983.236608</ref> для организации [[Общий порядок сообщений|общего порядка сообщений]].
Лучше, чем [[Алгоритм Лампорта]], потому что для multicast сообщений общается только с получателями, а не со всеми процессами системы.

Используются [[Логические часы Лампорта|логические часы Лампорта]].
Ниже алгоритм расписан чуть подробнее, чем в Garg и на лекции, но вроде всё ещё верно.

У каждого процесса есть очередь принятых необработанных multicast сообщений.
Каждое сообщение имеет временну́ю метку и флаг — финализирована ли метка.

# Инициатор отправляет сообщение и своё время (''предварительное время сообщения'') всем получателям
# При приеме сообщения процесс запоминает сообщение со временем в очередь (как нефинализированное) и отправляет свое время инициатору
# Когда инициатору вернулись все подтверждения, он выбирает максимальное время из них и снова отправляет сообщение с финализированным временем
# Получатель может обработать сообщение, если оно помечено как финальное и имеет минимальное время среди всех известных получателю сообщений (и финальных, и нефинальных; иначе может получиться, что финализация сообщений произойдёт в разном порядке у разных получателей и нарушится общий порядок)

Полный порядок задается финальными временными метками. Финальные метки нужны, чтобы как-то зависеть от времени получателей.
Доказательство на лекции и в Gaarg не приводилось.

Итого $3(k-1)$ сообщений на каждый multicast на $k$ процессов (не обсуждалось на лекции, но вроде так).

Викиконспекты - Вклад участника [ru]

2 Phase Locking

Алгоритм Скина