УДК 681.3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где

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

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

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

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

 - флаг намерений процесса 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

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

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

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

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

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

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 с.: ил. – Парал. тит. англ.