Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 83
Текст из файла (страница 83)
Любые попытки Тпотребовать новой блокировки являются ошибкой профаммирования и приводят к прерыванию транзакции Т.Точка бгокировкиФаза подъема\^^Фаза спада^Г"^Время — •SРис. 5 . 2 1 . Двухфазная блокировкаМожно доказать [139], что если все транзакции используют двухфазную блокировку, любой план, сформированный путем перекрытия этих транзакций, сериализуем. В этом причина популярности двухфазной блокировки.320Глава 5. СинхронизацияВо многих системах фаза спада не начинается до тех пор, пока транзакция неокончится подтверждением или прерыванием, что и приведет к снятию блокировок, как показано на рис.
5.22. Такой режим, именуемый строгой двухфазной блокировкой {strict two-phase locking), имеет два серьезных преимущества. Во-первых,транзакция всегда считывает значения, записанные подтвержденной транзакцией, поэтому невозможно прерывание транзакции из-за того, что ее вычислениябазируются на недоступных данных. Во-вторых, любые наложения и снятия блокировок могут выполняться системой без использования транзакций: любые блокировки устанавливаются при доступе к элементу данных и снимаются по окончании транзакции. При таком поведении устраняются каскадные прерывания{cascaded aborts): отмена подтвержденной транзакции по той причине, что онаполучает элемент данных, который получать не должна.Точка бг окировкиФаза подъемаФаза спадаWS ^оQ.i/ОоъWWВсе блокировкиснимаютсяодновременно ^v^~^•уГ^Время — •Рис.
5.22. Строгая двухфазная блокировкаКак двухфазная блокировка, так и строгая двухфазная блокировка могут привести к тупикам. Если два процесса пытаются заблокировать одну и ту же парублоков, но в разном порядке, результатом будет взаимная блокировка, или тупик{deadlock). В этом случае используются традиционные технологии предотвращения тупиков, такие как выполнение блокировок в некотором строго заданномпорядке. Также возможно обнаружение взаимных блокировок путем составления полного графа транзакций, показывающего, какой процесс какую блокировку создал и какую хочет создать, с последующей проверкой этого графа на циклы.
И наконец, когда заранее известно, что никакая блокировка не может принормальной работе длиться более t секунд, можно использовать схему с тайм-аутом: если блокировка непрерывно принадлежит процессу более t секунд, это может происходить из-за взаимной блокировки.Существует несколько способов реализации двухфазной блокировки в распределенных системах.
Допустим, что данные, с которыми мы работаем, разбросаны по нескольким машинам. При централизованной двухфазной блокировке{centralized two-phase locking) за установку и снятие блокировок отвечает однамашина. Все менеджеры транзакций взаимодействуют с одним централизованным менеджером блокировок, который принимает от них запросы на блокиров-5.6. Распределенные транзакции321ку. После того как блокировка установлена, менеджер транзакций работает непосредственно с менеджерами данных. Отметим, что при такой схеме элементыданных могут быть также реплицированы на несколько машин. После выполнения операции менеджер транзакций возвращает блокировку менеджеру блокировок.При первичной двухфазной блокировке {primary two-phase locking) с каждогоэлемента данных делается первичная копия.
Блокировки устанавливает и снимает менеджер блокировок той машины, на которой размещена копия. Первичная двухфазная блокировка работает практически так же, как и централизованная, за исключением того, что блокировка может быть распределена понескольким машинам.И, наконец, при распределенной двухфазной блокировке {distributed two-phaselocking) предполагается, что данные могут быть распределены по нескольким машинам.
В противоположность первичной и централизованной двухфазной блокировке планировщики каждой из машин отвечают не только за установку и снятие блокировок, но и за пересылку операций менеджерам данных (локальным).В этом смысле распределенная двухфазная блокировка значительно ближе к базовой схеме двухфазной блокировки, но выполняется теперь на всех машинах,содержащих данные.Классическое исследование двухфазной блокировки для систем баз данныхи вообще управления параллельным выполнением можно найти в [47].Пессимистическое упорядочение по отметкам времениАбсолютно другой подход к управлению параллельным выполнением состоитв том, чтобы в момент начала каждой из транзакций Т присваивать ей отметкувремени ts{T).
Используя алгоритм Лампорта, мы можем убедиться в уникальности отметок времени, что в данном случае необходима. Каждая операция, являющаяся частью транзакции Г, также получает отметку времени ts{T). Кроме того,каждый элемент данных х в системе получает отметку времени чтения Z^SRD(X)и отметку времени записи ts^^Y(i^)• Отметка времени чтения соответствует отметке времени транзакции, которая последней считывала х, а отметка времени записи соответствует отметке времени транзакции, которая последней записывала х.При использовании упорядочивания по отметкам времени, если две операциивступают в конфликт, менеджер данных выполняет сначала операцию с наименьшей отметкой.Теперь представим себе, что планировщик получает от транзакции Т с отметкой времени ts операцию read{T,x), причем ts<tSwR{x).
Другими словами, онуведомляется о том, что операция записи значения х была произведена до началавыполнения Т. В этом случае транзакция Т просто прерывается. С другой стороны, если ts > tswR{x), все правильно, и операция чтения выполняется обычнымобразом. Кроме того, ^RD(^) устанавливается в значение max{ts, ^5RD(^:)}.Точно таким же образом обстоит дело и при получении планировщиком оттранзакции Г с отметкой времени ts операции записи write{T,x).
Если ts< tSRD(x),нам остается только прервать транзакцию, поскольку текущее значение х былосчитано предыдущей транзакцией. Транзакция Т просто слишком запоздала.322Глава 5. СинхронизацияС другой стороны, если ts > tSYcoipc), то, поскольку никакая предыдущая транзакция не считывала значения х, нам предстоит изменить его. Таким же образом^ W R W устанавливается в max{ts, ^5WR(^)}.Для того чтобы лучше разобраться в упорядочении по отметкам времени, рассмотрим следующий пример.
Представим себе три транзакции, Ти Тг и Гз. Транзакция Т\ отработала уже давно и использовала все элементы данных, необходимые транзакциям Т2 и Гз, так что на всех этих элементах стоят отметки временичтения и записи ts{T\). Транзакции Т2 и Гз начинаются параллельно с отметками^5(Г2)<^(Гз).Рассмотрим сначала чтение транзакцией Гг элемента данных х.
Пока транзакция Гз не подтверждена, обе отметки, 15л^к{х) и 1зш^{х), будут иметь значениеts{T\), которое меньше, чем ts(T2). На рис. 5.23, аи б мы видим, что ts(T2) больше, чем tswR(x) и ^5RD(X), так что запись допустима и будет предварительно выполнена (транзакция Гз еще не подтверждена). Она станет постоянной после завершения Гг. Теперь у элемента данных будет новая отметка времени записи,отметка времени транзакции Гг.tSRD(x)tSwR(x)|(Ti)|(Tl)А1з(Т2)|(Ti)tSRD(x)Пробнаязапись1з(Т2)к) к)tSRD(x)h)|(Т2)^OKВремяtSwR(x) tstent(x) ts(T2)|(Ti)Время'ts(T2)ts(T2)|(Ti)ВремяtSwR(x)'SWRM|(Т2)J|(Тз)|(Т2)OKВремя •ts(T2)^b)|(Тз)Время — ItSwR(x)|(Тз)Время — •Прерывание> Прерываниеts(T2)k)tSwR(x)|(Тз)Время •1з(Т2)b)tstent(x)|(Тз)ВремяРис.
5.23. Управление параллельным выполнением транзакцийс использованием отметок времениНа рис. 5.23, виг транзакции Г2 не везет. Транзакция Гз производит чтение(рис. 5.23, в) или запись (рис. 5.23, г) хи подтверждается. Транзакция Г2 прерывается. Однако она может получить новую отметку времени и стартовать снова.Рассмотрим теперь чтение. На рис.
5.23, д конфликтов нет, и чтение можетбыть произведено немедленно. На рис. 5.23, е в середину встревает какой-то бездельник и пытается записать х. Отметка времени этого ловкача меньше, чем у Г2,и поэтому Г2 просто дожидается, пока тот завершится, после чего считывает новый файл и продолжает работу.5.6. Распределенные транзакции323На рис. 5.23, ж транзакция 7з изменяет значение х и вновь подтверждается.А транзакции Гг снова приходится прерываться.
На рис. 5.23, з транзакция Гз находится в процессе изменения х до тех пор, пока не подтверждается. ТранзакцияТ2 снова чересчур запоздала и должна быть прервана.Свойства отметок времени и блокировки различны. Когда транзакция сталкивается с большими (устаревшими) отметками времени, она прерывается, блокировка же в сходных условиях либо ожидает, либо может быть выполненанемедленно. С другой стороны, при работе с отметками времени не бывает взаимных блокировок, а это большой плюс.Базовое упорядочение при помойки отметок времени существует в нескольких вариантах, среди которых следует отметить устойчивое упорядочение и многовариантное упорядочение. Подробности можно найти в [177, 337].Оптимистическое упорядочениепо отметкам времениТретий подход к выполнению нескольких транзакций в одно и то же время — этооптимистическое упорядочение по отметкам времени [244].
Идея, лежащая в основе этого подхода, удивительно проста: идите вперед и делайте то, что вы хотите, не обращая внимания на то, что одновременно происходит что-то еще. Есливозникнут проблемы, волноваться об этом мы будем после (этот алгоритм используют также многие политики). На практике конфликты относительно редки,так что большую часть времени все идет гладко.Конфликты могут быть нечастыми, но они все же случаются, и нам необходим способ их разрешения. Оптимистическое управление отслеживает случаи чтения и записи элементов данных. В момент подтверждения транзакции проверяется, не был ли с момента ее начала изменен какой-то элемент данных, нужныйдругим транзакциям. Если был, транзакция прерывается, если не был, транзакция подтверждается.Оптимистическое управление параллельным выполнением транзакций отлично реализуется на основе закрытых рабочих пространств.
В этом случае каждаятранзакция изменяет свои данные в частном порядке, не пересекаясь с другими.В конце работы новые данные либо принимаются, либо отбрасываются, что приводит нас к относительно простой и понятной схеме работы.Большое преимущество оптимистического управления параллельным выполнением транзакций состоит в том, что при его использовании достигается максимальный параллелизм и не бывает взаимных блокировок, поскольку никакойпроцесс никогда не ждет завершения блокировки. Недостаток такого управления в том, что временами оно дает сбой, и нам приходится начинать транзакциюснова. В условиях высокой загрузки вероятность сбоев может существенно возрасти, что делает оптимистическое управление плохим выбором.Как указывалось в [337], исследования оптимистического управления параллельным выполнением транзакций были сосредоточены в первую очередь на нераспределенных системах. Кроме того, создание коммерческих систем и прототипов сильно затруднено, что делает невозможным сравнение подобных системс другими.324Глава 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
