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

Таблица 4.1. Пример построения графа конфликтов: пять комитетов, в каждый из которых входит по пять человек.

Комитет 1	Комитет 2	Комитет 3	Комитет 4	Комитет 5
A	F	J	A	Q
B	G	K	K	R
C	H	L	N	N
D	I	I	O	D
E	E	M	P	S

Для решения задачи планирования расписания каждого из представленных комитетов можно построить соответствующий граф конфликтов, в котором вершины будут соответствовать комитетам, а ребра

– возможным конфликтам между ними. В этом случае возможность возникновения конфликта между двумя комитетами определяется наличием одного или более сотрудников, которые одновременно входят в состав обоих комитетов. Например, между вершинами, соответствующими комитету 1 и комитету 2, будет существовать ребро, т.к. они имеют в своем составе общего для них сотрудника Е. В свою очередь комитет 1 и комитет 3 имеют разные и непересекающиеся составы, поэтому в графе конфликтов ребро между соответствующими вершинами будет отсутствовать.
Граф конфликтов для представленной задачи планирования расписания заседаний пяти комитетов приведен на рис. 4.4. По постановке задачи комитеты, соответствующие соседним вершинам в этом графе, не могут проводить заседания одновременно. Поэтому из графа конфликтов сразу видно, что для проведения заседаний потребуется минимум три четырехчасовых интервала, т.е. минимум 12 часов: например,
одновременно могут заседать комитеты 1 и 3, комитеты 2 и 5, и еще один интервал необходимо выделить для заседания комитета 4. Если же комитеты не планируют свою занятость наперед, а действуют независимо и выражают свое желание провести заседание в произвольный момент времени, при этом возможно вызывая "конфликты доступа" к своим сотрудникам, то проведение заседания становится эквивалентным входу процесса в КС, для обеспечения которого необходимо получить доступ к ресурсам – членам комитета.

Рис. 4.4. Граф конфликтов для задачи заседаний пяти комитетов.

Для разрешения конфликтов между процессами требуется некоторый механизм, позволяющий при любом состоянии системы задавать приоритет процессов друг над другом таким образом, что при возникновении конфликта он бы разрешался в пользу процесса с большим приоритетом. В данном случае приоритет процесса, по сути, определяет порядок предоставления разделяемых ресурсов в пользование тому или иному процессу, т.е. задает отношение предшествования между обращениями процессов к разделяемым ресурсам в случае возникновения конфликтов. Будем представлять такое отношение предшествования для любой пары потенциально конфликтующих процессов с помощью ориентированного графа предшествования H (англ. precedence graph), который может быть получен из графа G путем задания каждому ребру направления от процесса с большим приоритетом к процессу с меньшим приоритетом. На рис. 4.5 показан граф H для состояния системы, в котором процесс P₁ имеет приоритет над процессами P₂, P₄ и P₅, а процесс P₃ имеет приоритет над P₂ и P₄.

Очевидно, что для обеспечения различимости процессов между собой, граф H должен быть ациклическим. Действительно, если все процессы, составляющие цикл, оказываются в конфликтной ситуации, то они будут неразличимы между собой, т.к. для любых двух процессов P_i и P_j, входящих в цикл, P_i будет иметь приоритет над P_j и, одновременно, P_j будет иметь приоритет над P_i.

Рис. 4.5. Граф предшествования для задачи заседаний пяти комитетов.

В качестве примера рассмотрим ситуацию, когда граф предшествования H образует цикл между вершинами, соответствующими процессам P₁, P₅ и P₄, как показано на рис. 4.6. На этом рисунке процесс P₁ имеет приоритет над процессом P₅, P₅ имеет приоритет над P₄, и P₄ имеет приоритет над P₁. Если конфликт доступа к разделяемому ресурсу возникает только между двумя процессами из перечисленных выше, он может быть легко разрешен в пользу процесса с большим приоритетом. Проблема же возникнет тогда, когда все три процесса одновременно захотят использовать разделяемые ресурсы и войдут в конфликт. Тогда выбрать один процесс из трех детерминированным способом не представится возможным.

Рис. 4.6. Пример цикла в графе предшествования.

Если граф H не содержит циклов, то вершину, в которую не входит ни одно ребро, будем называть корнем. Тогда в качестве отличительного свойства процессов можно использовать значение глубины соответствующей ему вершины (англ. depth), определяемой как наибольшее число ребер по любому направленному пути от корня графа к данной вершине. Глубина корня графа равна нулю. По определению две соседние вершины не могут иметь одну и ту же глубину. Например, на

рис. 4.5 глубина процессов P₁, P₅ и P₄ соответственно равна 0, 1 и 2. Обратим внимание, что, опираясь на понятие глубины вершины, граф H задает отношение частичного порядка на множестве процессов.
Таким образом для обеспечения свойства различимости процессов, алгоритм разрешения конфликтов должен гарантировать ацикличность графа H при любом состояния системы. Однако отсутствие циклов в графе H в любом состоянии системы само по себе не обеспечивает свойство справедливости в разрешении конфликтов. Необходимо, чтобы даже при постоянном возникновении конфликтных ситуаций каждый процесс за конечное время получал бы возможность разрешать все свои конфликты в свою пользу. Это требование может быть выполнено при условии, что каждый процесс, находящийся в конфликтной ситуации, будет "подниматься вверх" по графу H до тех пор, пока не станет первым в порядке предшествования среди всех процессов, с которыми он конфликтует. Фраза "процесс будет подниматься вверх по графу H" подразумевает под собой тот факт, что состояние системы будет меняться, и вместе с ним будет меняться граф H так, что в некотором будущем состоянии рассматриваемый процесс сможет разрешить все свои конфликты в свою пользу. В крайнем случае, процессу может понадобиться "подняться в самый верх" графа H до его корня. Если процесс станет корнем графа H, т.е. будет иметь нулевую глубину, то любой его конфликт с любым другим процессом разрешится в его пользу, т.к. корневой процесс имеет приоритет над всеми своими соседями.
Каким же образом мы можем изменять граф H? Единственный способ заключается в изменении ориентации его ребер. Кроме того, для построения именно распределенного алгоритма работы с графом H необходимо реализовать соответствующее представление этого графа в распределенной системе и каждое его изменение производить локально одним из процессов этой системы.
Таким образом, обобщая все вышесказанное, можно заключить, что распределенный алгоритм работы с графом предшествования H должен удовлетворять следующим требованиям.

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

Для реализации распределенного представления графа H и алгоритма работы с ним рассмотрим обобщенную задачу обедающих философов, которая моделирует проблему разрешения конфликтов в распределенных системах. Решение этой задачи определяет представление графа предшествования H в распределенной системе с помощью вспомогательных ресурсов и демонстрирует алгоритм работы с этим графом.