Вариант решения к домашнему заданию 7.
Задача 1 (20 очков)
а) Начальное состояние: A=c, B=d
Упорядоченный график Т1->T2:
Read(c, t), t:=c+2, write(A, c+2) A=c+2, B=d
T1: Read(d, t), t:=d*3, write(B, d*3) A=c+2, B=d*3
T2: Read(d*3,s), s:=d*3*2=d*6, write(B, d*6) A=c+2, B=d*6
T2: Read(c+2,s), s:=c+2+3=c+5, write(A, c+5) A=c+5, B=d*6
Упорядоченный график Т2->Т1:
T2: Read(d, s), s:=d*2, write(B, d*2) A=c, B=d*2
T2: Read(c, s), s:=c+3, write(A, c+3) A=c+3, B=d*2
T1: Read(c+3,t), t:=c+3+2=c+5, write(A, c+5) A=c+5, B=d*2
T1: Read(c*2,t), t:=d*2*3=d*6, write(B, d*6) A=c+5, B=d*6
б) Упорядочиваемый график:
Rt1(A, t); Wt1(A, t); Rt1(B, t); Wt1(B, t); Rt2(B, t); Wt2(B, t); Rt2(A, t); Wt2(A, t)
Упорядочиваемый график в силу специфики данной транзакции:
Rt1(A, t); Wt1(A, t); Rt2(B, t); Wt2(B, t); Rt1(B, t); Wt1(B, t); Rt2(A, t); Wt2(A, t)
Неупорядочиваемый график:
Rt1(A, t); Rt2(B, t); Wt2(B, t); Rt2 (A, t); Wt2 (A, t); Wt1(A, t); Rt1(B, t); Wt1(B, t)
в) Имеется 2 упорядоченных графика Т1 T2 и T2 T1.
Дополнительно 10 баллов за ответ: 402 упорядочиваемых графика (предполагая, что можно переупорядочить перекрывающиеся внутренние действия транзакций).
Правила: запись транзакции T1 должна всегда предшествовать чтению той же переменной транзакцией T2, либо запись транзакции T2 должна всегда предшествовать чтению той же переменной транзакцией T1.
Задача 2 (20 очков)
а) 1. Т1 Т2 Т3
2. Да. Эквивалентный упорядоченный график Т1 Т2 Т3
б) 1.
Т1 Т2 Т3 Т4
|
2. Нет. В графе предшествования имеется цикл Т1 Т2
Задача 3 (20 очков)
Удалить 23
 |
Пояснение Действие
Блокировать и читать корень a L(a) R(a)
Блокировать и читать узел c L(c) R(c)
Поскольку узел c в данный момент полон, мы знаем
Что корень не изменится при удалении, следовательно,
мы можем его разблокировать UL(a)
Блокировать и читать лист g L(g) R(g)
Если мы удалим 23 из узла g, только один элемент 29
Останется в узле, что меньше разрешенного минимума.
Мы должны перенести элемент от соседа (например) h,
поэтому блокировать и читать лист h. L(h) R(h)
Помещаем 29 и 31 в узел g, 37 и 41 в узел h.
Узел c будет теперь содержать 29,37 и 43. Чтобы снять
Блокировку как можно раньше, обновляем сначала
узел c и разблокируем его. W(c) UL(c)
Обновить узел g значениями 29 и 31 и разблокировать его. W(g) UL(g)
Обновить узел h значениями 37 и 41 и разблокировать его. W(h) UL(h)
Вставить 35. Здесь нам понадобиться создать новый блок (Create)
прежде, чем мы его сможем заблокировать
 |
Пояснение Действие
Блокировать и читать корень a L(a) R(a)
Блокировать и читать узел c L(c) R(c)
Блокировать и читать узел h L(h) R(h)
Поскольку h полон, мы должны расщепить его и создать
новый лист j который будет содержать 31 и 35. Запись j может
быть выполнена после обновления узла-родителя c, поэтому мы
разблокируем c как можно раньше. Узел j будет пока находиться в
буфере памяти. Create(j) L(j)
Новый элемент должен быть вставлен в узел c. Поскольку он полон,
он должен быть расщеплен и должен быть создан новый узел k
Узел c будет содержать 23,31 а узел k - будет добавлено к
корню, чтобы адресовать новый блок k. Create(k) L(k)
Обновить корень, добавив 37 и разблокировать его W(a) UL(a)
Обновить узел c и разблокировать его. W(c) UL(c)
Обновить новый узел k и разблокировать его. W(k) UL(k)
Обновить узел h и разблокировать его. W(h) UL(h)
Обновить узел j и разблокировать его W(j) UL(j)
Задача 4 (20 очков)
а) Проверка T1. Поскольку нет транзакций, прошедших проверку, проверка успешна.
Проверка T2. T1 проверена, но не закончена. Поэтому нужно проверить пересечение
RS(T2) WS(T1) = {B, C} {A} = {}. Поскольку Т1 еще не закончена к моменту проверки Т2, мы должны еще сравнить множества записи Т1 и Т2. WS(T2) WS(T1) =
{B} {A} = {}. Следовательно, проверка Т2 успешна.
Проверка T3 (включает сравнение с Т1 и Т2). T1 проверена, но незакончена до старта T3, поэтому проверяем RS(T3) WS(T1) = {C} {A} = {}. Кроме того, Т1 не закончена к моменту проверки Т3, поэтому проверяем W(T3) W(T1) = {C} {A} = {}
T2 проверена, но незакончена до старта T3, поэтому проверяем RS(T3) WS(T2) =
{C} {B} = {}. Кроме того, Т2 не закончена к моменту проверки Т3, поэтому проверяем
W(T3) W(T2) = {C} {B} = {}. Все пересечения пусты, следовательно, проверка успешна.
б) . Проверка T1. Поскольку нет транзакций, прошедших проверку, проверка успешна.
Проверка T2. T1 проверена, но не закончена. Поэтому нужно проверить пересечение
RS(T2) WS(T1) = {B, C} {C} = {C}. Проверка не успешна. Транзакция Т2 отменяется и не записыват значение В.
Проверка T3 (включает сравнение только с Т1, так как Т2 - отменена). T1 проверена, но незакончена до старта T3, поэтому проверяем RS(T3) WS(T1) = {В} {С} = {}.
Кроме того, Т2 не закончена к моменту проверки Т3, поэтому проверяем
W(T3) W(T1) = {А} {C} = {}. Проверка успешна.
Задача 5 (20 очков)
а) IX
б) SIX
в) S
г) группового режима не существует (S, IX, SIX не могут сосуществовать одновременно)
д) группового режима не существует (S, IX не могут сосуществовать одновременно)
