Взаімоблокіровке

Вище було описано, як може використовуватися блокування (а точніше, строгий протокол двофазної блокування) для вирішення трьох основних проблем управління паралельним виконанням Але, на жаль, було також показано, що блокування може сама стати причиною виникнення проблем, з яких основною є проблема взаимоблокировки У попередньому розділі були наведені два приклади взаимоблокировки На рис 1610 показаний трохи більш загальний варіант цієї проблеми на даному малюнку через rl і г2 позначені будь-які блокуються ресурси, а не тільки кортежі бази даних (див розділ 169), а за допомогою операторів LOCK EXCLUSIVE позначаються будь оператори, для виконання яких потрібна видача запитів на блокування X, явних або неявних

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

кожна з них очікує, поки одна з решти транзакцій не звільнить блокування,

щоб отримати можливість продовжити свою работу2 На рис 1610 показана взаімоблокіровка, в якій беруть участь дві транзакції, але можливі також такі ситуації (принаймні, в принципі), коли під взаімоблокіровке беруть участь три, чотири або більшу кількість транзакцій Однак експерименти, проведені в системі System R, показують, що на практиці взаимоблокировки, в яких беруть участь більше двох транзакцій, майже ніколи не виникають [169]

Рис 169 Проблема аналізу несумісності виключається, але в момент часу t7

виникає взаємо блокування

Якщо сталася взаімоблокіровка, бажано, щоб система виявила її і розірвала Для виявлення взаимоблокировки необхідно визначити наявність циклу в графі очікування (Wait-For Graph) Так називається граф, який, неформально висловлюючись, показує хто кого чекає (Див упр 164) Щоб розірвати взаємоблокування, необхідно вибрати одну з транзакцій, що беруть участь під взаімоблокіровке (тобто одну з транзакцій, які входять до складу циклу в графі очікування), в якості жертви і

2  Іноді в літературі для позначення взаимоблокировки застосовується також досить барвистий термін смертельні обійми (Deadly embrace)

виконати її відкат, що дозволяє звільнити її блокування і дати можливість іншим транзакцій продовжити свою роботу

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

Рис 1610 Приклад взаимоблокировки

До речі, слід зазначити, що невдале завершення роботи транзакції, обраної в якості жертви, і подальший її відкат відбуваються не з вини самої цієї транзакції У деяких системах здійснюється автоматичний перезапуск такої транзакції з самого початку на підставі припущення про те, що умови, якими раніше було викликано виникнення взаимоблокировки, ймовірно, більше не повторяться В інших системах просто передбачена передача у відповідь додатком коду винятку deadlock victim (Жертва взаимоблокировки) вибір способу подальших дій для правильного виходу з цієї ситуації надається самому додатком Зрозуміло, що з точки зору прикладного програміста перший з цих двох підходів є кращим А якщо навіть сам програміст іноді захоче взяти участь в усуненні зазначеної проблеми, він має для цього всі можливості, але з очевидних причин завжди бажано приховувати її існування від кінцевого пользоштеля

Запобігання взаімоблокіровок

Деякі підходи до усунення взаімоблокіровок засновані на тому, що існує можливість модифікувати протокол блокування різними способами, з тим щоб повністю уникнути взаімоблокіровок, а не чекати їх виникнення, після чого їх усувати (як це робиться в більшості систем) Один з подібних підходів коротко розглядається в даному розділі Цей підхід реалізовано в двох версіях, званих очікування-скасування і скасування-очікування, і був вперше запропонований для використання в розподілених системах [1619], але може також застосовуватися в централізованих системах Короткий опис розглянутого підходу до запобігання взаімоблокіровок наведено нижче

■ Кожна транзакція позначається відміткою часу її початку (яка повинна бути унікальною)

■ Якщо транзакція А запрошувати блокування на кортежі, який вже заблокує ван транзакцією в, то виконуються такі дії в залежності від застосовуваного варіанта

■ Очікування-скасування (Wait-Die) Якщо виконання транзакції А почалося рань ше, ніж у, А переходить в стан очікування в іншому випадку відбувається її скасування Це означає, що здійснюється відкат і перезапуск транзакції А

■ Скасування-очікування (Wound-Wait) Якщо виконання транзакції А почалося пізніше, ніж у, вона переходить в стан очікування в іншому випадку, вона скасовує В Це означає, що відбувається відкат і перезапуск транзакції В

■ Якщо транзакція повинна бути перезапущено, їй після запуску присвоюється її первісна відмітка часу

Слід зазначити, що перший компонент назви використовуваної версії (Очікування або скасування) в будь-якому випадку вказує, що станеться, якщо виконання транзакції А почалося раніше, ніж В Цілком очевидно, що у версії очікування-скасування безліч всіх очікують транзакцій складається з транзакцій, що почалися раніше і які очікують завершення роботи тих транзакцій, які були розпочаті пізніше, а у версії отменаожіданіе безліч всіх очікують транзакцій складається з транзакцій, що почалися пізніше і очікують завершення роботи тих транзакцій, які були розпочаті раніше Цілком очевидно, що при використанні будь-який з цих версій взаімоблокіровка не може взагалі виникнути Крім того, можна легко переконатися в тому, що в кінцевому підсумку гарантовано успішне завершення роботи кожної транзакції Це означає, що виникнення активного тупика неможливо (жодна з транзакцій не повинна очікувати до нескінченності), до того ж жодна транзакція не повинна перезапускатися знову і знову нескінченну кількість разів Основним недоліком цього підходу (при використанні будь-якої з версій) є те, що в ньому доводиться виконувати забагато відкатів

Джерело: Дейт К Дж, Введення в системи баз даних, 8-е видання: Пер з англ – М: Видавничий дім «Вільямс», 2005 – 1328 с: Ил – Парал тит англ

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*