Снимки: предварительные сведения

Глобальное состояние - совокупность состояний всех локальных состояний процессов и каналов.

Глобальное состояние согласовано, если выполнены два условия:
C1. если посылка сообщения по каналу от P_i к P_j входит в локальное состояние P_i, то либо это сообщение входит в состояние канала C_ij, либо событие приёма этого сообщения входит в локальное состояние процесса P_j. Имеются ввиду состояния канала C_ij и локальные состояния процессов P_i и P_j, входящие в данное глобальное состояние. 
C2. если посылка сообщения по каналу от P_i к P_j не входит в локальное состояние P_i, то это сообщение не входит в состояние канала C_ij и не входит в локальное состояние процесса P_j.

Две основные проблемы при записи состояний:
П1. Как отличить сообщения, которые нужно записать в снимок от тех, которые записывать не нужно. С1 и C2 говорят, что нужно записывать те сообщения от P_i, которые были посланы процессом P_i до фиксации своего локального состояния.
П2. Как определить момент, когда процессу нужно сделать снимок. С2 говорит, что процесс P_j должен зафиксировать своё состояние до обработки сообщения от P_i, которое было послано  P_i после фиксации своего состояния.

Снимки глобального состояния

Непростая тема. И вроде не такая уж большая . Нужно только понять, что такое согласованное состояние и изучить два алгоритма - Чанди-Лэмпорта (требует FIFO каналов) и Лая-Янга (нет требования FIFO). А что-то трудно идёт.

По книге Фоккинга разбираться сложно. Гораздо лучше написано у Кшемкальяни и Сингала. Вот ссылка на их лекцию (на самом деле, это просто кусок их книги, перенесённый на слайды).

У Фоккинга нашёл только хороший перевод понятия FIFO-канала : каналы с обработкой сообщений в порядке очереди.

Дополнение. Почитав Кшемкальяни (упомянутую лекцию и их же статью An introduction to snapshot algorithms in distributed computing), понял, что весьма упрощённо представлял себе область. На самом деле, там три группы алгоритмов:

1. для FIFO-каналов. Здесь алгоритм Чанди-Лэмпорта и его модификации ( Spezialetti and Kearns, Venkatesan, Helary). 
2. для не-FIFO.  Алгоритм Лая-Янга, Маттерна
3. для систем с каузальной доставкой. Алгоритмы Acharya-Badrinath, Alagar-Venkatesan.

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

Здесь я пишу о своём нынешнем понимании алгоритма банкира, которое пока является неполным.

Этот алгоритм - стратегия, которая позволяет ресурсы потребителям, избегая тупиковых ситуаций (deadlock avoidance). Такой алгоритм пригодится, например, операционной системе, которая распределяет процессам память, даёт доступ к принтеру и т.д.

Тупиком здесь является ситуация, когда у ОС (или у банкира) нет достаточно ресурсов, чтобы удовлетворить запрос хотя бы одного потребителя (это моё понимание). Получается, что потребители ждут выделения ресурсов  от ОС, а ОС в свою очередь ждёт, пока ему вернут достаточно ресурсов, чтобы можно было выдать их кому-нибудь. 

Нам дано: количество ресурсов и количество потребителей (процессов). Важное ограничение алгоритма: необходимо знать максимальную потребность в каждом ресурсе каждого потребителя. 

В двух словах алгоритм выглядит следующим образом. У нас есть Available - вектор наличных ресурсов (один на всю систему) и Need - вектор потребностей каждого процесса. Просматриваем потребности процессов, начиная с первого. Если у i-го процесса Need <= Available, то система выдаст ему все нужные ресурсы. Процесс отработает, вернёт ресурсы и будет исключен из списка работающих процессов. Далее опять происходит просмотр обновлённого списка работающих процессов, определяется следующий процесс, который получит ресурсы.  

Ссылки:
Dijkstra’s Banker’s algorithm detailed explanation [ссылка] - лучшая
Wiki: Banker’s algorithm [ссылка]
What is Banker's Algorithm? [ссылка]