автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы и модели проектирования параллельных СУБД

На правах рукописи

САМАРЕВ Роман Станиславович

Методы и модели проектирования параллельных СУБД

Специальность 05.13.11 - Математическое и программное

обеспечение вычислительных

машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

□ОЗОбВ107

Москва - 2007

003066107

Работа выполнена на кафедре «Компьютерные системы и сети» (1АУ-6) факультета «Информатика и системы управления» (ИУ) Государственного образовательного учреждения высшего профессионального образования «Московский государственный технический университет имени Н.Э. Баумана» (МГТУ

им. Н.Э. Баумана).

Научный руководитель: доктор технических наук, профессор

Сюзев Владимир Васильевич

Официальные оппоненты: доктор технических наук, профессор

Кузнецов Сергей Дмитриевич

канд.техн. наук Короткое Сергей Викторович

Ведущая организация: ЗАО «Концерн ВНИИНС»

(Всероссийский научно-исследовательский

институт автоматизации управления в непромышленной сфере)

Защита состоится «18» октября 2007 г. в 16 часов 00 минут на заседании диссертационного совета Д 212 141.10 по защите диссертаций при Московском Государственном Техническом Университете имени Н.Э. Баумана по адресу: 107005, г. Москва, 2-я Бауманская ул., д. 5.

С диссертацией можно ознакомиться в библиотеке МГТУ им. Н.Э. Баумана.

Отзыв на автореферат в одном экземпляре, заверенный печатью, просим направлять а адрес совета университета

Автореферат разослан Ученый секретарь

диссертационного совета С Р. Иванов

кандедат технических наук, до цен г ¿/%>€'

Общая характеристика работы

Актуальность проблемы Интенсивное развитие вычислительной техники в последние годы, привело к массовому использованию недорогих многопроцессорных высокопроизводительных вычислительных систем (ВС) архитектуры х86 Тем не менее, применяемые унаследованные (ранее разработанные) СУБД, часто не используют предоставляемые ресурсы ВС, т к не рассчитаны на параллельное выполнение одиночных запросов В итоге, при малой плотности запросов, СУБД использует лишь минимально необходимое количество ресурсов ВС, так что, в конечном счете, добавление новых процессоров или параллельных дисковых накопителей не приводит к какому-либо улучшению ее характеристик Расчет на пиковую нагрузку СУБД приводит к тому, что в среднем ВС будет серьезно недогружена

Другой проблемой использования СУБД является то, что монопольное использование ВС не всегда возможно Часто на ВС, на которой работает СУБД, работают и другие программы, также требующие значительных ресурсов При малой плотности запросов к СУБД, влияние других программ может быть незначительным, однако, например в случае использования СУБД в сочетании с Web-сервером, вполне возможна ситуация полной загрузки ВС Операционная система, типа MS Windows на ВС с вытесняющей многозадачностью, не способна оптимально разрешить ситуацию одновременного использования ресурсов ВС, типа ЦП, ОЗУ или НЖМД при большом количестве одновременно работающих процессов/потоков Т е линейное увеличение количества параллельных процессов приводит к нелинейному снижению производительности системы в целом, поскольку доля служебных операций по переключению потоков, вытеснению памяти, позиционированию головок НЖМД на нужный сектор занимает значительное время

В настоящее время широко распространены параллельные СУБД для вычислительных систем без общей памяти, однако, массовое использование архитектуры х86 не позволяет использовать такие параллельные СУБД без изменений Кластер, построенный путем объединения отдельных х86-систем, можно рассматривать как единую систему, с несколькими независимыми узлами, не имеющими общей памяти, но каждый узел может быть многопроцессорным, однако в этом случае его возможности не используются в полной мере

Итак, оптимальной СУБД с точки зрения производительности и времени отклика будет СУБД, реализующая внутризапросный параллелизм, причем доступные в данный момент времени ресурсы ВС используются максимально, но с учетом того, что превышение некоторого предела загрузки ВС приведет к релейному падению производительности системы в целом

Актуальность темы данной работы обусловлена тем, что, несмотря на наличие большого количества работ в области параллельных баз данных, они, в основном, ориентированы на использование специализированных ВС (Соколинский Л Б, DeWitt D, Graefe G) Отличием данной работы является то, что объектом исследования является объектная система управления базами данных (ОСУБД), предназначенная для работы на ВС с общими ресурсами с архитектурой х86, для которой обеспечивается внутризапросный параллелизм в условиях не монопольного использования ресурсов ВС

Цели и основные задачи работы Целью работы является разработка методов и моделей проектирования параллельных СУБД и их приложений с задан-

ными характеристиками, а также оценка предельных характеристик СУБД и приложений Для достижения поставленной цели решаются следующие задачи

1 Анализ параллельных архитектур СУБД и методов повышения эффективности использования системных ресурсов Выбор критериев производительности СУБД

2 Разработка алгебраической модели параллельной ОСУБД Метод оценки характеристик производительности систем на основе СУБД

3 Моделирование и исследование свойств модели

4 Разработка параллелизатора запросов для асинхронного выполнения микроопераций в СУБД

5 Разработка метода измерения производительности систем на основе СУБД

6 Создание инженерных методик реорганизации СУБД в соответствии с заданными характеристиками с использованием предложенных моделей Исследование характеристик производительности систем на основе СУБД с использованием этих методик Реализация методик для улучшения характеристик сервера ОСУБД

Методы исследований Примененные в работе модели используют классический теоретико-множественный аппарат, теорию вероятностей, СМО, методы математической статистики и стохастические алгебры процессов Вычислительный эксперимент проводился при помощи модифицированного автором средства решения моделей "PEPA" (англ) - PEPAWorkbench, а также с использованием системы математического моделирования MATLAB

Эксперименты проводились на реальных базах документов, полученных в результате эксплуатации информационно-поисковой системы (ИПС), в частности, накоплена база новостных сообщений в ИПС «Обзор СМИ», эксплуатируемой в Управлении информационного и документального обеспечения Аппарата Совета Федерации Федерального Собрания Российской Федерации

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

Разработана комплексная модель сервера объектной системы управления базами данных ODB-Jupiter, а также модели отдельных подсистем с использованием алгебраического подхода

Разработан метод параллельного выполнения внутренних операций сервера БД с учетом доступных ресурсов ВС на момент начала обработки Реализован программный модуль унифицированного параллельного выполнения операций

Практическая ценность и реализация результатов

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

ние релейной деградации производительности ВС в целом Модуль параллелиза-тора встроен в сервер ИПС «Обзор СМИ», применяемой в Совете Федерации РФ в качестве центрального модуля распределения рабочей загрузки сервера СУБД Также, параллелизатор встроен в систему резервного копирования и восстановления информации, используемой в ФГУП «Концерн Системпром» Разработана обобщенная методика реорганизации СУБД с последовательной обработкой в СУБД с параллельной не конвейерной обработкой, что позволяет существенно улучшить эксплуатационные характеристики унаследованных СУБД

Апробация работы

Содержание отдельных разделов и диссертации в целом было доложено

- На заседаниях аттестационной комиссии при ежегодной аттестации аспирантов кафедры «Компьютерные системы и сети» МГТУ им Баумана

- На семинарах и заседаниях кафедры «Компьютерные системы и сети» МГТУ им Баумана

- На межвузовской юбилейной научно-технической конференции аспирантов и студентов «Современные информационные технологии» 15 ноября 2000 г

- На конференции «Корпоративные базы данных 2003» 17 апреля 2003 г

- На семинаре московской секции ACM SIGMOD 25 января 2007 г

Публикации

Основные результаты работы опубликованы в 9 печатных работах

Личный вклад автора

Все основные научные результаты, методика оценки характеристик производительности ИС на основе СУБД, алгебраические модели СУБД и отдельных подсистем, метод параллельного выполнения операций, разработанные на их основе алгоритмы и программные средства, экспериментальные исследования, приведенные в диссертации, получены автором лично

Содержание работы

Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы Общий объем диссертации 253 страницы, включая 53 рисунка, список литературы и приложения Библиография включает 140 наименование, из них 71 из иностранных источников

В разделе «Введение» обосновывается актуальность темы диссертации, рассматривается место задач моделирования и проектирования СУБД и их приложений в современных информационных технологиях, дается краткая характеристика таких задач Формулируется цель работы и её связь с другими аспектами информационных систем Кроме того, обосновывается необходимость использования схемы выполнения запросов СУБД с внутренним параллельным расщеплением процесса обработки

В настоящее время посредством математического моделирования СУБД принято решать следующие задачи

1 Подбор методов индексации данных по используемым типам данных, понимая под типами в том числе и сложные типы пользователей, а также оптимизация схемы данных для ускорения работы приложений СУБД

2 По известному набору операций и их прогнозируемой плотности в ИС, определение загрузки функциональных модулей СУБД, реализуемость выполнения в конкретных условиях на конкретной СУБД, а также характеристики производительности ИС в целом

3 По известной архитектуре ВС и структуре СУБД подбор необходимого оборудования для выполнения требований конкретной ИС

Как показало исследование, в общем случае, задача подбора оборудования является сложно реализуемой по причине отсутствия единообразного подхода для оценки характеристик оборудования различных производителей Задача подбора методов индексации актуальна в СУБД, предоставляющих достаточные средства для их реализации Таким образом, наиболее актуальной задачей является вторая задача

В главе «Анализ существующих методов построения параллельных СУБД и ИС на их основе, анализ методов моделирования» рассматриваются общие аспекты построения СУБД, необходимые для решения вопроса оценки производительности, методы формализации данных и операций в СУБД

Создание СУБД предполагает не только разработку функциональных модулей, как таковых, но и формальное математическое описание модели хранения данных и манипулирования с ними В работе отмечены реляционная модель данных Кода, ее развитие К Дейтом и объектная модель Близко связанными с моделями хранения являются формальные методы манипулирования данными и языки запросов, построенные на основе этих методов Использование формальных методов описания операций позволяет на их основе строить математические модели баз данных (БД) Наиболее широко применяются алгебраические методы описания операций Среди них можно выделить работы Е Ф Кодда по реляционной алгебре, её современную формализацию Е M Бениаминовым в виде многосортной алгебры, К Бири по формальному описанию БД объектно-ориентированных СУБД средствами многосортной алгебры, работы с использованием других алгебраических методов, такие как HERM-алгебра, основанная на машине абстрактных состояний Ю Гуревича в работах Б Талхайма (Bernhard Thalheim) При некоторой модификации также применимы методы императивной спецификации динамических систем AB Замулина Использование алгебраических подходов позволяет провести формальное описание логического плана выполнения запроса (уровень языка запроса), его трансляцию в физический план выполнения (уровень внутренней обработки запросов) и, как следствие, иметь возможность проведения анализа его оптимизации и выполнения по микрооперациям физического плана

В работе рассматривается классификация M Стоунбрейкера для многопроцессорных вычислительных комплексов (МВК) и расширение Л Б Соколинского

В СУБД различаются методы хранения данных на внешних накопителях Так, выделяют метод прямого хранения данных (и модификации), часто применяемый в объектных СУБД, метод нормализованного хранения данных (и модификации), характерный для реляционных СУБД

Существенными моментами функционирования СУБД являются методы работы с транзакциями и методы выполнения блокировок данных В настоящее время производители СУБД используют различные методы, в зависимости от целевой области применения СУБД Рассматриваются модель транзакций в соответствии с требованиями ODMG 3 0 и расширенный вариант на примере ОСУБД Versant, реализующую модель длинных транзакций, позволяющих выполнять распределенную изолированную обработку данных

Для эффективного использования ресурсов МВК необходимо, чтобы СУБД реализовывала алгоритмы параллельной обработки в соответствие с особенностями их архитектуры Рассматривается классификация методов параллельного выполнения запросов различного уровня обработки

Существенным аспектом при проектировании СУБД является то, каким образом происходит взаимодействие клиентов и серверов СУБД Рассматривается базовая классификация клиент-серверного взаимодействия, а также расширения этой классификации применительно к объектным СУБД

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

Среди методов моделирования производительности ИС в целом и серверов СУБД в частности, можно выделить

1 Модели, основанные на коммуникации клиентов и серверов данных Чаще всего строятся и анализируются средствами СМО Данный класс моделей позволяет оценить производительность ИС в предположении, что поток запросов клиентов однороден, кроме того возможна оценка времени их выполнения в среднем Модели позволяют оценить использование различных каналов связи, методов кэширования данных, однако столь высокий уровень абстракции не позволяет получить оценку влияния внутренних особенностей обработки запросов сервером СУБД

2 Модели хранения данных на ВЗУ, что позволяет оценить минимальное время доступа к данным и производительность ИС в целом В зависимости от назначения модели, могут учитываться как физические характеристики накопителей данных, такие как время позиционирования головок НЖМД, скорость считывания и схема разметки дисков или только методы размещения данных на них В настоящее время, модели с использованием внутренних характеристик НЖМД мало применимы, поскольку большинство таких характеристик накопителей от разных производителей не является адекватно сравнимыми

3 Модели имитационного представления внутренней обработки данных описывают сервер СУБД с позиции последовательности обработки запросов Могут учитывать транзакционную обработку, разнородность запросов и, как следствие, различные методы их выполнения Данный класс моделей может быть реализован любыми математическими средствами

4 Методы, на основе моделей запросов к СУБД применимы в том случае, если проводится анализ характеристик ИС в целом, а не отдельного сервера БД или тракта клиент-сервер Выделяются методы, основанные на аналитическом описании процесса обработки запросов эмпирическими формулами, исходя из априорного предположения об однотипности функционирования коммерческих СУБД и, как следствие, на однотипности выполняемого набора операций проекции, слияния и выборки данных К этому же классу методов относятся работы, в где проводится анализ исходных запросов в алгебраической форме, анализ способов их преобразования в физический план конкретной СУБД и выполнение, при помощи модели, имитирующей внутреннюю обработку запросов конкретной СУБД Эти модели могут быть реализованы как традиционными средствами СМО, так и в форме алгебр процессов

5 Условно в отдельную группу можно выделить модели, в которых проводится анализ производительности сервера СУБД на основе имеющихся сведений о порядке обработки данных в транзакции применительно к конкретной ИС В печатных источниках выявлены модели, в которых анализ производительности проводится в зависимости от количества элементов данных внутри транзакции, так и модели блокировки данных применительно к транзакциям OLTP систем Приводится краткий обзор некоторых инструментальных средств моделирования, реализующих перечисленные модели

В результате проведенных исследований можно заключить, что методы, ориентированные на моделирование характеристик отдельных подсистем или сервера СУБД в целом, не позволяют достоверно оценивать поведение ИС на основе СУБД, поскольку не учитывают взаимного влияния выполняемых запросов (в интерпретации не элементарных операций, а последовательности некоторых действий) различных пользователей Для получения достоверных характеристик ИС в целом необходимо проводить анализ логических и физических планов выполнения запросов, а также учитывать особенности выполнения микроопераций физического плана сервером СУБД

Полная модель ИС на основе СУБД, таким образом, включает в себя следующие частные модели

- Модель взаимодействия клиента и сервера СУБД, включая многозвенные клиент-серверные архитектуры,

- Модель преобразователя исходных запросов в логический план выполнения по схеме данных,

- Модель оптимизатора логического плана,

- Модель планировщика физического плана выполнения,

- Модели функциональных обработчиков запросов

В качестве математического метода моделирования целесообразно использовать алгебраические методы В данной работе основным методом выбрана алгебра процессов "PEPA" (Performance Evaluation Process Algebra), позволяющая выполнять моделирование параллельных систем, имеющих определенные точки синхронизации, использующая формальный метод описания модели

Алгебра процессов "PEPA" является удобным средством моделирования взаимодействующих процессов Тем не менее, она имеет ряд ограничений, затрудняющих ее использование В числе таких ограничений можно назвать отсутствие возможности анализа каждого процесса алгебры в отдельности, что не позволяет строго определить время выполнения того или иного процесса, производительность того или иного процесса в случае, если несколько разных процессов содержат в себе одинаковые типы действий Следует также отметить то, что, предоставляя структурное описание процессов, алгебра "PEPA" потенциально может быть использована для введения в модель дополнительных данных

В главе рассмотрен объект исследования работы - объектная СУБД ODB-Jupiter и информационно-поисковая система (ИПС) «Обзор СМИ», применительно к которой рассматриваются схема данных и схема обработки запросов, набор выполняемых операций, метод формирования индексных данных ОСУБД ODB-Jupiter является специализированной документально-ориентированной объектной СУБД для работы в составе ИПС В дальнейшем, с использованием ИПС, на основе данной СУБД, проводится анализ и моделирование характеристик ИПС и СУБД, а также реорганизация СУБД для улучшения характеристик производительности

В главе «Разработка метода моделирования производительности ИС. использующей СУБД» на основе ранее выбранной алгебры процессов "PEPA" реализован метод моделирования производительности ИС

Формальный синтаксис алгебры "PEPA" с квазиоперацией VMQ и расширенным комбинатором кооперации может быть представлен в форме Бэкуса-Наура следующим образом

Рфашс = {а,г).Р | Р + Q, CstaHc = VMk¿P)><VMk¿Q)\P!L Основные языковые конструкции

Префикс компонент (а,г) Р выполняет действие с типом а и интенсивностью г Компонент (а,г) Р впоследствии становится компонентом Р Действие определяется как а = (а,г)

Выбор компонент P+Q представляет систему, которая может вести себя как компонент Р или компонент Q Компонент P+Q разрешает все текущие действия Р и Q, т е Act(P + Q) = Act(P) U Act(Q)

Кооперация VMkl(P)><VMkl(Q) называется совместное действие для компонентов Р и Q на множестве кооперации LoA Таким образом, возможна блокировка, при которой один компонент будет ожидать другой Если 1=0, то компоненты Р и Q выполняются параллельно VMk1 и VMk2 есть квазиоперации, не вводимые в аксиоматику алгебры, ассоциирующие виртуальные ВС, на которых выполняются процессы с их статически комбинируемыми описаниями Р и Q

Скрытие компонент P/L ведет себя как компонент Р, за исключением всех действий, имеющих тип, входящих во множество L Действия, типы которых попадают во множество L, объединяются в единое действие с неизвестным типом т, и их длительности объединяются Кроме того, эти действия не могут объединяться с другим компонентом операцией кооперации

В отличие от базовой интерпретации уравнения системы, в которой процессы неразличимы, в данной работе уравнение системы Sys есть функция кооперации по множеству динамических компонентов Р, каждый из которых представляет собой процесс Sys = fc.J{P,,P2 Р,,})

Процесс есть последовательность компонентов Pk ={C¡k С,*}, где С,' - элементарный компонент процесса г, определяющий действия для перехода к следующему компоненту, причем С* sds(Pk), где ds(C) есть порождающее множество компонента С

Алгебра процессов "PEPA" не имеет непосредственного метода решения Процесс решения разбивается на два этапа - генерация замкнутой марковской цепи с постоянными параметрами и ее решение традиционными для марковских цепей методами Главным определяемым параметром "PEPA" является вероятность состояний марковской цепи (эквивалентных компонентам "PEPA") в установившемся режиме Остальные параметры модели определяются с помощью полученной марковской цепи с использованием т н метода стоимостных структур и соответствующей интерпретацией полученных значений

В работе предлагается сохранять на момент генерации замкнутой марковской цепи информацию о позиции процесса в уравнении системы, в рамках которого выполняется действие, вызывающее переход к другому состоянию, что не делается в базовом варианте "PEPA" Таким образом, интенсивность перехода q(C,,Cj) между компонентами алгебраической модели С, и С, (эквивалентными со-

стояниями марковской цепи) определяется как <?(С,,С,) = X . где С,к и С/

h aeAct(C? |С* )

есть компоненты, соответствующие к-му процессу Форма q(C,,Cj) соответствует принятой в "РЕРА" форме, в то время как q(C,k,C,k) является ее расширением

Элементы q(C,,Cj) представляют собой недиагональные элементы инфини-тезимальной образующей матрицы Q марковского процесса Диагональные элементы вычисляются как сумма недиагональных элементов каждой строки, взятая с обратным знаком Решением является решение матричного уравнения П Q=0, где П - матрица стационарных вероятностей состояний Дополнительным нормирующим условием является ¿П(С,)=1

Базовый метод анализа производительности в алгебре процессов "РЕРА" основан на методе стоимостных структур (reward structures) Однако данный метод не обладает достаточной семантикой, поскольку стоимость назначается для определенных состояний, определяемыми неформализованными критериями В методе стоимостных структур каждому переходу между состояниями назначают определенный вес Каждый переход ассоциирован с конкретным действием из исходной модели Суммарная стоимость r, = ^р.ГКС,), где десть стоимость, соответствующая компоненту С,, а П(С,) есть стационарная вероятность нахождения системы в состоянии, соответствующего компоненту С, Следует заметить, что вектор р в общем случае может содержать произвольные числа, в соответствие с семантикой оцениваемой марковской цепи Расширение информации исходной модели в промежуточной марковской цепи позволило определить следующие характеристики производительности, использование которых в "РЕРА" затруднено из-за невозможности разделения характеристик различных процессов Производительность системы по типу действия Производительность системы по типу действия представляет собой число заявок, обрабатываемых данным типом действия Производительность процесса, таким образом, определяется как суммарный поток вероятности по некоторому типу действия а. Thr* , где к - индекс процесса Очевидно, общая производительность

(форма "РЕРА") по типу ее есть Thra =

к

Время отклика Актуально для определения в рамках одного процесса

уравнения системы Определяется как rk = —пг-Х!—~—■ гДе ' производи-

Thra у Та (Ч:У )

тельность по характеризующей деятельности k-го процесса, время вне обработки заявки Z = Y—-—*с е {*С ,„„,}, где компонент *CV обозначает динамический

У ГЛСу)

компонент конкретного процесса клиента

Абсолютная утилизация ресурса. Физический смысл данной величины -процент времени выполнения системой данного множества типов действий В процессе оптимизации системы позволяет явно обнаруживать узкие места Допустим, существует множество компонентов Сотра, которые имеют возможные переходы с действиями a, <= Act(C,),C, еСотра Тогда абсолютной утилизацией ресурса, соответствующего типу действия а, является V = ^ П(С, ),С, g Сотра

Uа = Thr¡¡n¡€ , где Na- число параллельных процессов в уравнении системы,

Относительная утилизация ресурса Под относительной утилизацией ресурса подразумевается эффективность использования конкретного типа действий в системе со статически комбинируемыми процессами, в частности, параллельной кооперации действий Те данная величина представляет собой меру эффективности параллельного использования типов действий (дисбаланс параллелизма) Для определения относительной утилизации определим понятие предельной производительности циклического процесса как = —Ц-, где Л, есть

интенсивности переходов между состояниями процесса с индексом к в уравнении системы при рассмотрении этого процесса как самостоятельную марковскую цепь При этом пассивные действия игнорируются

Относительная утилизация по типу действия a определяется как

Na 'Thra

выполняющих данный тип действия, a Thra- общая производительность по типу действия a

Традиционный способ наложения ограничений в моделях "PEPA" заключается во введении в модель дополнительных контролирующих процессов, объединяемых посредством комбинатора кооперации по некоторому общему ограничивающему набору типов действий При этом уже на этапе генерации марковской цепи отбрасываются состояния, в которые система не может перейти после наложения ограничения Однако данный метод требует изменение модели каждый раз, когда возникает необходимость изменения наложенных ограничений, что требует выполнения длительной операции генерации новой марковской цепи Кроме того, введение дополнительных процессов имеет существенный недостаток - усложнение модели, а также возможное увеличение количества состояний в виду возможного введения фиктивных промежуточных действий для кооперации с контролирующим процессом В ряде источников зафиксировано расширение алгебр процессов посредством добавления в дескриптор действия дополнительных параметров Однако, такой подход усложняет восприятие модели и управление параметрами Поэтому, в данной работе расширение производится не для конкретных действий, а для типа действия в целом

Естественным следствием анализа модели "PEPA" по каждому процессу является ассоциация каждого перехода марковской модели с набором действий, которые становятся активными в этот момент Поскольку в рамках марковской цепи, генерируемой по модели "PEPA", один переход между соседними состояниями может быть ассоциирован лишь с одним действием, другие процессы, комбинируемые в данном состоянии кооперацией, также имеют возможные переходы, ассоциированные со своими действиями

Множество возможных комбинаций активных действий в любом состоянии

системы с,2,2 c„¡ есть декартово произведение условных множеств актив-

ных действий по компонентам всех процессов системы

CAct({C,A,C,^ С0}) = Аа(С1А\/^({С,л,Сы% С,»х

хАсКС 1/м({Си>Сш С,»х С.»

В общем случае С,/}) = {ЯЛс1,,ЯЛс12 где КАаесть

элементарное множество действий по различным процессам уравнения системы

Кроме того, система описывается конечной матрицей доступных ресурсов и матрицами реакции на превышение ресурсов, соответственно

-RSU ■^2 1 V 2 1

SYSRS ~~ RS,2 RS2 2 2 и svs:x = 2 к'22 К 2 , где п - количество ти

^2,„ и Кп

пов ресурсов, т - количество виртуальных вычислительных систем, на которых происходит выполнение процессов, г = {1,2,3}

Каждый столбец матриц определяет предельный условный объем некоторых ресурсов виртуальной вычислительной системы I/Мк, на которой выполняется конечное множество процессов {Ргоск1, Ргоск2 Ргос^}

Действие характеризуется определенным типом и является неделимым, переводящим систему в другое состояние Различают активные и пассивные действия Каждый тип действия а, характеризуется параметром вектором потребле-

ния ресурсов acta =

Щ i i rs,, t,,

где rs,j есть величина потребления j-ro ресурса, t,it

есть среднее время, за которое происходит потребление ресурса j Нулевое значение t,j является признаком статического потребления ресурса, независимо от

. \t,, >0,(га,, Яа t ) времени, те функция потребления Use{acta)-j ( -o (rs ) Активные действия характеризуются коэффициентом активности га Пассивное действие может быть реализовано только в рамках кооперации с компонентом, описывающим активное поведение системы Пассивное действие не потребляет ресурсы

Таким образом, для любого перехода, переводящего систему Sys{Clm с,, с,> 8

соседнее состояние через действие а, множество потреблений ресурсов определяется как матричная сумма

Rsm = е RAct,RAct е CAct({Cu Са }),Рк е VMm, где к-

v к w

индекс процесса в уравнении системы, v - индекс множества Rs в множестве комбинаций переходов для состояния Sys{c^ с с >, w-индекс действия во множестве активных действий, m-индекс виртуальной машины

Критерий не превышения ресурса j Rs™ < SYS" Vv

1) Интенсивность активных действий в состоянии, вызвавшем максимальное пре-

Rsm

вышение ресурса; есть функция, Л'(А) = Я /(&), где А =

RS,

Для функции/(д) вида/(д) = /,(д)/2(д) Приняты/2(д) =

JRS,,^'

где к], =1 и /1(A) = l-F№,(^)(A-l) = exp(-fe, (A-l)f') = exp - fr,2,

¡VeibulHa fl)

Итоговая функция коррекции интенсивности имеет следующий вид

V

В главе рассмотрено применение конструкций алгебры "PEPA" для моделирования ИС Рассмотрены особенности применения "PEPA" как для элементарных структур типа очередей обработки, так и более сложные подсистемы, включая иерархический внутренний параллелизм, обеспечиваемый в реальных ИС разработанным в данной работе параллелизатором

Применительно к объекту исследования ОСУБД и ИПС на ее основе, разработаны модели различного уровня детализации и отдельных подсистем

В главе «Характеристики производительности СУБД с использованием адаптивного планировщика параллельных запросов» проводится разработка метода и его реализация в виде программного модуля, обеспечивающего асинхронное параллельное выполнение операций В отличие от других работ по организации параллельной обработки данных (Volcano - G Graefe, DBS3 - Mikal Ziane и др , Gamma - D DeWitt, Омега - Соколинский J1 Б , Цимблер МЛ), разработанный метод позволяет его использовать не только в рамках монопольного использования ресурсов ВС для решения задач СУБД, но и в составе комплекса программ, функционирующего на тех же ВС с учетом текущих ресурсов ВС Отличием разработанного метода организации параллелизма от традиционных подходов типа MPI, OpenMP, трС является наличие централизованного управления степенью параллелизма и возможность реакции на динамическое состояние ВС, посредством обратной связи через корректор параллелизатора

Предлагаемый метод параллельного выполнения запросов предполагает, что в рассматриваемой СУБД, поступающий запрос поступает через диспетчер запросов в функциональный модуль, обеспечивающий корректность выполнения запроса Микрооперации, из которых состоит физический план выполнения запроса, рассматриваются как самостоятельные операции, процессом выполнения которых необходимо управлять для достижения равномерной загрузки ВС Для организации параллельного выполнения запроса строится параллельный план с максимально возможной степенью параллелизма В данном методе предполагается соответствие типа выполняемой микрооперации группе потоков обработки, однако их активное количество может меняться в зависимости от текущего состояния ВС Кроме того, число входных и выходных параметров обработчиков зависит от типа операторов Используются операции постановки заявки на выполнение и ожидания результата выполнения конкретной микрооперации Это позволяет, имея линейный физический план выполнения запроса, построить параллельный план выполнения, выделив точки постановки на обработку и ожидания обработанных данных, который будет выполнен максимально параллельно с учетом текущей загрузки ВС и СУБД Отказ от конвейерной схемы обработки данных

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

Заявки и результаты обработки

Диспетчер

обращений —[

Модуль управления обработчиками

Очереди результатов по типам обработчиков

або-

!лекто| ы сообщен м

Очереди заявок по типам обработчиков

TZ

Обработчики типа 1 ■ I

I ^ГШП р»Гн"~1; 1

Фор лирова|ели рерульта-

р

Планировщик

Измеритель веса операции

Анализатор рекурсивного вызова

Модуль задержки

Анализатор состояния

% загрузки, длина входной очереди

Корректор

Таймер

Анализатор состояния ВС_

Весовой корректор

Анализатор

загрузки обработчиков

Функциональная схема асинхронного адаптивного параллелизатора

Программный модуль «параллелизатор» обеспечивает максимально возможное параллельное выполнение всех поступивших операций не конвейерного типа Решение о постановке операции (соответствующей ей заявки) принимается планировщиком Корректор обеспечивает контроль состояния ВС и внесения поправок в планировщик Выполнение обеспечивается обработчиками Формально определим параллелизатор

Параллелизатор Par = <Hnd, WW где Wsvs, wcur- векторы доступных

ресурсов и текущего состояния системы

Множество обработчиков Hnd={hnd}, где hndj=<{op}, ц>, где орел, а - множество типов операций (число каналов обработки для различных операций различно)

Текущее состояние j-ro обработчика st, = < пс, Nc, /,„, /„„,, L,„, L0„, >, где пс, Nc- число активных и доступных каналов обработки, /,„, l,„ - текущая и допустимая длины входной очереди, lout, Uut текущая и допустимая длины выходной очереди

Операция ор,=< {Q, {tcuj, wcpl >, где t,„, t0UteT - типы входных и выходных параметров, т— множество типов данных

Заявка q=<№, pr, paramsop,, wq>, где № - последовательный номер операции в системе, рг — приоритет заявки, params op, =< {paramm t„J, { paramout toui} > - множества значений входных и выходных параметров соответствующих типов

w =

rst

, W = » op 1 w2 w - t r'srs rs2

_rsN_ .WN. bsk_

где 1¥<:ш - вектор текущего состояния,

№ор, - вес операции, - вектор доступных ресурсов, гэ, - величина потребления ¡-го ресурса, N - число типов ресурсов, IV, - величина потребления ко ресурса, по-

лученная на основе априорных данных или в результате накопленных статистических данных во время работы системы, / - тип операции, RS, - Допустимая величина потребления j-ro ресурса, полученная на основе априорных данных или выполненного тестирования Частным случаем условия постановки заявки операции на выполнение является неравенство WsJrs > + WJp/ для всех ресурсов Рассмотрены и другие варианты планирования, однако до стадии реализации доведена именно эта схема

В работе проводится анализ доступных для измерения ресурсов ОС MS Windows счетчиков производительности, необходимых для работы корректора

В главе «Методики проектирования параллельных СУБД» приводятся разработанные методики проектирования параллельных СУБД в контексте реорганизации существующей последовательной СУБД

Разработана обобщенная методика реорганизации СУБД, включающая методику оценки характеристик производительности ИС на основе СУБД, в рамках которой проводится создание и параметризация моделей ИС и сервера СУБД, методику нагрузочного тестирования сервера ОСУБД в составе ИС, необходимую для получения параметров моделей и оценки характеристик производительности реальной ИС Также, методика учитывает создание и модификацию алгоритмов сервера БД для обеспечения параллельного обслуживания запросов

Методика нагрузочного тестирования сервера ОСУБД в составе ИС предполагает выбор метода измерения интервалов времени выполнения внутренних функций программы, создание замкнутого контура тестирования программа-клиент ИС - сервер СУБД - модуль нагрузочного тестирования, обеспечивающего нагрузку сервера СУБД в соответствии с реальными запросами клиентов ИС, выбор способа и измерение характеристик сервера СУБД, а также обработку полученных данных

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

Для решения задачи измерения производительности ИС в целом, разработан комплекс программ, позволяющих сформировать контур выполнения клиент ИС - сервер БД - контрольно управляющий модуль Особенностью данного комплекса тестирования является то, что на сервер БД поступает полноценный запрос, сформированный реальным приложением ИС Контрольно-управляющий модуль обеспечивает съем в реальном времени внутренних характеристик выполнения запросов с сервера БД и обеспечивает выдачу команд и анализ результатов полученных приложением ИС

Методика оценки характеристик производительности ИС на основе СУБД предполагает выявление требований к производительности ИС, выявление струк-

туры СУБД, модели данных, схемы данных, множеств последовательностей выполняемых операций В рамках данной методики производится создание необходимых моделей, их параметризация с использованием значений, полученных при применении предыдущей методики на реальной ИС, проводится модификация моделей в соответствие с будущими алгоритмами работы, проводится вычислительный эксперимент и оценка полученных значений

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

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

, з 1ой[1 + %иш (1 / козу (и) -1)1 вычислен как к , = —^-—озуч '—а, где время выполнения кода програм-

1°В(П)

мы распределяется между временем обмена с ОЗУ и временем работы ЦП Причем, доли выполнения связаны соотношением %сри =1-%шм, при условии пренебрежения потерей времени на остальных аппаратных подсистемах Учитывая, что коэффициент к\ в начальный момент может быть подобран эмпирически, это

позволяет оценить распределение долей времени работы ЦП и обмены ОЗУ на конкретной ВС Из приведенного выражения можно определить, что

-1

Пересчет долей времени выполнения выполняем по формуле

%"мш , о/

МРМ г С.

способности подсистем памяти существующей и новой системы, а ТНгсри и ТЬгсри иовая индексы производительности процессоров в соизмеримых величинах существующей и новой системы (Для процессоров одной серии для пересчета производительности применимы значения тактовых частот)

В работе приводится метод использования разработанного параллелизато-ра в тексте программ, а также пример его применения Модуль параллелизатора предназначен для использования в программах на С++ с использованием специальных классов-переходников, что позволяет использовать большинство компиляторов С++, в то время как использование специальных директив в методах типа ОрепМР требует специальные компиляторы Метод предполагает, что программист создает класс-потомок унифицированного класса сообщения, где добавляет необходимые обработчику входные и выходные параметры Классы обработчики реализуются на основе унифицированного класса посредством перекрытия метода выполнения Предусмотрена возможность присоединение модуля асинхронно-14

го корректора, универсальная реализация которого нецелесообразна, т к размерность весового вектора и алгоритм коррекции зависит от требований программы

Рассматривается применение методики нагрузочного тестирования сервера ОСУБД в составе ИС применительно к ИПС «Обзор СМИ»

Разработанные методики обеспечивают выполнение задачи реорганизации СУБД с последовательной схемой обработки запросов в СУБД с параллельной схемой обработки запросов, обеспечивают оценку характеристик производительности ИС в целом и отдельных подсистем сервера СУБД, а также моделирование, анализ и предсказание характеристик ИС на ВС, для которых не проводился эксперимент на ИС

В главе «Выполнение модельных и натурных экспериментов, анализ результатов» представлены результаты моделирования и результаты экспериментальных данных, полученных в процессе выполнения тестовых последовательностей в ИПС «Обзор СМИ»

В работе проведено моделирование ИС по экспериментальным данным, полученным на ВС на основе ЦП AMD Athlon 64 х2 4400+, AMD Opteron 880 (4 шт ), Intel Xeon 2 6 (4 шт ) Анализ адекватности моделей проверен на подсистеме полнотекстового поиска Эксперимент проведен с целью оценить возможности внутренней параллельной обработки, исключив влияние медленных подсистем ВС, типа внешних накопителей данных Для этого, тестовые запросы были подобраны таким образом, чтобы все промежуточные данные, необходимые для их обработки, были помещены в ОЗУ Следует заметить, что такой режим в значительной степени соответствует установившемуся режиму работы ИПС «Обзор СМИ», поскольку при имеющемся наборе данных, наиболее вероятна работа пользователей системы с общим ограниченным массивом данных

Результаты экспериментальных данных показывают снижение времени отклика в ИС с параллельным обслуживанием запросов в режимах одиночной загрузки серверов от 37 для 2-процессорной ВС до 65 процентов для 8-процессорной ВС Кроме того, улучшено использование ресурсов процессоров Таким образом, можно заключить об эффективной работе параллелизатора, обеспечивающего диспетчеризацию заявок на выполнение и его минимальном влиянии на ИС в целом

В разделе «Общие выводы» сформулированы основные выводы и результаты данной работы, а также намечены дальнейшие пути развития метода моделирования ИПС и улучшения характеристик параллелизатора

Основные результаты работы

1 Разработан алгебраический метод моделирования производительности, позволяющий оценивать параллельные СУБД с внутренним расщеплением параллельных процессов, обладающий свойством композиционности и позволяющий получать численные значения характеристик производительности, времени отклика, процент использования ресурсов по типу действия

2 Предложен и реализован метод параллельного выполнения операций, который предполагает контроль допустимого уровня параллелизма в реальном времени и позволяет предотвратить состояние деградации производительности ВС в целом Использование данного метода позволило увеличить производительность и уменьшить время отклика СУБД при работе на малых плотностях запросов в зависимости от архитектуры ВС от 37 до 65 процентов и не ухудшить их на режимах полной нагрузки

3 Разработан способ измерения временных характеристик подсистем ОСУБД и ОСУБД в целом, позволяющий измерять малые величины времени и времена взаимодействия параллельных процессов, существенно повышающий точность моделирования и проектирования

4 Разработаны инженерные методики применения предложенных моделей, позволяющие повысить производительность проектируемой ИС на базе ОСУБД

5 Создана модель ОСУБД ODB-Jupiter, позволившая определить возможность функционирования ИС и выполнить ее преобразование в систему с внутренним параллельным выполнением запросов

6 Предложенные в данной работе методы, модели и алгоритмы реализованы в программных комплексах ИПС «Обзор СМИ», ИПС «Архив председателя Совета Федерации Федерального Собрания РФ» в Аппарате Совета Федерации Федерального Собрания Российской Федерации, комплекс резервного копирования и восстановления информации в ЗАО «Всесоюзный институт волоконно-оптических систем связи и обработки информации», доведены до состояния промышленного программного продукта, внедрены на нескольких предприятиях

Работы по теме диссертации

1 Разработка многопоточного сервера СУБД для Windows NT / А М Андреев, Д В Березкин, Ю А Кантонистов, Р С Самарев //Компьютерная хроника -1999 -N4 -С 73-84

2 Андреев А М, Березкин Д В, Самарев Р С Внутренний мир объектно-ориентированных СУБД // Открытые системы - 2001 - № 3 - С 47-57

3 Настраиваемый интерфейс WEB-сервера ИПС, удаленное администрирование сервера ИПС / А М Андреев, Д В Березкин, Р С Самарев, А В Челмодеев //Современные информационные технологии сборник докладов и сообщений -М МГТУ, 2001,-С 110-117

4 Объектная распределенная ОСУБД / А М Андреев, Д В Березкин, Р С Самарев, А В Челмодеев // Современные информационные технологии в управлении и образовании - новые возможности и перспективы использования Сборник научных трудов - М ФГУП НИИ «Восход», МИРЭА, 2001 - С 65-68

5 Березкин Д В , Самарев Р С Система построения архивов электронных документов // Информатика и системы управления в XXI веке сборник трудов - М МГТУ, 2003 - №1 - С 376-379

6 Березкин Д В, Морозов В В Самарев Р С Подсистема сбора сообщений с сайтов новостной сети Интернет // Информатика и системы управления в XXI веке сборник трудов - М МГТУ, 2003 - №1 -С 409-410

7 Андреев А М , Березкин Д В , Самарев Р С Моделирование информационных систем // Информатика и системы управления в XXI веке Сборник трудов - М МГТУ, 2003 - №1 - С 385-400

8 Березкин Д В, Каплин К В, Самарев Р С Компилятор OQL для объектной СУБД //Информатика и системы управления в XXI веке сборник трудов - М МГТУ, 2003 - №1 - С 380-384

9 Анализ производительности разрабатываемых СУБД и ИС на их основе с использованием алгебраических моделей / А М Андреев, Д В Березкин, Р С Самарев, В В Сюзев//Вестник МГТУ Приборостроение-2007 -№3- С 94-115

Подписан и к печати 04.09.07. Заказ № 577 Объем 1,0 печл. Т ираж 70 экз. Типография МГГУ им. Н.Э. Баумана 105005, Москва, 2-я Вауманская ул., д. 5 263-62-0I

ВВЕДЕНИЕ.

Актуальность темы.

Цели и основные задачи.

Объект исследования.

Предмет исследования.

Научная новизна.

1. АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ ПОСТРОЕНИЯ ПАРАЛЛЕЛЬНЫХ СУБД И ИС НА ИХ ОСНОВЕ,

АНАЛИЗ МЕТОДОВ МОДЕЛИРОВАНИЯ.

1.1. Анализ существующих методов построения параллельных СУБД. Особенности организации.

1.1.1. Модели данных.

1.1.2. Схема данных и языки запросов.

1.1.3. Архитектура ВС для СУБД.

1.1.4. Методы размещения данных.

1.1.5. Транзакционная обработка данных.

1.1.6. Блокировка данных.

1.1.7. Методы организации параллельного выполнения запросов.

1.1.8. Архитектура взаимодействия клиента и сервера СУБД.

1.2. Анализ методов моделирования производительности ИС.

1.2.1. Анализ математических методов моделирования.

1.2.2. Применение методов моделирования для оценки характеристик производительности СУБД.

1.2.3. Средства моделирования СУБД и ИС.

1.3. Анализ ОСУБД ODB-Jupiter как объекта исследования.

1.3.1. ИПС «Обзор СМИ».

1.4. выводы.

2. РАЗРАБОТКА МЕТОДА МОДЕЛИРОВАНИЯ

ПРОИЗВОДИТЕЛЬНОСТИ ИС, ИСПОЛЬЗУЮЩЕЙ СУБД.

2.1. Расширение свойств алгебры РЕРА.

2.1.1. Формальное определение алгебры процессов.

2.2. Решение моделей.

2.2.1. Генерация сокрагценной марковской цепи.

2.2.2. Генерация полной марковской цепи.

2.3. Весовое расширение алгебры.

2.3.1. Структурные и параметрические ограничители.

2.3.2. Выбор факторов в векторе потребления ресурсов.

2.3.3. Анализ целесообразности введения операции взаимоисключения в РЕРА.

2.4. Модели производительности ИС, использующей СУБД.

2.4.1. Модель выполнения запросов.

2.4.2. Анализ обработки запросов в ОСУ БД ODB-Jupiter и

ИПС «Обзор СМИ».

2.4.3. Упрощенная модель сервера СУБД.

2.4.4. Модель запросов подсистемы поиска.

2.4.5. Полная модель ИС.

2.4.6. Модели пропускной способности подсистемы памяти.

2.4.7. Модель для оценки числа обработчиков параллелизатора.

2.5. Выводы.

3. УЛУЧШЕНИЕ ХАРАКТЕРИСТИК ПРОИЗВОДИТЕЛЬНОСТИ СУБД С ИСПОЛЬЗОВАНИЕМ АДАПТИВНОГО ПЛАНИРОВЩИКА ПАРАЛЛЕЛЬНЫХ ЗАПРОСОВ.

3.1. Разработка параллелизатора запросов.

3.1.1. Синхронное адаптивное управление.

3.1.2. Асинхронное адаптивное управление.

3.1.3. Выбор параллельного планировщика.

3.1.4. Оценка применимости выбранных параметров планировщика для идентификации состояния системы.

3.2. Реализация модуля параллелизатора.

3.3. Выводы.

4. МЕТОДИКИ ПРОЕКТИРОВАНИЯ ПАРАЛЛЕЛЬНЫХ СУБД.

4.1. Методика реорганизации СУБД в соответствии с заданными характеристиками.

4.2. Методика нагрузочного тестирования сервера ОСУБД в составе ИС.

4.3. Методика оценки характеристик производительности

ИС на основе СУБД.

4.4. Методика разбиения последовательного кода программы на независимые.

4.5. Методика параметризации моделей для различных

ВС с различными методами доступа к ОЗУ.

4.6. Метод использования параллелизатора в тексте программ.

4.6.1. Пример применения метода.

4.7. Применение методики нагрузочного тестирования сервера ОСУБД в составе ИС.

4.7.1. Выбор средства анализа программного кода.

4.7.2. Выбор метода измерения временных интервалов.

4.7.3. Трассировка выполнения программы.

4.7.4. Выбор способа организации синхронизации потоков.

4.7.5. Организация нагрузочного тестирования ИС.

4.7.6. Измерение показателей ИС.

4.7.7. Съем данных с реальной системы.

4.8. ВЫВОДЫ.

5. ВЫПОЛНЕНИЕ МОДЕЛЬНЫХ И НАТУРНЫХ ЭКСПЕРИМЕНТОВ, АНАЛИЗ РЕЗУЛЬТАТОВ.

5.1. Выполнение модельного эксперимента с разработанными моделями.

5.1.1. Модель запросов подсистемы поиска по реквизитам.

5.1.2. Модели пропускной способности подсистемы памяти.

5.2. Анализ результатов моделирования.

5.2.1. Эксперимент и моделирование подсистемы полнотекстового поиска ИС.

5.3. Анализ экспериментальных данных.

5.4. выводы.

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

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

Другой проблемой использования СУБД является то, что монопольное использование вычислительной системы не всегда возможно. В большинстве малых и средних коммерческих организациях, на ВС, на которой работает СУБД, работают и другие программы, также требующие значительных ресурсов. При малой плотности запросов к СУБД, влияние других программ может быть незначительным, однако, например в случае использования СУБД в сочетании с Web-сервером, вполне возможна ситуация полной загрузки вычислительной системы. Операционная система, типа MS Windows на ВС с вытесняющей многозадачностью с архитектурой х86, не способна оптимально разрешить ситуацию одновременного использования процессора или НЖМД при большом количестве одновременно работающих процессов/потоков. Таким образом, линейное увеличение количества параллельных процессов в различных программах приводит к нелинейному снижению производительности системы в целом, поскольку доля служебных операций по переключению потоков, вытеснению памяти, позиционированию головок НЖМД на нужный сектор занимает значительное время. К аналогичным последствиям приведет неограниченное параллельное выполнение запросов при большой их входной плотности [114].

В настоящее время широко распространены параллельные СУБД для вычислительных систем без общей памяти, однако, массовое использование архитектуры х86 не позволяет использовать классические параллельные СУБД в чистом виде. Кластер, построенный путем объединения отдельных х86-систем, можно рассматривать как единую систему, с несколькими независимыми узлами, не имеющими общей памяти. При этом каждый узел может быть многопроцессорным, что требует реализации соответствующих алгоритмов, а кроме того, создание кластера на х86 требует организации быстродействующего межпроцессорного обмена данными, что также является проблемой.

Итак, оптимальной СУБД с точки зрения производительности и времени отклика будет СУБД, реализующая внутризапросный параллелизм, причем доступные в данный момент времени ресурсы ВС используются максимально, но с учетом того, что превышение некоторого предела загрузки ВС приведет к релейному падению производительности системы в целом.

Рассмотрим актуальность проблемы моделирования производительности СУБД и ИС на их основе. На рис. 1 приведена обобщенная схема анализа производительности СУБД.

Рис.1 Исходные данные, этапы анализа СУБД и получаемый результат

Моделирование характеристик СУБД актуально в следующих случаях:

- Создание новой СУБД;

- Проверка допустимых режимов работы существующей СУБД;

- Выполнение оптимизации работы существующих приложений.

Архитектура СУБД наиболее существенно влияет на производительность будущих систем, построенных с применением данной СУБД. Поэтому целесообразно проводить моделирование работы СУБД и возможных последствий от введения каких-либо элементов архитектуры СУБД на ранних стадиях разработки. Кроме того, существует возможность оценить возможные области применения СУБД по предельно допустимым режимам работы.

В случае, когда СУБД уже разработана, необходимо знать ее допустимые режимы эксплуатации (типы приложений и наборы операций, которые не приведут к снижению производительности), а также иметь возможность оценивать требуемые параметры оборудования, такие как быстродействие процессоров, дисков, их количество, схему объединения в кластер и пр.

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

Цели и основные задачи

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

- Анализ параллельных архитектур СУБД и методов повышения эффективности использования системных ресурсов. Выбор критериев производительности СУБД.

- Разработка алгебраической модели параллельной объектной СУБД. Метод оценки характеристик производительности систем на основе СУБД.

- Моделирование и исследование свойств модели.

- Разработка параллелизатора запросов для асинхронного выполнения операций в СУБД.

- Разработка метода измерения производительности реальной системы.

- Создание инженерных методик реорганизации СУБД в соответствии с заданными характеристиками с использованием предложенных моделей. Исследование характеристик производительности систем на основе СУБД с использованием этих методик. Реализация методик для улучшения характеристик сервера ОСУБД.

Объект исследования

Объектом исследования является класс систем, предназначенных для работы на многопроцессорных ВС общего назначения, включающих в себя объектные системы управления базами данных, в частности ОСУБД ODB-Jupiter и ИС на её основе.

Предмет исследования

Предметом исследования является анализ процессов обработки запросов в параллельных объектных системах управления базами данных и информационных систем на их основе.

Научная новизна

В работе получены следующие новые результаты:

На основе стохастической алгебры процессов "РЕРА" (англ.) разработан метод, позволяющий проводить расширенный анализ сложной информационной системы па основе алгебраических моделей, включая анализ по каждому параллельному процессу в отдельности, а также весовое расширение "РЕРА", позволяющее анализировать модель с позиции потребления различных ресурсов системы, описываемых как многомерный вектор.

Разработана комплексная модель сервера ОСУБД ODB-Jupiter, а также модели отдельных подсистем с использованием алгебраического подхода.

Разработан метод параллельного выполнения внутренних операций с учетом доступных ресурсов ВС на момент начала обработки.

7. Общие выводы

В работе получены следующие основные результаты:

1. Разработан алгебраический метод моделирования производительности, позволяющий оценивать параллельные СУБД с внутренним расщеплением параллельных процессов, обладающий свойством композиционности и позволяющий получать численные значения характеристик производительности, времени отклика, процент использования ресурсов по типу действия.

2. Предложен и реализован метод параллельного выполнения операций, который предполагает контроль допустимого уровня параллелизма в реальном времени и позволяет предотвратить состояние деградации производительности ВС в целом. Использование данного метода позволило увеличить производительность и уменьшить время отклика СУБД при работе на малых плотностях запросов от 37 до 65 процентов в зависимости от ВС и не ухудшить их на режимах полной нагрузки. Разработанный метод может применяться для организации параллельного выполнения программ, реализованных с применением промежуточного машинонезависимого кода (Java, .Net) при соответствующем внедрении в среду выполнения.

3. Разработан способ измерения временных характеристик подсистем ОСУ БД и ОСУБД в целом, позволяющий измерять малые величины времени и времена взаимодействия параллельных процессов, существенно повышающий точность моделирования и проектирования.

4. Разработаны методики применения предложенных моделей, позволяющие повысить производительность проектируемой ИС на базе ОСУБД.

5. Создана модель ОСУБД ODB-Jupiter, позволившая определить возможность функционирования ИС и выполнить преобразование ОСУБД в систему с внутренним параллельным выполнением запросов.

6. Предложенные в данной работе методы, модели и алгоритмы реализованы в программных комплексах ИПС «Обзор СМИ», ИПС «Архив председателя Совета Федерации Федерального Собрания РФ», РКВИ (ФГУП «Концерн «Системпром»,ВИВОСС и ОИ), доведены до состояния промышленного программного продукта, внедрены на нескольких предприятиях.

6. Заключение

Разработанный метод моделирования и соответствующие модели обеспечивают оценку характеристик СУБД и ИС на их основе. Наличие средств моделирования иерархических параллельных процессов позволяет использовать разработанный на основе алгебры процессов 'РЕРА' метод для широкого класса задач и, в частности, позволяет моделировать параллельные СУБД с внутренним расщеплением параллельных процессов. Полученные результаты свидетельствуют о принципиальной возможности использования данных методов для качественной и количественной оценки производительности ИС. Проблемы, связанные с решением полных моделей ИС, и, соответственно, большой размерностью промежуточных марковских цепей, являются принципиально устранимыми, однако их решение требует разработки соответствующих методов понижения размерности и фрагментарного решения, что является целью будущей работы.

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

1. Андреев A.M., Березкин Д.В., Кантонистов Ю.А. Выбор СУБД для построения информационных систем корпоративного уровня на основе объектной парадигмы //СУБД.- 1998.-№ 4-5.- С. 26-50.

2. Андреев A.M., Березкин Д.В., Кантонистов Ю.А. Среда и хранилище: ООБД //МИР ПК.-1998.-№ 4.- С. 74-81.

3. Концепция создания АИС МАГП / A.M. Андреев, Д.В. Березкин, Ю.А. Кантонистов, Е.В. Громыко // Компьютерная хроника 1999.-№ 4- С. 85-98.

4. Разработка многопоточного сервера СУБД для Windows NT /A.M. Андреев, Д.В. Березкин, Ю.А. Кантонистов, Р.С. Самарев //Компьютерная хроника. -1999.-№4.-С. 73-84.

5. Объектно-ориентированная база данных "ODB-Jupiter" / A.M. Андреев, Д.В. Березкин, Ю.А. Кантонистов, Ю.М. Смирнов // Изв. ВУЗов. Приборостроение.- 1998.-Т.41, № 1-2.-С. 40-56.

6. Андреев A.M., Березкин Д.В., Самарев Р.С. Особенности создания корпоративных информационных систем на основе ОСУБД ODB-Jupiter //Корпоративные базы данных: материалы конференции. М., 2003. - 20 с.

7. Андреев A.M., Березкин Д.В., Самарев Р.С., Внутренний мир объектно-ориентированных СУБД // Открытые системы. -2001.-№ 3 С. 44-54.

8. Сети Петри Электронный ресурс. /Е.А. Голенков, В.А. Левин, Д.И. Харитонов и др-Режим доступа: http://www.iacp.dvo.ru/labl l/otchet/ot2000/pn3.html

9. Аткинсон М., Бансилон Ф., ДеВитг Д., Манифест систем объектно-ориентированных баз данных //СУБД 1995.-№ 4- С.142-155.

10. И.Барский А.Б. Параллельные информационные технологии: Учебное пособие. М.: ИНТУИТ; БИНОМ. Лаборатория знаний, 2007. - 503 с.

11. Бениаминов Е.М. Алгебраические методы в теории баз данных и представлении знаний.-М.: Научный мир-2003.- 184 с.

12. Бениаминов Е.М., Ефимова Е.А. Элементы универсальной алгебры и её приложений в информатике (уч. пособие). -М.: Научный мир, 2004. 168 с.

13. Боггс У., Майкл Б. UML и Rational Rose 2002. М.: Лори, 2004. - 528 с.

14. Бурдаков А.В. Модели и методы анализа вычислительных систем с архитектурой брокера объектных запросов: Диссертация на соискание ученой степени кандидата наук. М: МГТУ им Н.Э. Баумана, 2002. - 195 с.

15. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. М: Издательство Бином, 2000. - 560 с.

16. Варламов О.О. Эволюционные базы данных и знаний для адаптивного синтеза интеллектуальных систем. Миварное информационное пространство. М.: Радио и связь, 2002. - 282 с.

17. Вахалия Ю. Unix изнутри. СПб.: Питер, 2003. - 844 с.

18. Вентцель Е.С., Овчаров Л.А., Теория случайных процессов и ее инженерное приложение. М.: Высшая школа, 2000. - 383с.

19. Венцель Е.С. Исследование операций. М.: Советское радио, 1972. - 552 с.21 .Венцель Е.С. Теория вероятностей. М.: Высшая школа, 2000. - 383 с.

20. Вербицкий В.М. Основы численных методов: Учебник для вузов. М.: Высшая школа, 2002. - 840 с.

21. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. - 608 с.

22. Волков Д.А. Концепция универсального сервера для архитектуры клиент-сервер // Программирование. 2000. - №6- С. 65-72.

23. Волков И.К., Загоруйко Е.А. Исследование операций. М: МГТУ им Баумана, 2000.-436 с.

24. Волков И.К., Зуев С.М., Цветкова Г.М.Случайные процессы. М: МГТУ им Баумана, 2000.-446 с.

25. Гарсиа-Молина Г., Ульман Дж., Уидом Джен. Системы баз данных. Полный курс.: Пер. с англ. -М.: Издательский дом "Вильяме", 2003. -1088 с.

26. Глушков В.М., Цейтлин Г.Е., Ющенко E.JI. Алгебра. Языки. Программирование. Киев: Наука думка, 1974. - 328 с.

27. Горбатов В.А., Фундаментальные основы дискретной математики. М.: Наука. Физмалит, 2000. - 544 с.

28. Математическая статистика: Учеб. для вузов / В.Б. Горяинов, И.В. Павлов, Г.М. Цветкова и др.: Под ред. B.C. Зарубина, А.П. Крищенко. 2-е изд., стереотип. - М.: Изд-во МГТУ им. Баумана, 2002. - 424 с.

29. Дейт К. Дж. Введение в системы баз данных. 8-е издание. М.: Издательский дом Вильяме, 2005 год. - 1328 с.

30. Дейт К. Дж., Дарвен Хью. Основы будущих систем баз данных. Третий манифест. Изд. 2-е. /Перев. с англ. С.Д. Кузнецов, Т.А. Кузнецова; Под ред. С.Д. Кузнецова. М.: Янус-К, 2004. - 656 с.

31. Зб.Зильбершац А., Здоник С. Стратегические направления в системах баз данных //СУБД. 1997.—№ 4.- С. 4-23.37.3олотарев С., Рыбаков А. Программное обеспечение многоядерных систем //Открытые системы. 2006.-№2. - С. 12-17.

32. Ивницкий В.А. Теория сетей массового обслуживания. М.: Издательство физико-математической литературы, 2004. - 772 с.

33. Капитонова Ю.В., Летичевский А.А. Математическая теория проектирования вычислительных систем. М.: Наука. Гл. ред. физ-мат. лит., 1988. - 296 с.

34. Кельтон В., Jloy А. Имитационное моделирование. Классика CS. 3-е изд. -СПб.-Киев: Издательская группа BHV, 2004. 847 с.

35. Постреляционная СУБД Cache 5. Объектно-ориентированная разработка приложений / В. Кирстен, М. Ирингер, М. Кюн, Б. Рериг: Пер.с англ. 2-е изд. - М.: БИНОМ, 2005. - 416 с.

36. Клейнрок Л. Вычислительные системы с очередями / Пер. с англ. Б. С. Цы-бакова. М.: Мир, 1979. - 600 с.

37. Клейнрок Л. Теория массового обслуживания. / Пер. с англ. И. И. Грушко; Ред. В И. Нейман. -М.: Машиностроение, 1979.-432 с.

38. Кобзарь А.И. Прикладная математическая статистика. Для инженеров и научных работников. -М.: ФИЗМАТЛИТ, 2006. 816 с.

39. Когаловский М.Р. Энциклопедия технологий баз данных. М.: Финансы и статистика, 2002. - 800 с.

40. Котов В.Е. Алгебра регулярных сетей Петри // Кибернетика-1980 №5. -С. 10-18.

41. Котов В.Е. Сети Петри. -М.: Наука, 1984. 160 с.

42. Теоретические основы проектирования оптимальных структур распределенных баз данных /В.В. Кульба, С.С. Ковалевский, С.А. Косяченко, В.О. Сиро-тюк. М: СИНТЕГ, 1999. - 660 с.

43. Ломазова И.А. Объектно-ориентированные сети Петри. // Системная инфор-матика-2002-Вып. 8. С. 143-205.

44. Попов Э.В. Статические и динамические экспертные системы. М.: Финансы и статистика 1996. - 319 с.

45. Рихтер Дж. Windows для профессионалов: Программирование для Windows 95 и Windows NT4 на базе API: Пер. с англ. М.: Издательский отдел «Русская Редакция» ТОО «Channel Trading Ltd.», 1997. - 712 с.

46. Саймон А.Р. Стратегические технологии баз данных: менеджмент на 2000 год: Пер. с англ. /Под ред. и с предисл. М.Р.Когаловского. М.: Финансы и статистика, 1999 - 479 с.

47. Самарев Р.С. Внутренняя организация ОСУБД Versant, Poet, ODB-Jupiter. //Корпоративные базы данных: материалы конференции М.,2001.- С.79-92.

48. Себеста Р.У. Основные концепции языков программирования, 5-е изд.: Пер. с англ. М.: Издательский дом "Вильяме", 2001. - 672 с.

49. Соколинский Л. Б. Организация параллельного выполнения запросов в многопроцессорной машине баз данных с иерархической архитектурой. //Программирование. 2001.- №6 - С. 13-29.

50. Соколинский Л.Б. Параллельные машины баз данных // Природа. Естественно-научный журнал Российской академии наук. 2001. - N8. - С. 10-17.

51. Соломон Д., Руссинович М. Внутреннее устройство Microsoft Windows 2000. Мастер-класс : Пер. с англ. М.: Издательско-торговый дом «Русская Редакция», 2004. - 746 с.

52. Соммервилл И. Инженерия программного обеспечения, 6-е издание.: Пер. с англ. М.: Издательский дом «Вильяме», 2002. - 624 с.

53. Таненбаум Э., ван Стен М. Распределенные системы. Принципы и парадигмы. СПб.: Питер, 2003. - 877 с.

54. Логический подход к искусственному интеллекту: От модальной логики к логике баз данных/ А. Тейз, П. Грибомон, Г. Юлен, А.Пирот и др.: Пер. с франц. М.: Мир, 1998. - 994 с.

55. Фаулер М., Скотт К. UML в кратком изложении. М.: Мир, 1999. - 191 с.

56. Ширяев А.Н. Ветоятность. В 2-х кн. 3-е изд., перераб. и доп. - М.: МЦНМО, 2004. - Кн. 1.-520 е.; Кн. 2.-408 с.

57. Шлеер С., Меллор С. Объектно-ориентированный анализ: моделирование мира в состояниях-Киев: Диалектика, 1993.-240 с.

58. Bause F. Combining Qualitative and Quantitative Analysis of Generalized Stochastic Petri Nets. Dortmund (Gemany): Universitat Dortmund, 1994. - 11 p.

59. Bause F., Buchholz P., Kemper P. Hierarchically Combined Queueing Petri Nets. Dortmund (Gemany): Universitat Dortmund, 1994. - 9 p.

60. Beeri Catriel, Milo Tova. Functional and Predicative programming in OODB's III 1th Principles of Database Systams.-San Diego (CA), 1992. P. 176-190.

61. Beeri Catriel. New Data Models and Languages the Challenge III 1th Principles of Database Systams.-San Diego (CA), 1992.-P. 1-15.

62. Bernando M, Donatiello L, Gorrieri R. A formal Approach to the Integration of Perfomance Aspects in the Modeling and Analysis of Concurrent Systems. Bologna: Universita di Bologna, 1998. - 54 p.

63. Bernardo M. An Algebra-Based Method to Associate Rewards with EMPA Terms //24th Int. Colloquium on Automata, Languages and Programming. Bologna (Italy), 1997.-P. 358-368.

64. Bertino Elisa, Foscoli Paola. Index organization for object-oriented database system //IEEE Transaction on knowledge data engineering. 1995. - Vol.7, No 2. -P. 193-209.

65. Bhide A. An Analysis of Three Transaction Processing Architectures //Fourteenth International Conference on Very Large Data Bases (VLDB'88). Los Angeles (California, USA), 1988. - P. 339-350.

66. Bradley Jeremy Т., Gilmore Stephen Т., Thomas Nigel. How Synchronisation Strategy Approximation in PEPA Implementations affects Passage time Performance Results. Edinburgh (United Kingdom), 2003. - 14 p.

67. Clark G. Techniques for the Construction and Analysis of Algebraic Performance Models: PhD thesis. Edinburgh (United Kingdom), 2000. - 163 p.

68. Clark G., Gilmore S., and Hillston J. Specifying performance measures for PEPA //Proceedings of the Fifth International AMAST Workshop on Real-Time and Probabilistic Systems, number 1601 in LNCS. Bamberg (Germany), 1999. -Springer-Verlag. - P. 211-227.

69. Codd E. F. A Relational Model of Data for Large Shared Data Banks //Communication of the ACM. -1970.-V 13, Number 6. P. 377-383.

70. Complete Overview of Petri Nets Tools Database Электронный ресурс. /Prof. Dr. Eike Best, Christian Stehno. Режим доступа: http://www.informatik.uni-hamburg.de/TGI/PetriNets/tools/compIetedb.html.

71. Dandamudi S. and Au Siu-Lun. Locking Granularity in Multiprocessor Database Systems //Proceedings of the Seventh International Conference on Data Engineering. Kobe (Japan), 1991. - P. 268-277.

72. Delis A., Roussopoulos N. Performance and scalability of client-server database architectures //Proceedings of 18th International Conference on VLDB. Vancouver, 1992.-P. 610-623.

73. Verifying a Performance Estimator for Parallel DBMSs /Е. W. Dempster, N. T. Tomov, J. Lu etc. // Lecture Notes in Computer Science. Berlin, 1998. - Vol. 1470-P. 126-135.

74. Modelling Parallel Oracle for Performance Prediction /E.W. Dempster, N.T. Tomov, M.H. Williams etc. //Distributed and Parallel Databases. 2003. - Vol 13 -P. 251-269.

75. Donatelli S., Hillston J., Ribaudo M. A Comparison of Performance Evaluation Process Algebra and Generalized Stochastic Petri Nets //Proc. of 6th Int. Workshop on Petri Nets and Performance Models. North Carolina (USA), 1995. - P. 158-169.

76. Dumas Sophie, Gardarin Georges. A Workbench For Predicting The Performances Of Distributed Object Architectures //Proceedings of the 1998 Winter Simulation Conference. Washington (DC, USA) 1998. - P. 515-522.

77. Foxon Tim, Garth Mike, Harrison Peter. Capacity planning in client-server systems //Distrib. Syst. Engng. 1996.-№ 3.- P. 32-38.

78. Gardarin G., Sha F., and Tang Z.-H. Calibrating the query optimizer cost model of IRO-DB, an object oriented federated database system //VLDB'96, Proceedings of 22th International Conference on Very Large Data Bases. Mumbai (India), 1996. -P. 378-389.

79. Gilmore S, Hillstone J., Ribaudo M. An Efficient Algorithm for Aggregating PEPA Models //IEEE Transactions of software. 2001.-Vol 27,No 5.- P.449-464.

80. Gilmore S., Hillston J., KIoul L. PEPA nets: A structured performance modelling formalism //Performance Evaluation. 2003. - Vol 54, No 2. - P.79-104.

81. Gotz N, Herzog U, Rettelbach M. Multiprocessor and Distributed System Design. The Integration of Functional Specification and Performance Analysis using Stochastic Process Algebras //Performance^ conference. Rome, 1993.—P. 121-146.

82. Graefe G. Encapsulation of Parallelism in the Volcano Query Processing System //Proceedings of the 1990 ACM SIGMOD international conference on Management of data. Atlantic City (New Jersey, US A), 1990. - P. 102-111.

83. Graefe Goetz, Query Evaluation Techniques for Large Databases //ACM Computing Surveys. 1993.-Vol. 25, No. 2. - P. 73-169.

84. He Zhen, Suk Lee Byung, Snapp Robert. Self-Tuning Cost Modeling of User-Defined Functions in an Object-Relational DBMS //ACM Transactions on Database Systems.- 2005.- Vol. 30, No. 3,- P. 812-853.

85. Hermanns H, Herzog U, Mertsiotakis V. Stochastic Process Algebras as a Tool for Performance and Dependability Modelling. Erlangen (Germany): University of Erlangen-Niirnberg, 1995. - 10 p.

86. Herzog U, Mertsiotakis V. Stochastic Process Algebra as Applied to Failure Modelling. Erlangen (Germany): University of Erlangen-Niirnberg, 1994. - 20 p.

87. Hillston J. A Compositional Approach to Performance Modelling. Cambridge: Cambridge University Press, 1996. - 168 p.

88. Hoare C.A.R. Communicating Sequential Processes. Englewood Cliffs (New Jersey, USA): Prentice-Hall, 1985.-256 p.

89. Hrischuk C.E. The Automatic Generation of Software Performance Models From a Prototype. Master of Engineering thesis. Ottawa (Ontario, Canada): Carleton University, 1995. - 98 p.

90. Jensen K. Coloured Petri Nets Basic Concepts, Analysis Methods and Practical Use: Volume I. Monogr. in Theor. CS. 2nd ed. - Б.г: Springer-Verlag, 1997. -234 p.

91. Jensen K. An introduction to the Theoretical Aspects of Coloured Petri Nets //A Decade of Concurrency, Reflections and Perspectives, REX School/Symposium. London (UK), 1993. - P. 230-272. - (Lecture Notes In Computer Science; Vol. 803)

92. Kwiatkowska M., Norman G., and Parker D. Probabilistic symbolic model checking with PRISM: A hybrid approach //International Journal on Software Tools for Technology Transfer (STTT). 2004. - Vol 6, No 2. - P. 128-142.

93. Quantitative System Performance. Computer System Analysis Using Queuing Network Models /Edward D. Lazowska, John Zahorjan, G. Scott Graham, Kenneth C. Sevcik. Englewood Cliffs (New Jersey, USA): Prentice-Hall, 1984. - 417 p.

94. Legrand Iosif C., Newman Harvey B. The Monarc Toolset For Simulating Large Network-Distributed Processing Systems //Proceedings of the 2000 Winter Simulation Conference. Orlando (FL, USA), 2000. - P. 1794-1801.

95. Machado Javam C., Collet Christine. A Parallel Execution Model for Database Transactions //Proceedings of the Fifth International Conference on Database Systems for Advanced Applications. Melbourne (Australia), 1997. - P. 511-520.

96. Marsan M. Ajmone, Conte G., Balbo G. A Class of Generalized Stochastic Petri Nets for the Performance Evaluation of Multiprocessor Systems //ACM Transactions on Computer Systems. 1984. - Vol 2, no 93. - P. 93-122.

97. Mehta Manish, DeWitt David J. Managing Intra-operator Parallelism in Parallel Database Systems //Proceedings of the 21st VLDB Conference. Zurich (Switzerland), 1995.-P. 382-394.

98. Mehta Manish, Soloview Valery, DeWitt David J. Batch Scheduling in Parallel Database Systems //Proceedings of the Ninth International Conference on Data Engineering. Vienna (Austria), 1993. - P. 400-410.

99. Milner R. Communicating and Concurrency. New-York: Prentice-Hall, 1989. -300p.

100. Milner R. Calculi for synchrony and asynchrony //Theoretical Computer Science. -1983. Vol 25, no 3. - P. 267-310.

101. Mines N. Garofalakis, Yannis E. Ioannidis. Multi-dimensional Resource Scheduling for Parallel Queries //SIGMOD '96. Montreal (Canada), 1996. - P. 365-376.

102. Mohan C. ARIES, A transaction recovery method supporting fine granularity locking and partial rollbacks using write-ahead logging //ACM Transactions on Database Systems (TODS).- 1992.-Volume 17, Issue l.-P. 94-162.

103. Molloy M. K. Performance analysis using stochastic Petri nets //IEEE Transactions on Computers. 1982. - Vol 31, no 9. - P. 913-917.

104. Movaghar A., Meyer J.F. Performability Modelling with Stochastic Activity Networks //Proc. Of Real-Time Systems Symposium. Austin (Texas, USA), 1984.-P. 215-224.

105. Plotkin G.D. A Structural Approach to Operational Semantics. Aarhus (Denmark): University of Aarhus, 1981.-133 p.

106. Ribaudo M. On the Aggregation Techniques in Stochastic Petri Nets and Stochastic Process Algebras //The Computer Journal. 1995. -Vol 38. - P. 600-611.

107. Sanders W. H., Meyer J. F. METASAN: A Performability Evaluation Tool Based on Stochastic Activity Networks //Proceedings of the IEEE-ACM Fall Joint Computer Conference. Dallas (TX, USA), 1986. - P. 807-816.

108. Sanders W. H., Obal W. D. II, Qureshi M. A., Widjanarko F. K. The UltraSAN Modeling Environment //Performance Evaluation. 1995. -Vol. 24, no. 1. - P. 89115.

109. Sokolinsky L.B., Axenov 0., Gutova S. Omega: The Highly Parallel Database System Project // Proceedings of the First East-European Symposium on Advances in Database and Information Systems (ADBIS'97). St.-Petersburg (Russia), 1997.-Vol. 2.-P. 88-90.

110. Stonebraker Michael. The Case for Shared Nothing //Database Engineering Bulletin. -1986. -Vol. 9, Number 1. P. 4-9.

111. Strulo B. Process Algebra for Discrete Event Simulation: Ph. D. thesis. London: Imperial College, 1993. - 14 p.

112. Teeuw W. В., Rich C., Scholl M. H., Blanken H. M. An Evaluation of Physical Disk I/Os for Complex Object Processing //Ninth International Conference on Data Engineering. Vienna, 1993. - P. 363-371.

113. Thalheim Bernhard. Database Component Ware //Fourteenth Australasian Database Conference. Adelaide (Australia), 2003. - Vol. 17 - P. 13-26.

114. The Object Database Standard: ODMG 3.0. San Francisco (California): Morgan Kaufmann Publishers Inc., 2000.-260 p.

115. Thoman D.R., Bain L.J., Antle C.E. Inferences on Parameters of the Weibull Distribution //Technometrics. 1969. -№11. -P. 455-460.

116. Versant ODBMS, Versant С++ Reference Manual 5.2. Freemont (CA, USA): Versant Corporation, 1999. - 500 p.

117. Versant ODBMS, Versant Object Database Fundamentals Manual Электронный ресурс. Режим доступа: http://www.versant.com/developer/resources/objectdatabase/documentation/databa sefimdman.pdf, свободный.

118. The Stochastic Rendezvous Network Model for Performance of Synchronous Client-Server-like Distributed Software /С.М. Woodside, J.E. Neilson, D.C.

119. Petriu, S. Majumdar //IEEE Transactions on Computers. 1995. - Vol. 44, No.l. -P. 20-34.

120. Zhou Shaoyu, Williams M. Howard, Taylor Hanish. Practical Throughput Estimation for Parallel Databases // Software Engineering Journal. 1996. -Vol. 11. - P. 255-263.

121. Таким образом, внедрение результатов диссертационной работы Самарева Р.С. в модифицированную версию ИПС «Обзор СМИ» позволило существенно повысить эффективность функционирования системы в интересах пользователей Совета Федерации.

122. Начальник отдела прикладных информационных систем и электронных информационных ресурсов Управления информационного и документационного обеспечения Аппарата Совета Федерации

123. Заместитель начальника отдела прикладных информационных систем и электронных информационных ресурсов Управления информационного и документационного обеспечения Аппарата Совета Федерации