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

Методы эффективной реализации векторных часов 82

1. 
   Дифференциальная пересылка векторного времени 83
   
2. 
   Часы, фиксирующие прямую зависимость 85
   
3. 
   Адаптивный метод Жарда-Жордана 90
   

Матричное время 93

1. 
   Основные свойства 95
   

Раздел 4. Взаимное исключение в распределенных системах 96

1. 
   Общие концепции 96
   
2. 
   Централизованный алгоритм 101
   
3. 
   Алгоритмы на основе получения разрешений 103
   
   1. 
      Алгоритм Лэмпорта 103
      
   2. 
      Алгоритм Рикарта-Агравала 109
      
   3. 
      Алгоритм обедающих философов 114
      
4. 
   Алгоритмы на основе передачи маркера 132
   
   1. 
      Широковещательный алгоритм Сузуки-Касами 133
      
   2. 
      Алгоритм Реймонда на основе покрывающего дерева 138
      

Список литературы 152
Основная литература 152
Дополнительная литература 152

ВВЕДЕНИЕ

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

Однако отметим, что понятия параллельной и распределенной обработки данных не являются эквивалентными. Действительно, параллелизм подразумевает одновременное существование и выполнение задач. Распределение же обозначает территориальную удаленность процессов друг от друга. При этом задачи, связанные с распределенной обработкой данных, могут выполняться несколькими последовательными этапами в различные периоды времени. Конечно, в некоторых случаях, параллельная обработка данных может быть эффективно реализована с помощью распределенного программного обеспечения, особенно, при проведении большого объема вычислений, слабо связанных между собой. Поэтому можно сказать, что в общем случае распределенная обработка данных не подразумевает параллелизма, но возможность "параллельного использования" распределенных вычислительных систем существует.
Также обратим внимание, что для совместной работы процессов им необходим некоторый механизм взаимодействия. В мире параллельных систем обычно считается, что взаимодействие процессов обеспечивается с помощью разделяемых переменных. В этом случае один процесс осуществляет запись в одну из таких переменных, а другой – считывает записанное значение. В свою очередь в распределенных системах процессы взаимодействуют путем пересылки сообщений. Поэтому для обмена данными или координации совместных действий процессы должны использовать механизмы отправки и приема сообщений.
В настоящее время имеется немало книг, посвященных вопросам параллельного программирования. Тем не менее, по мнению автора, ощущается определенный недостаток в русскоязычной литературе, знакомящей читателей с основными проблемами в области распределенной обработки данных и существующими подходами к их решению. Среди известных автору источников по данной тематике можно выделить переводы книги Э. Таненбаума [2, 6] и монографии Ж. Теля [3, 7]. В книге Э. Таненбаума основное внимание уделяется архитектуре и технологиям построения распределенных систем, а не распределенным алгоритмам, в сущности, образующим ядро практически любого распределенного программного обеспечения. Поэтому, на взгляд автора, эта книга в большей степени ориентирована на инженеров-практиков, нежели на теоретиков, изучающих фундаментальные принципы и модели,
лежащие в основе всех распределенных систем. В свою очередь монография Ж. Теля посвящена преимущественно распределенным алгоритмам. Материал монографии излагается математическим языком, исследование особенностей распределенной обработки данных проводится на основе понятия системы переходов. Все утверждения и теоремы, приведенные в книге, сопровождаются строгими формальными доказательствами. Как следствие, подобный уровень изложения материала требует от читателя определенной начальной подготовки и, не исключено, что может отпугнуть молодого специалиста, только начинающего изучение распределенных алгоритмов и принципов работы распределенных систем.
В этой связи автор ставил своей целью написание учебного пособия, направленного на изучение фундаментальных аспектов организации распределенной обработки данных и ориентированного на неподготовленного читателя. С этой же целью описание модели распределенного вычисления и доказательство всех утверждений проводится до определенной степени неформально, но на уровне, достаточном для понимания существенных особенностей функционирования распределенных систем, выделяющих их среди систем других классов.
Материал учебного пособия следует рассматривать в качестве введения в проблематику распределенных вычислений. В пособии представлено несколько базовых понятий, концепций и алгоритмов, которые послужат основой для дальнейшего изучения предмета распределенных вычислений заинтересованными студентами. В первом разделе обсуждаются цели и задачи распределенных систем, а также сложности их разработки. Во втором разделе представлена модель распределенного вычисления, используемая при дальнейшем изложении. Кроме того, не опираясь на понятие единого физического времени, вводится отношение "произошло раньше", связывающее события процессов между собой. В третьем разделе рассматриваются различные механизмы логических часов, позволяющие упорядочивать события в одну или несколько последовательностей, которые могли бы происходить в системе, и, как следствие, значительно упрощающие разработку алгоритмов для распределенных систем. Четвертый раздел посвящен изучению основных распределенных алгоритмов взаимного исключения, ключевые идеи которых используются и для решения многих других задач в распределенных системах. Представленный в пособии список литературы содержит перечень источников, которые автор рекомендует в первую очередь для получения более подробной информации по рассматриваемым и дополнительным вопросам из области распределенных вычислений [1-7] и материал из которых в той или иной степени был использован при написании данного пособия [1-30].
Учебное пособие предназначено, прежде всего, для студентов, обучающихся по направлению "Информатика и вычислительная техника" и "Программная инженерия", изучающих дисциплину "Распределенные вычисления" и связанные с ней дисциплины. Пособие может быть полезно для специалистов в области информатики, вычислительной техники и программирования в качестве введения в проблематику распределенных вычислений.
Автор понимает, что, как и "в любой хорошо отлаженной программе всегда есть хотя бы одна ошибка", так и в любой многократно вычитанной книге она также наверняка присутствует. Поэтому автор будет благодарен за все присланные по адресу [e-mail] обнаруженные ошибки и опечатки, а также критические замечания.