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

 

УДК 681.3

РЕАЛИЗАЦИЯ ВЗАИМНЫХ ИСКЛЮЧЕНИЙ

КРИТИЧЕСКИХ ИНТЕРВАЛОВ КАК ОДНОГО ИЗ ВИДОВ

СИНХРОНИЗАЦИИ ДОСТУПА ПРОЦЕССОВ К РЕСУРСАМ В ЭВМ

Шаганян С.Н., Бараненко Р.В.

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

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

Анализ последних исследований. Синхронизация процессов подразумевает для каждого процесса исключение возможности одновременного с ним обращения других процессов к разделяемым даннымвзаимоисключение. Любая попытка взаимного исключения должна опираться на некий фундаментальный механизм исключений аппаратного обес­печения. Наиболее общим механизмом может служить ограничение, согласно которому к некоторой ячейке памяти в определенный момент времени может осуществлять обращение только один процесс [1].

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

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

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

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

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

На сегодняшний день существующие алгоритмы [1, 3-5] решают проблему взаимоисключения критических интервалов процессов достаточно сложным путем, корректность которого трудно доказать, сложны для программной реализации и не обеспечивают необходимой скорости взаимодействия процессов и ресурсов в ЭВМ.

Цель статьи. Целью работы является разработка простого для реализации и корректного алгоритма синхронизации доступа процессов к ресурсам в ЭВМ, обеспечения быстродействия ЭВМ на необходимом уровне и оптимизации управления работой многозадачных операционных и многопроцессорных вычислительных систем.

Основной материал. Решение проблемы взаимоисключения критических интервалов процессов должно удовлетворять требованиям [1]:

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

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

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

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

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

,

(1)

где

,

(2)

где        - процесс заблокирован;

 - процесс работает;

 - передача управления другому процессу.

Здесь  - глобальная переменная, управляющая работой процессов;

 - флаг намерений процесса P0;

 - флаг намерений процесса P1.

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

Для решения поставленной задачи предлагается использовать алгоритм для взаимных исключений для двух процессов, предложенный голландским математиком Деккером (Dekker). В данном алгоритме реализована возможность слежения за состоянием обоих процессов. Для избежания проблемы «взаимной вежливости» используется глобальная переменная. Под «взаимной вежливостью» понимается состояние, когда каждый процесс указывает о своем желании войти в критический раздел, но готов отложить свой вход, уступая его другому процессу, так что, в конце концов, ни один из процессов не может войти в критический раздел. Приведем описание этого алгоритма для двух процессов [6].

Когда процесс Р0 намерен войти в критический раздел, он устанавливает свой флаг равным true, а затем про­веряет состояние флага процесса Р1. Если он равен false, Р0 разрешается операционной системой немедленно входить в критический раздел; в противном случае Р0 обращается к глобальной переменной turn. Если turn = 0, это означает, что сейчас — очередь процесса Р0 на вход в кри­тический раздел, и Р0 периодически проверяет состояние флага процесса Р1. Этот процесс, в свою очередь, в некоторый момент времени обнаруживает, что сейчас не его очередь для входа в критический раздел, и устанавливает свой флаг равным false, давая возможность процессу Р0 войти в критический раздел. После того как Р0 будет выведен системой из критического раздела, он установит свой флаг равным false для осво­бождения критического раздела и присвоит переменной turn значение 1 для переда­чи прав на вход в критический раздел процессу Р1. Блок-схема предлагаемого алгоритма приведена на рис.1.

Результаты работы алгоритма представлены в табл. 1, где * - любое из двух значений: 0 или 1.


Таблица 1

Результаты работы алгоритма взаимоисключения

в виде таблицы истинности функции процесса

turn

flag[0]

flag[1]

Состояние критического раздела,  

0

0

*

2 (Передача управления)

0

1

0

1 (Работа процесса P0)

0

1

1

0 (Заблокирован)

1

*

0

2 (Передача управления)

1

0

1

1 (Работа процесса P1)

1

1

1

0 (Заблокирован)

 

Рис.1 Блок-схема алгоритма взаимоисключения критических интервалов

для двух процессов

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

 

In given article the aspects of synchronization of access of processes to resources in the computer in light of realization of mutual exceptions of critical intervals of processes are considered, mathematical model of problem of mutual exceptions of critical intervals of two processes, principle of realization of mutual exceptions of critical intervals of processes and mutual exceptions algorithm are offered.

 

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

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

3.                  Dijkstra E. Cooperating Sequential Processes. Technological University, Eindhoven, The Netherlands, 1965. (Reprinted in Great Papers in Computer Science, P. Laplante, ed. New York, NY: IEEE Press, 1996).

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

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

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

 





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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Бараненко Р.В., Шаганян С.М., Дячук М.В. Аналіз алгоритмів взаємних виключень критичних інтервалів процесів у розподілених системах

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

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

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

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

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

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

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

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

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

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

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

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

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

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