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

Различимость. В каждом состоянии системы для любого множества конфликтующий процессов как минимум один процесс должен быть отличим от других процессов в таком множестве. Примером такого свойства может являться уникальный идентификатор процесса.

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

Если конфликты доступа возникают в одном и том же состоянии системы, то детерминированная схема разрешения конфликтов будет давать одни и те же результаты, потому как результат работы детерминированного метода полностью определяется состоянием системы. В этом случае схема разрешения конфликтов не будет справедливой. Таким образом для удовлетворения требования справедливости разрешения конфликтов необходимо, чтобы при возникновении конфликтов состояние системы не было одинаковым. Примером информации, учет которой позволяет гарантировать то, что конфликты возникают при различных состояниях системы, является время. При этом под временем можно понимать как реальное физическое время, так и логическое время, рассмотренное ранее. Так, в представленных выше алгоритмах взаимного исключения Лэмпорта и Рикарта-Агравала конфликты доступа к КС разрешались с помощью механизма скалярных часов. Процессы использовали присваиваемые запросам отметки времени для разрешения конфликта доступа в пользу процесса с наименьшим временем возникновения запроса. Если же показания скалярных часов нескольких процессов совпадали, то для определения процесса, победившего в конфликте, использовалось другое отличительное свойство, а именно, уникальный идентификатор процесса. Ниже мы рассмотрим другой подход к разрешению конфликтов доступа, основанный на расположении вспомогательных ресурсов. Важно отметить, что вспомогательные ресурсы используются исключительно для целей разрешения конфликтов и не имеют прямого отношения к реальным разделяемым ресурсам, из-за которых может возникнуть конфликт доступа. Возможность возникновения конфликтов между процессами в распределенной системе можно задать в виде неориентированного графа G, где каждому процессу P_i поставлена в соответствие вершина графа. Ребро, соединяющее две вершины, соответствующие процессам P_i и P_j, существует в G тогда и только тогда, когда между процессами P_i и P_j может возникнуть конфликт доступа: другими словами, когда существует один или несколько разделяемых ресурсов, требующих эксклюзивного доступа, к которым эти процессы могут обратиться одновременно. Такой
граф G называют графом конфликтов (англ. conflict graph).
Для иллюстрации построения и использования графа конфликтов рассмотрим следующий пример.
Представим какой-нибудь законодательный орган, в который входят пять комитетов. Каждый комитет сформирован из пяти человек, таким образом, как показано в Таблице 4.1. Общее собрание этого законодательного органа можно провести в любое время, когда не проходит заседание любого из его комитетов. Пусть каждый из представленных пяти комитетов собирается запланировать еженедельное четырехчасовое заседание для своих членов. При этом было бы
желательно, чтобы такие заседания проводились по возможности одновременно. В противном случае, если все комитеты будут собираться в непересекающиеся периоды времени, общее время занятости всех комитетов составит 20 часов, что ограничивает возможность проведения общего собрания законодательного органа. Из Таблицы 4.1 следует, что не все комитеты могут заседать одновременно, т.к. некоторые сотрудники входят сразу в несколько комитетов и, очевидно, не могут одновременно присутствовать на нескольких заседаниях: в Таблице 4.1. такие сотрудники отмечены серым цветом. Например, сотрудник E одновременно входит в состав комитета 1 и комитета 2.