Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 82
Текст из файла (страница 82)
Если транзакция прерывается, журнал используется для восстановления первоначального состояния. Начиная с конца и продвигаясь к началу,из журнала считываются записи и описанные в них изменения отменяются. Этодействие называется откатом {rollback) транзакции.Как и предыдущая, эта схема также может использоваться для работы с распределенными транзакциями. В этом случае каждая машина поддерживает собственный журнал изменений в локальной файловой системе. Откат в случае прерывания транзакции каждая машина производит по отдельности, восстанавливая свои исходные файлы.5.6.4. Управление параллельнымвыполнением транзакцийИтак, мы рассмотрели основные способы достижения атомарности транзакций.Достижение атомарности (и долговечности) транзакций при наличии сбоев — этоважнейшая тема, к которой мы вернемся в главе 7, когда будем рассматривать нетолько транзакции.
Такие свойства, как непротиворечивость и изолированность,основаны на возможности управления выполнением параллельных транзакций,то есть транзакций, выполняющихся одновременно и над одним и тем же набором совместно используемых данных.Цель управления параллельным выполнением транзакций состоит в том, чтобы позволить нескольким транзакциям выполняться одновременно, но таким образом, чтобы набор обрабатываемых элементов данных (например, файлов илизаписей базы данных) оставался непротиворечивым. Непротиворечивость достигается в результате того, что доступ транзакций к элементам данных организуется в определенном порядке так, чтобы конечный результат был таким же, каки при выполнении всех транзакций последовательно.Управление параллельным выполнением лучше всего можно понять в терминах трех менеджеров, организованных по уровням, как это показано на рис. 5.19.Нижний уровень предоставляет менеджера данных {data manager), который физически осуществляет операции чтения и записи данных.
Менеджер данных ничего не знает о том, какая транзакция выполняет чтение или запись. На самомделе он вообще ничего не знает о транзакциях.Средний уровень представлен планировщиком {scheduler). Он несет основнуюответственность за правильность управления параллельной работой, определяя,какой транзакции и в какой момент разрешается передать операцию чтения илизаписи менеджеру данных. Он также планирует отдельные операции чтенияи записи с теми же гарантиями непротиворечивости и изолированности, что и для316Глава 5.
Синхронизациятранзакций. Позже мы рассмотрим планирование, основанное на использованииблокировок, и планирование, основанное на использовании отметок времени.ТранзакцииМенеджертранзакцийREAD/WRITEПланировщикМенеджерданныхBEGIN_TRANSACTIONEND_TRANSACTIONLOCK/RELEASEилиоперациис отметками времениВыполнение чтения/записиРис. 5.19. Обобщенная организация менеджеровдля управления транзакциямиНа самом верхнем уровне находится менеджер транзакций (transaction manager), который отвечает, прежде всего, за атомарность и долговечность. Он обрабатывает примитивы транзакций, преобразуя их в запросы к планировщику.^\1Менеджертранзакций>^ПланировщикПланировщикг-X<1 'ПланировщикГ''МенеджерданныхМенеджерданныхМенеджерданныхМаш11наАМаш лиг ВМашк на СРис.
5.20. Обобщенная организация менеджеров для управленияраспределенными транзакциямиМодель, приведенная на рис. 5.19, может быть адаптирована к использованиюв распределенных системах, как показано на рис. 5.20. Каждая машина в этомслучае имеет своих планировщика и менеджера данных, которые совместно обес-5.6. Распределенные транзакции317печивают гарантии непротиворечивости локальных данных. Каждая транзакцияобрабатывается одним менеджером транзакций.
Последний работает с планировщиками отдельных машин. В зависимости от алгоритма управления параллельным выполнением транзакций планировщик также может работать с удаленнымименеджерами данных. Мы вернемся к разговору о распределенном управлениипараллельным выполнением чуть ниже.ИзолированностьОсновная задача алгоритмов управления параллельным выполнением — гарантировать возможность одновременного выполнения многочисленных транзакцийдо тех пор, пока они изолированы друг от друга.
Это значит, что итоговый результат их выполнения будет таким же, как если бы эти транзакции выполнялись одна за другой в определенном порядке.В листинге 5.4 представлены три транзакции, которые выполняются одновременно в трех отдельных процессах. Если бы они выполнялись последовательно,итоговыми значениями переменной х были бы 1, 2 или 3, в зависимости от того,какая из транзакций выполнялась бы последней (х может быть совместно используемой переменной, файлом или сущностью другого типа).Листинг 5 . 4 .
Три транзакции Т^, Т2 "^ ''"зBEGINJRANSACTIONX = 0:X = X + 1;ENDJRANSACTIONBEGINJRANSACTIONX = 0:X = X + 2:ENDJRANSACTIONBEGIN TRANSACTIONx"= 0 ;X = X + 3;ENDJRANSACTIONВ табл. 5.3 показаны различные способы упорядочивания, называемые планами {schedules). План 1 реально сериализован. Другими словами, транзакции выполняются строго последовательно, так что они по определению удовлетворяютусловию сериализуемости. План 2 не сериализован, но также допустим, посколькув результате его выполнения значение х, которое будет получено после отработки транзакций, соответствует значению, полученному при строго последовательном выполнении транзакций. Третий план недопустим, потому что в результатеего выполнения х становится равным 5, что при последовательном выполнениитранзакций невозможно.
Системе необходимо убедиться, что отдельные операции перемелсаются правильно. Давая системе свободу выбора любой очередности операций и проверяя корректность получаемых результатов, мы избавляемпрограммистов от необходимости реализовывать собственные взаимные исключения, что упрощает их работу.318Глава 5. СинхронизацияТаблица 5.3.
Возможные планы по очередности выполнения операцийНомерпланаОчередность операцийПравильностьплана1х=0;х=х+1:х=0:х=х+2:х=0:х=х+3:Правильно2х=0:х=0:х=х+1:х=х+2:х=0:х=х+3:Правильно3х=0:х=0:х=х+1;х=0:х=х+2:х=х+3:НеправильноДля того чтобы разобраться в планах и управлении параллельным выполнением, нет необходимости точно знать, как именно переменные будут вычисляться. Другими словами, неважно, будет ли значение х увеличено на 2 или 3. Чтодействительно важно, так это то, что значение х изменится.
Соответственно, мыможем описать транзакцию как наборы операций чтения и записи определенныхэлементов данных. Так, например, каждая из трех транзакций, Ть Т2 и Тз, приведенных в листинге 5.4, может быть представлена в виде последовательностей:write(Tl.x); read(Ti.x); wr1te(Ti,x)Основная идея управления параллельным выполнением состоит в том, чтобыправильно спланировать конфликтующие операции {conflicting operations).
Двеоперации конфликтуют, если они работают с одним и тем же элементом данных,и как минимум одна из них — это операция записи. В конфликте чтения-записи(read-write conflict) запись — это одна из операций. Кроме того, мы имеем делои с конфликтом двойной записи (write-write conflict), при этом не имеет значения,принадлежат ли конфликтующие операции к одной транзакции или к разным.Следует отметить, что две операции чтения никогда не конфликтуют между собой.Алгоритмы управления параллельным выполнением обычно классифицируются по способу синхронизации операций чтения и записи.
Синхронизация может производиться посредством механизма взаимного исключения совместно используемых данных (то есть блокировки) или явного упорядочивания операцийс помощью отметок времени.Дальнейшее деление можно провести между оптимистическим и пессимистическим управлением параллельным выполнением. Для пессимистических подходов фундаментальным является закон Мерфи, согласно которому если что-нибудь можно сделать неправильно, это что-то будет сделано неправильно. Припессимистических подходах операции синхронизируются до их выполнения,и, таким образом, конфликты разрешаются до того, как они проявятся. В противоположность этому, оптимистические подходы основаны на идее о том, чтообычно ничего плохого не случается. Поэтому операции без затей выполняются,а синхронизация производится в конце транзакции.
Если в этот момент обнаруживается конфликт, одна или более транзакций прерываются. Далее мы рассмотрим два пессимистических и один оптимистический методы. Прекрасный обзорразличных подходов можно найти в [46].Двухфазная блокировкаСамый старый и наиболее широко используемый алгоритм управления параллельным выполнением транзакций — это блокировка {locking). В своей простей-5.6. Распределенные транзакции319шей форме, когда процесс в ходе транзакции нуждается в чтении или записи элемента данных, он просит планировщик заблокировать для него этот элемент данных.
Точно так же, когда необходимость в этом элементе данных исчезает, планировщика просят снять блокировку. Задача планировщика состоит в том, чтобыустанавливать и снимать блокировку таким образом, чтобы получать только допустимые планы выполнения. Другими словами, мы нуждаемся в примененииалгоритма, предоставляющего нам только сериализуемые планы.
Один из такихалгоритмов — двухфазная блокировка.При двухфазной блокировке (Two-Phase Locking, 2PL), которая продемонстрирована на рис. 5.21, планировщик сначала, на фазе подъема {growingphase), устанавливает все необходимые блокировки, а затем, на фазе спада {shrinking phase),снимает их. Говоря конкретнее, выполняются три правила, описанные в [47].4 Когда планировщик получает операцию орег{Т,х) от менеджера транзакций, он проверяет, не конфликтует ли эта операция с другими операциями, уже получившими блокировку. Если в наличии конфликт, операцияорег{Т,х) откладывается (и транзакция Г вместе с ней). Если конфликтанет, планировщик производит блокировку для элемента данных х и передает операцию менеджеру данных.'f Планировщик никогда не снимает блокировку с элемента данных х, еслименеджер данных уведомляет его, что он осуществляет операцию, в которой участвует этот элемент данных."¥ После того как планировщик снимает с данных блокировку, установленную по требованию транзакции Г, он никогда не делает по требованиюэтой транзакции другую блокировку, при этом неважно, на какой элементданных транзакция Т требует установить блокировку.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
