Методи і засоби забезпечення ефективності обробки запитів у комп'ютерних системах із множинним доступом

Размещено на http://www.allbest.ru/

ВІННИЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

УДК 517.977.5

МЕТОДИ І ЗАСОБИ ЗАБЕЗПЕЧЕННЯ ЕФЕКТИВНОСТІ ОБРОБКИ ЗАПИТІВ У КОМП'ЮТЕРНИХ СИСТЕМАХ ІЗ МНОЖИННИМ ДОСТУПОМ

Спеціальність 05.13.05 - Комп'ютерні системи та компоненти

АВТОРЕФЕРАТ дисертації на здобуття наукового ступеня

кандидата технічних наук

Штельмах Ігор Миколайович

Вінниця 2011

Дисертацією є рукопис.

Роботу виконано у Вінницькому національному технічному університеті Міністерства освіти і науки, молоді та спорту України.

Науковий керівник: доктор технічних наук, професор Шабатура Юрій Васильович, Академія сухопутних військ імені гетьмана Петра Сагайдачного, м. Львів, завідувач кафедри електромеханіки та електроніки

Офіційні опоненти: доктор технічних наук, доцент Кулик Анатолій Ярославович, Вінницький національний технічний університет, професор кафедри автоматики та інформаційно-вимірювальної техніки

доктор технічних наук, професор Соколовський Ярослав Іванович, Національний лісотехнічний університет України, м. Львів, завідувач кафедри обчислювальної техніки і моделювання технологічних процесів

Захист відбудеться „ 16 ” квітня 2011 р. о 9:30 годині на засіданні спеціалізованої вченої ради Д 05.052.01 у Вінницькому національному технічному університеті за адресою: 21021, м. Вінниця, Хмельницьке шосе, 95, ГНК ауд. 210.

З дисертацією можна ознайомитися у бібліотеці Вінницького національного технічного університету за адресою: 21021, м. Вінниця, Хмельницьке шосе, 95.

Автореферат розіслано „ 11 ” березня 2011 р.

Вчений секретар

спеціалізованої вченої ради С.М. Захарченко

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Стрімкий розвиток та доступність сучасних комп'ютерних систем та мереж, сприяють їх активному застосуванню в різноманітних галузях людської діяльності. На зміну мейнфреймам та суперкомп'ютерам, з'явився новий клас комп'ютерних систем із множинним доступом (КСМД), які використовують в якості комунікаційного середовища глобальні комп'ютерні мережі. Як і для будь-якої системи масового обслуговування (СМО), їх ключовою якісною характеристикою є показник пропускної здатності, який по суті зводиться до тривалості обробки кожного запиту. Якщо для систем з незначною кількістю регулярних користувачів, коротка тривалість обробки запитів зумовлює зручність користування, то для великих систем, які обробляють вхідні потоки запитів із високою інтенсивністю, зниження тривалості обробки не тільки підвищує зручність користування, але й забезпечує зменшення витрат на розширення апаратних ресурсів. Таким чином, для КСМД в умовах обмежених ресурсів, тривалість обробки запитів стає визначальним критерієм їх ефективності.

Застосування принципу Паретто для процесу обробки запитів у КСМД дозволяє зробити припущення про те, що приблизно 80% ресурсів таких систем споживається лише 20% операцій в їх програмних компонентах. Пошук таких ресурсоємних операцій, які в англомовних публікаціях дістали назву «вузьких місць» (англ. bottleneck), та зменшення їх впливу, дозволяють значно знизити ресурсоємність процесу обробки запитів, а, відповідно, і тривалість їх обробки.

Задача підвищення ефективності процесу обробки запитів у комп'ютерних системах, шляхом виявлення «вузьких місць» та зменшення їх впливу, не є новою. Її почали досліджувати ще на ранніх етапах розвитку комп'ютерних систем. Основи роботи перших систем такого класу були описані Леном Клеєнроком, як обчислювальні системи колективного користування із множинним доступом. Гленом Амонсоном запропоновано новий підхід до пошуку «вузьких місць» у великих комп'ютерних системах, який базується на аналізі дерева викликів операцій в процесі обробки запитів. Задача зменшення впливу виявлених «вузьких місць» на тривалість обробки запитів докладно розглядається в роботах Tарека Абделзахера (Мічиганський університет, США). Питання підвищення ефективності обчислювальних систем реального часу розглядаються також в багатьох роботах вітчизняних авторів, зокрема В.І. Жабіна, П.І. Жежнича, М.Є. Щербакової, С.А. Горбатюка. Основний акцент в них робиться на прискоренні роботи компонентів паралельних обчислювальних систем. Важливість та актуальність задачі скорочення тривалості обробки запитів в КСМД підтверджує той факт, що у 2010 році компанія Google модифікувала алгоритм ранжування у своїй пошуковій системі таким чином, щоб він враховував швидкість завантаження сторінок web-ресурсів. Окрім цього, під егідою Google проводиться ціла кампанія під назвою «Let's make the web faster», направлена на прискорення швидкодії комп'ютерних систем.

Отже, на сьогоднішній день, існує велика кількість методів підвищення ефективності процесу обробки запитів комп'ютерними системами із множинним доступом, однак всі вони направлені на розв'язання окремих задач. Застосування цих методів дозволяє одержати значний приріст продуктивності, однак потребує точної інформації про умови в яких спостерігається вплив «вузьких місць», їх місце розташування в програмних чи апаратних компонентах, природу виникнення. Постійне зростання структурної та функціональної складності комп'ютерних систем, значно ускладнює процес збору такої інформації, оскільки «вузькі місця» можуть проявляти себе в специфічних умовах, наприклад при виконанні окремих задач, або через деякий проміжок часу після початку експлуатації системи. Так, наприклад, «вузькі місця», пов'язані із обробкою запитів до баз даних, проявляються лише при наявності значного масиву даних.

Таким чином, однією з головних проблем підвищення ефективності процесу обробки запитів у комп'ютерних системах із множинним доступом є врахування їх структурної та функціональної складності, зокрема актуальною є задача розробки нового підходу до підвищення ефективності процесу обробки запитів, який дозволить здійснювати оптимізацію комплексно, включаючи етапи виявлення критичних запитів, локалізації «вузьких місць» та зменшення їх впливу на загальну ефективність процесу обробки запитів.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалась в рамках пріоритетних напрямків розвитку науки і техніки в Україні, окреслених у концепції Національної програми інформатизації, затвердженої Законом України «Про Концепцію Національної програми інформатизації» від 4 лютого 1998 року, яка передбачає активне впровадження обчислювальних систем на базі глобальних комп'ютерних мереж, а також госпдоговірній роботі, в якій здобувач виступав відповідальним виконавцем: «Розробка теорії та прикладного забезпечення для здійснення автоматичного моніторингу і підвищення часової ефективності обчислювальних систем інтегрованих в комп'ютерні мережі» (номер держ. реєстрації 0109U006870).

Мета і завдання дослідження. Метою даної роботи є підвищення ефективності процесу обробки запитів у комп'ютерних системах із множинним доступом в умовах обмежених ресурсів за рахунок вдосконалення існуючих і розробки нових методів виявлення та зменшення впливу «вузьких місць».

У результаті проведеного аналізу сформульовані основні завдання дослідження, які необхідно виконати для досягнення поставленої мети:

- проаналізувати відомі методи та технології підвищення ефективності процесу обробки запитів у КСМД;

- розробити новий підхід до підвищення ефективності обробки запитів, який дозволяв би здійснювати комплексне застосування методів виявлення, локалізації та зменшення впливу «вузьких місць» у програмних компонентах;

- розробити математичне та алгоритмічне забезпечення для вирішення задачі виявлення та локалізації «вузьких місць»;

- розвинути існуючі методи зменшення впливу «вузьких місць» для ресурсоємних розрахунків і запитів до баз даних;

- удосконалити метод оптимізації розподілу обчислювальних ресурсів між сервісними задачами комп'ютерних систем із множинним доступом;

- розробити програмне забезпечення для застосування запропонованих теоретичних положень та методів на практиці;

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

Об'єктом дослідження є процес обробки запитів у комп'ютерних системах із множинним доступом в умовах обмежених ресурсів.

Предметом дослідження є методи підвищення ефективності обробки запитів у комп'ютерних системах із множинним доступом.

Методи дослідження базуються на використанні теорії систем масового обслуговування, теорії множин, теорії графів, генетичних алгоритмів і математичної статистики для розробки методів аналізу ефективності та оптимізації процесу обробки запитів у КСМД; імітаційного моделювання для дослідження ефективності й достовірності розробленого підходу і методів; математичної статистики та теорії масового обслуговування для аналізу результатів експериментальних досліджень.

Наукова новизна одержаних результатів.

- Запропоновано новий підхід до підвищення ефективності процесу обробки запитів у комп'ютерних системах із множинним доступом, який полягає в комплексному застосуванні методів виявлення, локалізації та зменшення впливу «вузьких місць», що дозволяє автоматизувати процес підвищення продуктивності програмних компонентів таких систем.

- Удосконалено метод виявлення та локалізації «вузьких місць» у процесі обробки запитів, що здійснюється автоматично, і дозволяє визначати критичні запити з урахуванням нерівномірності завантаженості обчислювальних ресурсів, за рахунок застосування кластеризації параметрів запитів, врахування завантаженості обчислювальних ресурсів і використання графової моделі процесу обробки запитів.

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

- Розроблено модифікований метод кешування проміжних результатів розрахунків, що дозволяє здійснювати кешування не лише окремих запитів до баз даних або елементів інтерфейсу, а й результати виконання найбільш ресурсоємних операцій, на основі аналізу актуальності вхідних даних.

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

Практичне значення одержаних результатів. Проведені в роботі теоретичні дослідження використані при створенні методів та алгоритмічного забезпечення для підвищення ефективності процесу обробки запитів у комп'ютерних системах із множинним доступом. Розроблені алгоритми і методи реалізовані у вигляді програмної системи «Server Software Optimization Toolbox (SSOT)», яка може бути використана для підвищення ефективності процесу обробки запитів у переважній більшості сучасних КСМД. Зокрема, реалізовано програмне забезпечення для здійснення моніторингу процесу обробки запитів і локалізації «вузьких місць», зменшення впливу знайдених «вузьких місць» шляхом застосування кешування проміжних результатів розрахунків та оптимізації структури запитів до баз даних, а також оптимізації розподілу рівня споживання обчислювальних ресурсів сервісними задачами.

Результати досліджень впроваджені на 2-х підприємствах, що підтверджується відповідними актами:

- На підприємстві Contentum (Німеччина) у процесі підвищення ефективності роботи КСМД UMS4 та Regio-TV.de.

- На підприємстві ТОВ «TEAM Лтд» при створенні та введенні в експлуатацію програмного забезпечення для здійснення автоматичного моніторингу і підвищення часової ефективності обчислювальних систем.

Особистий внесок здобувача. Всі результати, які складають основний зміст дисертації, отримані здобувачем самостійно. В роботах, опублікованих у співавторстві, здобувачу належать такі ідеї і розробки: комплексний підхід до підвищення ефективності роботи КСМД [1,2], метод моніторингу процесу роботи КСМД [3], вдосконалений метод локалізації «вузьких місць» [4], підхід до оптимізації структури SQL-запитів на основі модифікації їх структури з використанням генетичних алгоритмів [5,6,9], алгоритмічне та програмне забезпечення для здійснення моніторингу динаміки часових затримок в комп'ютерних мережах [7,8].

Апробація результатів дисертації. Результати дисертаційної роботи доповідались та обговорювались на 12 науково-технічних конференціях:

- IV Міжнародній науковій конференції студентів та молодих вчених „Політ” (м. Київ, 2004);

- IV, V Міжнародних науково-практичних конференціях „Інтернет-Освіта-Наука” (м. Вінниця, 2004, 2008);

- Міжнародній науковій конференції «Інтелектуальні системи прийняття рішень і прикладні аспекти інформаційних технологій» (ISDMIT'2006) (м. Євпаторія, 2006);

- V Міжнародній науково-практичній конференції "Комп'ютерні системи в автоматизації виробничих процесів" (м. Хмельницький, 2007);

- VІІІ, ІХ Міжнародних конференціях «Контроль і управління в складних системах» (м. Вінниця, 2005, 2008);

- Науково-практичних конференціях професорсько-викладацького складу, співробітників і студентів Вінницького національного технічного університету (м. Вінниця, 2006-2010).

Публікації. Результати теоретичних і експериментальних досліджень викладені в 23 наукових працях, серед яких 17 статей, 9 з них в журналах, що входять до переліку ВАК України, 4 тези доповідей, свідоцтво про реєстрацію авторського права на твір та патент на корисну модель.

Структура та обсяг дисертації. Дисертаційна робота складається із вступу, 4 розділів, висновків, списку використаних джерел (135 найменувань) і додатків. Основний зміст викладено на 150 сторінках друкованого тексту, містить 65 рисунків, 12 таблиць. Загальний обсяг дисертації 212 сторінок.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі до дисертаційної роботи обґрунтовано актуальність теми, вказано зв'язок роботи з науковими програмами, сформульовано мету та задачі досліджень. Наведено основні наукові і практичні результати, відомості про їх впровадження, апробацію і публікації.

У розділі 1 проведено аналіз існуючих методів, моделей та підходів до підвищення ефективності процесу обробки запитів у комп'ютерних системах із множинним доступом.

Аналіз об'єкту дослідження показав, що сучасні КСМД характеризуються значною структурною та функціональною складністю. Підвищення ефективності процесу обробки запитів такими системами потребує розгляду більшості їх компонентів, а також зміни їх стану в часі. Відслідковувати таку інформацію досить складно, особливо в умовах постійного зростання кількості користувачів та об'ємів даних, які опрацьовуються. Тому виникає необхідність розробки нового підходу, який дозволив би враховувати структурну та функціональну складність комп'ютерних систем із множинним доступом, відслідковувати критичні ресурсоємні запити, визначати компоненти системи які здійснюють найбільший вплив на тривалість обробки критичних запитів та застосовувати ефективні методи зменшення впливу таких критичних компонентів на тривалість обробки запитів.

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

У розділі 2 розроблено концептуальні засади нового підходу до підвищення ефективності процесу обробки запитів в умовах обмежених ресурсів, який базується на поетапному застосуванні методів виявлення, локалізації та зменшення впливу «вузьких місць» у їх програмних компонентах, що дозволяє автоматизувати процес підвищення продуктивності комп'ютерних систем. Блок-схему даного підходу наведено на рис. 1.

Для підвищення ефективності процесу обробки запитів у КСМД, необхідно виявити підмножину елементів системи , які споживають найбільшу кількість ресурсів, тобто є «вузькими місцями».

Размещено на http://www.allbest.ru/

Рис. 1 Блок-схема комплексного підходу до підвищення ефективності обробки запитів у КСМД

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

, (1)

де - матриця зв'язків між компонентами. При цьому одержимо приріст ефективності системи, якщо буде виконана умова .

Як показав аналіз об`єкту дослідження, сучасні КСМД складаються з трьох основних підмножин складових компонентів - комунікаційного середовища , серверної та клієнтської складової . Зважаючи на специфіку систем із множинним доступом, для оптимізації використано елементи серверної складової та комунікаційного середовища , як такі, що зазнають найбільших навантажень в умовах надходження потоку запитів із високою інтенсивністю.

Програмні компоненти серверної складової КСМД здійснюють обробку двох основних класів запитів: клієнтські запити та сервісні задачі. Хоча сервісні задачі виконуються одним потоком, постійно або із заданою періодичністю, вони можуть суттєво впливати на ефективність обробки запитів користувачів, оскільки споживають обмежені системні ресурси, а тому також потребують врахування. Таким чином, на першому етапі запропонованого підходу використано 3 основних напрямки підвищення ефективності КСМД: збільшення ефективності програмних компонентів; збільшення ефективності обміну даними через комунікаційне середовище; збільшення ефективності розподілу в часі обчислювальних ресурсів, які споживаються сервісними задачами.

Ефективність програмних компонентів, які приймають участь у процесі обробки запитів користувачів, визначається тривалістю обробки кожного запиту. В даному напрямку необхідно визначити критичні стани системи, при переході до яких спостерігається вплив «вузьких місць».

КСМД може мати різних станів. Перехід системи від стану до здійснюється подією . Всі події в системі утворюють множину подій

, (2)

де - загальна кількість подій (запитів) в системі.

Тривалості обробки всіх запитів в системі утворюють множину

. (3)

Кожен запит здійснює виклик певного набору функцій програмного забезпечення . Часову ефективність системи в процесі обробки запиту можна визначити як відносний функціонально-часовий критерій

. (4)

Якщо підмножина функціональності КСМД містить «вузькі місця», тобто , в системі виникають затримки, в результаті чого значно зростає тривалість переходу до нового стану . Сукупність запитів в результаті яких справджується така умова названо критичними.

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

, (5)

де - тестова функція з фіксованим набором операцій, - час виконання тестової функції при нульовому навантаженні системи. Ділення (4) на (5) дозволяє отримати відносний показник часової ефективності

, (6)

де - тривалість виконання тестової операції при переході до стану .

Щоб врахувати вплив зміни рівня доступних обчислювальних ресурсів в момент переходу до стану - введено коефіцієнт завантаженості обчислювальних ресурсів в момент переходу до нього:

. (7)

Також введено відносний коефіцієнт функціональності конкретного запиту до КСМД в порівнянні з тестовою операцією

. (8)

Підставивши в (6) вираз (8) та помноживши його на (7), одержано відносний коефіцієнт часової ефективності в момент переходу системи до стану , в якому корегується вплив завантаженості обчислювальних ресурсів КСМД в момент здійснення моніторингу

. (9)

У виразі (9) залишається одне невідоме - відносний показник функціональності стану КСМД. Підставивши замість нього значення , можна оцінити, як відрізняється часова ефективність при обробці переходів до різних станів, і чи відповідає цей розподіл очікуваній різниці між функціональністю цих станів, заданою в технічній документації. Таким чином, відносний показник часової ефективності обробки запиту , який враховує зміну завантаженості обчислювальних ресурсів сервера в часі, можна визначити наступним чином:

. (10)

Підмножину запитів до системи , при обробці яких досягаються максимальні значення показника відносної часової ефективності (10) і можна вважати множиною «критичних запитів». Приклад візуалізації коефіцієнтів часової ефективності для різних станів системи, показано на рис. 2.

Размещено на http://www.allbest.ru/

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

В процесі локалізації «вузьких місць» необхідно визначити елементи програмних компонентів КСМД, які призводять до значних затримок при обробці множини «критичних запитів».

За основу для побудови моделі процесу обробки запитів, використано дерево викликів (Call graph). Масив з результатами профайлингу тривалості процесу обробки запиту, можна легко трансформувати в граф дерева викликів . Схематичне зображення такої графової моделі показано на рис. 3.

Размещено на http://www.allbest.ru/

Вершинами даного графа є окремі операції в процесі обробки запиту, ребрами - їх виклики. Модель доповнено вагами ребер, які визначають тривалість виконання кожної операції. Окрім того, введено поняття рівня операції , тобто кількості проміжних вершин від початку графа викликів.

«Вузькими місцями» вважається підмножина вершин графа викликів , таких що тривалість виконання кожної з них здійснює значний вплив на сумарну тривалість обробки запиту . Міра такого впливу визначається як:

. (11)

Введено поняття критичного значення міри впливу , при досягненні якої операція буде вважатися «вузьким місцем».

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

Теорема 1. Якщо операція в графі викликів здійснює виклик операцій на нижньому рівні , то загальна тривалість її виконання включає в себе сумарну тривалість виконання дочірніх операцій.

Наслідок з теореми 1. Операцію в графі викликів можна вважати «вузьким місцем» тільки тоді, коли різниця між мірою її впливу на загальну тривалість виконання програми та сумарною мірою впливу дочірніх операцій перевищує критичне значення міри впливу , тобто тоді коли виконується умова

. (12)

Однак, якщо жодна із дочірніх операцій не визначена як «вузьке місце», можна зробити висновок про недосконалість роботи викликаючої операції, тому в такому випадку вона визначається як «вузьке місце». Окрім того, в графі можуть існувати вершини, які описують операції які виконуються підпрограмами стандартних бібліотек, і не має сенсу розглядати їх виклики як «вузькі місця». Доцільно ввести множину , яка описує файли таких бібліотек, тоді операції можуть розглядатися як «вузькі місця» за умови .

На основі розробленого теоретичного та математичного забезпечення, а також застосування алгоритму обходу графа в глибину, розроблено алгоритм методу автоматичної локалізації «вузьких місць». На відміну від існуючих методів, визначення множини «вузьких місць» в запропонованому методі здійснюється автоматично, а не шляхом візуального аналізу дерева викликів.

Множина знайдених «вузьких місць» надається користувачеві з метою вибору методів зменшення їх впливу. Проведені дослідження показали, що є 2 основних класи «вузьких місць»: затримки в процесі проведення складних розрахунків та затримки в сервері СУБД при обробці складних запитів до баз даних. Відповідно до природи виникнення «вузьких місць», у роботі застосовується 2 методи зменшення їх впливу - оптимізація виконання ресурсоємних операцій та оптимізація виконання ресурсоємних запитів до баз даних. Дані методи детально розглянуті в третьому розділі роботи.

Окрім часової ефективності процесу обробки запитів програмними компонентами, значний вплив на загальну ефективність роботи КСМД здійснюють комунікаційні канали, пропускна здатність яких є обмеженою. Комунікаційні канали КСМД складаються з великої кількості складових елементів, і тому в разі виникнення проблем з їх використанням, необхідно визначити, які саме з цих компонентів є «вузькими місцями». Саме для цього в запропонованому підході розроблено метод моніторингу часових затримок в елементах комп'ютерних мереж, що дозволяє виявляти такі «вузькі місця» та підвищувати ефективність комунікаційної складової.

Третім напрямком є підвищення ефективності розподілу в часі рівня споживання обчислювальних ресурсів сервісними задачами. Для його реалізації здійснюється постійний моніторинг рівня споживання ресурсів кожною сервісною задачею та застосовується метод оптимізації його розподілу в часі.

Для кращого розуміння розподілу ресурсів між задачами в комп'ютерних системах із множинним доступом, побудовано його графічну інтерпретацію, показану на рис. 4. По осі позначаються порядкові номери дискретних часових інтервалів, на які розбивається період роботи системи. Сукупність часових інтервалів складає множину , де - загальна кількість дискретних часових інтервалів. По осі позначається рівень споживання обчислювальних ресурсів. Для кожного інтервалу часу визначається середній рівень споживання обчислювальних ресурсів:

Размещено на http://www.allbest.ru/

, (13)

де - порядковий номер періоду моніторингу, - загальна кількість періодів роботи системи, - рівень споживання ресурсів одержаний у результаті моніторингу на протязі -го періоду спостереження, у інтервал часу . Середнє значення рівня використання обчислювальних ресурсів на протязі періоду, можна визначити як

. (14)

Для характеристики нерівномірності розподілу рівня використання обчислювальних ресурсів запропоновано використання дисперсії

. (15)

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

. (16)

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

(17)

Тоді загальний рівень використання ресурсів для часового інтервалу після запуску сервісної задачі можна визначити як

. (18)

Рівномірність розподілу використання ресурсів після розміщення сервісної задачі можна оцінити, розрахувавши згідно (15) дисперсію . Оптимальним розміщенням даної сервісної задачі буде такий стартовий інтервал , для якого дисперсія розподілу ресурсів (18) буде мінімальною , і для якого виконується умова (16). Окрім того, в роботі розглянуто випадок, коли в системі виконується не одна, а сервісних задач.

Внесення змін у програмне або апаратне забезпечення КСМД, яке здійснюється в процесі оптимізації їх роботи, в будь-якому випадку справляє вплив на різноманітні показники. Так, оновлення програмного або апаратного забезпечення може збільшувати затрати на експлуатацію системи, застосування кешу може зменшувати об'єм вільного дискового простору і т.п. Для того, щоб визначити міру негативного впливу на основні показники функціонування КСМД при проведенні оптимізації програмного або апаратного забезпечення, на заключному етапі підходу пропонується нечітка модель комплексної оцінки взаємодії показників ефективності КСМД.

У розділі 3 розроблено методи підвищення ефективності процесу обробки запитів у комп'ютерних системах із множинним доступом.

На основі теоретичного забезпечення, розглянутого в другому розділі, запропоновано удосконалений метод виявлення та локалізації «вузьких місць» у процесі обробки запитів, який на відміну від існуючих, здійснюється автоматично, дозволяє визначати критичні запити з урахуванням нерівномірності завантаженості обчислювальних ресурсів у часі. При здійсненні локалізації «вузьких місць» у програмних компонентах, запропонований метод враховує не лише окремі процедури, які безпосередньо здійснюють значний вплив на процес обробки запитів, а й процедури які знижують продуктивність системи за рахунок багаторазового виклику дочірніх процедур.

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

Структурну схему запропонованого методу показано на рис. 5. На вхід подається початковий запит . Парсер SQL обробляє вхідний запит та формує на основі нього об'єктну модель. Процедура генетичної оптимізації кодує об`єктну модель у вигляді хромосоми, та здійснює пошук оптимальної хромосоми, яка забезпечує мінімальне значення функції відповідності.

Размещено на http://www.allbest.ru/

Функція відповідності визначається як час обробки запиту SQL на сервері СУБД. В результаті отримується оптимальний запит , який має мінімальний час обробки та повертає необхідну вибірку даних .

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

Для зменшення впливу «вузьких місць», спричинених періодичним виконанням ресурсоємних розрахунків, розроблено модифікований метод кешування проміжних результатів розрахунків. Він представляє програмне забезпечення КСМД як множину окремих елементів (підпрограм) , де - кількість методів.

Кожна підпрограма має множину вхідних параметрів , де - кількість вхідних параметрів підпрограми .

Для виконання розрахунків підпрограма здійснює множину запитів до бази даних КСМД , де - кількість запитів до баз даних.

Кожен запит до бази даних здійснює вибірку з множини таблиць

,

де - кількість таблиць, з яких здійснюєтся вибірка даних -м запитом.

В результаті виконання підпрограми одержується множина вихідних даних .

Сучасні СУБД дозволяють визначити час останньої модифікації будь-якої таблиці БД за допомогою спеціальної функції :

. (19)

Застосувавши функцію (19) над множиною таблиць , одержуємо множину часових міток модифікації таблиці , яка використовується запитом :

. (20)

Якщо для підпрограми в кеші системи збережено множину значень її вхідних параметрів , часові мітки модифікації таблиць БД для кожного запиту а також множину даних , то адекватність даного кешу при повторному виклику підпрограми можна визначити за допомогою виразу

. (21)

Таким чином, якщо згідно (21) справджується рівність , - то дані кешу для підпрограми при вхідних параметрах є адекватними.

На відміну від існуючих, запропонований метод дозволяє здійснювати кешування не лише окремих запитів до баз даних або елементів інтерфейсу, а й результати виконання найбільш ресурсоємних операцій, на основі аналізу актуальності вхідних даних. Висока швидкодія методу досягається за рахунок застосування пам'яті зі швидким доступом.

Окрім цього, розроблені додаткові методи діагностики та контролю стану КСМД. Для локалізації «вузьких місць» у комунікаційному середовищі КСМД запропоновано математичне та алгоритмічне забезпечення для здійснення моніторингу та виявлення «вузьких місць» у комп`ютерних мережах. Суть запропонованого підходу полягає у періодичній відправці тестового пакету даних через комунікаційне середовище КСМД. Для кожного фрагменту мережі фіксується час передачі пакету, в результаті чого можна виявити фрагменти мережі, які характеризуються найбільшою тривалістю передачі пакетів або найбільшим відсотком втрати даних. Такі фрагменти комунікаційного середовища можна також вважати «вузькими місцями».

Для оцінки взаємодії показників ефективності процесу обробки запитів, розроблена функція нечіткого логічного висновку. Запропоновано та обґрунтовано використання нечіткої логіки для побудови моделі системи з врахуванням її нелінійності та високої складності. Розроблено структуру системи нечіткого логічного висновку яка може буде використана при побудові реальної системи оцінки взаємодії показників ефективності КСМД.

У розділі 4 наведено результати практичної реалізації запропонованого підходу, та проведено аналіз їх застосування на сучасних апаратно-програмних платформах.

Застосування методу моніторингу та локалізації «вузьких місць» у процесі обробки запитів, дозволило виявити «критичні» запити, які мають аномально велику тривалість обробки, та «вузькі місця», які істотно (40 - 79%) впливають на загальну часову ефективність КСМД при обробці запитів.

Експериментальні дослідження методу кешування проміжних та вихідних результатів розрахунків обчислювальних систем з врахуванням актуальності вхідних даних, підтвердили його працездатність та результативність при здійсненні оптимізації виявлених «вузьких місць». Зокрема, при оптимізації виконання операції get_forecast_data_artikel КСМД UMS4, було зменшено середню тривалість обробки запитів на 69,4%, загальний час обробки всіх запитів - на 71%, в результаті чого пропускну здатність системи при обробці даного запиту було збільшено на 244%.

Размещено на http://www.allbest.ru/

Запропонований метод оптимізації структури запитів до баз даних на основі генетичних алгоритмів було досліджено при оптимізації ресурсоємного SQL запиту, при обробці запиту «bestchoice» до КСМД UMS4. Було зменшено середню тривалість обробки запитів на 77,1%, загальний час обробки всіх запитів - на 75,27%, в результаті чого пропускну здатність системи при обробці даного запиту було збільшено на 303,8%. Графік тривалості обробки вхідного та оптимізованого запитів показано на рис. 6.

Результати проведених досліджень використано при розробці комплексної системи моніторингу та оптимізації програмних компонентів КСМД - Server Software Optimization Toolbox (SSOT), яка забезпечує можливість використання в переважній більшості сучасних обчислювальних систем. Діаграму розгортання якої показано на рис. 7.

Размещено на http://www.allbest.ru/

Візуальний інтерфейс системи дозволяє автоматизувати роботу адміністратора КСМД по виявленню та зменшенню впливу «вузьких місць» у процесі обробки запитів. Її успішно впроваджено в компанії Contentum (Німеччина), для підвищення ефективності роботи системи аналізу та прогнозування даних про продаж кольорових металів UMS4 а також відео-порталу німецької телекомпанії RegioTV. Для моніторингу стану обчислювальних ресурсів серверів даної КСМД, було впроваджено допоміжну підсистему оперативного моніторингу стану обчислювальних та комунікаційних ресурсів.

Впровадження системи для КСМД RegioTV, дало змогу автоматично визначати час запуску сервісної задачі конвертації відео-файлів, який забезпечує оптимальний розподіл обчислювальних ресурсів на протязі доби.

В додатках наведено результати експериментальних досліджень, лістинги основних класів та методів розробленого програмного комплексу SSOT, акти впровадження результатів дисертаційної роботи.

ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ ТА ВИСНОВКИ

У дисертаційній роботі наведено результати теоретичних та експериментальних досліджень ефективності процесу обробки запитів у комп'ютерних системах із множинним доступом, а також методів її підвищення. Одержані результати дозволяють зробити наступні висновки:

1. Проведений аналіз літературних джерел показав, що існує велике різномаїття методів підвищення ефективності роботи КСМД, однак в переважній більшості вони розглядаються з практичної точки зору, та дозволяють підвищити ефективність виконання лише певних операцій за рахунок втрат функціональності, часто з використанням ручної праці, не заглиблюючись у теоретичні основи поняття ефективності. Саме тому визначено підмножину характеристик, які будуть ключовими при розробці нових методів підвищення ефективності процесу обробки запитів у КСМД. В якості основного критерію для оцінки вибрано часову ефективність. Виділено множину підходів до підвищення часової ефективності та обмеження щодо їх застосування, щоб забезпечити якість програмних компонентів, які здійснюють обробку запитів, відповідно до міжнародного стандарту ISO 9126.

2. Формалізовано задачу підвищення ефективності процесу обробки запитів у КСМД, введено поняття відносного функціонально-часового критерію ефективності, виконано його прив'язку до графової моделі процесу обробки запитів.

3. Запропоновано новий підхід до підвищення ефективності обробки запитів у комп'ютерних системах із множинним доступом, який полягає в комплексному застосуванні методів виявлення, локалізації та зменшення впливу «вузьких місць» у їх програмних компонентах, що дозволяє автоматизувати процес підвищення продуктивності комп'ютерних систем.

4. Удосконалено метод моніторингу та локалізації «вузьких місць» у процесі обробки запитів, що здійснюється автоматично, і дозволяє визначати критичні запити з урахуванням нерівномірності завантаженості обчислювальних ресурсів, за рахунок застосування кластеризації параметрів запитів, врахування завантаженості обчислювальних ресурсів і використання графової моделі процесу обробки запитів.

5. Дістав подальшого розвитку метод оптимізації структури запитів до серверів баз даних, що дозволяє оптимізувати не лише порядок виконання операцій об'єднання даних із кількох таблиць, а й операцій умови, сортування і інших, за рахунок оптимізації їх структури з використанням об'єктної моделі та алгоритмів генетичної оптимізації.

6. Розроблено модифікований метод кешування проміжних результатів розрахунків, що дозволяє здійснювати кешування не лише окремих запитів до баз даних або елементів інтерфейсу, а й результати виконання найбільш ресурсоємних операцій, на основі аналізу актуальності вхідних даних.

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

8. Запропонований підхід та методи які входять до його складу, підтвердили свою працездатність та ефективність у процесі експериментальних досліджень. При оптимізації процесу обробки запитів у досліджених КСМД, зменшення тривалості їх обробки сягало 69-71%.

9. Результати проведених теоретичних досліджень використані при створенні алгоритмічного та програмного забезпечення для здійснення оптимізації та підвищення ефективності процесу обробки запитів. Розроблені алгоритми і методи реалізовані у вигляді системи «Server Software Optimization Toolbox (SSOT)», яка може бути використана для підвищення ефективності роботи переважної більшості сучасних КСМД. Систему успішно впроваджено в компанії Contentum (Німеччина), для підвищення ефективності роботи системи аналізу та прогнозування даних про продаж кольорових металів UMS4 а також відео-порталу німецької телекомпанії RegioTV. У результаті впровадження, було зменшено середню тривалість обробки запитів у КСМД UMS4 з 4,22 с до 1,31 с (на 222%). Впровадження системи SSOT на підприємстві ТОВ «TEAM Лтд» (м. Вінниця) дозволило скоротити середню тривалість обробки запитів до сервера автоматизації роботи торгівельних представників Mobile X-Trade на 46%.

ПУБЛІКАЦІЇ ЗА ТЕМОЮ ДИСЕРТАЦІЙНОЇ РОБОТИ

1. Штельмах І.М. Ідентифікація стану обчислювальної системи інтегрованої в комп'ютерні мережі з використанням нечіткої логіки/ Ю.В. Шабатура, І.М. Штельмах// Вісник Хмельницького національного університету. 2007. №2, Т.1. С. 63-66.

2. Штельмах І.М. Моделювання комплексної взаємодії показників ефективності обчислювальних систем інтегрованих в комп'ютерні мережі/ Ю.В. Шабатура, І.М. Штельмах// Наукові праці Донецького національного технічного університету. 2008. Вип. 14(129). С. 63-68.

3. Штельмах І.М. Автоматичний моніторинг часової ефективності програмного забезпечення обчислювальних систем / Ю.В. Шабатура, І.М. Штельмах // Вісник Кременчуцького державного політехнічного університету. 2008. Вип. 4/2009 (57). С. 122-124.

4. Штельмах І.М. Нова методика підвищення ефективності програмного забезпечення обчислювальних систем шляхом автоматичного визначення «вузьких місць» / Ю.В. Шабатура, І.М. Штельмах // Наукові праці ВНТУ. [Електронний ресурс]. Вінниця, 2009. №2. Режим доступу: http://www.nbuv.gov.ua/e-journals/vntu/2009-2/2009-2.files/uk/09yvssob_ua.pdf.

5. Штельмах І.М. Комп'ютерне моделювання процесу визначення ефективності діяльності докторів наук та професорів ВНЗ із підготовки науково-педагогічних кадрів та створення якісної наукової продукції / Ю.В. Мокіна, І.М. Штельмах // Вісник Вінницького політехнічного інституту. 2005. № 4. С. 42-49.

6. Штельмах І.М. Підвищення ефективності обчислювальних систем на основі генетичної оптимізації SQL-запитів до баз даних / Ю.В. Шабатура, І.М. Штельмах, М.Ю. Шабатура // Вісник Вінницького політехнічного інституту. 2009. N1. С. 41-46.

7. Штельмах І.М. Ефективна експлуатація обчислювально-інформаційних систем в умовах низької пропускної здатності комунікаційних каналів / Ю.В. Шабатура, І.М. Штельмах // Вісник Харківського нац. технічного університету сільського господарства ім. П. Василенка. 2007. Вип. 57, Т.2. С 178-182.

8. Штельмах І.М. Дослідження динамічних характеристик інформаційних каналів мережі INTERNET / Ю.В. Шабатура, І.М. Штельмах // Матеріали МНК „Інтелектуальні системи прийняття рішень та прикладні аспекти інформаційних технологій”. Євпаторія, 2006. Т.2. С. 170-173.

9. Shtelmakh I. Automatic optimization of SQL-Queries on basis of genetic algorithms / Y. Shabatura, I. Shtelmakh, M. Shabatura // The Sixth International Conference “INTERNET-EDUCATION-SCIENCE”. Vinnytsia, Ukraine, October 7-11, 2008. 2008. P. 294-299.

АНОТАЦІЯ

Штельмах І. М. Методи і засоби забезпечення ефективності обробки запитів у комп'ютерних системах із множинним доступом. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 - комп'ютерні системи та компоненти. - Вінницький національний технічний університет, Вінниця - 2011.

Дисертаційну роботу присвячено розв'язанню задачі створення методів та засобів оптимізації процесу обробки запитів у комп'ютерних системах із множинним доступом (КСМД) з метою підвищення їх ефективності в умовах обмежених ресурсів.

Розроблено новий підхід до підвищення ефективності роботи КСМД, який базується на комплексному застосуванні методів виявлення, локалізації та зменшення впливу «вузьких місць» у їх програмних компонентах. Удосконалено метод оптимізації розподілу запитів по часовій шкалі, який на відміну від існуючих, дозволяє здійснювати оптимізацію розподілу в часі виконання сервісних задач та вибрати такі часові інтервали, в яких їх запуск забезпечує найбільш рівномірний розподіл ресурсів. Розроблені алгоритми і методи реалізовані у вигляді програмної системи «Server Software Optimization Toolbox (SSOT)», яка може бути використана для підвищення ефективності процесу обробки запитів в переважній більшості сучасних КСМД.

Ключові слова: комп'ютерні системи, обробка запитів, підвищення ефективності, вузькі місця, оптимізація.

SUMMARY

Shtelmakh I.M. Methods and tools of providing the effectiveness of query processing in computer systems with multiple access. - A manuscript.

Thesis for a candidate's degree of technical sciences on specialty 05.13.05 - computer systems and components. - Vinnytsia National Technical University, Vinnytsia - 2011.

Thesis is devoted to task solution for creation of methods and tools for optimizing query processing in computer systems with multiple access (CSMA) to improve their effectiveness in light of limited resources.

A new approach to increase efficiency of CSMA, based on a complex using of methods for detection, localization and reducing bottlenecks in their software components has been developed. Method of optimizing the distribution of requests for time scale has been improved, and allows to optimize distribution of service tasks run times and choice intervals, which provides most uniform distribution of used resources.

Developed algorithms and methods are provided in the form of software «Server Software Optimization Toolbox (SSOT)» which can be used to improve the efficiency of the vast majority of modern CSMA.

Key words: computer systems, queries processing, efficiency improvement, bottlenecks, optimization.

АННОТАЦИЯ

Штельмах И.Н. Методы и средства обеспечения эффективности обработки запросов в компьютерных системах с множественным доступом.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - компьютерные системы и компоненты. - Винницкий национальный технический университет, Винница - 2011.

Диссертационная работа посвящена решению задачи разработки методов и средств оптимизации процесса обработки запросов в компьютерных системах с множественным доступом (КСМД) с целью повышения их эффективности в условиях ограниченных ресурсов.

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

Формализирована задача повышения эффективности процесса обработки запросов в КСМД, введено понятие относительного функционально-временного критерия для оптимизации эффективности, выполнено его привязку к графовой модели процесса обработки запросов.

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

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

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

...