Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Итак, мы видим, что проектирование интегральных схем служит источником многих геометрических задач, связанных с прямоугольниками, из числа которых были проиллюстрированы лишь некоторые важные задачи.
8.1. Некоторые приложения геометрии прямоугольников
397
8.1.2. Конфликтующие запросы к базам данных
Одна интересная геометрическая модель была разработана недавно для конфликтующих запросов к базе данных от нескольких пользователей [Yannakakis, Papadimitriou, Kung (1979)]. Обычно транзакция одного пользователя является последовательностью шагов, каждый из которых адресуется к одному элементу базы данных (переменной) и корректирует его. Такая корректировка переменной, однако, имеет определенную продолжительность. В течение этого промежутка времени необходимо предотвращать любые попытки других пользователей обращаться к этой же переменной. (Более конкретный пример: если запрашиваемой переменной является пассажирское место в авиалайнере, то очевидно, что для сохранения правильного учета все транзакции, использующие эту переменную, должны обрабатываться последовательно.) Весьма распространенным методом разрешения таких конфликтов является блокировка [Eswaran, Gray, Lorie, Traiger (1976)], когда пользователь «блокирует» переменную в начале корректировки и «деблокирует» в конце. Блокированная переменная недоступна другим пользователям.
Эту ситуацию можно промоделировать следующим образом. Работа каждого пользователя является последовательностью шагов типа «блокировка х», «корректировка х» и «деблоки-ровка х», где х — переменная. Если существует d пользователей, то каждому из них сопоставляем одну из осей d-мерного декартова пространства Еа и для каждой оси устанавливаем взаимно однозначное соответствие между шагами транзакции и точками с целочисленными координатами. При этом корректировке переменной соответствует интервал (интервал блокировки) на оси, который ограничен точками, соответствующими шагам блокировки и деблокировки. Поэтому, если k пользователей (k s?T d) обращаются к одной и той же переменной, то декартово произведение соответствующих интервалов блокировки образует ^-мерный прямоугольник. Для случая двух пользователей U\ и U2 эта ситуация проиллюстрирована на рис. 8.4(a). Состояние базы данных представимо точкой на координатной плоскости (U\, U2), фиксирующей историю работы каждого пользователя; например, точка с координатами (8,3) на рис. 8.4(a) обозначает, что шаги 8 и 3 пользователей соответственно И\ и U2 выполнялись одновременно. Ясно, что в системе транзакций с блокировкой точка состояния не может лежать внутри прямоугольника, связанного с переменной.
Как указывалось ранее, любой пользователь может обращаться к нескольким переменным. Каждый доступ к переменной х состоит из последовательности шагов «блокировка х»,
Гл. 8. Геометрия прямоугольников
Рис. 8.4. Моделирование базы данных с блокировкой транзакций, (а)—два пользователя, одна переменная; (Ь) —два пользователя, три переменные.
«корректировка х» и «деблокировка х»; последовательность шагов определенного пользователя (его работа) изображается посредством множества точек на соответствующей ему оси, как это показано на рис. 8.4(b) для случая двух пользователей.
Расписание иллюстрирует реальное изменение базы данных и складывается случайным образом путем объединения работ каждого из пользователей. Поскольку работа каждого является последовательностью шагов, то допустимое расписание изобра-
8.1. Некоторые приложения геометрии прямоугольников
399
жается монотонно неубывающей ступенчатой кривой на плоскости (U\,U2) рис. 8.4(b). Начальный участок такой кривой описывает частичное расписание.
'Последовательным называется такое расписание, при котором пользователи работают поочередно, т. е. пользователь получает доступ к базе данных и сохраняет его до конца своей работы. Очевидно, что для d пользователей существует d\ последовательных расписаний (а для двух пользователей будет ровно два таких, которые показаны на рис. 8.4(b)). Система работы с базой данных считается безопасной, если результат
Рис. 8.5. Иллюстрация ЮЗ-замыкания для объединения прямоугольников. Любое расписание, исключающее эту область, будет свободным от тупиков.
работы по любому законному расписанию (т. е. расписанию, обходящему прямоугольники) совпадает с результатом работы по последовательному расписанию. Это условие можно выразить в чисто геометрических терминах [Yannakakis, Papadi-mitriou, Kung (1979)], если потребовать, чтобы любое безопасное расписание было гомотопно (т. е. преобразуемо непрерывной деформацией, избегающей прямоугольники) последовательному расписанию.
С другой стороны, такая система может достигнуть условия безвыходности (тупика), в котором она будет пребывать неопределенное время без постороннего вмешательства. Эта ситуация представлена, например, частичным расписанием с, показанным на рис. 8.4(b) и состоящим из последовательности шагов 5г1, 5ц, S22, S12, 5гз- Шаг 5i2 (блокировка х\) не может выполниться, поскольку х\ уже блокирована (на шаге 52i); поэтому 5]2 должен ожидать, а управление передается пользователю U2, которому нужно выполнить шаг 52з (блокировку х2). Но х2 уже заблокирована (на шаге 5ц), поэтому никакая дальнейшая работа невозможна, ибо оба пользователя пытаются проделать невыполнимые шаги.
