Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 71
Текст из файла (страница 71)
Возможна ли при подсчете поколений ссылок такая ситуация, когда объектбудет сочтен мусором и уничтожен, поскольку невозможно определить, к какому поколению относится этот объект, хотя на него еще имеются ссылки?21. Возможно ли при подсчете поколений ссылок, чтобы значение G[i] оказалосьменьше нуля?22. При работе со списком ссылок, если после посылки команды ping процессу Рне был получен ответ, процесс удаляется из списка ссылок на объект.
Будетли правильным удалить этот процесс?23. Опишите очень простой способ определения момента достижения шага стабилизации при сборке мусора путем трассировки по [255].Глава 5Синхронизация5.1. Синхронизация часов5.2. Логические часы5.3.Глобальное состояние5.4. Алгоритмы голосования5.5. Взаимное исключение5.6. Распределенные транзакции5.7. ИтогиВ предыдущих главах мы рассматривали процессы и связь между процессами.Хотя связь и очень важна, это еще не все. Не менее важны вопросы взаимодействия и синхронизации процессов друг с другом.
Взаимодействие частично обеспечивается именованием, которое позволяет процессам как минимум совместно использовать ресурсы и вообще сущности.В этой главе мы в основном сосредоточимся на том, как процессы синхронизируются между собой. Так, например, важно, что несколько процессов не способны одновременно получать доступ к совместно используемым ресурсам, таким как принтеры, а должны взаимодействовать, позволяя друг другу временнополучать эксклюзивный доступ к этому ресурсу. Другой пример.
Несколько процессов могут время от времени нуждаться в соглашениях о порядке прохождения сообщений, о том, например, что сообщение m1 от процесса Р будет отправлено раньше, чем сообщение т2 от процесса Q.Как оказывается, синхронизация в распределенных системах часто значительно сложнее, чем синхронизация в однопроцессорных или мультипроцессорных системах.
Проблемы и решения, которые обсуждаются в этой главе, являютсяпо своей природе глобальными и случаются во множестве различных ситуацийв распределенных системах.Мы начнем с обсуждения синхронизации, основанной на реальном времени,продолжим обсуждение синхронизацией, у которой всего один относительныйпараметр упорядочивания, не считая упорядочивания по абсолютному времени.Мы обсудим также понятие распределенного глобального состояния и то, какэто состояние записывается в процессе синхронизации.5.1. Синхронизация часов275Во многих случаях важно, чтобы группа процессов назначила один из процессов координатором.
Это обычно происходит в соответствии с алгоритмом голосования. Мы рассмотрим различные алгоритмы голосования в отдельном разделе.Две отдельные темы, касающиеся синхронизации, — это взаимные исключения в распределенных системах и распределенные транзакции. Распределенныевзаимные исключения позволяют совместно использовать ресурсы, предотвративвозможность одновременного доступа нескольких процессов.
Распределенныетранзакции делают нечто похожее, но посредством совершенствования механизма контроля за параллельным выполнением. Взаимные исключения и транзакции будут обсуждаться в отдельных разделах.Существуют распределенные алгоритмы на любой «вкус и цвет» для распределенных систем самых разных типов. Множество примеров (и дополнительнойинформации) можно найти в [17, 421, 497]. Более формальный подход к изобилию существующих алгоритмов проводится в [277].5 . 1 .
Синхронизация часовв централизованных системах время определяется однозначно. Если процессунеобходимо время, он организует системный вызов, и ядро выдает ему ответ. Если процесс Л запрашивает время, а немного позже то же самое делает процесс J3,значение, которое получит 5, будет больше (или, возможно, равно) значению, полученному А. Оно не может быть меньше. В распределенных системах достижение договоренности о времени не столь тривиально.Для того чтобы понять, к чему могут привести проблемы определения глобального времени, достаточно одного примера с программой make операционнойсистемы UNIX.
Обычно в UNIX большие программы разбиваются на несколькофайлов исходного текста, и внесение изменений в один из этих файлов требуетповторной компиляции не всех, а только одного из этих файлов. Такой подходзначительно повышает производительность работы программистов. Например,если программа содержит 100 файлов, а исправлен был только один, достаточноперекомпилировать только этот файл.Обычная методика применения программы make проста. Когда программистзаканчивает свою работу, изменив все файлы с текстом программы, он запускаетпрограмму make, которая проверяет время последней модификации всех файловс исходным текстом и всех объектных файлов программы.
Если файл с исходным текстом input.c имеет время последней модификации 2151, а соответствующий ему объектный файл input.o — 2150, make считает, что input.c со времени создания input.o был изменен, и перекомпилирует его. С другой стороны, еслиoutput.c имеет время последней модификации 2144, а output.o — 2145, компиляция не требуется. Таким образом, программа make проверяет все файлы с исходным текстом в поисках тех из них, которые нуждаются в повторной компиляции,вызывая при необходимости компилятор.Представим теперь, что произойдет, если в распределенной системе отсутствует глобальное соглашение о времени. Предположим, что output.o, как и ранее.276Глава 5.
Синхронизацияимеет отметку времени изменения 2144, а output.c после создания был модифицирован, но получил отметку времени 2143, потому что часы на машине, где оннаходится, немного запаздывают, как это показано на рис. 5.1. Тогда программаmake не станет вызывать компилятор. В результате исполняемый файл программы будет содержать смесь объектных файлов из старых и новых исходных файлов. При исполнении это легко может привести к ошибкам, и программист сойдет с ума, пытаясь понять, что в его коде не так.Компьютер,на которомвыполняетсякомпиляцияКомпьютер,на которомвыполняетсяредактирование214421452146фI,^s.^ Создан файл output.o214212147I<Время по локальнымчасам214321442145Ф11^ \Создан файл output.c<Время по локальнымчасамРис.
5 . 1 . Когда каждая из машин имеет собственные часы, событие, происшедшее позжедругого, может быть отнесено к более раннему времениПоскольку время лежит в основе человеческого мышления, а эффект от отсутствия синхронизации может быть, как мы сейчас показали, столь печален, изучение синхронизации можно начать с простого вопроса: Можно ли синхронизировать все часы в распределенной системе?5.1.1. Физические часыПочти все компьютеры имеют встроенные периодические процессы для подсчетавремени. Несмотря на постоянное использование для этих устройств названия«часы», они не являются часами в обычном смысле этого слова.
Пожалуй, болееправильным словом было бы таймер (timer). Таймер компьютера — это обычноособым образом обработанный кристалл кварца. Находясь под напряжением,этот кристалл колеблется с постоянной частотой, которая зависит от свойств кристалла, таких как способ разрезания и величина напряжения.
С каждым кристаллом ассоциированы два регистра — счетчик (counter) и регистр хранения (holdingregister). Каждое колебание кристалла уменьшает счетчик на единицу. Когда значение счетчика достигает нуля, генерируется прерывание и счетчик перезагружается из регистра хранения. Таким образом, можно запрограммировать таймер генерировать прерывания 60 раз в секунду или с любой другой желаемой частотой.Каждое прерывание вызывается одним тиком таймера (clock tick).Когда система загружается в первый раз, она обычно просит пользователя ввести дату и время, которые пересчитываются в число тиков, начиная с определенной стартовой даты, и сохраняются в памяти. Многие компьютеры имеют специальную микросхему CMOS RAM с питанием от аккумулятора, в результате в нихнет необходимости вводить время при каждой загрузке.
После каждого тика таймера процедура обработки прерывания добавляет единицу к хранящемуся в памяти времени. Таким образом, часы (программные) сохраняют верное время.5.1. Синхронизация часов277Для единственного компьютера и единственных часов маленькая неточностьэтих часов не вызовет проблемы. Поскольку все процессы в машине используютодни и те же часы, они будут внутренне непротиворечивы. Так, например, еслифайл input.c имеет отметку времени 2151, а файл input.o — 2150, make перекомпилирует этот файл, даже если часы отстают на два деления и истинное время составляет соответственно 2153 и 2152.
Все это, разумеется, относится к относительному времени.В том случае, если мы перейдем к рассмотрению нескольких компьютеров,каждый из которых имеет собственные часы, картина изменится. Несмотря на точто частота каждого из кристаллов обычно весьма стабильна, невозможно гарантировать, что кристаллы на различных компьютерах будут иметь абсолютно одинаковую частоту. На практике, когда в систему входит п компьютеров, все п кристаллов работают с несколько отличаюш;ейся частотой, что ведет к постепеннойпотере синхронизации и выдаче часами при обраш^ении к ним различных значений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
