Керування транзакціями. Паралелізм

Три проблеми паралелізму
При обробці транзакцій в загальному випадку можливі три типи ситуацій, при яких паралельне виконання транзакцій, кожна з яких сама по собі є коректною, через взаємні завади здатні привести до невірного результату.

T1 T2 … Tn
DB
(цілісний
стан)

Приклад:
T1: Read(A) T2: Read(A)
A ← A+100 A ← A×2
Write(A) Write(A)
Read(B) Read(B)
B ← B+100 B ← B×2
Write(B) Write(B)
Constraint: A=B

Графік A - послідовний
T1 T2
Read(A); A ← A+100
Write(A);
Read(B); B ← B+100;
Write(B);
Read(A);A ← A×2;
Write(A); Read(B);B ← B×2;
Write(B);

Графік B - послідовний
T1 T2
Read(A);A ← A×2;
Write(A);
Read(B);B ← B×2;
Write(B);
Read(A); A ← A+100
Write(A);
Read(B); B ← B+100;
Write(B);

Графік C – умовно-послідовний
T1 T2
Read(A); A ← A+100
Write(A);
Read(A);A ← A×2;
Write(A);
Read(B); B ← B+100;
Write(B); Read(B);B ← B×2;
Write(B);

Графік D – не умовно-послідовний
T1 T2
Read(A); A ← A+100
Write(A);
Read(A);A ← A×2;
Write(A);
Read(B);B ← B×2;
Write(B);
Read(B); B ← B+100;
Write(B);

Графік E - умовно-послідовний
T1 T2’
Read(A); A ← A+100
Write(A);
Read(A);A ← A×1;
Write(A);
Read(B);B ← B×1;
Write(B);
Read(B); B ← B+100;
Write(B);
Такий як Графік D,
тільки з новою T2’

Проблеми паралелізму
Неправильний кінцевий результат виникає через безконтрольне чергування операцій двох правильний транзакцій.

Проблема втрати результатів оновлення
T1 T2
Read(A);
Read(A);
Write(A);
Commit;
Write(A);
Commit;

Проблема залежності від незафіксованих результатів
T1 T2
Read(A); A ← A+100
Write(A);
Read(A);A ← A×2;
Rollback
Write(A);
Commit;

Проблема неузгодженої обробки

Конфлікти
Конфлікти типу RR
операції читання не можуть порушувати роботу одна одної
Конфлікти типу WR
може виникнути проблема неузгодженої обробки
Конфлікти типу RW
може виникнути проблема незафіксованих оновлень
Конфлікти типу WW
може виникнути проблема втраченого оновлення

Блокування
У випадку, коли при виконанні деякої транзакції необхідно мати гарантії, що певний об’єкт бази даних не буде неочікувано змінений без відома транзакції, потрібний об’єкт блокується.

Механізм блокувань
В системі підтримуються блокування двох типів: виняткові блокування (блокування X - exclusive) і колективні блокування (блокування S - shared).
Якщо транзакція A володіє винятковим блокуванням (X), то запит від деякої іншої транзакції B на отримання блокування кортежу t будь-якого типу не може бути негайно задоволений.
Якщо транзакція А володіє колективним блокуванням (S) кортежу t, то виконуються наступні умови:
запит деякої іншої транзакції B на отримання блокування X кортежу t не може бути негайно задоволений;
запит деякої іншої транзакції B на отримання блокування S кортежу t може і повинен бути негайно задоволений (це означає, що з цього часу транзакція B також буде володіти блокуванням S кортежу).

Матриця сумісності

Проблема втрати результатів оновлення
T1 T2
Read(A); lock S
Read(A); lock S
Write(A); lock X
WAIT
WAIT Write(A); lock X
WAIT WAIT
WAIT WAIT
WAIT WAIT

Проблема залежності від незафіксованих результатів
T1 T2
Read(A); lock S
A ← A+100
Write(A);lock X
Read(A);lock S
WAIT
WAIT
Rollback ;(unlock A) A ← A×2;
Write(A); lock X
Commit;(unlock A)

Взаємне блокування
Взаємоблокування являє собою таку ситуацію, в якій дві або кілька транзакцій одночасно перебувають у стані очікування, причому
кожна з них очікує, поки одна з решти транзакцій не звільнить блокування.
Вирішення – вибір транзакції «жертви»

Упорядкованість
Упорядкованість - це загальноприйнятий критерій правильної організації почергового виконання набору транзакцій; іншими словами, така організація виконання вважається правильною тоді і тільки тоді, коли вона є впорядковуваною (?).
Тобто, якщо при почерговому виконанні заданої множини транзакцій буде отримано такий самий результат, що й при послідовному

Обґрунтування
Окремі транзакції є правильними
Будь-яка послідовність транзакцій, на підставі якої може бути організовано виконання транзакцій одна за одною, також є правильною
Почергове виконання операцій окремих транзакцій можна вважати коректним, якщо отримані результати будуть еквівалентні тим, що були б отримані при послідовному виконанні цих же транзакцій