Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 84
Текст из файла (страница 84)
Синхронизация5.7- Итогис взаимодействием между процессами тесно связан вопрос синхронизации процессов в распределенных системах. Синхронизация — это все то, что позволяетнам делать правильные вещи в правильное время. Проблема распределенных систем и вообще компьютерных сетей состоит в том, что для них не существует понятия единых совместно используемых часов. Другими словами, процессы на различных машинах имеют свое собственное мнение о времени.Существуют различные способы синхронизации часов в распределенных системах, но все они основаны на обмене показаниями часов, а это требует учитывать задержки на посылку и получение сообщений.
Точность алгоритмов синхронизации в значительной мере определяют вариации в задержках доступа испособы учета этих вариаций.Во многих случаях знания абсолютного времени не требуется. Достаточно,чтобы соответствующие события в различных процессах происходили в правильной последовательности. Лампорт показал, что, введя понятие логическихчасов, можно заставить набор процессов соблюдать общее соглашение относительно правильной очередности событий. В сущности, каждое событие е, такоекак посылка или прием сообщения, получает абсолютно уникальную логическую отметку времени С{е), такую, что если событие а происходит раньше 6, тоС{а) < С(Ь).
Отметки времени Лампорта могут быть расширены до векторныхотметок времени: если С(а) < С(Ь), то мы всегда знаем, что событие а причиннопредшествует событию Ь.Поскольку в распределенных системах нет понятия совместно используемойпамяти, часто трудно определить текущее состояние системы. Определение глобального состояния распределенной системы можно выполнить путем синхронизации всех процессов так, чтобы каждый из них определил и сохранил своелокальное состояние вместе с сообщениями, которые передаются в этот момент.Сама по себе синхронизация может быть выполнена без остановки процессови записи их состояния.
Вместо этого в ходе работы распределенной системыс нее можно сделать мгновенный слепок — распределенный снимок состояния.Синхронизация между процессами часто требует, чтобы один из процессоввыступал в роли координатора. В этом случае если координатор не фиксирован,необходимо, чтобы процессы в распределенных вычислениях могли решить, который из них будет координатором. Это решение принимается посредством алгоритмов голосования. Алгоритмы голосования, как правило, задействуются присбое или отключении существовавшего координатора.Важный класс алгоритмов синхронизации — распределенные взаимные исключения.
Эти алгоритмы гарантируют, что в распределенном наборе процессовдоступ к совместно используемым ресурсам имеет максимум один процесс. Распределенные взаимные исключения можно легко обеспечить с помощью координатора, который будет следить, чья сейчас очередь. Существуют также и полностьюраспределенные алгоритмы, но их минус — чересчур большая чувствительностьк сбоям процессов и связи.5.7. Итоги325С взаимными исключениями тесно связаны распределенные транзакции.Транзакция состоит из набора операций с совместно используемыми данными,при этом вся транзакция целиком либо полностью выполняется, либо полностьюне выполняется.
Кроме того, несколько транзакций могут выполняться одновременно, при этом результат оказывается таким, как если бы эти транзакции выполнялись в некоторой заданной очередности. И наконец, транзакции долговечны, в том смысле, что после завершения их результат неизменен.Вопросы и задания1.
Назовите как минимум три источника задержек между радиостанцией WWV,которая рассылает сигналы точного времени, и процессором в распределенной системе, устанавливающим свои внутренние часы.2. Рассмотрим поведение двух машин в распределенной системе. Обе они имеют часы, которые считаются выставленными на 1000 тиков в миллисекунду.Одни из часов действительно выдают такую частоту тиков, другие же тикаютвсего 990 раз в миллисекунду. Если поправки UTC приходят раз в минуту,какое максимальное расхождение может возникнуть между часами?3.
Добавьте к рис. 5.7 новое сообш;ение одновременно с сообщением А так, чтобы ни до сообщения Л, ни после него ничего не происходило.4. Является ли абсолютно необходимым подтверждение каждого сообщения дляполностью упорядоченной групповой рассылки с отметки времени по Лампорту?5. Рассмотрим коммуникационный уровень, в котором сообщения доставляются в том же порядке, в котором они были отправлены. Приведите пример, когда даже такое упорядочение излишне строго.6. Представьте себе, что два процесса одновременно обнаруживают передачу координатора и решают провести голосование по алгоритму забияки.
Что произойдет в этом случае?7. На рис. 5.12 мы видим два одновременно курсирующих сообщения ГОЛОСОВАНИЕ. Хотя мы не испытываем проблем с тем, что их два, было бы симпатичнее убрать одно из них. Придумайте алгоритм, который делал бы это, неоказывая влияния на основной алгоритм голосования.8.
Многие распределенные алгоритмы требуют наличия координирующего процесса. В какой степени такие алгоритмы могут считаться распределенными?9. При централизованном подходе к взаимным исключениям (см. рис. 5.13) после получения сообщения от процесса о том, что он не нуждается большев исключительном доступе к критической области, которую использовал, координатор обычно разрешает доступ первому процессу в очереди.
Приведитедругой возможный алгоритм работы координатора.10. Рассмотрим снова рис. 5.13. Представьте себе, что координатор стал неактивным. Обязательно ли это приведет к сбою системы? Если нет, при каких326Глава 5. Синхронизацияусловиях это произойдет? Существует ли способ решить проблему и сделатьсистему устойчивой к потере координатора?И. Алгоритм, предложенный в [380], имеет недостаток. Если в процессе возникает сбой и он перестает отвечать другим процессам на их запросы на входв критическую область, отсутствие ответа интерпретируется как запрет доступа.
Мы предложили, чтобы ответ на все запросы приходил немедленно, дабы проще было обнаружить сбойные процессы. Существуют ли такие условия, при которых этот метод окажется неприемлемым?12. Как изменяться элементы в табл. 5.1, если мы предположим, что алгоритмыреализуются в локальной сети, которая поддерживает аппаратную широковещательную рассылку?13. Распределенные системы могут иметь множество независимых критическихобластей. Представим себе, что процесс О хочет войти в критическую область А,а процесс 1 хочет войти в критическую область В.
Приведет ли использование алгоритма, предложенного в [380], к взаимной блокировке? Поясните свойответ.14. Рассматривая рис. 5.16, мы говорили об атомарном обновлении списка товаров с использованием магнитных лент. Как вы полагаете, почему, несмотряна простоту эмуляции магнитных лент при помощи диска (в качестве файла),этот способ все же не используется?15. В табл. 5.3 представлены три плана, два приемлемых и один неприемлемый.Для этих же транзакций (см. листинг 5.4) создайте полный список значений х,которые могут получиться в результате, и укажите, какие из них допустимы,а какие нет.16. Когда для реализации транзакций над файлами используется закрытое рабочее пространство, может случиться так, что в родительское рабочее пространство придется копировать большое количество индексов файлов.
Как это сделать, не вводя условий гонок?17. Приведите полный алгоритм попытки блокирования файла с успешным и неуспешным результатами. Рассмотрите блокировку на чтение и на запись,а также возможность файла быть в момент попытки неблокированным, заблокированным на чтение, заблокированным на запись.18.
Системы, использующие блокировки для управления параллельным выполнением транзакций, обычно отличают блокировку на чтение от блокировкина запись. Что произойдет, если процесс всегда устанавливал блокировку начтение, а теперь хочет заменить ее блокировкой на запись? Что произойдетв случае замены блокировки на запись блокировкой на чтение?19. Используя упорядочение по отметке времени в распределенных системах,предположим, что операция записи wnte(Ti,x) может быть передана менеджеруданных, поскольку единственная грозящая конфликтом операция wnte(T2,x)имеет меньшую отметку. Почему имеет смысл потребовать от планировщикаповторно передать операцию write(Ti,x) менеджеру данных после завершения транзакции Гг?5.7.
Итоги32720. Является ли оптимистическое управление параллельным выполнением транзакций более (или менее) строгим, чем использование отметок времени? Почему?21. Гарантирует ли использование отметок времени в управлении параллельнымвыполнением транзакций сериализуемость процесса? Почему?22. Мы много раз говорили, что в случае прерывания транзакции мир возвращается в свое первоначальное состояние, как если бы никакой транзакции небыло.
Мы лгали. Приведите пример, когда вернуть мир в исходное состояниеневозможно.Глава 6Непротиворечивостьи репликация6.1. Обзор6.2. Модели непротиворечивости, ориентированные на данные6.3. Модели непротиворечивости, ориентированные на клиента6.4. Протоколы распределения6.5. Протоколы непротиворечивости6.6. П р и м е р ы6.7. ИтогиВажным вопросом для распределенных систем является репликация данных. Данные обычно реплицируются для повышения надежности и увеличения производительности. Одна из основных проблем при этом — сохранение непротиворечивости реплик.
Говоря менее формально, это означает, что если в одну из копийвносятся изменения, то нам необходимо обеспечить, чтобы эти изменения быливнесены и в другие копии, иначе реплики больше не будут одинаковыми. В этойглаве мы детально рассмотрим, что в действительности означает непротиворечивость реплицируемых данных и различные способы, которыми она достигается.Мы начнем с общего обзора, в ходе которого обсудим, для чего используетсярепликация и как она влияет на масштабируемость. Особое внимание мы уделим репликации на базе объектов, важность которой для распределенных системв настоящее время растет.Чтобы добиться высокой производительности в операциях с совместно используемыми данными, разработчики параллельных компьютеров уделяют большое внимание различным моделям непротиворечивости данных в распределенныхсистемах с разделяемой памятью. Эти модели, одинаково успешно применяемыедля различных типов распределенных систем, детально рассматриваются в этойглаве.Реализация моделей непротиворечивости разделяемой памяти для крупномасштабных распределенных систем обычно представляет собой нелегкую задачу.6.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
