Ковалёва Татьяна Валериевна

Тема магистерской работы: "Исследования алгоритмов определения блокировок в распределенных системах"    

Научный руководитель: Александр Иванович Андрюхин

::Биография::
::Диссертация::
::Библиотека::
::Ссылки::
::Отчет о поиске::
::Индивидуальное задание::

Автореферат магистреской работы


Актуальность проблемы

При параллельном исполнении процессов могут возникать такие ситуации, при которых два и более процесса всё время находятся в состоянии блокировки. О таких процессах говорят, что они находятся в состоянии взаимной блокировки, тупика, дедлока (deadlock) или клинча (clinch) (смертельного объятия — deadly embrace). С проблемой тупиков тесно связана проблема бесконечного откладывания, когда процесс, даже не находящийся в состоянии тупика, ожидает события, которое может никогда не произойти из-за необъективных" принципов, заложенных в системе планирования ресурсов [1-3].

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

Обзор имеющихся исследований

В распределенных базах данных возможны запросы различного вида. К примеру, транзакции могут требовать комбинации ресурса A и (AND) ресурса B или(OR) ресурса C. В [2] рассматриваются модели запросов AND, OR, AND-OR, C(n,k). В модели AND транзакция разрешена при наличии набора свободных ресурсов и она блокирована до тех пор, пока не доступны все ресурсы, которые ею запрошены. В OR-модели запрос множества ресурсов считается удовлетворенным, если гарантирован доступ к какому-либо ресурсу множества (так при требовании чтения множества копий данных нам достаточно возможности чтения какой-либо копии). Модели вида AND-OR, C(n,k) являются расширениями двух предыдущих моделей AND и OR. В наиболее общей модели C(n,k) (в [2] обозначается как (n k) транзакция разрешена при условии получения любых k ресурсов из набора ресурсов размерности n. Ясно, что запросы вида AND (OR) для n ресурсов описываются моделью C(n,n) (C(n,1)) соответственно.
Согласно принятой классификации алгоритмы определения и разрешения deadlock можно условно разделить на три группы: алгоритмы централизованного, распределенного и иерархического управления [2-4].
Для централизованных алгоритмов необходим глобальный граф ожиданий всей сети, что является практически невозможным в настоящее время ввиду размерностей реальных сетей. Имеются проблемы для такого подхода, как большая нагрузка на центр обработки собираемой информации по определению циклов в глобальном графе, большая вероятность определения фальшивой deadlock-ситуации и др. Представителями централизованных алгоритмов являются однофазный и двуфазный Ho-Ramamoorhy-алгоритмы [5].
Поле распределенных алгоритмы ввиду их практической значимости наиболее исследуемо и нем выделяют четыре типа [2-4].

  • Алгоритмы проталкивания пути (Path-pushing), в которых передается информация о необходимом пути продвижения от узлов ожидания к блокированным узлам. Представителями этого типа являются Obermarck's алгоритм [6], Menasce-Muntz-алгоритм [7], Badal-алгоритм [8].
  • Алгоритмы прогонки (Edge-chasing), в которых определение циклов инициируется узлом, который не может выполнять операции из-за блокировки своих действий и который генерирует пробные сообщения. Эти сообщения изменяют характеристики заблокированных узлов при своем продвижении. Представителями этого типа являются Mitchell-Meritt-алгоритм [9], Chandy-Misra-Haas-алгоритм (AND-модель) [10].
  • Диффузионные алгоритмы, в которых инициация диффузионных вычислений определения циклов выполняются незаблокированными процессами и используются более сложные модели deadlock, нежели в алгоритмах прогонки. Представителями этого типа являются Chandy-Misra-Haas алгоритм (OR-модель) [10], Hermann-Chandy-алгоритм [11].
  • .Алгоритмы определения глобального состояния распределенной сети. В них выполняется попытка получения дампа глобального WFG. Представителями этого типа являются Kshemkalyani-Singhal-алгоритм [12], Bracha-Toueg-алгоритм [13].
Рассмотрим кратко наиболее известные распределенные алгоритмы, в частности Chandy-Misra-Haas-алгоритм, который оперирует с сообщениями специального вида, называемыми зондами (probe). Они представляют собой тройки целых чисел (I,J,K) [10]. Здесь I — номер процесса, который инициировал определение deadlock и зонд передается со страницы J на страницу K. Зондовые сообщения передаются по ребрам глобального графа ожиданий и deadlock обнаруживается, когда зондовое сообщение возвращается к инициирующему его процессу.
Для представителя иерархических алгоритмов Ho-Ramamoorhy-алгоритма [5] процессы группируются в независимые кластеры. Периодически определяется центральный контрольный кластер, который динамически выбирает управляющий центр для каждого кластера.

Основными проблемами для предлагаемых алгоритмов определения и разрешения deadlock являются определение их корректности;

  • высокая эффективность определения deadlock;
  • высокая эффективность разрешения deadlock;
  • фальшивые deadlock-ситуации.

Для корректности алгоритма определения и разрешения блокировок, необходимо, чтобы он удовлетворял двум критериям:
  • алгоритм должен определять все существующие deadlock-ситуации за конечное время;
  • алгоритм не должен генерировать сообщения о несуществующих deadlock-ситуации.

Теоретическая основа

Необходимой теоретической моделью при анализе блокировок в распределенных системах является направленный граф распределения (ожидания) ресурсов — WFG, вершинами которого являются процессы и ресурсы, а ребра графа определяют запрос конкретным процессом определенного ресурса. Заметим, что в литературе по распределенным базам данных он именуется графом ожидания транзакций (TWG), где транзакция понимается как последовательность запросов, выполняющих чтение или запись объектов данных.

Ясно, что если в графе существуеториентированный цикл, в котором за ребром захвата ресурса следует ребро запроса ресурса, то система находится в deadlock-состоянии.

Далее представлены примеры различных типов тупиков, которые могут возникнуть с повторно используемыми (SR) и потребляемыми (CR) ресурсами. Цель заключается в том, чтобы проиллюстрировать разнообразие ситуаций, в которых возможны тупики, и обосновать формальную модель.

1. Разделение ресурса

Рисунок 1.1 — Простой пример тупика

Процессы р1 и p2 могут достичь меток r1 и r2 соответственно в одно и то же время, например, строго последовательно pi сначала получает T, затем p1 получает D, затем pi доходит до r1, и, наконец, р2 достигает r2. Сразу же после этого момента два наших процесса войдут в тупик. Процесс p1 будет блокироваться по Т, сохраняя за собой D, тогда как р2 блокируется по D, сохраняя Т; p1 не может продолжаться, если не продолжается p2, и наоборот. Эта тупиковая ситуация графически показана на рисунке 1.1. квадратами обозначены ресурсы, а кружки представляют процессы. Стрелка (направленная дуга) от ресурса к процессу указывает на распределение, тогда как стрелка от процесса к ресурсу есть запрос. Подставьте D для R1 и Т для R2 (следует заметить, что этот пример был бы даже более реалистичным, если бы Т был другим файлом данных; р1 и р2 тогда запрашивают одна и те же файлы данных, но в обратном порядке).

Рисунок 1.2 — Разделение единственного ресурса

Единственный ресурс R типа SR, такой, как основная или вспомогательная память, содержит m единиц, достаточных для распределения, и разделяется n процессами р1, ..., рn, 2 <= m <= n. Пусть каждый процесс использует элементы ресурса R в последовательности

Requesl(R);Request(R);
Release(R); Release(R)

где каждая из операций Request и Release действуют на единицу ресурса R. Когда распределены все единицы ресурса может легко возникнуть тупик; все процессы, держащие по единице ресурса R могут навсегда заблокироваться на второй операции Request, тогда как некоторые процессы могут аналогично заблокироваться на первой операции Request. Такое состояние системы показано на рис. 1.2для случая n = 3 и m = 2. Это относительно общий тип тупика. Он может возникнуть, например, в подсистеме спулинга, в которой несколько вводных и выводных процессов конкурируют за получение пространства вспомогательной памяти; если пространство становится полностью распределенным (а) входным файлам заданий, ожидающих загрузки, и (b) выходным записям частично выполненных заданий, то система попадает в тупик.

2. Ресурсы типа SR и CR

Вычислительный процесс рс сообщается с процессом ввода-вывода pi0 Предположим, что время развития рс обратно пропорционально размеру пространства памяти, которое он может приобретать динамически; например, рс может быть задачей обработки сложного списка. Следовательно, рс запрашивает у системы, например, с помощью операции Request(M, all) все доступные блоки памяти. А процесс ввода-вывода время от времени требует для целей буферизации один блок памяти, который он запрашивает посредством операции Request(M). Эти два процесса рс и рi0 могут быть синхронизированы следующим образом:

рсRequest(M, all); pi0: Request(IOrequest);
Release(IOrequest);
rc: Request(IOcompletion); rio: Request(M);
Release(M,all);
Release(IOcompletion);

Рисунок 2.1 — Синхронизация процессов

Эти два процесса будут всегда попадать в тупик при выполнении операции Request с метками rс и rio. Вычислительный процесс pc не может получить сигнал „завершение ввода-вывода" до тех пор, пока pio не получит свой буфер, а система не может выделить память по запросу от рio, пока рс не получит уведомление „завершение ввода-вывода" и не освободит память М.

3. Обмен сообщениями

Пусть процесс p1 вырабатывает сообщения S1, p2 вырабатывает сообщения S2 и р3 вырабатывает сообщения S3; S1, S2 и S3 — это ресурсы типа CR. Предположим, что p1 получает сообщения от р3, р2 от p1 и р3 от р2. Если связь с помощью этих сообщений со стороны каждого процесса устанавливается в
следующем порядке:
PC. ... Release(Si); Request(Sj); ...
(где для i=1,2,3 j= 3, 1, 2 соответственно), то никаких трудностей не возникает. Однако перестановка этих двух операций вызывает тупик. Дання ситуация представлена на рисунке 3.1:
p2: ... Requesl(S3); Release(S1); ...
р2: ... Request(S1; Release(S2); ...
р3: ... Requesi(S2); Release(S3);...

Рисунок 3.1 — Результат перестановки двух операций

4. Полезный тупик

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

Как показано на примерах, проблема тупика предполагает взаимодействие потенциально многих процессов и ресурсов; поэтому она должна рассматриваться как глобальная системная проблема. Проблема тупика может быть разделена на три основные части:

  • Распознавание. Каким образом можно определить при данной системе процессов, разделяющих ресурсы и взаимодействующих друг с другом, вошло ли некоторое множество из них в тупик? Одним из ключей к решению этой п роблемы, полученной из рассмотрения первых пяти примеров, является существование в графах типа „процесс-ресурс" цикла (направленного пути от некоторой вершины к ней самой).
  • Восстановление. Каковы „наилучшие" способы выхода из тупика? „Чрезвычайные" системные меры необходимы, но нужно как можно меньше вторгаться в ход выполнения работ.
  • Предотвращение. Главный вопрос — как можно избежать тупика?

Теорма о тупике

Чтобы распознать состояние тупика, необходимо для каждого процесса определить, сможет ли он когда-либо снова развиваться (для процесса может существовать возможность выполнить операцию в некотором настоящем и будущем состоянии, но это не гарантирует нам, что процесс когда-нибудь действительно снова оживет; распределитель ресурсов или планировщик процессов может не допустить этого либо намеренно, либо случайно).
Так как мы рассматриваем возможность продвижения процесса, а не сам факт продвижения процесса, то достаточно изучить только самые „благоприятные" изменения oсостояния. Стратегия распознавания тупика состоит в моделировании наиболее благоприятного развития для каждого незаблокированного процесса при немультипрограммном (последовательном) режиме работы. Незаблокированный процесс приобретает любые ресурсы, в которых он нуждается, освобождает все свои ресурсы и затем „засыпает"; освобождение ресурсов может „разбудить" некоторые ранее заблокированные процессы. Это продолжается до тех пор, пока не останется незаблокированных процессов. Если oсуществуют некоторые заблокированные процессы при завершении этой последовательности действий, то начальное состояние S является состоянием тупика, а оставшиеся процессы находятся в тупике в S; в противном случае S не есть состояние тупика. Процесс P1 заблокирован, если он не способен выполнить ни одну из трех операций, определенных в последнем разделе. Это может возникнуть только тогда, когда р, выдал запросы, которые не могут быть удовлетворены за счет имеющихся ресурсов; т. е должен существовать по крайней мере один ресурс R1, такой, что Наиболее благоприятные действия для незаблокированного процесса pt могут быть представлены редукцией (сокращением) графа повторно используемых ресурсов:
  • Граф повторно используемых ресурсов сокращается процессом pi, который не является ни заблокированной, ни изолированной вершиной, с помощью удаления всех ребер, входящих в рi и выходящих из pi Эта процедура является эквивалентной приобретению процессом рi неких ресурсов, на которые он выдал ранее запросы, а затем освобождению всех его ресурсов; тогда PI становится изолированной вершиной.
  • Граф повторно используемых ресурсов несокращаем, если он не может быть сокращен ни одним процессом.
  • Граф повторно используемых ресурсов является полностью сокращаемым, если существует последовательность сокращений, которые устраняют все ребра графа.
Граф сокращений представлен на рисунке 4.1

Рисунок 4.1 — Граф сокращений


Граф в состоянии S полностью сокращаем.

Теорема:
Состояние S есть состояние тупика тогда и только тогда, тогда граф повторно используемых ресурсов в состоянии S не является полностью сокращаемым.

Доказательство:
Предположим, что S есть состояние тупика и процесс pi находится в тупике. Тогда для всех Т, таких, что S—>Т, pi заблокирован в Т. Так как сокращения графа идентичны для серии операций процессов, то конечное несокращаемое состояние в последовательности сокращений должно оставить процесс pi блокированным. Следовательно, граф не является полностью сокращаемым.
Предположим, что S не является полностью сокращаемым. Тогда существует процесс рi, который остается заблокированным при всех возможных последовательностях сокращений. Так как любая последовательность сокращений, оканчивающаяся несокращаемым состоянием, гарантирует, что все ресурсы типа SR, которые могут когда-либо стать доступными в действительности освобождены, то pi навсегда заблокирован и, следовательно, находится в тупике.

Подходы к разрешению проблемы тупиков

Невозможность процессов завершить начатую работу из-за возникновения взаимных блокировок снижает производительность ВС. Поэтому проблеме тупиков уделяется большое внимание. Для разрешения проблемы тупиковых ситуаций можно воспользоваться одной из следующих стратегий:
  • стратегией предотвращения (предупреждения) тупиков;
  • стратегией обхода тупиков;
  • стратегией распознавания (обнаружения) тупиков и последующего восстановления .

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

Цель средств обхода тупиков заключается в том, чтобы можно было предусматривать менее жесткие ограничения, чем в случае предотвращения тупиков, и тем самым обеспечить лучшее использование ресурсов. Методы обхода тупиков учитывают возможность их возникновения, однако в случае увеличения вероятности конкретной тупиковой ситуации здесь принимаются меры по аккуратному обходу тупика. Наиболее известным алгоритмом обхода тупиковых ситуаций является алгоритм банкира, предложенный Дейкстрой и осуществляющий контролируемое выделение ресурса. Каждый процесс предоставляет заранее анонс, т.е. верхнюю границу своих запросов на каждый ресурс, а алгоритм банкира позволяет избежать тупика, пересчитывая риск при каждом выделении ресурсов.

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

Заключение

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

Литература

  1. Т.Бройнль.Паралельне програмування.К."Вища школа, 1997, 358 с.
  2. E. Knapp. Deadlock detection in distributed databases.ACM Computing Surveys, 19(4):303-328, December 1987.
  3. M. Singhal. Deadlock detection in distributed systems.IEEE Computer, 22(11):37-48, November 1989.
  4. A. D. Kshemkalyani and M. Singhal. Distributed detection of generalized deadlocks. In Proc. of the 17th Intl.Conf. on Distributed Computing System, pages 553-560, 1997.
  5. Ho, G. S., and Ramamoorthy, C. V. Protocols for deadlock detection in distributed database systems. IEEE Trans. Softw. Eng. SE-1982.8, 6 (Nov.), 554-557.
  6. R. Obermarck. Distributed deadlock detection algorithm.ACM Trans. on Database Systems, 7(2):187-208, June 1982.
  7. D A. Menasce and R. R. Muntz. Locking and deadlock detection in distributed data bases. IEEE Trans.Software Eng., 5(3):195-202, May 1979.
  8. D. Z. Badal. The distributed deadlock detection algorithm.ACM Trans. Comp. Syst., 4(4):320-337, November 1986.
  9. K. M. Chandy, J. Misra, and L. M. Haas. Distributed deadlock detection. ACM Trans. Comp. Syst., 1(2):141-156, May 1983.
  10. Hermann, T., and Chandy, K. M. 1983. A distributed procedure to detect AND/OR deadlock. Tech. Rep. TR LCS-8301, Dept. of Computer Sciences, Univ. of Texas, Austin, Tex.
  11. Mitchell, D. P., and Merritt, M. J. 1984. A distributed algorithm for deadlock detection and resolution. In-Proceedings of the ACM Symposium on Principles of Distributed Computing. ACM, New York, pp. 282-284.
  12. G. Bracha and S. Toueg. Distributed deadlock detection.Distributed Computing, 2:127-138, 1987.
  13. M.Samadi. Survey of Deadlock Detection In Distributed Operating Systems. http://mehr.sharif.edu/~msamadi