17245

Решение проблем параллелизма при помощи блокировок

Лекция

Информатика, кибернетика и программирование

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

Русский

2013-06-30

164.5 KB

6 чел.

Лекция №9

Решение проблем параллелизма при помощи блокировок

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

Проблема потери результатов обновления

Две транзакции по очереди записывают некоторые данные в одну и ту же строку и фиксируют изменения.

Время

Транзакция A

Транзакция B

S-блокировка

- доступна

---

Чтение

---

---

S-блокировка

- доступна

---

Чтение

X-блокировка

- недоступна

---

Ожидание…

X-блокировка

- недоступна

Ожидание…

Ожидание…

 

Ожидание…

Ожидание…

Обе транзакции успешно накладывают S-блокировки и читают объект . Транзакция A пытается наложить X-блокирокировку для обновления объекта . Блокировка отвергается, т.к. объект уже S-заблокирован транзакцией B. Транзакция A переходит в состояние ожидания до тех пор, пока транзакция B не освободит объект. Транзакция B, в свою очередь, пытается наложить X-блокирокировку для обновления объекта . Блокировка отвергается, т.к. объект уже S-заблокирован транзакцией A. Транзакция B переходит в состояние ожидания до тех пор, пока транзакция A не освободит объект.

Результат. Обе транзакции ожидают друг друга и не могут продолжаться. Возникла ситуация тупика (взаимоблокировки).

Проблема незафиксированной зависимости (чтение "грязных" данных)

Транзакция B изменяет данные в строке. После этого транзакция A читает измененные данные и работает с ними. Транзакция B откатывается и восстанавливает старые данные.

Время

Транзакция A

Транзакция B

---

S-блокировка

- доступна

---

Чтение

---

X-блокировка

- доступна

---

Запись

S-блокировка

- недоступна

---

Ожидание…

Откат транзакции

(Блокировка снимается)

S-блокировка

- доступна

---

Чтение

---

Работа с прочитанными данными

---

---

---

COMMIT

---

 

Все правильно

 

Результат. Транзакция A притормозилась до окончания (отката) транзакции B. После этого транзакция A продолжила работу в обычном режиме и работала с правильными данными. Конфликт разрешен за счет некоторого увеличения времени работы транзакции A (потрачено время на ожидание снятия блокировки транзакцией B).

Проблема несовместимого анализа

Неповторяемое считывание

Транзакция A дважды читает одну и ту же строку. Между этими чтениями вклинивается транзакция B, которая изменяет значения в строке.

Время

Транзакция A

Транзакция B

S-блокировка

- доступна

---

Чтение

---

---

X-блокировка

- недоступна

---

Ожидание…

Повторное чтение

Ожидание…

COMMIT
(Блокировка снимается)

Ожидание…

---

X-блокировка

- доступна

---

Запись

---

COMMIT
(Блокировка снимается)

 

Все правильно

 

Результат. Транзакция B притормозилась до окончания транзакции A. В результате транзакция A дважды читает одни и те же данные правильно. После окончания транзакции A, транзакция B продолжила работу в обычном режиме.

Фиктивные элементы (фантомы)

Транзакция A дважды выполняет выборку строк с одним и тем же условием. Между выборками вклинивается транзакция B, которая добавляет новую строку, удовлетворяющую условию отбора.

Время

Транзакция A

Транзакция B

S-блокировка строк, удовлетворяющих условию .
(Заблокировано n строк)

---

Выборка строк, удовлетворяющих условию .
(Отобрано n строк)

---

---

Вставка новой строки, удовлетворяющей условию .

---

COMMIT

S-блокировка строк, удовлетворяющих условию .
(Заблокировано n+1 строка)

---

Выборка строк, удовлетворяющих условию .
(Отобрано n+1 строк)

---

COMMIT

---

 

Появились строки, которых раньше не было

 

Результат. Блокировка на уровне строк не решила проблему появления фиктивных элементов.

Несовместимый анализ данных

Длинная транзакция выполняет некоторый анализ по всей таблице, например, подсчитывает общую сумму денег на счетах клиентов банка для главного бухгалтера. Пусть на всех счетах находятся одинаковые суммы, например, по 100 у.е. Короткая транзакция в этот момент выполняет перевод 50 у.е. с одного счета на другой так, что общая сумма по всем счетам не меняется.

Время

Транзакция A

Транзакция B

S-блокировка счета - успешно

---

Чтение счета и суммирование.

---

---

X-блокировка счета - успешно

---

Снятие денег со счета .

---

X-блокировка счета - недоступно

---

Ожидание…

S-блокировка счета - успешно

Ожидание…

Чтение счета и суммирование.

Ожидание…

S-блокировка счета - недоступно

Ожидание…

Ожидание…

Ожидание…

 

Ожидание…

Ожидание…

Результат. Обе транзакции ожидают друг друга и не могут продолжаться. Возникла ситуация тупика (взаимоблокировки).

Разрешение тупиковых ситуаций

При использовании протокола доступа к данным с использованием блокировок часть проблем разрешилось (не все), но возникла новая проблема – тупики (взаимоблокировки):

  •  Проблема потери результатов обновления - возник тупик.
  •  Проблема незафиксированной зависимости (чтение "грязных" данных, неаккуратное считывание) - проблема разрешилась.
  •  Неповторяемое считывание - проблема разрешилась.
  •  Появление фиктивных элементов - проблема не разрешилась.
  •  Проблема несовместимого анализа данных - возник тупик.

Общий вид тупика (dead locks) следующий:

Время

Транзакция A

Транзакция B

Блокировка объекта - успешна

---

---

Блокировка объекта -успешна

Блокировка объекта - конфликтует с блокировкой, наложенной транзакцией B

---

Ожидание…

Блокировка объекта - конфликтует с блокировкой, наложенной транзакцией A

Ожидание…

Ожидание…

 

Ожидание…

Ожидание…

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

Выделяют два принципиальных подхода к обнаружению тупиковой ситуации и выбору транзакции-жертвы:

  1.  СУБД не следит за возникновением тупиков. Транзакции сами принимают решение, быть ли им жертвой.
  2.  За возникновением тупиковой ситуации следит сама СУБД, она же принимает решение, какой транзакцией пожертвовать.

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

Второй способ характерен для промышленных СУБД (ORACLE, MS SQL Server и т.п.). В этом случае система сама следит за возникновением ситуации тупика, путем построения (или постоянного поддержания) графа ожидания транзакций.

Основой обнаружения тупиковых ситуаций является построение (или постоянное поддержание) графа ожидания транзакций.

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

Например:

где P1, P2, P3 – параллельные транзакции, R – элемент обработки.

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

Устно. Для распознавания тупика периодически производится построение графа ожидания транзакций (иногда граф ожидания поддерживается постоянно), и в этом графе ищутся циклы. Традиционной техникой (для которой существует множество разновидностей) нахождения циклов в ориентированном графе является редукция графа.

Прежде всего, из графа ожидания удаляются все дуги, исходящие из вершин-транзакций, в которые не входят дуги из вершин-объектов. (Это как бы соответствует той ситуации, что транзакции, не ожидающие удовлетворения захватов, успешно завершились и освободили захваты). Для тех вершин-объектов, для которых не осталось входящих дуг, но существуют исходящие, ориентация исходящих дуг изменяется на противоположную (это моделирует удовлетворение захватов). После этого снова срабатывает первый шаг и так до тех пор, пока на первом шаге не прекратится удаление дуг. Если в графе остались дуги, то они обязательно образуют цикл.

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

Для простоты изображения можно использовать другое определение графа ожидания.

Определение. Граф ожидания представляет собой ориентированный граф G = (V, E), состоящий из множества вершин V – определяющих выполняемые транзакций и множества ориентированных ребер или дуг E – формируемых следующим образом:

  1.  Создается вершина, соответствующая каждой транзакции.
  2.  Создается дуга  B, если транзакция A ожидает освобождение элемента данных, заблокированного в настоящее время транзакцией B.

Взаимоблокировка имеет место, если граф ожидания содержит цикл.

Например. Построим граф ожидания для примера взаимоблокировки при устранении проблемы потери результатов обновления (см. график выше).


A

B: S - locks

A: X - locks

Конфликт R – W

Ожидание…

A: X - locks

B: X - locks

Конфликт W - W

Ожидание…


 

А также другие работы, которые могут Вас заинтересовать

26258. Создание картограмм агрофизического состояния почв и интерпретация результатов в геоинформационных системах (ГИС) 384 KB
  Практическое занятие Создание картограмм агрофизического состояния почв и интерпретация результатов в геоинформационных системах ГИС Цели и задачи. Приобретение навыков картографирования агрофизического состояния почв с использованием педотрансферных функций и ГИСтехнологий. Рассматривается методика разработки картограмм агрофизических свойств почв в геоинформационных системах на примере плотности почв и запасов продуктивной влаги. Освоить методику картографирования физических и воднофизических свойств почв на конкретном первичном...
26259. Понятия природного ландшафта и агроландшафта и принципы ландшафтно-экологического анализ территории 102.5 KB
  Формируются определения природного ландшафта сельскохозяйственного ландшафта рассматриваются задачи ландшафтноэкологического анализа территории и географическая классификация ландшафтов. Ключевые слова: геосистема геосистемные уровни региональный локальный местности урочище подурочище фации агроэкологическая группа земель элементарный ареал агроландшафта классификация ландшафтов. Географическая классификация природных и природносельскохозяйственных ландшафтов. В качестве базовой категории в ландшафтоведении используется понятие...
26260. Особенности проектирования защиты растений в агроценозах и перспективы ее экологизации 63.5 KB
  Лекция Особенности проектирования защиты растений в агроценозах и перспективы ее экологизации Цели и задачи. Проектирование защиты растений в агротехнологиях различных уровней интенсификации. Принципы и возможности экологизации защиты растений. Проектирование защиты растений в агротехнологиях различных уровней интенсификации Проектирование систем защиты осуществляется на основе определения видового состава вредных организмов в рамках агроэкологической группы земель и их потенциальной вредоносности которая устанавливается с помощью...
26261. Особенности проектирования обработки почвы под основные культуры в связи с различными агроэкологическими условиями 99 KB
  Практическое занятие Особенности проектирования обработки почвы под основные культуры в связи с различными агроэкологическими условиями Цели и задачи Сформировать представление о современных системах обработки почвы в севооборотах и основных направлениях ее совершенствования. Рассматриваются особенности обработки почвы в различных агроэкологических условиях в соответствии с требованиями сельскохозяйственных культур. Ключевые слова: оптимальная и равновесная плотность почвы отвальная плоскорезная чизельная комбинированная основная...
26262. Оценка агроклиматических условий 285.5 KB
  Температура воздуха почвы и растения всегда зависит от количества солнечной радиации. В зависимости от длительности промерзания почвы и ее среднегодовой температуры выделяются четыре типа температурного режима почв: мерзлотный характерен для районов вечной мерзлоты среднегодовая температура почвы отрицательная; длительно сезонно промерзающий с длительностью промерзания не менее 5 месяцев среднегодовая температура почвы положительная глубина проникновения отрицательных температур более 2 м; сезонно промерзающий с длительностью...
26263. Подготовка семян к посеву 609.5 KB
  Домашнее задание Подготовка семян к посеву Цели и задачи. Освоить систему подготовки семян к посеву приобрести навыки сортировки калибровки и обработки семян различными препаратами и физическими средствами стимуляции. Аннотация Рассматриваются различные виды подготовки семян к посеву: сортировка калибровка тепловой обогрев протравливание инкрустация дражирование скарификция стратификация и др. Приводятся нормативные требования к качеству семян.
26264. Расчет потребности в элементах питания на планируемую урожайность 109 KB
  Развить умение рассчитывать дозы минеральных и органических удобрений на планируемую урожайность с использованием различных методов. Рассматриваются три группы способов расчета доз удобрений под планируемую урожайность: нормативные балансовые и статистические. Ключевые слова: нормативы затрат удобрений вынос элементов коэффициент использования запасы потери газообразные вымывание прибавка урожая балансовые коэффициенты нормативы расхода поступление. Нормативный метод расчета доз удобрений на планируемую урожайность.
26265. Выбор культуры и сорта 1.09 MB
  Менее требовательны к плодородию почвы культуры отличающиеся хорошо развитой корневой системой или повышенной усвояющей способностью корней рожь сорго овес нут чина пелюшка люпин желтый и синий сераделла гречиха и др. Легкие песчаные и супесчаные удобренные почвы можно использовать для возделывания озимой ржи овса песчаного сорго картофеля турнепса арбуза дыни сераделлы эспарцета песчаного люцерны желтой и житняка. Среднесуглинистые почвы больше подходят для овса проса сорго гречихи ячменя подсолнечника сои фасоли...
26266. Задачи и принципы построения агроэкологической оценки земель 30 KB
  Лекция: Задачи и принципы построения агроэкологической оценки земель Цели и задачи. Обосновать построение системы агроэкологической оценки земель исходя из агроэкологических требований сельскохозяйственных культур адаптивных технологий их возделывания для проектирования адаптивноландшафтных систем земледелия. Обосновать необходимость совершенствования системы агроэкологической оценки земель с позиций новых требований экологизации земледелия. Ключевые слова: адаптивноландшафтное земледелие агропроизводственная группировка почв...