Протоколы управления транзакциями в СУБД реального времени

В отличие от классических СУБД в системе реального времени с каждой транзакцией ассоциируется директивный срок, т.е. момент времени, до которого транзакция должна быть завершена.

По типу директивных сроков СУБДРВ можно разделить на три основные группы: с жесткими, крепкими и мягкими директивными сроками [79]. В системе с жесткими директивными сроками любая задержка эквивалентна катастрофе, а с крепкими и мягкими директивными сроками только понижает производительность системы. Различие последних состоит в том, что в системе с крепкими директивными сроками транзакция, пропустившая свой директивный срок, выкидывается из системы, а в системе с мягкими директивными сроками такая транзакция просто становится менее значимой, но все еще может быть с пользой завершена.

Формально различие между типами директивных сроков можно описать при помощи функции полезности транзакции в зависимости от времени завершения. На рисунке 4.9.1 показан вид этой функции для всех трех типов систем.

По достижении директивного срока в системах первого типа транзакция становится «вредной», т.е. имеет отрицательную полезность. Если же директивные сроки крепкие, то транзакция просто становится бесполезной, но не «вредной». А в системах с мягкими директивными сроками полезность транзакции начинает постепенно уменьшаться с увеличением времени опоздания.

Протоколы управления транзакциями в СУБД реального времени - student2.ru

Рисунок 4.9.1 – Функция полезности для систем с мягкими, крепкими и жесткими директивными сроками

Еще одним важным отличием от случая классических СУБД является использование других критериев производительности. В классических СУБД производительность обычно измеряется как среднее число завершившихся транзакций в единицу времени, а в системе, работающей в реальном времени, на первый план выходят другие параметры − количество транзакций, пропустивших свои директивные сроки, среднее опоздание транзакций и т. п. Производительность же обычно меряют при помощи величины, которая зависит от нескольких таких параметров.

Способы вычисления этих величин сильно отличаются для разных типов СУБД реального времени. Так, например, в системах с крепкими директивными сроками среднее время опоздания транзакций не играет никакой роли, в то время как в системах с мягкими директивными сроками этот параметр довольно полезен [79].

Отличие критериев производительности, используемых в базах данных реального времени, от тех, что используются в классических СУБД, является основной причиной далеко не лучшей производительности при применении в системах реального времени классических протоколов управления транзакциями. Это, очевидным образом, влечет необходимость использования в таких системах других протоколов, которые лучше справляются со специфическими требованиями систем реального времени.

Используемые в СУБД реального времени протоколы должны использовать приоритеты транзакций, основанные на их директивных сроках, при разрешении конфликтов для того, чтобы гарантировать, что транзакция с большим приоритетом не будет задержана транзакцией с меньшим приоритетом. Это требование совершенно не учитывается в классических протоколах и это является одной из основных причин их неудовлетворительной производительности.

В течение последних 10 лет для систем реального времени был предложен ряд специфических протоколов с улучшенными характеристиками для систем реального времени. Среди них есть как модификации классических пессимистических и оптимистических протоколов [79], так совершенно новые, созданные специально для систем реального времени, протоколы [79].

Пессимистический подход

Наиболее известными пессимистическими протоколами для баз данных в системах реального времени являются модификации «двухфазового протокола блокирования» (2PL). Рассмотрим вкратце некоторые из них:

1 2PL-HP (High Priority)

Основная идея этого протокола [79] – разрешать все конфликты в пользу транзакций с большим приоритетом. Когда транзакция Т запрашивает блокировку на какой-то элемент данных d, возможно три варианта ситуаций:

· если d свободен, то Т получает на него блокировку;

· если d заблокирован, то если Т хочет получить блокировку на d, которая не конфликтует с уже существующими блокировками d других транзакций, то она ее получает, только если приоритет Т выше, чем у всех транзакций, стоящих в очереди на блокировки на d; если Т имеет приоритет выше, чем у всех держателей блокировок на d, то все они должны быть оборваны и Т получает блокировку;

· иначе Т становится в очередь на эту блокировку.

Заметим, что такой протокол гарантирует отсутствие тупиков.

2 2PL-WP (Wait Promote)

Эта модификация 2PL основана на идее наследования приоритета [79]. Когда транзакция Т с большим приоритетом запрашивает блокировку на какой-то ресурс d, который в данный момент заблокирован другой транзакцией с меньшим приоритетом, то Т встает в очередь (как в 2PL). Однако транзакции, удерживающей блокировку на d, повышают приоритет до уровня приоритета Т. В результате эта транзакция может быть выполнена быстрее (поскольку ей меньше придется простаивать дожидаясь других ресурсов) и, следовательно, приближается момент получения блокировки на d транзакцией Т.

Однако при применении этого метода (из-за рекурсивного повышения приоритетов) легко может возникнуть ситуация, когда большинство или даже все транзакции имеют одинаковый приоритет. В таком случае поведение этого протокола будет мало отличаться от поведения классического 2PL.

Пример работы этих двух протоколов изображен на рисунке 4.9.2.

Протоколы управления транзакциями в СУБД реального времени - student2.ru

Рисунок 4.9.2 – Пессимистические протоколы 2PL-HP, 2PL-WP

Оптимистический подход

Для повышения производительности в СУБД реального времени возникающие между транзакциями конфликты должны разрешаться в пользу транзакций с большим приоритетом, но это невозможно при применении «назад смотрящих» оптимистических протоколов, поскольку в этом случае конфликты возникают с уже завершившимися транзакциями. Поэтому большинство оптимистических протоколов, применяемых в СУБД реального времени, относятся к классу «вперед смотрящих».

Рассмотрим два примера оптимистических протоколов для систем реального времени:

1 OPT-SACRIFICE

Этот протокол [79] является адаптированным к СУБД реального времени вариантом протокола OCC-FV (Optimistic Concurrency Control with Forward Validation). Согласно OPT-SACRIFICE транзакция Т0, достигшая фазы проверки, обрывается, если хотя бы одна из конфликтующих с ней транзакций имеет больший приоритет. Иначе же Т0 благополучно завершается, а все конфликтующие с ней транзакции завершаются анормально. Таким образом, проверяемая транзакция, которая уже почти завершилась, приносит себя в жертву ради еще работающей транзакции Т1 с большим приоритетом.

Этот протокол имеет ряд слабых мест. Во-первых, обрыв транзакции Т0 означает, что работа по ее выполнению была выполнена напрасно и ресурсы, потраченные на это, были потрачены зря. Кроме того, поскольку Т1 также может завершиться анормально (в силу своих причин или как жертва для другой, более высокоприоритетной, транзакции), то жертва Т0 может оказаться напрасной.

2 OPT-WAIT

Этот протокол [79] также принадлежит к классу «вперед смотрящих» протоколов. Согласно ему, транзакция Т, достигнув фазы проверки и обнаружив множество конфликтующих с ней транзакций Т´, ведет себя следующим образом:

· если приоритет T выше, чем у всех конфликтующих с ней транзакций ТiÎТ´, то T завершается нормально, а все Тi завершаются анормально;

· иначе Т не обрывается немедленно, а ждет завершения тех Тi из Т´, чей приоритет выше ее собственного:

· в случае если более высокоприоритетная транзакция из Т´ завершается нормально, то Т обрывается;

· если же ни одна из более высокоприоритетных транзакций из Т´ не завершится нормально, то Тi завершается нормально сама.

Этот протокол не страдает, в отличие от OPT-SACRIFICE, обилием бесполезных рестартов, так как все они совершаются по необходимости. Однако он также имеет ряд слабых мест. Эффект блокирования, возникающий в результате задержки транзакции на стадии проверки (вместо ее непосредственного завершения или обрыва), приводит к консервированию ресурсов, тем самым приводя к тем проблемам, с которыми сталкиваются пессимистические протоколы в системах реального времени. Кроме этого, даже в случае успешного завершения задержанной транзакции Т, это может вызвать анормальное завершение множества более низкоприоритетных транзакций (как работающих, так и задержанных). Более того, число анормальных завершений может возрасти за счет тех низкоприоритетных транзакций, которые конфликтовали с Т, но не конфликтовали с более высокоприоритетными. Это число может сильно расти с ростом времени задержки Т.

Пример работы двух оптимистических протоколов изображен на рисунке 4.9.3.

Протоколы управления транзакциями в СУБД реального времени - student2.ru

Рисунок 4.9.3 – Оптимистические протоколы OPT-SACRIFICE,

OPT-WAIT

Сравнение подходов

Традиционно протоколы управления транзакциями различаются по двум критериям: время обнаружения конфликтов и способ их обнаружения. Согласно этим критериям пессимистические и оптимистические протоколы представляют собой две крайности.

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

Оба способа разрешения конфликтов имеют свои недостатки. Блокирование приводит к консервированию ресурсов, а рестарты вызывают их растрату.

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

Слабым местом пессимистического протокола являются также простои транзакций в ожидании получения блокировки на какой-либо ресурс. Такие простои повышают вероятность пропуска директивного срока. При этом транзакция, которая держала блокировку на нужный ресурс, также может пропустить свой директивный срок − из-за того, что он слишком близок или из-за необходимости ждать получения блокировок на другие ресурсы. Тем самым возможно, что все транзакции не успеют завершиться к своим директивным срокам.

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

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

Наши рекомендации