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

Наиболее известными пессимистическими протоколами для баз данных в системах реального времени являются модификации «двухфазового протокола блокирования» (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.

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

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

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

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

1. OPT-SACRIFICE

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

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

2. OPT-WAIT

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

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

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

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

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

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

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

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

OPT-WAIT