Главная Контакты Добавить в избранное Авторы Вопросы и ответы
,

УДК 681.3

АНАЛІЗ АЛГОРИТМІВ ВЗАЄМНИХ ВИКЛЮЧЕНЬ КРИТИЧНИХ ІНТЕРВАЛІВ ПРОЦЕСІВ У РОЗПОДІЛЕНИХ СИСТЕМАХ

Бараненко Р.В., Шаганян С.М., Дячук М.В.

Постановка проблеми. Необхідність в усе більш і більш продуктивних системах виникла з першого дня винаходу комп'ютера. На початку це досягалося в результаті еволюції технологій виробництва процесорів. Але також розвивалися тенденції до використання декількох процесорів в одній обчислювальній системі для підвищення продуктивності, розроблялися мультизадачні операційні системи, системи з розподіленою пам'яттю, що підняли ряд проблем, що вимагають швидкого й ефективного рішення [1].

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

 

Аналіз останніх досліджень. Синхронізація процесів має на увазі для кожного процесу виключення можливості одночасного з ним звертання інших процесів до розподілених данихвзаємовиключення. Будь-яка спроба взаємного виключення повинна спиратися на якийсь фундаментальний механізм виключень апаратного забезпечення. Найбільш загальним механізмом може служити обмеження, відповідно до якого до деякої комірки пам'яті у визначений момент часу може здійснювати звертання тільки один процес [1].

Під процесом розуміється деяка послідовність дій, що складають деяке обчислення, що характеризується [1,2]:

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

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

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

Коли процес звертається до розподілених даних, мається на увазі, що він знаходиться у своєму критичному інтервалі [1,2]. Для синхронізації таких процесів використовуються спеціальні захищені глобальні змінні.

В даний час існуючі алгоритми [3-9] успішно вирішують проблему взаємовиключення критичних інтервалів процесів, але володіють при усіх своїх достоїнствах рядом недоліків, тому що використовують для рішення проблеми досить складні способи, коректність яких важко довести; більшість з них складні для програмної реалізації і/або не забезпечують необхідної швидкості взаємодії процесів і ресурсів в ЕОМ.

 

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

 

Основний матеріал. Застосування глобальних змінних і семафорів вирішує основну проблему синхронізації процесів, що складається у взаємному виключенні критичних інтервалів процесів. У загальному випадку її рішення повинне задовольняти вимогам [10]:

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

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

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

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

Існують різні алгоритми, що можуть бути використані для рішення поставленої задачі в розподілених обчислювальних системах [3-9].

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

Якщо ж деякий процес уже виконує критичний інтервал, зв'язаний з даним ресурсом, то ніяка відповідь не посилається; запитуючий процес ставиться до черги, і після звільнення критичного інтервалу йому відправляється відповідь-дозвіл.

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

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

2)                 Якщо одержувач уже знаходиться в критичному інтервалі, то він не відправляє ніякої відповіді, а ставить запит до черги.

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

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

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

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

1)                Централізований алгоритм є найбільш простим і найбільш ефективним. При його використанні потрібно тільки три повідомлення для того, щоб процес ввійшов і залишив критичний інтервал: запит, повідомлення-дозвіл для входу і повідомлення про звільнення ресурсу при виході.

2)                При використанні розподіленого алгоритму для одного використання критичного інтервалу потрібно послати  повідомлень-запитів (де  - число процесів) - по одному на кожен процес і одержати  повідомлень-дозволів, тобто усього необхідно  повідомлень.

3)                В алгоритмі Token Ring число повідомлень змінно: від 1 у випадку, якщо кожен процес входив до критичного інтервалу, до нескінченно великого числа, при циркуляції токена по кільцю, у якому жоден процес не входив до критичного інтервалу.

На жаль усі ці три алгоритми погано захищені від відмов. У першому випадку до краху приводить відмова координатора, у другому - відмова будь-якого процесу, а в третьому - втрата токена або відмова процесу.

 

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

Використання конкретних алгоритмів взаємного виключення критичних інтервалів процесів приведено в працях авторів [1, 10-12].

 

The problem of synchronization of processes in the distributed systems is considered, the comparative analysis of algorithms of mutual exception of critical intervals of processes is carried out, as a result of which their basic advantages and lacks are determined.

 

1.                 С.Н. Шаганян, Р.В. Бараненко Реализация взаимных исключений критических интервалов как одного из видов синхронизации доступа процессов к ресурсам в ЭВМ // Автоматика. Автоматизация. Электротехнические комплексы и системы – Херсон: ХГТУ, 2003, №2(12), С.70-73.

2.                 Фритч В. Применение микропроцессоров в системах управления: Пер. с нем. – М.: Мир, 1984. - 464 с., ил.

3.                 Столингс Вильям. Структурная организация и архитектура компьютерных систем, 5-е издание.: пер. с англ. – М.: Издательский дом «Вильямс», 2002. – 896 с.: ил. – Парал. тит. англ.

4.                 Шоу А. Логическое проектирование операционных систем /Пер. с англ. В.В. Макарова и В.Д. Никитина. – М.: Мир, 1981. – 360 с.

5.                 Цикритзис Д., Бернстайн Ф. Операционные системы /Пер. с англ. В.Л. Ушковой и Н.Б. Фейгельсон. – М.: Мир, 1977. – 336 с.

6.                 Системное программное обеспечение /А.В. Гордеев, А.Ю. Молчанов. – СПб.: Питер, 2001. – 736 с.: ил.

7.                 Peterson G. Myths About the Mutual Exclusion Problem. – Information Processing Letters, June 1981.

8.                 Hofri M. Proof of a Mutual Exclusion Algorithm. – Operating System Review, January 1990.

9.                 Столингс Вильям. Операционные системы, 4-е издание.: пер. с англ. – М.: Издательский дом «Вильямс», 2002. – 848 с.: ил. – Парал. тит. англ.

10.             С.Н. Шаганян, Р.В. Бараненко Принцип синхронизации доступа к данным в многопроцессорных ЭВМ с общей памятью // Вестник ХГТУ – Херсон: ХГТУ, 2003, №2 (18), С. 289-291.

11.             Свідоцтво про реєстрацію авторського права на твір №8645, “Комп¢ютерна програма “Автоматизована система прийняття рішень про розподілення інформації за індивідуальними параметрами об¢єктів в системах з обхідом тупиків “MedIS”. Автори: Р.В. Бараненко, Т.А. Ілюк, М.В. Пилипенко, Ю.Ю. Синицький, С.Ю. Синицький. Опубл. 23.10.2003.

12.             С.Н. Шаганян, Р.В. Бараненко Выполнение запросов о выделении ресурсов в системах с обходами тупиков // Вестник ХГТУ – Херсон: ХГТУ, 2004, №19, С. 63-65.

     

 





Ответы на вопросы [_Задать вопроос_]

Информационно-управляющие комплексы и системы

Теленик С.Ф., Ролік О.І., Букасов М.М., Андросов С.А. Генетичні алгоритми вирішення задач управління ресурсами і навантаженням центрів оброблення даних

Богушевский В.С., Сухенко В.Ю., Сергеева Е.А., Жук С.В. Реализация модели управления конвертерной плавкой в системе принятия решений

Бень А.П., Терещенкова О.В. Применение комбинированных сетевых методов планирования в судоремонтной отрасли

Цмоць І. Г., Демида Б.А., Подольський М.Р. Методи проектування спеціалізованих комп’ютерних систем управління та обробки сигналів у реально-му час

Теленик С.Ф., РолікО.І., Букасов М.М., РимарР.В., Ролік К.О. Управління навантаженням і ресурсами центрів оброблення даних при виділених серверах

Селякова С. М. Структура інтелектуальної системи управління збиральною кампанією

Еременко А.П., Передерий В.И. Принятие решений в автоматизированных системах с учетом психофункциональных характеристик оператора на основе генетических алгоритмов

Львов М.С. Алгоритм перевірки правильності границь змінення змінних у послідовних програмах

Ляшенко Е.Н. Анализ пожарной опасности сосновых насаждений в зоне Нижне-днепровских песков – самой большой пустыни в Европе

Кучеров Д.П., Копылова З.Н. Принципы построения интеллектуального автору-левого

Касаткина Н.В., Танянский С.С., Филатов В.А. Методы хранения и обработки нечетких данных в среде реляционных систем

Ходаков В.Е., Жарикова М.В., Ляшенко Е.Н. Применение когнитивного подхода для решения задачи поддержки принятия управленческих решений при ликвидации лесных пожаров

Гончаренко А.В. Моделювання впливу ентропії суб’єктивних переваг на прийняття рішень стосовно ремонту суднової енергетичної установки

Фарионова Н.А. Системный подход построения алгоритмов и моделей систем поддержки принятия решений при возникновении нештатных ситуаций

Биленко М.С., Серов А.В., Рожков С.А., Буглов О.А. Многоканальная система контроля качества текстильных материалов

Мотылев K.И., Михайлов M.В., Паслен В.В. Обработка избыточной траекторной информации в измерительно-вычислительных системах

Гончаренко А.В. Вплив суб’єктивних переваг на показники роботи суднової енергетичної установки

Гульовата Х.Г., Цмоць І.Г., Пелешко Д.Д. Архітектура автоматизованої системи моніторингу і дослідження характеристик мінеральних вод

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

ПотапенкоЕ.М., Казурова А.Е. Высокоточное управление упругой электромеханической системой с нелинейным трением.

Кузьменко А.С., Коломіц Г.В., Сушенцев О.О. Результати розробки методу еквівалентування функціональних особливостей fuzzy-контролерів

Кравчук А. Ф., Ладанюк А.П., Прокопенко Ю.В. Алгоритм ситуационного управления процессом кристаллизации сахара в вакуум-аппарате периодического действия с механическим циркулятором

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

Литвиненко В.И., Четырин С.П. Компенсация ошибок оператора в контуре управления следящей системы на основе синтезируемых вейвелет-сетей

Бардачев Ю.Н., Дидык А.А. Использование положений теории опасности в искусственных иммунных системах

Рожков С.О., Кузьміна Т.О., Валько П.М. Інформаційна база як основа для створення асортименту лляних виробів.

Ускач А.Ф., Становский А.Л., Носов П.С. Разработка модели автоматизированной системы управления учебным процессом

Мазурок Т.Л., Тодорцев Ю.К. Актуальные направления интеллектуализации системы управления процессом обучения.

Ускач А.Ф., Гогунский В.Д., Яковенко А.Е. Модели задачи распределения в теории расписания.

Сідлецький В.М., Ельперін І.В., Ладанюк А.П. Розробка алгоритмів підсистеми підтримки прийняття рішень для контролю якості роботи дифузійного відділення.

Пономаренко Л.А., Меликов А.З., Нагиев Ф.Н. Анализ системы обслуживания с различными уровнями пространственных и временных приоритетов.

Коршевнюк Л.О. Застосування комітетами експертів системи нечіткого логічного виводу із зваженою істинністю.. – С. 73 – 79.

Кирюшатова Т.Г., Григорова А.А Влияние направленности отдельных операторов и направленности всей группы на конечный результат выполнения поставленной задачи.

Петрушенко А.М., Хохлов В.А., Петрушенко І.А. Про підключення до мови САА/Д деяких засобів паралельного програмування пакету МРІСН.

Ходаков В.Е., Граб М.В., Ляшенко Е.Н. Структура и принципы функционирования системы поддержки принятия решений при ликвидации лесных пожаров на базе новых геоинформационных технологий.

Сидорук М.В., Сидорук В.В. Информационные системы управления корпорацией в решении задач разработки бюджета.

Нагорный Ю.И. Решение задачи автоматизированного расчета надежности иасуп с использованием модифицированного метода вероятностной логики

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

Гожий А.П., Коваленко И.И. Системные технологии генерации и анализа сценариев

Вайсман В.А., Гогунский В.Д., Руденко С.В. Формирование структур организационного управления проектами

Бабенко Н.И., Бабичев С.А. Яблуновская Ю.А. Автоматизированная информационная система управления учебным заведением

Яковенко А.Е. Проектирование автоматизированных систем принятия решений в условиях адаптивного обучения с учетом требований болонского процесса

Бараненко Р.В Лінеаризація шкали і збільшення діапазону вимірювання ємностей резонансних вимірювачів

Головащенко Н.В. Математичні характеристики шумоподібно кодованих сиг-налів.

Шерстюк В.Г. Формальная модель гибридной сценарно-прецедентной СППР.

Шекета В.І. Застосування процедури Append при аналізі абстрактних типів даних модифікаційних запитів.

Цмоць І.Г. Алгоритми та матричні НВІС-структури пристроїв ділення для комп'-ютерних систем реального часу.

Кухаренко С.В., Балтовский А.А. Решение задачи календарного планирования с использованием эвристических алгоритмов.

Бараненко Р.В., Козел В.Н., Дроздова Е.А., Плотников А.О. Оптимизация рабо-ты корпоративных компьютерных сетей.

Нестеренко С.А., Бадр Яароб, Шапорин Р.О. Метод расчета сетевых транзакций абонентов локальных компьютерных сетей.

Григорова А.А., Чёрный С. Г. Формирование современной информационно-аналитической системы для поддержки принятия решений.

Шаганян С.Н., Бараненко Р.В. Реализация взаимных исключений критических интервалов как одного из видов синхронизации доступа процессов к ресурсам в ЭВМ

Орлов В.В. Оценка мощности случайного сигнала на основе корреляционной пространственной обработки

Коджа Т.И., Гогунский В.Д. Эффективность применения методов нечеткой логики в тестировании.

Головащенко Н.В., Боярчук В.П. Аппаратурный состав для улучшения свойств трактов приёма – передачи информации в системах промышленной автоматики.