Введение в распределенные

Общие концепции

При рассмотрении распределенных алгоритмов взаимного исключения мы будем оставаться в рамках следующих допущений:
процессы выполняются и взаимодействуют асинхронно, ни один из процессов не выходит из строя, все каналы связи являются надежными и коммуникационная сеть не разбивается на несвязанные друг с другом части. Мы не будем делать никаких предположений о том, являются ли каналы между процессами очередями (FIFO) или нет (non-FIFO). Требование к свойству очередности каналов будет определяться отдельно для каждого обсуждаемого алгоритма. Также мы будем полагать, что обращения к разделяемым ресурсам происходят из одной единственной критической секции. Распространение представленных ниже алгоритмов на случаи работы с более чем одной критической секцией не вызывает затруднений.
С позиции организации работы с разделяемыми ресурсами в коде каждого процесса можно выделить следующие части: (1) критическая секция, в которой есть обращения к разделяемым ресурсам, и (2) предшествующая и последующая часть кода, где такие обращения отсутствуют. Общая структура кода процессов распределенной системы, рассматриваемая далее для изучения механизмов взаимного исключения, приведена в Листинге 4.1. В коде каждого процесса используются две функции: request_CS() для получения разрешения на вход в критическую секцию и блокировки процесса в случае необходимости и release_CS() для выхода из критической секции и предоставления возможности остальным процессам войти в нее. Каждая из этих функций принимает в качестве аргумента общий для всех процессов идентификатор критической секции
R. Суть разработки распределенных алгоритмов взаимного исключения как раз и состоит в построении механизмов, обеспечивающих работу этих двух функций.


Листинг 4.1. Структура кода с критической секцией.

P1		PN
void P1(int R) { while(true) {	…	void PN(int R) { while(true) {
/* предшествующий код */;